[plt-scheme] Lazy evaluation and tail calls

On Sat, Jan 17, 2009 at 6:42 AM, James Coglan <jcoglan at googlemail.com> wrote:
>
> I was wondering whether it's possible to have tail call optimisation when
> using normal order. I don't want to bang my head against the wall trying to
> make it happen if it can't be done.

To answer your question directly:  it isn't easy and it might not be possible
at all.  If anyone *really* knows the answer, it is Will Clinger.

I might be a bit behind the times here, but I believe it is still an
open question
the way you have phrased it.  I'll go out on a limb and suggest that a good
explanation is worthy of a degree.

There are a couple major obstacles to understanding.  First is a formal
definition of tail-recursion in a call-by-name or call-by-need
language.  It took
about 20 years for a good formal definition of tail-recursion to be developed
for plain old call-by-value Scheme.  Clinger identified a hierarchy of six
space complexity classes that a program and implementation may exhibit,
and showed that the intuitive notion of tail-recursion involved the
implementations
actual space usage as compared against the necessary space usage as
defined by the space complexity.

Unfortunately it is very difficult to reason about space usage in a call-by-need
or call-by-name language, even on an informal level.  So your first task would
be to figure out how to determine the space usage (preferrably statically!).
The second task would be to identify a number of space complexity classes.
I suspect that you'd find about the same number as in call-by-value, but I
could easily believe that you'd find a few more or a few less.  Or
perhaps *many*
*many* more, seeing as it is hard to understand.  Then you'd have to judge
whether an implementation (asymptotically) uses more storage than
the complexity class warrants.  *Then* you should figure out how to get
the implementation to avoid using the excess storage.

I think this would be quite a project.

But perhaps someone has already done most of the heavy lifting.  I'm not
entirely sure, but if Will is reading, maybe he can offer some corrections.

-- 
~jrm