Help with Abelson & Sussman problem?
Joseph D. Sloan
I'm looking for help with a problem in Abelson & Sussman.
Exercise 2.5 calls for representing the integers as functions,
i.e., Church numerals. The stated problem is fairly straight
forward considering the hint. My question or dilemma is what
comes next? Given the functions, how do you manipulate them as
numbers? For example, how do you test for equality of two
functions (integers)? Am I just being dense? Should this
be obvious? Any help or pointers would be appreciated.
Joe Sloan, duke!jds
Box 3090, DUMC
Durham, NC 27710
(919) 684-3754
Will Clinger
>
> I'm looking for help with a problem in Abelson & Sussman.
>Exercise 2.5 calls for representing the integers as functions,
>i.e., Church numerals. The stated problem is fairly straight
>forward considering the hint. My question or dilemma is what
>comes next? Given the functions, how do you manipulate them as
>numbers? For example, how do you test for equality of two
>functions (integers)? Am I just being dense? Should this
>be obvious? Any help or pointers would be appreciated.
None of it is obvious. Some of it is downright difficult.
The basic idea is that the Church numeral representing n is a function
that will take a function f and return the nth iterate of f (f^n, e.g.
cos^2). From this you should be able to figure out how to write zero,
successor, addition, multiplication, exponentiation, super-exponentiation,
and so on.
The hard one is predecessor. If you give up, you can find a definition
in Joe Stoy's book "Denotational Semantics: the Scott-Strachey Theory of
Programming Languages", published by MIT Press. Once you understand
predecessor, it should be fairly easy to define equality.
It's amazing how fast these things run. I just now defined the Church
numeral for 1024 and checked it by running ((Church1024 1+) 0) (where
1+ is the built-in procedure, not the successor function defined in
the exercise). It took about two seconds using a byte code interpreter
for Scheme on a 68000.
William Clinger
Tektronix Computer Research Laboratory
Joseph D. Sloan
I'm looking for help with a problem in Abelson & Sussman.
Exercise 2.5 calls for representing the integers as functions,
i.e., Church numerals. The stated problem is fairly straight
forward considering the hint. My question or dilemma is what
comes next? Given the functions, how do you manipulate them as
numbers? For example, how do you test for equality of two
functions (integers)? Am I just being dense? Should this
be obvious? Any help or pointers would be appreciated.
Joe Sloan, duke!jds