Friday, September 19, 2008

Church numerals (numbers and arithmetic using lambda calculus)

Here's how one would define zero and increment function using lambda calculus
(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))
- From SICP
Here zero is a function that takes a function (f) and returns a function which takes an argument (x) and applies f to x, zero times (or do not apply f to x).
The definition of add-1 can be easily understood by looking at the body of inner lambda expression. The body applies f to x (n+1) times, where n is the parameter.
So one would be
(define one (lambda (f) (lambda (x) (f x)))) ; We apply f one time to x
I'll leave the definition of one as an exercise.:-)


Snowy said...

You write very well.

Balagopal said...

Thank you very much :)