Lambda Calculus, Expressions

Until now we understood that λ calculus is nothing but a formal system to describe algorithms of computer programs. Although in theory it has mathematical support, but we are not interested in this scientific detail, so let us continue talking about how we can define algorithm and programs with the help of λ calculus.

Lambda calculus introduces an inexpensive way to express a function or an algorithm body. Nothing has all the good things,  λ calculus introduces an inexpensive way to write a function but it is a bit not like what we used to see in non-functional systems, like ordinary programming languages (say java 6 for example).

Suppose you want to multiply 1 and 2, divide 3 by 4 and then add these two results. There are some notation methods of doing this:

• Infix notation: 1 * 2 + 3 / 4
• Postfix notation: 1 2 * 3 4 / +
• Prefix notation: + * 1 2 / 3 4

Almost everybody knows the infix notation this is what usually we do in school math and we expect compilers pars our expressions in programming. But λ calculus expression is in prefix notation and this may bother us at first. 

Prefix notation
+ * 1 2 / 3 4

In this notation operators place to the left of their operands so to multiply 1 by 2 you have to write * 1 2 and to divide 3 by 4 you have to write / 3 4 and to sum these two expression you have to write + e1 e2 or + * 1 2 / 3 4 as we saw before. As you may have noticed this method of writing expression is exactly what we have in a parsing tree. 

This also applies for other mathematical functions like sine or cosine and ... instead of sin(x) you have to write just sin x. And  unless we want to do some grouping we do not use parentheses. So to write tan(sin(x)) simply write tan sin x,  or for tan(x) + sin(x) we have to write + tan x sin x. The example in next part shows we rarely need grouping too. And by the way, a valid λ expression is also called a λ term.

Order of operators

The following beautiful example from Wikipedia to calculate ((15 ÷ (7 − (1 + 1))) × 3) − (2 + (1 + 1)) shows everything:

− × ÷ 15 − 7 + 1 1 3 + 2 + 1 1 =
− × ÷ 15 − 7 2     3 + 2 + 1 1 =
− × ÷ 15 5         3 + 2 + 1 1 =
− × 3              3 + 2 + 1 1 =
− 9                  + 2 + 1 1 =
− 9                  + 2 2     =
− 9                  4         =
5

As you see you need to have both operands to start calculation so the first + 1 1 is the start of calculation. If you draw a parsing tree, you'll get the same result.

Abstract Syntax Tree 

During syntax analysis, a parser can create a tree like what we had for the above expression, we call it Abstract Syntax Tree or AST. AST almost contains the minimum punctuation and delimiters required to calculate the expressions. This is one of the reasons we called λ calculus is an inexpensive way of writing functions. You also need to pars an AST tree from left-to-right this is why we write and evaluate λ expressions left-to-right.

Many programming languages like Lisp, TCL and Ambi use the same notation method for writing expressions.