tail recursion in Scheme
Author Message tail recursion in Scheme

I need some help from someone familiar with the implementation details of a
scheme interpreter.  Pardon my ignorance - I'm new to Scheme (or it is new
to me :) ) and I'm trying to learn all the ins-and-outs of the language.

In order to learn Scheme, I've implemented a Scheme interpreter in C.  The
description of the language and the implementation I've taken from the book
"Structure and Interpretation of Computer Programs" by Abelson and Sussman
(Can I presume that this book is familiar to Scheme programmers, like K&R is
to C programmers?)  I've found the book to be well written and from the
discussion the implementation is straight-forward.

The implementation of the Explicit-Control Evaluator (the description begins
on page 420) claims to be tail recursive.  However it appears that the
evaluator isn't tail recursive.  The procedure compound-apply always creates
a new frame and hooks it to the current environment.  The creation of the
new environment is independent of eval-sequence.  Consider the following
function that creates a list of integers from 1 to n:

(define (count n)
(cond
((= n 0) nil)
(else
(cons n (count (- n 1))))))

If I understand things correctly, this is a tail-recursive function.  The
function consists of only one statement - cond.  Everything else turns into
an argument to cond.  This means that the list sent to eval-sequence has
only one entry (the cond statement).

Evaluation of cond involves evaluating the = clause and, in all but the last
iteration, the cons and count functions.  The result of evaluating count is
a procedure.  Which eventually gets sent to compund-apply which in turn
creates a new environment frame.  Since compound apply doesn't know anything
about the function it always creates a new frame - even for the last
function call in a sequence.

If the implementation were truly tail recursive then new frames would not be
created for tail recursive functions.

Have I missed some important detail?  Is there an omission or mistake in the
book?  I would be most grateful if someone could shed some light on the
matter.

Mark Glasser
------------------------------------------------------------------------

2339 Charleston Rd #A
Mountain View, CA 94043
(voice) 415.691.0333
(fax) 415.691.0334
------------------------------------------------------------------------

Mon, 25 Jul 1994 06:01:12 GMT  tail recursion in Scheme

Quote:

>         (define (count n)
>             (cond
>                 ((= n 0) nil)
>                 (else
>                     (cons n (count (- n 1))))))
> If I understand things correctly, this is a tail-recursive function.

You do not understand correctly.  A tail recursion is a recursive
call that is the very last thing the function does.  Here, you do
a recursive call and then call `cons' after returning.

Here is one way to achieve the effect of `count' with a tail recursion.

(define (count1 n k x)
(cond
((= n 0) x)
(else
(count1 (- n 1) (+ k 1) (cons k x)))))

(define (count n) (count1 n 1 nil))

(bugs possible; I didn't have a Scheme implementation handy to test this)

The point is that the recursive call is now the last thing `count1' does.
Yes, I understand this is a little more complicated than necessary,
but simplifying it might make it even harder to understand.
--
--Andrew Koenig

Mon, 25 Jul 1994 22:09:20 GMT  tail recursion in Scheme
Not to pick nits here, but people might need to be aware or be reminded
that the variable nil is no longer defined in the Scheme standard - at
least not in R4RS.  So to make portable code, you can either define nil
yourself, probably as either #f or '(), or you should use #f or '()
explicitly, as appropriate.

Greg

Tue, 26 Jul 1994 03:02:31 GMT  tail recursion in Scheme

Quote:
> >         (define (count n)
> >             (cond
> >                 ((= n 0) nil)
> >                 (else
> >                     (cons n (count (- n 1))))))

> > If I understand things correctly, this is a tail-recursive function.

> You do not understand correctly.  A tail recursion is a recursive
> call that is the very last thing the function does.  Here, you do
> a recursive call and then call `cons' after returning.

It's interesting that the corresponding Prolog program *is* tail-recursive!

count(0, []).
count(N, [N|L]) :- N > 0, N1 is N-1, count(N1, L).

In procedural terms, the cons cell is built when the procedure count/2 has
determined that N > 0, and a "variable" (a kind of pointer) associated with
the cdr position is passed into the recursive call to count.  This "variable"
identifies the location in which the result of the recursive call to count
should store its value.

This sort of technique - in effect "preconstructing" data structures and
passing pointers to the slots which have yet to be filled in - is currently
only used in logic programming settings as far as I know, but it should be
much more widely applicable.

(One way to do this would be to pass *every* procedure call an "extra
argument" that identifies the memory location(s) into which it should write
its result.  But this is probably not optimal.)

Mark

Tue, 26 Jul 1994 05:01:55 GMT  tail recursion in Scheme

[non-tail-recursive count procedure in Scheme deleted]

mj> It's interesting that the corresponding Prolog program *is*
mj> tail-recursive!

mj> count(0, []).  count(N, [N|L]) :- N > 0, N1 is N-1, count(N1, L).

mj> This sort of technique - in effect "preconstructing" data
mj> structures and passing pointers to the slots which have yet to be
mj> filled in - is currently only used in logic programming settings
mj> as far as I know, but it should be much more widely applicable.

mj> (One way to do this would be to pass *every* procedure call an
mj> "extra argument" that identifies the memory location(s) into which
mj> it should write its result.  But this is probably not optimal.)

As was pointed out by another person, it is easy to write a tail
recursive version of count in scheme with an auxiliary function of two
arguments, the second being the accumulator.

(define (count n)
(define (count-aux n acc)
(cond
((= n 0) acc)
(else (count-aux (- n 1) (cons n acc)))))
(count-aux n '()))

A standard (although somewhat obtuse) way of doing this in Common Lisp
is with an &optional parameter.

(defun count (n &optional (acc nil))
(cond
((= n 0) acc)
(t (count (- n 1) (cons n acc)))))

In either case, we're able to continue with the recursive call without
keeping memory allocated for the last call around.

;Brent

--

Department of Computer Science          (603) 862-3786
University of New Hampshire
Durham, NH 03824

Tue, 26 Jul 1994 05:36:50 GMT  tail recursion in Scheme

Quote:

> As was pointed out by another person, it is easy to write a tail
> recursive version of count in scheme with an auxiliary function of two
> arguments, the second being the accumulator.

As yet another person pointed out, the alternative version of count proffered
is *not* equivalent to the original version.

Let me try to make it clearer.  Standard Scheme compilation techniques
won't compile the simple recursive definition of append into a tail
recursive procedure.  The only way to write a procedure that does what
append does, and which compiles into a tail-recursive function, uses
set-car! and set-cdr!.  (At least as far as I know - I would like to
know if I am wrong).

But there is compilation technology that will compile the simple "pure
Scheme" definition into a tail-recursive procedure - Prolog compilers
use it routinely, and I tried to sketch how it might be adapted to
Scheme in my previous message.

My point still stands,

Mark

Tue, 26 Jul 1994 23:38:44 GMT  tail recursion in Scheme
It is possible to write an iterative (i.e., tail-recursive) procedure
that will accumulate the numbers right-to-left like the original:

(define (count n)
(define (helper low high result)
(if (> low high)
result
(helper (+ low 1) high (cons low result)) ))
(helper 1 n '()) )

I may be confused about the following, but I believe that the claim about
Prolog is incorrect.  It's true that Prolog will construct the list from
the inside out, but while that list construction is going on, doesn't it
have to remember the original question that was asked, and each of the
sub-questions, in order to know how to express its conclusion?  If so,
somewhere in the background there is a stack full of pending queries.

Tue, 26 Jul 1994 23:56:54 GMT  tail recursion in Scheme

Quote:
> I may be confused about the following, but I believe that the claim about
> Prolog is incorrect.  It's true that Prolog will construct the list from
> the inside out, but while that list construction is going on, doesn't it
> have to remember the original question that was asked, and each of the
> sub-questions, in order to know how to express its conclusion?  If so,
> somewhere in the background there is a stack full of pending queries.

I think append is a better example, since it's not so easy to rework
the straight-forward definition into one that standard Scheme compiler
techniques will compile into a tail-recursive function.

However standard Prolog compilation techniques - and the adaptation
I described for Scheme in my first message - will compile this into
a tail-recursive function.*  I'll just sketch how Prolog does this,
for more details look at R. O'Keefe's book "The Craft of Prolog", MIT Press.

append([], XYs, XYs).                                       % (a)
append([X|Xs], Ys, [X|XYs]) :- append(Xs, Ys, XYs).         % (b)

Suppose the goal is

1. append([a,b], [c,d], Ans).

This goal unifies only with the head of clause (b), so after binding

Ans = [a|Xs_1]

it can be deterministically reduced to (i.e. popped from the stack and
replaced with)

2. append([b], [c,d], Xs_1).

Again, this goal unifies only with the head of clause (b), so again after binding

Xs_1 = [b|Xs_2]

it can be deterministically reduced to

3. append([], [c,d], Xs_2).

Finally, the recursion bottoms out.  This goal only unifies with the head
of clause (a), yielding no more subgoals, and the binding

Xs_2 = [c,d].

Since the goal stack is empty, we have succeeded in proving the goal (1),
and we print the value of the binding after substituting values for
variables.

Ans = [a,b,c,d].

My point is that the logical variables in Prolog are behaving like pointers
to the cdr slots of the cons cells into which the result of the following
recursive procedure call should be inserted.  The fact that most Prologs
can compile this definition for append tail-recursively follows from their
ability to build a structure before all of its components have been computed.

One can construct a structure and fill in its values later in Scheme using
destructive assignment, so one could code a tail recursive version of append
that way.  But such a program is no longer in "pure Scheme", i.e. that subset
of Scheme whose semantics is based directly on the lambda calculus.
Staying within pure Scheme is desirable, since many optimizations that
are valid within pure Scheme are no longer valid in full Scheme.  Thus
when using present-day Scheme compilers, users are faced with either writing
pure Scheme code that is not tail recursive, or writing Scheme code that
is not pure, but is tail recursive.

My point is that there are already compilation techniques available that
will compile the simple, pure Scheme definitions of recursive functions
such as append into tail-recursive code.  Especially since members of
the Scheme community pride themselves in their optimization technology,
I am surprised that such techniques are not discussed, let alone standard
practice.  (If this approach has been discussed already somewhere - which
is quite possible - I would appreciate a reference).

Thanks,

Mark

* In the Prolog case append must be called with a ground first argument.

Wed, 27 Jul 1994 02:15:54 GMT  tail recursion in Scheme

Quote:

>   Let me try to make it clearer.  Standard Scheme compilation techniques
>   won't compile the simple recursive definition of append into a tail
>   recursive procedure.  The only way to write a procedure that does what
>   append does, and which compiles into a tail-recursive function, uses
>   set-car! and set-cdr!.  (At least as far as I know - I would like to
>   know if I am wrong).

>   But there is compilation technology that will compile the simple "pure
>   Scheme" definition into a tail-recursive procedure - Prolog compilers
>   use it routinely, and I tried to sketch how it might be adapted to
>   Scheme in my previous message.

>   My point still stands,

>   Mark

Many de-recursivation scheme are based on algebraic properties of the
functions involved: for example, the usual definition of the factorial
function uses nested calls to the associative '+'.

Of course a compiler may apply de-recursivation techniques only when
it can rely on these algebraic properties -- ie, when the functions
involved are well identified. As a matter of fact, many compilers take
some liberties with the 'well-known' functions (In Common Lisp,
redefinition of the standard functions is prohibited).

I believe Emmanuel Saint James is the one who has collected (and
implemented) the most complete set of such de-recursivation schemes:
everything you could think of! (From the Scheme point of view, his
focus is a bit twisted, since he applies his techniques to a
dynamically-scoped, interpreted language, but most of them could be
embedded in a compiler).  See his paper "Recursion is more efficient
than iteration", Lisp conf.  Austin, 1984.

V. Delacour

Wed, 27 Jul 1994 03:04:53 GMT  tail recursion in Scheme

Quote:

>My point is that there are already compilation techniques available that
>will compile the simple, pure Scheme definitions of recursive functions
>such as append into tail-recursive code.  Especially since members of
>the Scheme community pride themselves in their optimization technology,
>I am surprised that such techniques are not discussed, let alone standard
>practice.

One can get caught doing destructive optimizations if a continuation is
captured and re-entered more than once.  The compiler would have to
make sure that none of the involved procedures can grab the
continuation.  Even when that is possible, interrupt handlers may grab
the continuation.  These include keyboard interrupts, GC interrupts,
and timer interrupts.

Wed, 27 Jul 1994 04:40:59 GMT  tail recursion in Scheme

> >         (define (count n)
> >             (cond
> >                 ((= n 0) nil)
> >                 (else
> >                     (cons n (count (- n 1))))))
>
> > If I understand things correctly, this is a tail-recursive function.
>
> You do not understand correctly.  A tail recursion is a recursive
> call that is the very last thing the function does.

It's interesting that the corresponding Prolog program *is* tail-recursive!

count(0, []).
count(N, [N|L]) :- N > 0, N1 is N-1, count(N1, L).

However, a smart Scheme compiler could transform the non-tail
recursive form into this form (internally). Or it could transform it
into the version that generates the reverse list and applies REVERSE
to the result.

I doubt that any existing compilers do this, and it is a rather
special-purpose optimization. However, the idiom comes up often enough
in real programs that it might be worth it.

Thomas.

Wed, 27 Jul 1994 09:00:24 GMT

 Page 1 of 2 [ 24 post ] Go to page:  

Relevant Pages