Lambda-calculus program repository

This is NOT an Esoteric programming language, it is a program repository for Lambda calculus designed for beginners I highly recommend you read the page on Lambda calculus linked here.

Booleans:

In λ-calculus, everything is a function, there are no booleans. However, it is not to say that we can't make our own booleans, after all, it is Turing-complete.

True:

   λx.λy.x

False:

   λx.λy.y

These booleans are conditional statements, True is IF True, which selects the first operand, the If operand. False is IF False, which selects the second operand, the Else operand.

Numbers:

Ahhh... numbers, the most important concept in all of humanity. How will we get it into λ-calculus. Church Numerals, the solution to life and everything.

Zero:

   λf.λx.x

One:

   λf.λx.(fx)

Two:

   λf.λx.(f(fx))

Three:

   λf.λx.(f(f(fx)))

Four:

   λf.λx.(f(f(f(fx))))

To create a Church Numeral N, we take x, add N "(f"s before it, add N ")"s after it and add "λf.λx." in front of it all. Now, you may notice that for a Church numeral N, N = ((Nf)x). Hold that thought, it will become very important in the next chapter. You may also notice that Church numerals are loops that iterate a function f over an operand x. That will become very important too.

Arithmetic:

What do we do with the numbers that we constructed if we do not even have the ability to add? We create arithmetic operations, of course we do.

Successor (SUCC):

   λn.λf.λx.(f((nf)x))

Addition (ADD):

   λm.λn.λf.λx.(m(f((nf)x))))

Multiplication (MULT):

   λm.λn.λf.(m(nf))

Exponentiation (EXP):

   λm.λn.(nm)

Predecessor (PRED):

   λn.λf.λx.(((n(λg.λh.(h(gf))))(λu.x))(λu.u))

Subtraction (SUB):

   ​λm.λn.((n(λn.((n(λg.λh.h(gf)))(λu.x))(λu.u)))m)

As you can see, not all arithmetic operations can be created, we still don't have division, but we can create that in the next chapter, Loops, more importantly Recursion.

Recursion:

To get recursion, we need what is known as the fixed point combinator, A function Θ such that (ΘF) = (F(ΘF)). Luckily, the author of "On Computable Numbers" and the father of the computer, Alan Turing himself, has done that work for us.

The Turing Fixed-Point Combinator (Θ):

   (λf.(λx.(f(xx)))(λx.(f(xx))))

Factorial (FACT):

   ​(λf.(λx.f(xx))(λx.f(xx)))(λf.λn.(λn.n(λx.(λa.λb.b))(λa.λb.a))n(λf.λx.fx)(λm.λn.λf.m(nf))n
   (f((λn.λf.λx.n(λg.λh.h(gf))(λu.x)(λu.u))n)))

(The function is both lines concatenated)

Lists:

Lists are required to store memory for larger algorithms

Constructor (CONS):

   (λh.λt.λf.fht)

List (LIST):

   [a, b, c] = ​(λh.λt.λf.fht)a((λh.λt.λf.fht)b((λh.λt.λf.fht)c(λx.λy.y)))
             = CONS a (CONS b (CONS c (FALSE)))

We now have most high level operations and lists.

Summary:

Lambda Calculus is a very versatile language and there is no limit to creativity in it