Juliusz Chroboczek wrote: > JS> If you run your (loop) example on a laptop running on batteries > JS> you will see in not so long time that even (loop) is doomed to > JS> "terminate" because some resource is exhausted.
> I see. It's actually useless to try to write reliable programs, > because my machine might very well run out of batteries.
t...@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> 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.
Depends on a case by case basis. Every requirement to signal is a requirement to check. Every requirement to check is time lost not doing the application. In an application where data is already correct, such time is wasted. It is between the application writer and the vendor how much pre-testing has been done and how much is needed at runtime.
IMO, one of the coolest and strangest features of CL, is the manner in which its declarations are treated. They are "promises to have done right". They can sometimes be checked (as CMU CL has shown) but they sometimes cannot be. In most languages with declarations, declarations that can't be checked are failures rather than treating the programmer as an "oracle" who can tell the compiler things it might not be able to infer. Taking away this ability in favor of requirements to assure these truth has the potential effect of slowing the language down in places where you could have told the program a truth that proving would either be hard to do at compile time or expensive to do at runtime.
> Perhaps it wouldn't make it in, but > it sounds like a normal user request for portability.
And it sounded like a normal reaction of another member of the community to one person's seemingly trivial suggestion. Steele came to the first meeting of the CL committee post-CLTL (it was in 1986 in Monterrey, I believe) with a page full of "trivial" corrections he thought sure everyone would just rubber stamp. He was amazed to find that, in constrast to the willingness of a community pre-publication who had no investment in their implementation or user-code to accept new ideas, it was suddenly much harder to get change. New people had arrived on the scene with different points of view. People had started to invest in a particular point of view. etc. In the end, we accepted none of his trivial changes and in fact realized from that meeting that something formalized like ANSI would be needed (we weren't sure what the mechanism was, but we knew "friendly consensus" would no longer cut it) to move forward from there, since there were irresolvable divides afoot...
* Juliusz Chroboczek <j...@pps.jussieu.fr> | JS> If you run your (loop) example on a laptop running on batteries | JS> you will see in not so long time that even (loop) is doomed to | JS> "terminate" because some resource is exhausted. | | I see. It's actually useless to try to write reliable programs, | because my machine might very well run out of batteries.
Juliusz, I find your approach in this thread to be irrational, and I suspect that it has some philosophical underpinnings that I cannot quite get a grip on. You have removed the real world from your reasoning, and when people reintroduce it, they fall apart like they depend on a reality different from what is normally experienced. There is something wrong with a philosophy when that happens. In this case, your probably half- facetious response betrays, I think, a failure to differentiate between the normal and the exceptional. This is akin to what we find in politics when people make no distinction between normal and emergency ethics -- under normal circumstances, no person's life is in danger and endangering a person's life is wrong, but in an emergency, a person's life is in danger and it may be ethical to endanger another person's life, such as the attacker of the first person. If you attempt to apply normal ethics to the emergency situation, you _will_ endanger someone's life and that is wrong whichever way you look at it, so there is no right answer, anymore, meaning your ethics has failed, but you cannot argue that your normal ethics has failed across the board -- it has only failed in an emergency. Likewise with software: If your theory assumes a normal course of execution and termination, the theory _fails_ if apply it to exceptional termination, but that does not mean the theory is wrong apart from being abused for exceptional situations.
This issue is of course getting more complex in software where the normal course of execution includes a large number of exceptional situations, but running out of resources is clearly such an emergency that no theory of reliable _software_ can deal with it. The hardware exists. It cannot be abstracted away while the theories are still expected to have their usual predictive power. Regardless of how reliable your software is, if you are running it on a laptop computer in, say, Kabul, it just becomes so incredibly stupid to argue that the _software_ failed if the hardware evaporates and that it is useless to write reliable software when it might as well blow up on you, literally. On the other hand, we do have people from vendors in this newsgroup who argue that just because you need sockets, which are not standardized, you might as well disobey some other parts of the standard because the standard is not perfect in its power to encompass the needs of the world. I think it is the same bogus ideas that underlie the attitude to perfection and normalcy of both of you guys, that if you define a perfection that is inherently unattainable and impossible, you can go on griping about irrelevant flaws forever.
As far as I can tell, Common Lisp is good enough that it attracts people who can make up a desire for an irrationally perfect world and thus never actually be satisfied with what they are able to get in any real life. For instance, you will never get a guarantee for tail-call merging in the standard, and it is _completely_ useless to ask for it or even pretend that you can get more than actual support for what you want from vendors. The standard is not at fault for not giving you the irrationally perfect.
/// -- 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?
* Juliusz Chroboczek <j...@pps.jussieu.fr> | I, on the other hand, want to use CL (which I happen to find more | comfortable than Scheme) and still require that tail-call elimination | should be performed in some circumstances.
But you are not satisfied with it being done when you ask for it. You seem to think that if it is required in the standard, you will also be "guaranteed" to actually get it from your vendors, but it is the other way around. There are still lots of things that the standard mandates that people are not implementing exactly the same way. Like directory, which we saw just recently. However, instead of arguing for how it should be implemented and finding ways to get this, people get agitated to the point of looking like they are _betrayed_ because the standard is not sufficiently clear, as if it owed them that. I find this very odd, but it _is_ also something that happens again and again in this forum.
| With recursion (possibly indirect), tail-call elimination will, under the | right circumstances, convert unbounded space usage into constant space. | With some programming techniques, this means turning a guaranteed crash | into a reliable program.
If so, why is it not sufficiently to actually get what you want? Why do you have to have a "guarantee" to get it via the standard? Do you think you will pay less for it if people "had" to do it than if you ask for it?
/// -- 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?
Juliusz Chroboczek wrote: > JS> If you run your (loop) example on a laptop running on batteries > JS> you will see in not so long time that even (loop) is doomed to > JS> "terminate" because some resource is exhausted.
> I see. It's actually useless to try to write reliable programs, > because my machine might very well run out of batteries.
The interesting thing is what you do to make it useful again: you buy a laptop with longer runtime and you ensure that you load the batteries before all goes down. All this things are in no way standard in Scheme but it seems to work in reality. So why should it be a problem to ensure using a CL that supports tail-calls?
> 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. 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.
I think that the pro-tail-call-elimination-in-the-standard people should come up with a description, in language suitable for a standard of just what it is they want.
Judging by the experience of Scheme, where, despite Scheme being a much simpler language than CL from the point of view of tail-call-elimination, it has taken a *long* time to tie down what is meant by the requirement (witness article <m3ite0zzlc....@localhost.localdomain> in this thread), and it may actually not be tied down yet, I'm not sure.
In order for a CL *standard* to mandate tail-call-elimination in a way that is actually useful to programmers using the language it has to be described in a fairly precise way, and I haven't seen such a precise description in this thread, while I *have* seen a number of arguments from the anti-tail-call-elimination-in-the-standard people that such a precise description might be very hard. Rather we've had a lot of vague handwaving as the above quote (I'm not trying to pick on this article or its author in particular, it was just the closest to hand).
So I think it behooves the PTCEITS people to come up with a form of wording which is precise enough that it is suitable for use in a standard. At that point this whole discussion might have more purpose.
* 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?
EN> However, instead of arguing for how it should be implemented and EN> finding ways to get this, people get agitated to the point of EN> looking like they are _betrayed_ because the standard is not EN> sufficiently clear, as if it owed them that.
I don't think that's a fair assessment. Unlike some other languages, Common Lisp is specified with enough rigour to make it possible to write real code to the spec. I have found that the only cases when I consciously wrote non-portable Common Lisp code were either when I was writing intrinsically platform-dependent stuff, or when relying on the tail-call elimination behaviour of the implementation that I use.
In the light of the above, I think it is only natural to want to attract the community's attention to this issue.
KMP> It is specifically left to the market to sort out ...
[...]
KMP> This is not an argument. It is, to the best of understanding, a fact.
Okay, I read you now. You were not arguing why this sort of thing should not get into a hypothetical future standard, but why it didn't get in.
KMP> Two major points follow. If you find yourself hopelessly mired in the KMP> first [....]
Actually, your first point makes a lot of sense. I think I understand why X3J13 was not the right time to push tail-call elimination: it's very difficult to specify right (and you didn't have a lot of manpo- wer), and may require reengineering of already present functionality on the part of vendors. These seem like excellent reasons to me.
I am glad that you should agree that tail-call elimination is some- thing that deserves at least serious consideration (I hope I am not abusively putting words into your mouth here). Please count me as a happy CL user that would be even happier with guarantees about tail-call elimination. As Thomas Burdick noted, the fact that most current CL implementations do perform tail-call elimination in some form seems to indicate that I am not alone in this situation.
EN> Juliusz, I find your approach in this thread to be irrational, EN> and I suspect that it has some philosophical underpinnings that EN> I cannot quite get a grip on.
Okay, I'll try to make my ``philosophical underpinnings'' explicit.
One of the early proponents of rigour in the discipline of programming was Edsger W. Dijkstra. Together with Hoare and other people, Dijkstra developed a number of more or less formal techniques to aid in the writing of reliable software. (An important point to understand is that a formal technique is often useful in an informal setting: for instance, while Dijkstra introduced the notions of loop invariant and weakest precondition in a formal framework, most good programmers use them to reason informally about their programs.)
In one of his notes, Dijkstra mentions that when presenting his ideas, he sometimes met the objection ``but what if the compiler (resp. the hardware) is unreliable?''. Dijkstra argued (and I fully agree with this point) that this is immaterial to the argument at hand, and that the person asking this question had completely missed the point. The fact that we use compilers with bugs, hardware that breaks at random points, or power companies that arbitrarily decide that darkness is the norm does not make the task to write reliable software any less meritoric.
Similarly, I would argue that the fact that no Common Lisp implemen- tation fully conforms to the standard, or that my Common Lisp imple- mentation runs on hardware that may very well not survive the day (touch wood) does not make the task of writing a rigorous and precise specification for the language vain. The existence of the Common Lisp standard, which I regard as a brilliant example of how it is possible to be intelectually rigorous without relying on formal tools, seems to imply that at least part of the Common Lisp community shares this view.
>> | (Another thing I would like to see are stronger guarantees about what >> | conditions are signalled in exceptional situations;
>> What do these stronger guarantees actually entail?
TB> Uhm, I'm pretty sure he meant changing the wording to say that certain TB> conditions *will* be signalled in certain situations, instead of TB> *may*.
I was actually being much more modest, and thinking of changing a number of requirements that ``an error is signalled[1]'' to a precise specification of which proper subclass of ERROR should be signalled. I have sometimes found myself establishing handlers for ERROR in distributed code, which always makes me nervous, and in my personal opinion should never be necessary.
(As far as I can tell, there should be no cost associated to such a change other than the presence of a few extra condition classes in the Lisp runtime. In addition, I would like to mention that I do fully realise that the current wording does allow implementations to signal a more precise condition than ERROR -- but I hope you'll agree that this is of little comfort to portable code.)
A case in point is that of DESTRUCTURING-BIND, which in its current state requires handling ERROR whenever applying it to data that has not been pre-validated -- in which case I usually end up doing the destructuring by hand instead.
When I complained about that (IMHO) misdesign a few years ago on this respectable forum, Kent replied that X3J13 didn't have enough manpower to specify the exceptional situations more precisely. I fully accept this point, which I hope is clear from the wording I've used.
Juliusz Chroboczek <j...@pps.jussieu.fr> wrote: > On the other hand, consider the following:
> (defun foo () > (foo))
> and suppose that you compile FOO without tail-call elimination. Does > FOO terminate? [...] > The point I'm trying to make is that FOO terminates when compiled > without tail call elimination, and that FOO does not terminate if > compiled with tail call elimination. Thus, tail call elimination is > not a mere optimisation, but a semantic feature.
Have you considered the possibility of call frames allocated in the heap and being garbage-collectable? In that case the tail-call merging of the tail self-calls is *only* an optimization that saves you a trouble of allocating new call frame and gc'ing the previous one sometime later when gc is ran.
I think this was actually done for some functional programming language (istr it was TIM (three instruction machine), but I just don't remember...).
* Juliusz Chroboczek <j...@pps.jussieu.fr> | The existence of the Common Lisp standard, which I regard as a brilliant | example of how it is possible to be intelectually rigorous without | relying on formal tools, seems to imply that at least part of the Common | Lisp community shares this view.
I wonder if anyone does _not_ share it. Seriously. The resistance to "formal tools" is, however, pretty strong among those who have studied Scheme well and are sick and tired of completely fruitless formalisms that turn into huge implementation costs or restrictions on the freedom of the implementors. If there is one lesson one learns from having dealt with many language specifications, it is that overspecifying is far worse than underspecifying.
It seems to me that you are fighting an enemy that does not exist when you argue as if there are people who do not share what you have written and it seems pretty arrogant that yours is the only way to express or desire the values and results of "rigor". I actually think _everybody_ here are sufficiently well educated that you should presume that their objections to "formalism" is to their application, not the principles. Thus, it does not help to argue for the principles when peple are opposed to their application. Quite the contrary, arguing for the principles when the application is challenged only makes people more hostile to the application, because it implies that you think the principles are not understood unless they are agreed to be applied just your way.
I also think what Tim Bradshaw said here is very relevant: As long as you only ask for something that meet objections, there will be no progress. Write up an _exact_ proposal for what you want the community to agree to, and you might actually find people able to accomodate you, but if you only demand something that people have serious objections to, there is no way anyone can figure out what you are _really_ after, i.e., what you would be happy if you got. In general, if people cannot figure out when your complaints will end, you lose credibility fast, as it is essentially indistinguishable from an attitude problem.
/// -- 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?
Juliusz Chroboczek <j...@pps.jussieu.fr> writes: > >> | (Another thing I would like to see are stronger guarantees about what > >> | conditions are signalled in exceptional situations;
> >> What do these stronger guarantees actually entail?
> TB> Uhm, I'm pretty sure he meant changing the wording to say that certain > TB> conditions *will* be signalled in certain situations, instead of > TB> *may*.
> I was actually being much more modest, and thinking of changing a > number of requirements that ``an error is signalled[1]'' to a precise > specification of which proper subclass of ERROR should be signalled.
Oh, this is a lot more complex than you imagine. It's not that we don't understand your need, it's that it's very tricky for the language to specify this (and involved more personpower than we had available to do even specificationally, not even worrying about the burden it imposes on implementors).
> I have sometimes found myself establishing handlers for ERROR in > distributed code, which always makes me nervous, and in my personal > opinion should never be necessary.
People do understand this issue, but...
Let's work historically to show you how it came to be as it is.
First there was the non-typed condition system. ERROR had a message. ERRSET trapped things. "Sophisticated" systems could see the error message in limited cases and on the basis of the string could do certain very specialized actions.
Then there was the Symbolics "New Error System" (NES) [based on long experience with Multics PL/1 condition system] allowing object-oriented error handling, separating the "error kind" from the message. The very first roll-out was hugely detailed with a tree of error classes.
I did the "port" of NES to a proposal I felt was appropriate to CL. In so doing, I asked Dave Moon at Symbolics what depth of the error class tree I thought we should include in CL. He said that if he had it to do over (which is effectively what CL was, a doing over), he would not specify nearly as many classes.
He observed first that it isn't clear that it's good style, for example, for people to be making decisions on the basis of "unseen go tag" vs "unseen catch tag"; programs relying on this level of detail have serious style/design problems beyond the actual error that is manifesting. So we did some cutbacks based on what we thought reasonable programs should do, and I think those cutbacks were well-advised. I will defend those cutbacks to this day, and I think even you and others who want more elaboration would agree.
There is a second class where it would be better style to have a bit more elaboration. An example might be "file not found" and "directory not found" instead of just "file error". I don't doubt this would be radically useful.
In the historical context, these were not added for two reasons. One was that CLOS was new and untrusted, and it was a design constraint which youc an see if you look that none of the system have multiple inheritance in primitive types (so we could back out of multiple inheritance if it was a disaster, which some (mostly those who had never used it or who had stock hardware and worried the performance would not be as good as lisp-specialized hardware) felt was an essential option to keep open). (I believe the only exceptions are type NULL, which is handled in some bizarre primitive way by all systems, and the types SIMPLE-CONDITION, SIMPLE-ERROR, etc. which are specified in a way that you might think had to involve multiple inheritance because you have used a reasonable language that allowed this, but that actually can be done by stupid other ways like Java does (replicating functionality, etc.) to cover for lack of multiple inheritance, where that happens in an implementation.) Anyway, the second reason was somewhat independent, but had some bad play-in from the single-inheritance restriction: we couldn't agree on the type tree because it would be different for different vendors. (And, related to this, even if we could, it might bind us to a particular implementation that we later decided we needed to grow out of. You'll see how that plays out in my example below.)
Consider something like directory-not-found. In something like LispWorks or Allegro, I believe the Lisp file system can only open the local file system. Well, maybe except for NFS, so the issue probably still comes up. Anyway, mostly when you do OPEN a file is either there or it is not. Same with a directory. But the only "current practice" we had was the Lisp Machine, and its model was more elaborate. OPEN could open any file on the internet by saying (open "hostname:filename"). [You could manipulate independently what protocols, network paths, etc. were used to get to that hostname, so you might be using FTP to one host while using TFTP or SNA or something to another host.] But a file not found might be temporary (host down or not responding) or permanent (i got to the host but it says there's no file there). It might be a network problem or not. We couldn't easily make DIRECTORY-NOT-FOUND a subclass of NETWORK-ERROR, nor could be make it not a subclass of NETWORK-ERROR. We could have left the classes free-floating but that could have led to other confusions we hoped to avoid, making it hard to order the cases correctly when discriminating several error types, for example.
We ultimately decided to leave this area blank and to see what error classes ended up springing up and then try to repair the language later by adding specificity based on experience.
We did not know at the time that there would not be a near-term "later" and might never be a "later".
When we got done doing the standard, it had cost a lot of money to make and even more in the community to adopt (change code to be ANSI compliant). It cost just shy of a half million in salaries to produce, and I'm sure at least as much to adopt. That's money not spent producing product. We met after 5 years to see whether we should open the standard for change or just leave it laying, and the result was that it was thought to be not broken enough to be worth the risk/cost of tinkering. Yes, there are things people would want to change and this probably among them.
Here I won't use the "we wanted to leave it to the marketplace" argument but rather the "we were willing to leave it to the marketplace" argument. :-) That's less strong, I think all would agree. With multiple inheritance firmly in place, I'm confident that if the spec were open to tinkering, we could fix this. But opening to tinkering might break 180 other things that you didn't want broken, too, because democratic organizations are strange and often vote in things that are inconsistent with any single member's world view. Democracy optimizes worst case design better than it optimizes best case design, which it really doesn't address at all.
So you've got what you've got for the nearterm and that's pretty much that.
Personally, I think the right thing is to have community consensus and I wish the ALU would play a bigger role in that. Properly acting as a block, users could probably get some vendors to take note. Vendors don't want to make a random change for a random user whose personal sense of order is offended by what they offer, but if they had reasonable confidence they were talking to a group that represented enough users that they could make a change once and then stand by it as "what the community wanted", ESPECIALLY if, as here, it was a compatible change and did not disturb the spec, I think they would probably do it. Certainly there'd be a better chance.
I hope that helps you understand and accept the status quo as the best that could have been done then, and still for different reasons close to the best we can do now, modulo the question of whether smaller layered standards or just "conventions" could help. That last is still an open question, but numerous attempts by various people to make progress in this area have failed, so it's not like it hasn't been tried. Ultimately, people speak with their wallets as to what they really need, and I sense most people would rather write a few #+/#- conditionals than spend real dollars trying to solve this issue in an aesthetic way. They may be just saying they have better uses for their money in this struggling economy, and speaking practically, I can't really say 100% that that's a bad thing... CL is and always has been a language that caters to pragmatic folks.
Juliusz Chroboczek <j...@pps.jussieu.fr> writes: > I am glad that you should agree that tail-call elimination is some- > thing that deserves at least serious consideration (I hope I am not > abusively putting words into your mouth here).
No, that's fine. But see my other post of just a few moments ago on the issue of specializing condition types, where I discuss the problem that the community doesn't have a forum right now to consider such changes, and doesn't seem likely to.
I'm not an official representative of any committee, btw. Even when I was I couldn't speak for them. (X3)J13 speaks through its votes, not through a publicist. Members always just express their own opinions, nothing more. I've resigned my membership of the committee because I think it's done as much as it can do and I now support "other ways of moving ahead". The committee still exists, though, and it may or may not have another agenda--I don't know. Maybe Steve Haflich of Franz, who was chair of it last I heard, will join in with some remarks on what the status of the committee's work or non-work is. I'd heard some rumor of a vote to put the committee into official hibernation, but I don't know if that vote was taken or, if so, what the outcome might have been.
Juliusz Chroboczek <j...@pps.jussieu.fr> writes: > Similarly, I would argue that the fact that no Common Lisp implemen- > tation fully conforms to the standard,
The standard does not require that you don't have a resource problem. Conformance is straightforward.
On Tue, 09 Oct 2001 10:36:02 GMT, Erik Naggum <e...@naggum.net> wrote: > I keep rewriting it "tail-call merging" because I think _elimination_ is > just plain wrong terminology. Is that just me?
I had actually never thought much about it. But now that you point this out, "merging" seems more appropriate than "elimination".
> 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.
Maybe one of the reasons why the implementation of tail-call merging looks simple comes from the influence of textbook examples. A non-merging Scheme interpreter/compiler is often illustrated, and then changing a bunch of lines of code turns it into a merging one. For the toy examples discussed in books this is indeed simple.
j...@itasoftware.com wrote in message <news:r8swadq7.fsf@itasoftware.com>... > Normal order semantics are unreasonable? First I've heard of that.
You hang out in the wrong bars.
Normal order semantics has nice properties for certain kinds of analysis on certain kinds of programs. However, it's hard to keep those properties and write certain kinds of programs in a "natural" way. Since more people are interested in those programs than in those properties....
Normal order semantics also has a distinct lack of locality. That's "inefficient" for machines (which is not a big issue) and inefficient for humans (which is a HUGE issue).
I like to play with myself as much as the next guy, but the formal language community's mathturbating has gotten the rest of us C, C++, and Java. The popularity of those languages is not irrational - they, and their implementations, are better at what most users need than "good" languages; that superiority is the fault of the designers of "good" languages.
On Tue, 09 Oct 2001 21:17:46 +0100, Paolo Amoroso <amor...@mclink.it> wrote: >On Tue, 09 Oct 2001 10:36:02 GMT, Erik Naggum <e...@naggum.net> wrote:
>> 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.
>Maybe one of the reasons why the implementation of tail-call merging looks >simple comes from the influence of textbook examples. A non-merging Scheme >interpreter/compiler is often illustrated, and then changing a bunch of >lines of code turns it into a merging one. For the toy examples discussed >in books this is indeed simple.
These are very good points. I can't tell you how many times I have read that tail call elimination is trivial and any decent implementation will do it all the time--only to struggle with it and tear my hair out trying to implement it.
Problems I have run into, most recently with Corman Lisp. (I had earlier implemented a version in PowerLisp that occasionally generated the wrong code, and ended up taking it out).
In Corman Lisp, I made design decisions to use C-like calling conventions. This has some advantages over alternatives. As well as some disadvantages. In order to eliminate all tail calls, the function needs to generate code which will tear down the current stack frame, push the new arguments on the stack, and branch. However, once the frame is gone, it is not possible to evaluate the arguments any more. And if you evaluate them first, then you need to store them somewhere as you create them, but then you have to shuffle them around when you are done. And, in Corman Lisp, the garbage collector can happen any time (on another thread, for instance) and the stack needs to be in a reasonable looking state when it does. Shuffling of items on the top of the stack is messy, and it might actually be less efficient than just using a normal call.
The stack is so large, and only rarely do you ever run out of stack space--if you keep in mind how recursion works and use it appropriately.
I ended up implementing what I think is a half-way version in Corman Lisp. It optimizes recursive tail calls, in a way that is very efficient, but only in functions which have a fixed number of arguments. In this case, you don't have to tear down and rebuild the stack frame, and you just overwrite the existing arguments, giving the biggest bang for the buck. In addition, it is mostly done at the source level, using GO to restart the function, making code generation simple and not error-prone. I added some special compiler macros to overwrite the arguments, bypassing any inner scope variables that might have the same name.
This only works to call recursively however. If you try to call another function, keeping the same frame, it may take a different number of arguments or require a different sized stack frame. Even if these are the same at compile time, the called function can always be redefined to take a different number of parameters or a different sized frame.
I know there are probably some tricks I haven't thought of, but my point here is that, as Eric said, many design decisions are made, and some compromises are made, when implementing a compiler. I don't believe the problems of implementing full tail call merging are sufficient to forsake the function calling mechanism in this case. I am glad that tail call merging is an implementation decision and not a mandate of the standard. For heaven's sake, the standard doesn't even require a garbage collector. If an implementor designs a system that doesn't provide sufficient resources to use, then it won't get much use.
Interestingly, I have never had one user complain to me about the lack of tail recursion elimination (I only implemented it a couple months ago). Without the tail call elimination, a simple function can make >80,000 recursive calls before hitting the stack limit.
ana...@earthlink.net (Andy Freeman) writes: > j...@itasoftware.com wrote in message <news:r8swadq7.fsf@itasoftware.com>... > > Normal order semantics are unreasonable? First I've heard of that.
> You hang out in the wrong bars.
I suspected as much. Where do the hot babes who hack lisp hang out?
> Normal order semantics has nice properties for certain kinds of > analysis on certain kinds of programs. However, it's hard to > keep those properties and write certain kinds of programs in a > "natural" way. Since more people are interested in those programs > than in those properties....
Agreed, but that doesn't make the semantics unreasonable, just impractical. (And note that every applicative order language has a few normal-order constructs in it.)
As a followup, people who are interested in the debate over preserving termination characteristics when compiling might want to read these papers:
@inproceedings{ rozas169695taming, author = "Guillermo Juan Rozas", title = "Taming the {Y} operator", pages = "226--234", url = "citeseer.nj.nec.com/169695.html" }
@inproceedings{ weise91automatic, author = "D. Weise and R. Conybeare and E. Ruf and S. Seligman", title = "Automatic Online Partial Evaluation", booktitle = "Functional Programming Languages and Computer Architecture, Cambridge, Massachusetts, August 1991 (Lecture Notes in Computer Science, vol. 523)", publisher = "Berlin:\ Springer-Verlag", editor = "J. Hughes", pages = "165--191", year = "1991"
}
@misc{ mulmuley87full, author = "K. Mulmuley", title = "Full Abstraction and Semantic Equivalence", text = "K. Mulmuley. Full Abstraction and Semantic Equivalence. MIT Press, 1987.", year = "1987" }
Tim Bradshaw <t...@cley.com> writes: > * Thomas F Burdick wrote: > > 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. 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.
> I think that the pro-tail-call-elimination-in-the-standard people > should come up with a description, in language suitable for a standard > of just what it is they want.
That's not a bad idea.
> Judging by the experience of Scheme, where, despite Scheme being a > much simpler language than CL from the point of view of > tail-call-elimination, it has taken a *long* time to tie down what is > meant by the requirement (witness article > <m3ite0zzlc....@localhost.localdomain> in this thread), and it may > actually not be tied down yet, I'm not sure.
But Scheme claims to be "properly tail recursive", which is not something that I, for one, am advocating. I'd just like some portable way of requesting tail-call merging, and of finding out if it was accomplished. These are *very* different goals.
t...@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> But Scheme claims to be "properly tail recursive", which is not > something that I, for one, am advocating. I'd just like some portable > way of requesting tail-call merging, and of finding out if it was > accomplished. These are *very* different goals.
It depends on your purpose. Some people want to do things like:
Merely "requesting" merging is not going to make this a correct program, even with 80,000 stack being ok (as Corman says he can do), if upto is given initially as most-positive-fixnum.
In one of the first meetings of ANSI CL standardization, we (X3J13) wrote a charter. One goal was "establish normative Common Lisp programming practice." See http://world.std.com/~pitman/CL/x3j13-86-020.html for context.
We first agreed this was a good phrase and then talked for a while about what it might mean. :-) Someone (my memory says it was McCarthy, actually, who came to some of the first meetings, but I'm not 100% sure), suggested that it meant that we would try not to include things that encouraged people to do stuff they shouldn't.
Curiously, one cited example of that in the discussion was the inclusion of APPEND, though we decided to include it anyway. But as I recall it was used to illustrate the point that we don't want people calling APPEND all the time because it will encourage people to write O(n^2) programs where O(n) programs are better written either by CONS+NREVERSE paradigms or by something similar hidden in functionality/macrology such as LOOP.
I guess the idea was not just to say "this is what this operator does" but to also give some guidance about where it was and was not good to use it.
In Structure and Interpretation of Computer Programs (S&ICP), which is the approximate equivalent in the Scheme world to CLTL in our world, in terms of user reverence anyway, tail recursion is presented as, at minimum, "just another way to write a loop"... it's ALMOST presented as if "writing a loop is buggy unless you express it this way". A whole virtual religion has been spawned on the worship of the tail recursive call as a mechanism for iterating.
But in CLTL, the fact is that it is simply NOT a synonym for looping because looping has a well-defined storage usage and tail calling does not. Specifying that you WANT it to be otherwise does not change the fact. There are reliable ways to write loops, and tail recursion is not one of them in either present-day CL or in a CL where you can request this without being told the request will be granted.
It would work to have the request include programmer supplied information that could distinguish between "necessary" and "optional" as we have discussed for an optimize setting where (OPTIMIZE (TAIL-CALLS 3)) would mean "must have", (OPTIMIZE (TAIL-CALLS 0)) would mean "must not have", and anywhere in between would mean "optional". It's not like DYNAMIC-EXTENT where it's safe to ignore; it's more like SAFETY where if the programmer makes the request and the implementation can't oblige him/her, the implementation must signal an error rather than just do the wrong thing.
(Maybe this is what you meant by "and finding out if it was accomplished". But doing a request and not having it imperatively stop the program if it failed would be more like C (with error codes you can forget to check). The style of CL is to signal errors actively, not passively, so that the default is that if you fail to arrange to handle something, you know an error has not been detected because it would have been signaled if it HAD been detected.)
Erik Naggum <e...@naggum.net> writes: > * 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.
That's not much of an argument against the analogy.
> | 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?
You're right; I usually say "tail-call optimization", which I think is fine terminology, but I do think "merging" is better.
> 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.
Yes. In other words: "I want this tail call merged; tell me if you cannot do that".
> 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,
But that's not what I'm proposing.
> 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.
Sure they can. If a requested tail-call merge can't be performed, raise a condition.
> [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.]
I would not want to argue for making CL "properly tail-recursive"
> | 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.
Once again, I'm not proposing that CL become "properly tail-recursive" nor that we mandate the conditions under which tail-call merging occurs. Nor am I proposing something that would require a massive change to implement (I don't think).
> Contrary to popular belief in certain circles, it is not _sufficient_ to > specify something in a standard to actually get it.
Of course it's not. And people will sometimes claim to conform to standards they don't; that doesn't make standards worthless.
> 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?
You're right. The entire CL standard is worthless. Not only should we not think about what we'd like in a future standard, we should throw the whole thing we have now, out. Because, after all, how to we enforce it?
> But Scheme claims to be "properly tail recursive", which is not > something that I, for one, am advocating. I'd just like some portable > way of requesting tail-call merging, and of finding out if it was > accomplished. These are *very* different goals.
Well, come up with a design, and publish it. Probably the best group of people to ask if it is reasonable are implementors right now, since they'll bear all the cost of it (well, they'll pass it on in license fees of course). You should also probably start of with at least one non-trivial implementation (by `non-trivial' I mean one that doesn't answer `don't know' in all cases). If you can tie it down precisely, get vendors to agree to implement it and users like it, you're basically done. Duane Rettig's simple streams specification and implementation is an example of how to do this reasonably well, I think (although I'm not sure the simple streams spec is `standards quality' yet - I haven't read it recently - and it may be the case that it's hard to implement in other CLs).
* Thomas F. Burdick | That's not much of an argument against the analogy.
That someone can imagine something does not make it an analogy worth arguing against. It is incumbent on the analogy-producer to cough up something worth considering. Lacking that, _you_ have no argument, and it is counterproductive and _indecent_ to pretend that someone who rejects your analogy is at fault for doing so, and I do not generally reward silliness.
| Yes. In other words: "I want this tail call merged; tell me if you | cannot do that".
So we can get that today by defining something that always yields a warning or even error that it cannot tail-merge the call. That seems like _such_ a great thing to add to the standard! The moment you go beyond this silliness, however, you run into problems. I second Tim Bradshaw's request that you (or that formal theory dude) actually come up with something that can be subjected to careful scrutiny. As long as you only "want" something and make up silly imaginary analogies, there is absolutely no reason to believe that you _understand_ what you want.
| If a requested tail-call merge can't be performed, raise a condition.
At compile-time? Should the interpreter raise a condition, too?
| You're right. The entire CL standard is worthless.
Please turn your brain back on.
| Not only should we not think about what we'd like in a future standard, | we should throw the whole thing we have now, out. Because, after all, | how to we enforce it?
If you fail to appreciate that standards are specifications and tha clauses in standards are requirements, I can certainly fully understand why you "want" useless tail-call merging-requesting special forms and have no idea what you are embarking on.
Some astonishingly unintelligent politicians always suggest "good ideas" that cannot be enforced, in the fantastically irrational belief that people will sort of follow the spirit of the law when nothing bad happens to those who do not, and the actually believe that a law is the proper place to make feeble suggestions about people's "good behavior". Every now and then, this feeble-minded moralism passing for law-making is not obvious to sufficiently many politicians in time to avoid embarrassing laws to pass. If you do not understand that if you write it into law, there _will_ be a court of law facing those who disobey it and you _will_ impose punishment on those who "disagree" with you, you should not be messing with laws in the first place. The same goes for standards, although we have weaker means of dealing with the criminally-minded (i.e, those who believe themselves elevated far above the community consensus and not at all bound by its decisions) in our community than in the legal and law enforcement community. However, do not expect that those who profess a criminal mind's arrogance towards community consensus to be treated nicely. When you are in fact trying to change the community consensus through a change to a specification that requires and survives _only_ because it has the respect of law-abiding citizens, the people who will most likely be affected by an undesirable change are those who want to fuel their arrogance towards the specification. You have to recognize that some people in our community already harbor _massively_ irrational arrogance towards the standard and go out of their way to publish code that actively diminishes the value of adhering to the standard where the standard has spoken. These are people who are so hell-bent on their own views that _they_ know better than the whole community consensus, that it has no merit whatsoever to respect those who desire a community consensus over some personal likes and dislikes. Search for "religious zealot" in the archives of this newsgroup if you need to find a person who has shown us that opening up the standard to changes will be _very_ dangerous and that it should not be done for irrelevant and petty changes like getting a silly form to get an error if you cannot get tail-call merging.
Those of us who want tail-call merging already _have_ the guarantees we need because we have read the fine _documentation_ of our Common Lisp environments and recognize that this will _have_ to be an implementation- dependent quality. It has absolutely nothing to do with the semantics of the code, misguided formal theories to the contrary notwithstanding, and there is absolutely nothing in the language _today_ to suggest that you _can_ guarantee this feature, any more than you can "add" it to other languages that have not had the forethought to decide on "properly tail- recursive" _early_ in the design process.
Let me make an analogy. It is sometimes possible to turn a regular double-action pistol into an automatic pistol by breaking parts inside. Now, automatic firing of up to 19 rounds from a handgun can be a really good thing in approximately one situation, and we have wisely chosen not to include that situation in _lawful_ shooting activities, but some are not bound by the law so they want this feature. With the kind of guns that you can achieve this feature, it is hard enough to hit the target in its normal single-shot mode and the temperature of the gun rises so fast that you normally want to restrict your firing to five rounds at a time. The effect of automatic firing in this hand-gun is thus to cause the muzzle to rise with every shot, usually by a significiant angle, and to raise the temperature of the barrel and thus _decrease_ its diameter, not to mention the angle and temperature of the ejected cartridge. The hazardous nature of the modification should be fairly obvious even to people who think guns are only used to kill people. Still, there are automatic pistols on the market that are _designed_ with this feature and they are quite safe, at least for the guy pulling the trigger. I have no desire to own such a gun at all -- I shoot because it is a sport requiring strength, concentration, body control, etc, not because I like the actually _annoying_ sound effects, so when somebody who wants such guns looks at my guns and argue for the merits of automatic firing, I do think they are genuinely interested in automatic pistols, I think they are fucking nuts and would feel a lot safer if they left the range. This is approximately how I feel about Scheme freaks in the Common Lisp world.
/// -- 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?
