🚀 go-pugleaf

In article <8712@duke.duke.UUCP> jds@duke.UUCP (Joseph D. Sloan) writes:
>	
>	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