tags:

views:

246

answers:

2

In SICP, (ex 2.6) the following functions are described as ways of 'getting by without numbers'. I'm scratching trying to understand this. As a starting point, how do these functions get invoked? Can I actually apply them in some way where the output will be 1? (Or any other number?)

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

My initial attempts haven't been successful:

Welcome to DrScheme, version 4.1.5 [3m].
Language: Simply Scheme; memory limit: 128 megabytes.
> (add-1 (zero))
. . procedure zero: expects 1 argument, given 0
> (add-1 zero)
#<procedure>
> (add-1 1)
#<procedure>
> ((add-1 1))
. . #<procedure>: expects 1 argument, given 0
>
+3  A: 

this is the original lambda calculus it doesn't produce numbers, it totally replaces the number type with functions.

so, you have a 'zero' function, and if you call add-1 to it, you won't get 1, you get another function that represents 1. the point is that the functions produced comply with the basic arithmetic axioms, so they're equivalent to natural numbers

Javier
+7  A: 

These functions that represent numbers are called Church numerals (as SICP states). Their existence means that you can define a system of computation (such as the lambda calculus) without having numbers as first-class objects--you can use functions as the primitive objects instead. This fact is mainly of theoretical interest; Church numerals are not a good choice for practical computation.

You can see the correctness of your definitions of Church numerals by applying them with other objects as arguments. When you apply a Church numeral representing n to a function f, you get another function that applies f to its argument n times, e.g., f(f(f(x))) for n=3.

> (define (double x) (* 2 x))
> (zero double)
#<procedure>
> ((zero double) 1)
1
> ((zero double) 100)
100
> (define one (add-1 zero))
> ((one double) 1)
2
> ((one double) 100)
200
> (define (cons-a x) (cons 'a x))
> ((zero cons-a) '())
()
> (((add-1 one) cons-a) '(1 2 3))
(a a 1 2 3)
Nathan Kitchen
Penrose includes this in The Emperor's New Mind, I think it's just an excuse to use a different font. (in the book he represents "zero" and "one" as numbers in an outline typeface)
Jason S