Path: utzoo!attcan!uunet!zephyr.ens.tek.com!uw-beaver!ubc-cs!manis From: manis@cs.ubc.ca (Vincent Manis) Newsgroups: comp.edu Subject: Re: Recursion Summary Message-ID: <10248@ubc-cs.UUCP> Date: 27 Oct 90 01:26:30 GMT References: <9882@milton.u.washington.edu> <9892@milton.u.washington.edu> <9896@milton.u.washington.edu> Sender: news@cs.ubc.ca Distribution: na Organization: Institute for Pure and Applied Eschatology Lines: 28 Good God! We seem to have a heat vs light argument here. Needless to say, it is quite possible: (1) to map all recursive computations onto iterative one, and (2) to map all iterative ones onto recursive ones. The proof is quite straightforward, with (1) being done by rewriting procedure call as a push and a goto, and return as a pop, and (2) being done by rewriting while as a recursion, and then using Bohm-Jacopini's result about assignment-if-while being universal. Another proof appeals to quite practical arguments: conventional computers operate by sequential state dispatch (if you see this instruction, do this operation, and enter that state), yet recursion can be implemented on such machines. In the other direction, languages as various as TRAC (R), Scheme, and Prolog define WHILE as a user operation. I would recommend Marvin Minsky's Computation: Finite and Infinite Machines (Prentice-Hall, 1967, and still in print!) for good discussions of program equivalence, and Guy Steele's series of Scheme papers (Lambda: The Ultimate Imperative, Lambda: The Ultimate Declarative, and so on, available as MIT AI Tech Reports, from the mid '70's), for specific discussions of this topic. -- \ Vincent Manis "There is no law that vulgarity and \ Department of Computer Science literary excellence cannot coexist." /\ University of British Columbia -- A. Trevor Hodge / \ Vancouver, BC, Canada V6T 1W5 (604) 228-2394