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

* Bruce Hoult
| I don't know why, but you and Kent seem to want a lot more from "tail
| call optimization" than I do.

  Huh?  I have argued for a differentiation of "properly tail-recursive"
  and "tail call optimization".  What I want from tail call optimization is
  meant to be a severe restriction of what Scheme freaks want from their
  undesirable "properly tail-recursive" concept.

| Or, rather, you *don't* want it and so insist that if it can't work in
| every conceivable situation then it isn't worth having at all.

  Are you nuts?  Where did you get this garbage?  Of course I want it.
  However, I do not want it mandated by the standard, because that has a
  lot of negative aspects to it.  Hell, if I want a standard that says
  something so annoying as requiring a properly tail-recursive execution
  model, I would use Scheme.  I loathe Scheme.  Get a grip, Bruce, quit
  pretending that you are fighting an enemy you are not.  Please realize
  that there is a difference between a desire for a feature and a desire
  for a law (or specification) that require others to provide a feature.
  You seem to confuse the two, or at least not allow other people (Kent and
  me?) to make a distinction, and get all flustered because you think we do
  not want what we do not want there to be a law to _require_.

  I believe the rest of your message rests on these false premises, too.

| No it is not.

  Christ, Bruce, THINK!  I have no patience with this crap.  Go back and
  read what I wrote.  You have clearly not understood what I said, and now
  you argue against something you have misunderstood.  Quit that stupidity.

| You'd have to prove a bunch of other things as well, of  course, but that
| one alone is sufficient to show that it's very very  difficult to
| impossible to convert something inside an unwind-protect  into something
| that can be tail-called.

  This is just simply wrong.  _Listen_, now, OK?  

| Indeed.  Which is precisely why using a tail-call for things inside an 
| unwind-protect is a nonsense.

  You obviously fail to think about this, and that annoys me.  Consider
  this simple fact: What a function returns to is _not_ under its control.
  If a function returns to its caller, which does some work before it also
  returns, it could as well return to a different function that does that
  work.  This is the core of the argument for tail-call optimzation, is it
  not?  Why does it _not_ apply to unwind forms?  _Think_ about this, OK?

| The whole *point* of the tail call is that it doesn't return

  Huh?  What is this nonsense?  On the contrary, the whole point is that it
  returns to the caller of the caller in place of the caller, which has
  _redirected_ it to return elsewhere from what _its_ caller said it should
  return to.  The whole *point* with tail calls is that there is a simple
  semantic equivalence between call/return/return and jump/return, and that
  this is completely independent of _both_ what you jump _and_ return to.
  What I suggest is an _expansion_ of the mere implementation of tail-call
  optimization such that you can call functions for their side-effect after
  a call that returns a value simply by returning to them instead of
  callling them.  That is well within the conceptual framework of what you
  seem to be clamoring for.  Why do you not get this simple application of
  your concept of tail-call optimization?

| Anything that you have to come back and do later (e.g. unwind) totally
| nullifies that.

  _Wrong_.  _THINK_ about this, will you?  _How_ you arrange for something
  to be done after you have returned is ORHTHOGONAL to arranging to do it.

| This is true, but it's pretty pointless.  In a recursive call that
| contains an unwind-form you're going to grow your stack of
| unwind-forms-to-be-executed without bound.

  So you think tail-call optimization is _only_ for recursion?  What _is_
  this?  Bruce, you _are_ not the idiot you seem to be insisting on showing
  me right now.  What has gotten into you?  The Scheme freaks want a
  properly tail recursive execution model for a number of reasons.  Tail
  call optimization is a much weaker concept, and it will actually save a
  lot of stack space -- namely the stack space consumed by arguments and
  call frames -- _even_ if you have special bindings and unwind-protect
  forms.  _Those_ are the worth-while savings.  And what is this silly
  thing about "without bound"?  There will be no more and no less bound on
  the recursion regardless of tail-call optimization!  If you can save on
  _some_ resources, but not all, why are _you_ opposed to that?  Was it not
  _you_ who accused Kent and me of the following just a few lines up?

| Or, rather, you *don't* want it and so insist that if it can't work in
| every conceivable situation then it isn't worth having at all.

  Now _you_ are arguing this silly position which nobody else holds.  Quit
  the stupidity and _think_ about what you are saying, damn it!

| Sure, you'll save a little memory because the structure that you put on
| that stack each time is probably a little smaller than the entire stack
| frame for the function would be, but that's just a savings of a constant
| factor -- it doesn't make a tail-recursive function (or set of mutually
| tail-calling functions) execute in constant space, which is the purpose
| of the optimization.

  Why do you restrict an optimization to such a purpose?  Why do you need
  there to be "constant space" when there is a clear and present benefit
  from not over-using another resource?  And why do you drag in the _size_
  of call frames?  Christ, Bruce, that is _so_ beside the point.  Call
  frames can be *large* these days.  An unwind-protect/special stack can be
  very small.  Now _you_ want to discard the stack space savings because
  you will still need special/unwind-protect space?  What _is_ this?

  Whatever _are_ you defending, Bruce Hoult?  Whatever it is, I can assure
  you that it is _not_ under attack.  Just _think_ about the arguments you
  get and you might learn something that you are currently insisting on
  _not_ seeing.