Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!nike!ucbcad!ucbvax!hplabs!tektronix!tekcrl!tekchips!willc
From: willc@tekchips.UUCP (Will Clinger)
Newsgroups: net.lang.lisp
Subject: Re: Help with Abelson & Sussman problem?
Message-ID: <744@tekchips.UUCP>
Date: Thu, 16-Oct-86 15:22:40 EDT
Article-I.D.: tekchips.744
Posted: Thu Oct 16 15:22:40 1986
Date-Received: Fri, 17-Oct-86 06:03:07 EDT
References: <8712@duke.duke.UUCP>
Reply-To: willc@tekchips.UUCP (Will Clinger)
Organization: Tektronix, Inc., Beaverton, OR.
Lines: 32

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