Re: Space requirements

[Matthias Blume <blume@CS.Princeton.EDU>]

From: William D Clinger <will@ccs.neu.edu>
Subject: Re: Space requirements
Date: Thu, 15 Jan 1998 20:21:39 -0500

> ...
> 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?

I guess I was too busy last May to follow the discussion in an
alert-enough state.

Of course, it should have become clear by now that I agree with Will's
opinion that a definition based on space complexity is better.  In
fact, any discussion based on continuations does not add much unless
we provide metrics on how much space is used by those continuations.
After all, even a "naive" (or "pessimizing" according to Guy Steele)
CPS translator would still be properly tail-recursive if in the
resulting CPS program eta-redexes of the form (lambda (r) (k r)) use
no more space than k itself.  In this case we can leave those
eta-redexes in there -- they are only a mathematical concept and don't
take up physical space.  But again, to make this notion precise we
would have to provide space metrics for CPS programs...

> 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.

Sounds ok to me.

> 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.

Ditto.

-Matthias