Subject: Re: Tail recursion & CL
From: Erik Naggum <erik@naggum.net>
Date: Tue, 09 Oct 2001 10:36:02 GMT
Newsgroups: comp.lang.lisp
Message-ID: <3211612557359956@naggum.net>

* Thomas F. Burdick
| Oh, come on.  Imagine it's pre-ANSI CL and he's asking for an object
| system to be included in the standard.

  Oh, come on.  We are simply not in that position, anymore.

| It would be very nice to have some *portable* way of ensuring that (1)
| certain important tail-calls are eliminated; or (2) an error is raised.

  I keep rewriting it "tail-call merging" because I think _elimination_ is
  just plain wrong terminology.  Is that just me?

  What you seem to want is a portable way to query a function at the source
  level for the ability of all compilers to unwind its call stack to the
  point where it can redirect a particular function call to return to its
  caller.  What I keep arguing is that this requires a large set of other
  requirements that are simply not in the Common Lisp spirit.  The various
  conditions under which you can actually get tail-call merging in today's
  implementations of Common Lisp are what they are because of the freedom
  of these implementations to do their work in various smart ways.  If you
  _require_ a specific set of tail-call merging conditions, you will also
  mandate a particular set of implementation techniques for function calls
  of _all_ kinds, and you may actually find that a particular vendor is
  unable to comply with the new standard because function calls in Common
  Lisp are incredibly hairy things at the machine level, especially when
  you take CLOS into consideration.  [I have had the good fortune to work
  with Duane Rettig's code in Allegro CL, and I am quite simply in _awe_ of
  the attention to detail and efficiency and the cleverness of both the
  code transformations and the resulting machine code on such a weird and
  varied bunch of hardware archictures.  My own training and set of skills
  predisposes me towards strong hesitation towards the kinds of claims that
  Scheme makes, and I have studied Scheme implementations sufficiently to
  understand how this "properly tail-recursive" requirement has serious
  repercussions for the design and implementation of the whole language.]

| This is obviously something the vendors thought their user base wanted:
| CMUCL, CLISP, ECLS, Allegro, LispWorks, and MCL all have some form of
| tail-call elimination.  This sounds to me like a good candidate for
| standardization.

  It may indeed sound like that until you look beneath the hood and see how
  _differently_ they need to implement this seemingly simple concept
  because of their other design choices in implementing the function call.

  Contrary to popular belief in certain circles, it is not _sufficient_ to
  specify something in a standard to actually get it.  My own struggles
  with trusting people who claim publicly to be in favor of the standard
  while they sneer at it and ridicule it in private communication cause me
  to believe that if you require something that people are only politically
  motivated to back, they will find ways to implement it that are not worth
  much to you.  It is somewhat like implementing a relational database with
  SQL "support" that does not _actually_ support transactions and rollback,
  like MySQL, because of "efficiency" reasons.  This is fine as long as I
  do not need it, but the day I do, I may have to invest serious effort in
  recoding my application and move to a real relational database.  Now, why
  do people not implement something that is so fundamental to the task at
  hand to begin with?  Misguided ideas of their ability to judge the
  appropriateness of standard requirements is most often to blame, but
  irrational personal hangups can be just as powerful -- the upper-case
  nature of Common Lisp symbols is one of them, where one vendor argues
  strongly for a "modern" mode in lower-case, but does _not_ default the
  case-insensitive argument to their apropos to true so their users can at
  least give lower-case strings to apropos, and neither do they offer a way
  to use modern and standard mode side-by-side, which would have made it so
  much easier to experiment with modern mode.  This kind of "anti-standard
  attitude problem" is not at all specific to our community -- I have
  worked with standards of many kinds for 15 years and every single one of
  the areas were I have experience, there has been rogue vendors who think
  they know better or (more often than not) who simply fail to care enough
  to understand what they are doing.  Microsoft is the archetypical enemy
  of specifications because they have this holy mission of supporting what
  they claim are "customer needs", one such need being trust in conformance
  obviously ignored.

| > | (Another thing I would like to see are stronger guarantees about what
| > | conditions are signalled in exceptional situations; again, I do not have
| > | problems with my vendor here, as I can always test my implementation's
| > | behaviour, but with the standard itself.)
| > 
| >   What do these stronger guarantees actually entail?  Is it the ability to
| >   sue vendors if they decide to claim to purport to conform to a voluntary
| >   standard?  If so, nobody will volunteer to conform to it.
| 
| Uhm, I'm pretty sure he meant changing the wording to say that certain
| conditions *will* be signalled in certain situations, instead of
| *may*.  I see no reason why this would be an unreasonable request for
| a future version of the standard.  Perhaps it wouldn't make it in, but
| it sounds like a normal user request for portability.

  Sigh.  If you write something down in a law or a specification, you need
  a way to enforce it.  How do you envision that you would enforce the
  "guarantees" that you have gotten rolled into in the standard if you do?
  The unreasonability of the whole desire to see tail-call merging required
  is that the consequences of such a requirement leads to enforceability
  issues that I for one do not welcome at all.  It is just like bad law --
  it has the _sole_ effect of making people ignore and break less bad laws.

///
-- 
  My hero, George W. Bush, has taught me how to deal with people.  "Make no
  mistake", he has said about 2500 times in the past three weeks, and those
  who make mistakes now feel his infinite wrath, or was that enduring care?