Re: Space requirements

[William D Clinger <will@ccs.neu.edu>]

No work of art is ever completed; it is only abandoned.

I would hate to see R5RS delayed by waiting for any of my
research to be published, especially a paper that hasn't
even been accepted yet.  I can't guarantee that it will
ever be published.

It's kind of funny that, recently, the biggest complaint
heard on rrrs-authors has been that we ought to formalize
proper tail recursion as a safe-for-space-complexity
property, not as a characterization of the continuations
that are passed to procedures.  On 26 May 1997 I posted
a message to comp.lang.scheme that was something of an
outline for the paper I later wrote.  The response was
not very positive.  Several people complained that I was
defining a safe-for-space property, not proper tail
recursion, and insisted that proper tail recursion had
only to do with procedure calls and/or continuations.
As I recall, that discussion led to Richard's decision
to base the R5RS discussion of proper tail recursion upon
the concept of continuations, instead of (IMHO) its more
technically correct basis in space complexity.

So what's going on?  Did Richard and I misread the consensus
last May?  Are the R*RS authors that much more sophisticated
than the folks who responded on comp.lang.scheme?  Have the
R*RS authors changed their mind about this over the last
seven and a half months?

Notice how little progress we have made since last May.

I think we should say something in R5RS, and leave it to
R6RS or to the next revision of the IEEE/ANSI standard to
say something better.

Will

--------

Bracketed comments _were_ in my message of 26 May 1997:

--------

Definition.  An implementation of Scheme is safe-for-space
(in the sense of a naive interpreter) if and only if for
every Scheme program P and inputs D, the space required to
execute P on D is O(N), where N is the maximum space required
by the abstract machine described below for the closed program
formed from P and D, taken over all execution sequences that
have the following two properties:

  1. Assignments evaluate to value(#F).  [This restriction
     does not affect portable programs.  Allowing arbitrary
     values for assignments, as allowed by the semantics below,
     can create space leaks.]

  2. A GC rule is applied as soon as it becomes applicable.
     [This has the effect of requiring garbage collection
     without specifying how often the gc must run, thanks
     to the asymptotic bound.]

Definition.  An implementation of Scheme is properly tail
recursive if it is safe for space as defined above.

Alternative definition.  An implementation of Scheme is properly
tail recursive if and only if the space required for continuations
is O(M), where M is the space required for continuations by the
abstract machine.  [This begs the question of which space should be
charged against continuations in real implementations, so I don't
think this definition is as useful as the previous definition.]