file-text2 file-play home

Lambda Calculus

Lambda Calculus is often cited as the first functional programming language. Though there have been many attempts to derive a formal programming language from Lambda Calculus, the original language in its purest form does not support the following:

Here is what the syntax does allow:

Some things to notice:

Strictly speaking, Lambda Calculus does not support any non-function values. However, in order to “evaluate” an expression, we need to define a base case. Therefore, we will define the following “integer” representations:

Let’s look at how we would define Clojure’s inc function in Lamda Calculus:

λn.λs.λz.s(n s z)          #=> parenthesis help us describe order of operations
λn.λs.λz.s(n s z) 3        #=> let's apply this function to the value 3
λs.λz.s(3 s z)             #=> starting from the outside, we replace 3 for n
λs.λz.s((λa.λb.aaab) s z)  #=> 3 as a function call can be replaced for its "function representation"
λs.λz.s((λb.sssb) z)       #=> apply "3" to s...
λs.λz.s((λz.sssz))         #=> ...then to z
λs.λz.ssssz                #=> at this point, we can extract the nested function
4                          #=> we arrive at the "function" representation of 4!

Resources