Ken Anderson (········@stout.bbn.com) wrote:
: Originally i learned that goto's were to be avoided. So i avoided them
: using structured programming constructs. Now, I find myself doing a lot
: more tail recursion than i used to, such as:
Well,
effectively you can use lambda and tail recursive calls to emulate goto.
Consider this example in an evil language I was taught in school:
10 x := 0
20 x := x+1
30 if x > 10 then goto 50
40 goto 20
50 print "X = ", x
and its reformulation in perfectly valid Common Lisp
(let ((x))
(labels ((L10 () (setf x 0) (L20))
(L20 () (setf x (+ x 1)) (L30))
(L30 () (if (> x 10) (L50) (L40)))
(L40 () (L20))
(L50 () (format T "X = ~S~%" x)))
(L10)))
Recursion is a powerfull control structure. You have to use it carefully
or otherwise you could as well use goto. In Scheme with call/cc it is
sometimes very hard to understand the flow of control, even when
there are perfectly valid uses call/cc. It is almost always easier
to understand when you wrap it into some macro like catch/throw,
NonDet-Cond/Back-Track and so on.
I vaguely remember an article with the title "Lambda: The Universal Goto"
or so from Sussman? But all our retrieval system shows is
lambda. the ultimate imperative. Steele, G. / Sussman, J. -- mar 1976.
(Mit: reports; AI MEMO NO 353)
[Report R18518 48935]
Regards
Kai
--
_____________________________________________________________________________
Kai Zimmermann FB Informatik WSV, University of Hamburg, Vogt-Koelln-Str. 30
D-22527 Hamburg, Germany, Phone +49-40-54715-368, Fax -385
········@informatik.uni-hamburg.de
Kai Zimmermann (········@rzdspc21.informatik.uni-hamburg.de) wrote:
> I vaguely remember an article with the title "Lambda: The Universal Goto"
> or so from Sussman? But all our retrieval system shows is
>
> lambda. the ultimate imperative. Steele, G. / Sussman, J. -- mar 1976.
> (Mit: reports; AI MEMO NO 353)
> [Report R18518 48935]
Compare this with "LAMBDA: The Ultimate Declarative". This reminds me of
the RABBIT compiler (See references below).
The fact that lambdas (more precise is function invocation) could be
considered as GOTOs lead GLS to the implementation of RABBIT, A scheme to
MacLISP compiler; GLS actually used the MacLISP only as a "high-level
assembler", since he uses a very limited and strictly imperative subset of
MacLISP. I was quite somewhat impressed the first time I saw horrible large
nestings of lambda expressions resulting from macro expansion been tracked
down to the imperative level.
The underlying theory is the continuous passing style to which he converts
the scheme programs. Continuous passing style (CPS) means, that a function
does not return in the classical sense [,which means that function
invokation now identical to GOTO], but gets an additional argument, the
continuation, which is just another function to be called with the result
value. (This is compareable to the return address pushed onto the stack in
traditional implementation methods.) [Well, the continuation itself gets no
continuation.]
Together with the CPS goes the restriction, that the body of a lambda
expression may only hold one expression and that combinations (Scheme speak
for function calls) may only hold trivial expression (GLS term = variables,
constants and lambda expressions).
So someone has to define appropriate macros to yield the effect of e.g. a
PROGN (called `begin' in modern Scheme?!):
e.g. (A shortened example GLS gave)
(PROGN x y) should become:
((LAMBDA name1 (A B) (B)) ;I insert name[12] here to name the lambdas
x
(LAMBDA name2 () y)) ; <- this lambda could be viewed as continuation
== which would be compiled into something like ==>
<code for x> ;evaluate first arg for name1
LOAD reg2, [name2] ;evaluate second arg for name1
GOTO name1 ;invoke name1
name1: GOTO reg2 ;invoke B
name2: <code for y>
== after simple analysis, that reg2 has always the value [name2] ==>
<code for x>
GOTO name1
name1: GOTO name2
name2: <code for y>
== after elimination of superfluous GOTOs ==>
<code for x>
<code for y>
"What more could you ask for?" ; Original comment GLS made here.
Happy Lisping
Gilbert.
References
------------
GSL, "RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization)
AI-TR 474. MIT AI Lab (May 1978)
GLS, "LAMBDA: The Ultimate Declarative".
AI Memo 379. MIT AI Lab (November 1976)
PS. I wrote an interpreter for the Scheme dialect RABBIT is written in
using vanilla Common Lisp. If you interested in the interpreter, just
drop me a note.
--
Gilbert Baumann *** eMail ····@rz.uni-karlsruhe.de
In article <··········@rzsun02.rrz.uni-hamburg.de> ········@rzdspc21.informatik.uni-hamburg.de (Kai Zimmermann) writes:
>Ken Anderson (········@stout.bbn.com) wrote:
>: Originally i learned that goto's were to be avoided. So i avoided them
>: using structured programming constructs. Now, I find myself doing a lot
>: more tail recursion than i used to, such as:
>
>effectively you can use lambda and tail recursive calls to emulate goto.
I used to do that to deal with annoying "no goto" rules in courses,
when I didn't feel like messing with while-loops and the like just
to satisfy some TA.
>I vaguely remember an article with the title "Lambda: The Universal Goto"
>or so from Sussman? But all our retrieval system shows is
>
>lambda. the ultimate imperative. Steele, G. / Sussman, J. -- mar 1976.
> (Mit: reports; AI MEMO NO 353)
> [Report R18518 48935]
My memory agrees with your retrieval system, though there was at
least one other "Lambda the ultimate" paper: "Lambda: the ultimate
declarative". There was also on on the expensive procedure call
myth. It's possible that it had "ultimate goto" in the title.
The myth paper showed (among other things) the progressive
transformation of a goto-rich program via such things as
an explicit state + a case statement and tail-recursive procedure
calls to ... a program using gotos.
-- jeff