Lambda Calculus and Common Lisp

Warning: If you do not like mathematics this post may not be interesting to you.

When we talk about lisp or any dialect of it we come across the term functional programming. So what is functional programming any way and where it all started? If you ever have thought about such things here is my small attempt to answer some very fundamental questions in functional programming.

So what are the functions? Here are some basics.

In mathematics functions is some kind of relation between two things. But wait a minute isn’t functions are some code snippet that does some tasks? After all we programmers know functions that way. Yeah, both are correct and they do not have any difference. Like a function, which increments a variable by one, can be represented in following way:

f(x) = x + 1

So we can write a lot of functions like this in mathematic and solve them for a value. However there was no such concept as function in the begging of computer science instead there were just Turing machines which used to change state to provide result and solve problems by means of its states; this is such a great system that it can solve all computational problems.

Then Alonzo Church came up with lambda calculus and revolutionizes the whole concept of representing and solving problems. He wanted to solve some mathematical paradox (if you want to know about them see here and here); unfortunately that was not solved but we got our base for functional programming.

I think its enough of history; let’s start what this post is all about.

Basic Notations

Here is how you can represent the previous function in λ calculus:

λx.x+1

And if we want to evaluate for x = 2 we write it as:

(λx.x+1)2

Now we can write the same in common lisp as:

((lambda(x)
(+ x 1)) 2)

Now functional calculus we have learnt another thing which is higher order functions. Higher order functions are nothing but functions whose arguments are also functions (I will not get into the evaluation debate here).

Like this:

Suppose we have a function f(x) = x + 1 and g(x) = x + 2 and we are calling f(x) as f(g(x)).

How is it going to be evaluated?

f(g(x)) = g(x) + 1 = x + 2 + 1 = x + 3

So how do we represent it lambda calculus?

(λx.x+1)(λx.x+2)

Now if we want to evaluate this for x = 2 we write it as

(λx.x+1)(λx.x+2)2

In common lisp we write:

((lambda(x)(+ x 1))

((lambda(x)

(+ x 2))2))

Free or Unbound Variable

“The variable X is unbound.”

How many times you have got this message in your REPL? This comes directly from lambda calculus; here is how.

Any variable that is not a member of any lambda expression is called a free variable and it does not have any effect on the evaluation of that expression. However in programs we cannot use such variable for evaluation. If we do so we get this error message.

In lambda calculus a variable in cases like this:

λx.(x * y)

Here the variable y is free. The same happens in common lisp.

((lambda(x)

(* x y))1)

Logical Stuffs

In programming we use logical operators every day, the two mostly(or *ONLY*) used of them are *AND* and *OR*. How lambda calculus does it?

Before I start I want to give the meaning of the following lambda expression:

λxy.xxy => λxy. if x then x or y.

And this expression is the *OR* function in lambda calculus. So we can write it in common lisp as:

(lambda(x y) (if x x y))

The *AND* function also look quite similar

Lambda Calculus: λxy.xyx

Common Lisp: (lambda(x y) (if x y x))

So that’s all about very ugly comparison of lambda calculus and common lisp. I know that I missed lot of things which include reductions and reduction strategies. But one can read about lambda calculus tutorials to get fair idea on this; here is my choice:

www.cs.chalmers.se/Cs/Research/Logic/TypesSS05/Extra/geuvers.pdf

www.utdallas.edu/~gupta/courses/apl/lambda.pdf

Thanks for reading.