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.:-)