How to call circuit number functions from SICP
In SICP (ex 2.6), the following functions are described as "no-number workarounds". I scratch myself trying to figure it out. As a starting point, how do you call these functions? Can I actually apply them somehow when the output is 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 were not 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
>
source to share
These functions, which represent numbers, are called church numbers (like SICP states). Their existence means that you can define a computation system (like lambda calculus) without having numbers as first class objects, you can instead use functions as primitive objects. This fact is mainly of theoretical interest; Church numbers are not a good choice for practical calculations.
You can see the correctness of your definitions of the Church numbers by applying them to other objects as arguments. When you apply the Church digit representing n to a function f, you get another function that applies f to its argument n times, for example 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)
source to share
this is the original lambda calculus, it doesn't produce numbers, it replaces the number type entirely with functions.
So, you have a function "zero", and if you call add-1
to it, you don't get 1, you get another function that represents 1. the point is that the generated functions correspond to basic axiom arithmetic, so they are equivalent to natural numbers
source to share