willc@tekchips.UUCP (Will Clinger) (10/16/86)
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
jds@duke.UUCP@ndmce.uucp (Joseph D. Sloan) (10/18/86)
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