Tail recursion implementation and Lisp in Small Pieces

I'm defining my own Scheme-ish language, written in Common Lisp, and
I've been using Lisp in Small Pieces as a guide to implementation. I'm
having trouble getting tail recursion to work, though.

My interpreter is fairly simple, and I'm using Common Lisp closures to
implement continuations internally. Lisp in Small Pieces gives the
following code snippit as an example of a tail-recursive function to
implement (begin):

(define (evaluate-begin e* r k)
(if (pair? e*)
(if (pair? (cdr e*))
(evaluate (car e*) r (make-begin-cont k e* r))
(evaluate (car e*) r k))
(resume k empty-begin-value)))
(define-method (resume (k begin-cont) v)
(evaluate-begin
(cdr (begin-cont-e* k))
(begin-cont-r k)
(begin-cont-k k)))

It's fairly self-explanatory. The only thing that might be confusing is
Queinnec's use of a non-standard Object-Oriented system.
(make-begin-cont) just stores the fields and allows (resume) to specify
on it.

I implemented this almost verbatim, but my interpreter merrily descends
level after level in evaluating anything involving a begin. In other
words, it simply doesn't work.

(def (count n)
(write n)
(newline)
(count (+ n 1)))
Only manages about 1.5 thousand iterations.

As far as I can see, though, we're using identical methods. Is he
relying on the tail-recursive nature of Scheme itself here? (Which is
not of course guaranteed in Common Lisp.) Or is there something more
fundamental I'm missing?

Thanks for any assistance.

Apologies, Google seems to have mangled my indentation.

nepheles@myrealbox.com wrote:
> I'm defining my own Scheme-ish language, written in Common Lisp, and
> I've been using Lisp in Small Pieces as a guide to implementation. I'm
> having trouble getting tail recursion to work, though.
>
> My interpreter is fairly simple, and I'm using Common Lisp closures to
> implement continuations internally. Lisp in Small Pieces gives the
> following code snippit as an example of a tail-recursive function to
> implement (begin):

[snip tail-recursive begin evaluator in Scheme]

> I implemented this almost verbatim, but my interpreter merrily descends
> level after level in evaluating anything involving a begin. In other
> words, it simply doesn't work.
>
> (def (count n)
>      (write n)
>      (newline)
>      (count (+ n 1)))
> Only manages about 1.5 thousand iterations.
>
> As far as I can see, though, we're using identical methods. Is he
> relying on the tail-recursive nature of Scheme itself here? (Which is
> not of course guaranteed in Common Lisp.) Or is there something more
> fundamental I'm missing?

If your common lisp does not eliminate tail-calls, you're still building
up stack, even if your code looks tail-recursive.  My recollection of CL
is rusty, but I don't think tail-call elimination was one of its
features.

You need the equivalent of a GOTO (with args) to get the desired
results.  In Scheme, this is simply a tail-call :)

To solve your problem, you need to return to the caller, before actually
performing the tail call; that is, instead of performing the tail-call,
you return a data structure which says 'make a tail-call with these
args'.

Then, you need a special data structure for the initial continuation.

Finally, you wrap up the whole thing in a procedural loop.
--
A. Kanawati
NO.antounk.SPAM@comcast.net

Is there any open-source interpreter written in a Lisp-ish language
that implements this strategy? Most seem to either depend on the
underlying Lisp for tail recursion, or implement it atop a more complex
register machine.

nepheles@myrealbox.com wrote:
> Is there any open-source interpreter written in a Lisp-ish language
> that implements this strategy? Most seem to either depend on the
> underlying Lisp for tail recursion, or implement it atop a more complex
> register machine.

You don't need to go as far as a register machine.  You can develop
intermediate forms that are not very different from what you see in
the Scheme-based expression of these techniques.

The basic trick is to have a procedure call become a special kind
of return value, and then wrap the thing in a loop.  Something like:

(setq result (one-step args...)
(while (is-call-next result)
(setq result (call-next result)))

This way, you always unwind the stack before making the tail call.

--
A. Kanawati
NO.antounk.SPAM@comcast.net

nepheles@myrealbox.com wrote:
> Is there any open-source interpreter written in a Lisp-ish language
> that implements this strategy? Most seem to either depend on the
> underlying Lisp for tail recursion, or implement it atop a more complex=

> register machine.

The paper

<http://www.cs.indiana.edu/~sganz/pu...icfp99/paper.ps>
<http://www.cs.indiana.edu/~sganz/pu...cfp99/paper.pdf>

explains trampolining quite well.


But back to your original question - which interpreter in
LiSP are you mimicking? I believe some of the interpreters
in LiSP snarf tail recursion where as others don't.

--=20
Jens Axel S=F8gaard

I'm not specifically copying any of the interpreters, but it seems that
mine is most similar to that in section 3, with elements of 4 and 6
mixed in. It's sometimes hard to grok exactly what Quiennec means due
to the translation (for instance, "conditionals" seems to be translated
as "alternatives"). There's a discussion of tail recursion in section
3.6.2, and I haven't found it mentioned anywhere else, so I'm assuming
that the details he outlines are sufficient to construct a properly
tail-recursive interpreter.

nepheles@myrealbox.com wrote:

> (define (evaluate-begin e* r k)
>   (if (pair? e*)
>     (if (pair? (cdr e*))
>       (evaluate (car e*) r (make-begin-cont k e* r))
>       (evaluate (car e*) r k))
>     (resume k empty-begin-value)))

> (define-method (resume (k begin-cont) v)
>   (evaluate-begin
>     (cdr (begin-cont-e* k))
>     (begin-cont-r k)
>     (begin-cont-k k)))
>=20
> It's fairly self-explanatory. The only thing that might be confusing is=

> Queinnec's use of a non-standard Object-Oriented system.
> (make-begin-cont) just stores the fields and allows (resume) to specify=

> on it.
>=20
> I implemented this almost verbatim, but my interpreter merrily descends=

> level after level in evaluating anything involving a begin. In other
> words, it simply doesn't work.
>=20
> (def (count n)
>   (write n)
>   (newline)
>   (count (+ n 1)))
> Only manages about 1.5 thousand iterations.
>=20
> As far as I can see, though, we're using identical methods. Is he
> relying on the tail-recursive nature of Scheme itself here? (Which is
> not of course guaranteed in Common Lisp.) Or is there something more
> fundamental I'm missing?

I have reread chapter 3 and I see the same two potential places
for memory leaks while interpreting the count program as you do (with
regard to tail recursion):

1. In the implementation of evaluate-begin
2. In CL's use of stack frames versus Scheme's tail recursion

In chapter 3.2 the interpreter makes all continuations explicit. Thus
to make a the interpret respect proper tail recusion, it must not
build superfluous continuations. But since you are aware of this,
it is most likely the second thing that bites you.

What happens when interpreting count?

(count 10)           ; evaluate calls evaluate-application
; which eventually calls invoke
; which calls evaluate-begin on:

(begin               ; evaluate-begin eventually
(write n)          ; calls evaluate on:
(newline)
(count (+ n 1)))

(count 11)           ; which call evaluate-application
; which eventually calls invoke
; which calls evaluate-begin etc.

Since all the above calls are tail calls, no stack space are
will be exhausted in Scheme where as in CL you end up
using all the stack space.


To test the theory try allocating more stack space for your
CL program before you start it, and see whether you can
get to loop more than before.


The interpreter in chapter 7 does not have this problem,
since the only reliance on tail calls are in the definition
of the function run on page 237:

(define (run)
(let ((instruction (fetch-byte)))
(case
..
((5) (let ((j (fetch-byte)))
(set! *val* (activation-frame-argument *env* j)) ))
.. ) )
(run))

Turning this into a normal loop in CL is luckily simple.

--=20
Jens Axel S=F8gaard

You can check Peter Norvig's PAIP[1], where he implements (among other
interesting things) a Scheme interpreter and compiler in Common Lisp.

The source code is available from this site, but I'm not sure if it's
documented enough by itself.  But this is a great book and I think you
won't regret purchasing it, anyway.

[1] Paradigms of Artificial Intelligence Programming: Case Studies in
Common Lisp -- http://www.norvig.com/paip.html

> As far as I can see, though, we're using identical methods. Is he
> relying on the tail-recursive nature of Scheme itself here? (Which is
> not of course guaranteed in Common Lisp.) Or is there something more
> fundamental I'm missing?
>
> Thanks for any assistance.


Most good common lisp implementations support the elimination of tail
recursive frames. But you may need to check your implementations' use of
declarations. Usually declarations guaranteeing efficient tail calls
involve some high level speed optimisation and/or low level debug
optimisation.