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?