The Following is (at least partially) an info page.
This means it is meant to be helpful as a standalone piece of information.
It also means I am (relatively) confident that what it contains is true*.
It will still be interconnected with many other pages and I reccomend exploring said links, but it should be able consumed on its own.
*please let me know if its not.
The Lambda Calculus is a model of computation.
There are many ways to model computation. One which you may have heard of is the turing machine. the lambda calculus is another such model of computation except it is pretty easily interpreted by humans. Functional programming is based on the lambda calculus. My very favorite way to demonstrate the lambda calculus is with boolean logic.The lambda calculus is composed of special functions (called lambdas) which take one thing and return one thing. They are written like this: λx.x where the lambda (λ) denotes it is a lambda, the x on the left of the dot denotes an argument and the x on the right of the dot denotes what is returned. Finally, we can call lambda just by writing its argument next to it. For example:
Identity = λx.x
Identity 1 // 1
Here is some booleans:
TRUE = λx.(λy.x)
FALSE = λx.(λy.y)
(The parenthesis are not necessary but are included to make it easier to understand.)
Lets break this down. TRUE is a lambda on x which returns a lambda on y which returns x. (This process of kind of cheating the one argument limit on lambdas by returning lambdas is called currying, and it will be on the test.) It looks like this when applied:
TRUE 1 // λy.1
TRUE 1 2 // 1
Likewise FALSE is a lambda on x which returns a lambda on y which returns y. It looks like this when applied:
FALSE 1 // λy.y
FALSE 1 2 // 2
As we saw earlier, a lambda is a function which takes in a thing and returns a thing. Luckily for us, a lambda is a thing! Lets define some boolean logic. (also we are going to drop the parenthesis now.)
or = λx.λy.x TRUE y
and = λx.λy.x y FALSE
Or is a lambda x which returns a lambda y which returns the lambda which is returned by x applied to TRUE applied to y. This is very hard to follow when said like this but it should make sense when shown like it was earlier.
or TRUE // λy.TRUE TRUE y
or TRUE FALSE // TRUE TRUE FALSE
TRUE TRUE // λy.TRUE
TRUE TRUE FALSE // TRUE
∴
or TRUE FALSE // TRUE
I will leave the breakdown of application of the "and" lambda as an excersize for the reader.