Lambda Calculus For Programmers
Written by Mike James   
Wednesday, 18 July 2012
Article Index
Lambda Calculus For Programmers
Reduction
Using lambdas

Bound free and names

Variables that occur withing lambda expressions next to a lambda are called bound variable - the others are free variables.

You can think of bound variables as the parameters of the function.

Now that we have beta reduction defined you can see that there is a sense in which it doesn't matter what you call a bound variable. For example:

λx. x

is the identity function because (λx. x) e gives e. Obviously

λy. y

is also the identify function.

So we can change the name of a parameter without changing the function. This is alpha reduction (or alpha conversion or alpha-renaming).

Exactly how you do the renaming and how you combine expressions that use the same names for variables can get a little complicated. The safest rule to follow is to change bound variable names so that they are different from any free variables in another expression and to make sure that free variables are have distinct names in different expressions.

For example don't write :

(λx.x)x

use

(λy.y)x

The rules for how to deal with name clashes can seem complicated at first but if you remember that each lambda expression is an entity in its own right and any variables names do not carry across from one entity to another you should find it fairly easy. You can think of it as function local variables if it helps.

Using lambdas

You can now see what lambda expressions are all about even if some of the fine detail might be mysterious but what next?

The point is that lambdas provide a form of universal computation using just the symbols and the rule - no extra theoretical baggage needs to be brought into the picture. This is where is gets far too theoretical for some practical programmers. For example we don't just introduce integer values that can be stored in variables. Instead we invent symbols, well lambda expressions that behave just like the integers.

if you have never seen this sort of thing done before it can see very complicated but keep in mind that all we need are some symbols that behave like the integers.

One possible set of such symbols is:

0 =  λsz. z
1 = λsz. s(z)
2 = λsz.s(s(z))
3 = λsz.s(s(s(z))

and so on.

You can see the general structure we have a function of s and z and the number of s variables in the body of the function grows by one each time. In general the symbol that represents n has n s variables.

Ok so what have these strange lambda expressions got to do with integers?

The answer is that for a symbol to represent an integer it has to obey the basic properties of the integers - or rather we have to find some other symbols that behave in a way that mirrors the properties of the integers - i.e. addition, subtraction and so on. 

One of the basic properties of the integers, more fundamental than arithmetic, is the successor function which gives you the very next integer. succ(n)=n+1.

It is fairly easy to create a successor function as a lambda expression:

 Succ= λabc.b(a b c)

This may look like a mystery at first but try it out. Apply Succ to the zero symbol - i.e. let's succ it and see:

Succ 0 = λabc.b(a b c) (λsz. z)

The first resolution is to substitute the zero symbol for a

Succ 0 = λabc.b(a b c) (λsz. z)
= λbc.b((λsz. z) b c) 

In this expression we can make two more resolutions as the inner function (λsz. z) can be applied to b to give(λz. z)c which can be reduced to give c:

Succ 0 = λabc.b(a b c) (λsz. z)=
λbc.b((λsz. z) b c)=
λbc.b((λz. z) c))=
λbc.b(c)

That is:

Succ 0 = λabc.b(abc) (λsz. z)= 
λbc.b(c) = λsz.s(z) =1

Notice that we can change the parameter names to s and z without changing the lambda expression.

You can try the same calculation for other integer symbols and you will find that it works. The reason it works is that the succ function as defined adds one more occurrence of the b variable to the integer.

From here you can continue to invent functions that add, multiply and so on. You can also define Booleans and logical operations, recursion, conditionals and everything you need to build a computational system.

For most this is two low level and abstract to follow though. After all if it takes this long to create the integers how long would it take to create the rest?

So our account of the lambda calculus finishes here, but you should be able to see that this simple system is capable of being used to construct a Turing machine, and  a Turing machine can be constructed that is equivalent to a lambda expression and reduction.

The two are equivalent as far as computation goes.

The role of lambda in programming

Now we get to a difficult part.

Why is this very theoretical idea turning up in highly practical programming languages? It turns up in functional languages because the ideas fit together - the lambda calculus is a functional programming language. In other languages it turns up because it provides a simple way of defining anonymous functions that can be passed to other functions.

In a language that has functions as first class objects, i.e. where functions are objects and can be passed as parameters to other functions, then there is no real need of anything like a lambda expression. Even languages as simple as JavaScript don't really need to call anything a lambda expression, because all functions are first class objects and and anonymous function is just one you don't bother assigning to a variable.

In languages such as Java and C# functions only occur as members of objects. There aren't such things as free floating functions that don't belong to some object. There hence cannot be anything like an anonymous function. To avoid adding functions as object in their own right you have to introduce something that looks like a lambda expression. A function head that defines the parameters and a function body that defines what to do with the parameters to obtain a return result. Notice that any lambda expression defined as part of a programming language goes well beyond what we have discussed here - in particular the variables are used as variables and store complex data types and the standard operations are defined. While it is true that all of these things could be reduced to formal lambda expressions this isn't of much interest to the practicing programmer - and nor should it be.

So the lambda expressions that you meet in object-oriented languages really don't have that much to do with the lambda calculus, and not that much to do with the grammar of lambda expressions. They are just anonymous functions that you can pass to another function and a way of avoiding the need to implement functions as objects.

Related Articles

What is a Turing Machine?

Computability

Reverse Polish Notation - RPN

Lambda Expressions

Javascript Jems - Lambda expressions

 

blog comments powered by Disqus

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.

 

 



Last Updated ( Sunday, 22 July 2012 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.