Saturday, April 6, 2013

Order of evaluation for nested lambda expressions in Scheme

I have been working through MIT's Structure and Interpretation of Computer Programs. I'm interested in learning computer science and have found the book to be approachable, though a bit heavy on the theoretical side of the science.

Exercise 2.6 deals with the Church numerals, i.e. natural numbers that are defined in terms of the lambda calculus. I have struggled a bit to understand these concepts, but the struggle ended when I made the following realization.

Consider the definition of 'one' in Scheme's notation for the lambda calculus:
(define one (lambda (f) (lambda (x) (f x))))
Here, f is any function and x is any variable. I was initially confused by the order of operations in this expression. For example, if I had a function called square
(define square (lambda (x) (* x x)))
then I didn't understand how I could use the definition of one to apply the function square to x. The two approaches I tried were
((one 2) square)
((one square) 2)
As it turns out, the second line of code returns the number 4, whereas the first one returns a function. The reason I was confused was because in the definition of one, the expression (lambda (f) ...) occurs in the outermost set of nested parentheses, whereas when calling one, the function that is substituted for the formal parameter f is entered in the innermost set of parentheses.