[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Tail recursive Common Lisp interpreter?
- To: edsel!eb@SU-NAVAJO.ARPA
- Subject: Tail recursive Common Lisp interpreter?
- From: "George J. Carrette" <GJC@MC.LCS.MIT.EDU>
- Date: Sat, 28 Dec 85 19:38:46 EST
- Cc: Common-Lisp@SU-AI.ARPA
- In-reply-to: Msg of Sat 28 Dec 85 15:15:18 pst from edsel!eb at su-navajo.arpa (Eric Benson)
Thats an extremely interesting discovery. One known way to win: You
can implement an explicit control evaluator like one might in Scheme.
The control-point from a block then falls out like schemes lexical
catch contruct does. Or, what is easier, given a Scheme with lexical catch,
write your Common-Lisp interpreter in that.
Here is another tail-recursion story. One of Papert's hackers was relating
to me one day how LOGO was tail recursive even though it used shallow
binding, and how that this was a pretty clever thing (to pull off)
So I said, ok, lets try to write:
(DEFUN IFACT (N ACC) (IF (ZEROP N) ACC (IFACT (1- N) (* N ACC))))
and thus (DEFUN FACT (N) (IFACT N 1)). Well, my first try didnt work
at all, in fact, it didnt return ANY VALUE. I was then told that, OH,
to return a value you have to use OUTPUT. Thus (excuse the inexact logo syntax)
TO IFACT :N :ACC IF N=0 OUTPUT ACC ELSE OUTPUT IFACT N-1 N*ACC
well, the OUTPUT caused the tail recursion to be broken.
Or, you cant teach an ancient dog old tricks.
Or, you can dress the language up but you cant take it ...