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.