[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: a (revised) draft of R5RS



I am unaware of any method of making the requirement that Scheme
implementations be tail recursive precise.  As stated, it is a useless
requirement.

Greg Morrisett and Robert Harper have made available an outstanding
paper which formalizes the memory requirements of an implementation
that uses tail-call elimination for ML, among other things.

    ftp://reports.adm.cs.cmu.edu/usr/anon/1996/CMU-CS-96-176.ps

Following their model, a language designer can make precise the
requirement that an implementation of a programming language behave as
if it uses tail-call elimination by requiring that, asymptotically,
implementations use no more space then a memory aware abstract machine
which uses tail-call elimination.  Let me call implementations that
meet this requirement tail-call aware implementations.

I propose we drop the requirement that Scheme implementations be tail
recursive and instead require that they be tail-call aware.  We should
justify this new requirement by the fact that it seems to allow the
use of syntactically recursive procedures to describe iterative
computations that execute in constant space and leave it at that.

John