Subject: Re: Tail recursion & CL
From: Erik Naggum <erik@naggum.net>
Date: Mon, 22 Oct 2001 02:33:51 GMT
Newsgroups: comp.lang.lisp
Message-ID: <3212706829871008@naggum.net>

* Bruce Hoult
| This is hardly surprising.

  But it obviously is, to _so_ many people.

| At heart, the idea of tail-call merging  comes from the observation that
| if the compiler generates code like...
| 
|   jsr foo
|   ret
| 
| ... then it can be replaced with:
| 
|   jmp foo

  I think this is a very good summary of the _actual_ issue.  However, if
  the language mandates that it be "properly tail-recursive", there will be
  a lot more cases like that than if it does not mandate it, and lots of
  things that would make it impossible to do it, will be taken out of the
  language.  Given that we find cases like this in our compiled code and
  can exploit the existing stack framework, wanting tail-call merging is
  harmless to the language.  Given that requesting more tail-call merging
  on an abstract level has far-reaching consequences for the rest of the
  language, this means that the request is not just a desire to change
  these two instructions into one where they occur, but an implicit desire
  for all the other changes that come with it.

| I guess that's not pleasing to purists, but it's good enough for me.

  Me too.  I am perfectly happy with Allegro CL's way of separating the
  mergeability of tail-calls to self and to non-self.  Since a tail-call to
  self can easily be made into a jump to a _different_ location than one
  would normally jump to enter a function, not the least because you know
  the exact argument list and can do everything you may need to do arrange
  for optional and keyword arguments and what-not before you jump to the
  real code, effectively only setting the lambda variables to new values,
  the complexity of unwinding the stack and all that evaporates, the stack
  frame can be reused, and (almost) all the complexity of a non-self tail-
  call is simply not there.  Nonetheless, Allegro CL does an impressive job
  of merging non-self calls, too.  It turns out to be quite useful in CLOS.

///
-- 
  Norway is now run by a priest from the fundamentalist Christian People's
  Party, the fifth largest party representing one eighth of the electorate.
-- 
  The purpose of computing is insight, not numbers.   -- Richard Hamming