Subject: Re: Tail recursion & CL
From: Erik Naggum <>
Date: Tue, 02 Oct 2001 08:38:30 GMT
Newsgroups: comp.lang.lisp
Message-ID: <>

* Erik Naggum
| I think you might mean the form that evaluates to the value of the
| function.  It might, for instance, be possible to unwind special 
| bindings and unwind-protect forms in such a way that you could jump
| to a function with it returning to the cleanup forms, so the notion
| of "last" might be very confusing and counterproductive.

* Bruce Hoult
| I covered this in that previous message as well.
| Anything subject to unwind protect or the like is prima facie NOT in
| tail position.  It is possible that a smart compiler may be able to
| optimize things so that it can be moved into tail position, but that's
| not something you could depend on.

  If you had covered it, you would have known that this is not simply an
  "optimization", but a design decision that would have to be taken if you
  wanted true support for tail calls.  Both special bindings and unwind-
  protect are so common in Common Lisp programs that separating them from
  the call stack would have been a _necessary_ design decision, in order
  that tail calls actually produce useful results.  Since you said you had
  covered this, contrary to my usually flawless short-term memory (I study
  SQL intensely right now, so there may be some irregular lossage :), I
  looked for where you had, but I cannot find it.

| It seems especially dangerous to move something out from the body of an
| unwind-protect -- you'd have to prove first that it was impossible for it
| to throw.

  This is utter nonsense.  Please try to understand how a system that does
  unwind forms _must_ set up these things.  The body forms in practice _do_
  return, throws or not, through a chain of unwind form, including special
  bindings, and whether you do this by setting up in-band catcher code or
  through a separate stack of unwind-forms-to-be-executed, is immaterial.
  If you do the latter on a separate stack, there is no difference between
  a normal return from the code that sets it upand a return from somewhere
  else: the setup has already been done and the execution is performed as
  part of the return procedure.

  If you decide to mandate tail-call optimization into jumps, this design
  would have to be "required" of an implementation because refusing to do
  tail calls simply in the face of special bindings would just be stupid --
  having an elegant solution as it does.  If you do not mandate it, you can
  get away with only "simple" tail-call optimization, and you can get an
  even more inexpensive tail-call technique when you get it, if you get it.

  In essence, I believe "properly tail-recursive" is a design decision that
  affects how the call stack must be designed (and continuations fall right
  out of a heap-allocated call frame and chain design) and how you can deal
  with special bindings and unwind-protect (it is no accident that Scheme
  does not), while tail-call _optimization_ is possible even in languages
  such as ANSI C.  I therefore also believe that it is a _disservice_ to
  the community to require "properly tail-recursive" because it requires
  too many negative and unwanted properties of the implementation, but that
  it is perfectly legitimate to ask the implementations for such a feature.
  Amazingly, this is the actual situtation: E.g., Allegro CL does a very
  good job of optimizing tail calls to both self and non-self if you ask
  for it in their proprietary way, but optimization _is_ a "proprietary"
  process, anyway.  I think some language designers fail to understand this
  and believe in _mandated_ optimization, which only limit and restrict how
  their languages may be implemented to the techniques known at the time
  their favorite optimization theory was in vogue, or techniques developed
  along that evolutionary branch.  The less you prescribe in terms of how
  to optimize, the more you can take advantage of free-ranging research in
  optimization, both software and hardware.  This is why C is _still_ best
  optimized for PDP-11-style processors.