>[ This is a terminology gripe and a request for different language >usage] >[...] >There are several ways to say what is being meant here in a more >accurate or less confusing way. "Tail Call Optimizaton" is perfectly >good, as is "Tail Merging" (the former is more descriptive, and the >latter is self-defining because it has no confusing predefinitions).
You shouldn't redefine terms that are already in usage in the compiler community, that only causes un-needed confusion.
Tail merging is an already used term for something different:
> >[ This is a terminology gripe and a request for different language > >usage]
> >[...]
> >There are several ways to say what is being meant here in a more > >accurate or less confusing way. "Tail Call Optimizaton" is perfectly > >good, as is "Tail Merging" (the former is more descriptive, and the > >latter is self-defining because it has no confusing predefinitions).
> You shouldn't redefine terms that are already in usage in the compiler > community, that only causes un-needed confusion.
You are correct. In the myopia of the context, I called "Tail Merging" self-defining, whereas it really can't be defined at all; it is a descriptive label, rather than a definition. Hopefully because of the context, most readers understood what I had been talking about. Please note that I would prefer to use Tail Call Merging, or Call Tail Merging, and my real preference is to use Tail Call Optimization for those cases which I would ever care to examine.
I will endeavor to no longer use the term Tail Merging again under these circumstances.
> Tail merging is an already used term for something different:
Tail Merging is used to mean many things, according to the context. It is not a very good term to use as a definition, because without context it is ambiguous.
[ Descripotion of Branch Tail Merging elided ]
Thank you for pointing out the ambiguity that this term can have.
Note that the first of these examples gets away with using the term Tail Merging only because the context is clear. The second, as was the case of my own usage, was not necessrily clear and the context should have been made clear by using a more specific descriptive term.
There is a revised and greatly expanded journal version of this conference paper:
Clinger, W.D., Hartheimer, A.H., and Ost, E.M. Implementation strategies for first-class continuations. Journal of Higher Order and Symbolic Computation}, 12(1), 1999, pages 7-45.
The journal version is not available in electronic form, but it should be available in university libraries, and I have a finite number of reprints that I can mail to people who are seriously interested in this subject.
Gareth McCaughan wrote: > ....There's one reason why > it might hurt CL more than Scheme: producing efficient code > in the presence of call/cc requires sophisticated control-flow > analysis....
I don't believe this is true, but it is possible that Gareth is talking about control-flow analyses that would allow an implementation of CL's CATCH in terms of a general CALL/CC (for example) to be as fast as existing implementations of CATCH.
The rest of what Gareth said is true.
By the way, Kaz Kylheku's explanation of the difference between closures and continuations was quite good, in my opinion.
Pascal Costanza wrote: > Actually it would be much simpler to implement Common Lisp on top of > .NET, because you can always circumvent the CLR by switching to native > code on the fly. (As far as I know you can also manipulate virtual > method tables in .NET - you can't do that in Java.) But then again, > there would be no point in using .NET if a fair amount of effort would > be needed to just circumvent it. ;) Except, of course, for simpler > interoperability with other .NET languages.
Another reason that a .NET CL implementaion would be easier is that it has primitives for checked overflow of integer arithmetic, something that the JVM does not provide.
Trying to concentrate on call/cc, I would say that there are (at least) two sides to the answer.
From one view point, call/cc is a very generic operator whihc can be used to implement a variety of concepts, such as exception mechanisms or iteration constructs.
This is less usefull in CL because CL has lots of such constructs build in.
From another view point, call/cc is a multiprocessing construct which allows a computation to be split up into multiple restartable computations.
This is usefull and something which the current CL standard lacks. The main reason for this (as I understand it) is that at the time of writing of the standard there was no general consensus on what a good multiprocess abstraction should look like, and thus it was left out.
This is kind of a pity, also because some of CL's competitors (such as Java) has standard abstractions for this, but in practice it isn't a very big deal. The different implementations has varying degrees of support for multiprocessing, and true preemptive multiprocessing is pretty hard to implement (ie. not something that will happen to your favourite CL implementation just because some standard requires it).
------------------------+-------------------------------------------------- --- Christian Lynbech | Ericsson Telebit, Skanderborgvej 232, DK-8260 Viby J Phone: +45 8938 5244 | email: christian.lynb...@ted.ericsson.se Fax: +45 8938 5101 | web: www.ericsson.com ------------------------+-------------------------------------------------- --- Hit the philistines three times over the head with the Elisp reference manual. - peto...@hal.com (Michael A. Petonic)
> Another reason that a .NET CL implementaion would be easier is that it has > primitives for checked overflow of integer arithmetic, something that the > JVM does not provide.
i thought some people were already working on CL on .NET. i wouldn't be surprised to see one within a year, if not sooner.
Say, he surrenders up to him his soul, So he will spare him four and twenty years, Letting him live in all voluptuousness, Having thee ever to attend on me, To give me whatsoever I shall ask, To tell me whatsoever I demand, To slay mine enemies, and aide my friends, And always be obedient to my will.
-- Christopher Marlowe The Tragicall History of D. Faustus oz --- oh dear, where did that smiley go? ah, there it is... :-)
> From another view point, call/cc is a multiprocessing construct which > allows a computation to be split up into multiple restartable > computations.
This has come up before. If you want to take advantage of OS-supported threads (and hence use more than one processor on any kind of SMP machine) then call/cc is not a good way of doing this. Unfortunately, most of the existing CL threading systems suck pretty badly (or at least tend to encourage you to write programs that suck, by, say, using WITHOUT-PREEMPTION for synchronization), but that's no reason to start using call/cc instead.
Now about 15 hoary old lisp hackers are going to complain about how WITHOUT-PREEMPTION is the right approach to synchronisation, because, like, no one has multiprocessor machines anyway, and no programs we ever write will run on them, because they cost such a lot and no one uses them anyway. Anyway, everyone knows that a single processor machine is turing equivalent to a multiprocessor, so why would we want one? I hear rumours about so-called 64bit machines, too: they will never catch on.
> This has come up before. If you want to take advantage of > OS-supported threads (and hence use more than one processor on any > kind of SMP machine) then call/cc is not a good way of doing this. > Unfortunately, most of the existing CL threading systems suck pretty > badly (or at least tend to encourage you to write programs that suck, > by, say, using WITHOUT-PREEMPTION for synchronization), but that's no > reason to start using call/cc instead.
This seems hardly true of LW as they have mutex like locks. Of what possible use would without-preemption be for synchronization, unless it is a big system wide function? What problems have you had with the threading/process systems?
William D Clinger wrote: > Gareth McCaughan wrote: > > ....There's one reason why > > it might hurt CL more than Scheme: producing efficient code > > in the presence of call/cc requires sophisticated control-flow > > analysis....
> I don't believe this is true, but it is possible that Gareth is > talking about control-flow analyses that would allow an implementation > of CL's CATCH in terms of a general CALL/CC (for example) to be as fast > as existing implementations of CATCH.
It is indeed possible. It's some time since I've looked properly at any of this stuff, and I may have been misremembering.
It is not only possible but certain that you know more about what is necessary for producing efficient code in the presence of call/cc than I do, so I hereby retract my claim quoted above.
-- Gareth McCaughan Gareth.McCaug...@pobox.com .sig under construc
"Wade Humeniuk" <w...@nospam.nowhere> wrote in message <news:vTDo9.36431$OO4.2501505@news1.telusplanet.net>... > This seems hardly true of LW as they have mutex like locks. Of what possible > use would without-preemption be for synchronization, unless it is a big > system wide function? What problems have you had with the threading/process > systems?
Well the problems are really problems of example: I can't give concrete instances this week, but I'm fairly sure that if you look at samples in various manuals you'll see stuff like:
(defun foo (x) ;; we need to synchronize access to X, so (without-preemption ;; just stop all other threads dead, why not? (setf (cdr x) (compute-thing x))))
WITHOUT-PREEMPTION is like having a single mutex for everything, except it's actually even worse, because it stops even threads which aren't interested in that mutex.
In general my problem with various Lisp threading systems is the way they are used not the facilities they have (other than not implementationally having the ability to make use of a more-than-one CPU machine, which is obviously hard to do). This is kind of a nebulous conplaint, I guess. I think that better presentation (for instance putting stuff like WITHOUT-PREEMPTION in some `only for use in weird cases' package) would help.
>>>>> "Tim" == Tim Bradshaw <tfb> writes: >> From another view point, call/cc is a multiprocessing construct which >> allows a computation to be split up into multiple restartable >> computations.
Tim> This has come up before. If you want to take advantage of Tim> OS-supported threads (and hence use more than one processor on any Tim> kind of SMP machine) then call/cc is not a good way of doing this.
True, but multiprocess abstractions can be usefull and natural even without OS level premptive multitasking.
For instance, it can be very convenient to be able to terminate a large computation and still maintain the ability to restart it later, without having to recreate the state of the computation at the point of interruption.
I am not saying that MP abstractions is the only way to do such things (Grahams book "On Lisp" demonstrates alternatives based on closures) , but it is a very common abstraction.
------------------------+-------------------------------------------------- --- Christian Lynbech | Ericsson Telebit, Skanderborgvej 232, DK-8260 Viby J Phone: +45 8938 5244 | email: christian.lynb...@ted.ericsson.se Fax: +45 8938 5101 | web: www.ericsson.com ------------------------+-------------------------------------------------- --- Hit the philistines three times over the head with the Elisp reference manual. - peto...@hal.com (Michael A. Petonic)
d...@goldshoe.gte.com (Dorai Sitaram) writes: > A consequence of TCE being different from the > optimizations you are talking about is that there > are programs -- and I am _not_ just talking about > straight iterations -- that would become incorrect, > rather than just unoptimized, if the user wrote them > expecting TCE but the language didn't support it.
There are no programs for which a non-tail-recursive language returns a *different* result from a tail-recursive one. There *are* programs for which a tail-recursive implementation will return a result, but a non-tail recursive one might not.
Duane Rettig <du...@franz.com> writes: > I don't know the Lisp Machine architectures intimately, so I don't > know if they ever had this capability, but I could easily envision > such an architecture, and it could even be emulated in GP hardware. > In short, if the unbinding of specials were part of the Lisp calling > convention, then the above example would indeed describe a > tail-position situation.
The Lisp Machine didn't try to hard to be tail recursive. The MIT CADR, the LMI Lambda, and the TI Explorer had a `tail recursion switch' that directed the microcode to attempt tail recursion provided that a number of conditions had not been violated (no special bindings, no stack-allocated structures, no catches, no &rest args, etc.). However, there were bugs in the code that checked these items, so when you turned it on, the machine would generally crash.
The Symbolics machines would re-arrange the stack upon function entry, so in general tail-recursion wasn't possible (on the early machines. I don't know if the Ivory had chaged this).
The LMI K-machine had tail-recursion capability in hardware, but special bindings would cause a non-tail recursive call.
Jim White <j...@pagesmiths.com> writes: > One thing Kent mentions is that Scheme's model of concurrency has > problems with parallel processors using shared memory.
I don't recall Scheme having a model of concurrency.
> True, but multiprocess abstractions can be usefull and natural even > without OS level premptive multitasking.
> For instance, it can be very convenient to be able to terminate a > large computation and still maintain the ability to restart it later, > without having to recreate the state of the computation at the point > of interruption.
Yes, they can, but given that all but the tiniest OSs provide OS-supported threading, which you'd clearly want to support in the language if you could, it seems silly to provide another kind of thing (call/cc) to do part of the same job.
Emoirically, what has happened in CL is that, even though few (if any) implementations make use of OS-supported threads, they provide multiprocessing constructs as such rather than via some amazing primitive like call/cc. This seems very much the CL Way (TM) to me.
> > This seems hardly true of LW as they have mutex like locks. Of what possible > > use would without-preemption be for synchronization, unless it is a big > > system wide function? What problems have you had with the threading/process > > systems?
> Well the problems are really problems of example: I can't give > concrete instances this week, but I'm fairly sure that if you look at > samples in various manuals you'll see stuff like:
I looked through the LW MP User and Reference Manual and there are no examples of thread synchronization.
> (defun foo (x) > ;; we need to synchronize access to X, so > (without-preemption > ;; just stop all other threads dead, why not? > (setf (cdr x) (compute-thing x))))
Yes an example like that should be
(defvar *x-lock* (mp:make-lock))
(defun foo (x) ;; we need to synchronize access to X, so (mp:with-lock (*x-lock*) (setf (cdr x) (compute-thing x))))
> WITHOUT-PREEMPTION is like having a single mutex for everything, > except it's actually even worse, because it stops even threads which > aren't interested in that mutex.
Maybe programmers are tempted to use without-preemption because they are worried that the number of locks would explode to handle sync issues between threads. However in my experience the number of places where a mutex is necessary is very limited.
> In general my problem with various Lisp threading systems is the way > they are used not the facilities they have (other than not > implementationally having the ability to make use of a more-than-one > CPU machine, which is obviously hard to do). This is kind of a > nebulous conplaint, I guess. I think that better presentation (for > instance putting stuff like WITHOUT-PREEMPTION in some `only for use > in weird cases' package) would help.
Well there are some cases that without-preemption (and especially without-interrupts) are needed, but the only place I can remember needing this type of functionality was in embedded systems (limited memory resources and the constant IO interrupts this had to be managed). I was pleasantly suprised to see the completeness of LW MP package. It performs all the threading functionality I am familiar with, with maybe the exception of semaphores (but that could be done with mutexes/locks or mailboxes and a little code). LW even has inter-process signalling with mp:process-interrupt.
With the LW MP package the lisp environment seems to be like a little Operating System. Since LWW uses native windows threads its lisp processes will get allocated to different CPUs on a multi-CPU machine. Is this not correct? I know this is not the case on LWL (or other Unixes) since it uses user processes. I assume one would just have to code around that problem with mutiple LW unix processes to make use of multiple CPUs. Maybe Xanalys is working on a native UNIX threading implementation?
tfb+goo...@tfeb.org (Tim Bradshaw) writes: > Emoirically, what has happened in CL is that, even though few (if > any) implementations make use of OS-supported threads, [snip]
Concerning the "if any" part: It looks like Scieneer Common Lisp makes use of them for Solaris, HP/UX, and Linux. See
> > One thing Kent mentions is that Scheme's model of concurrency has > > problems with parallel processors using shared memory.
> I don't recall Scheme having a model of concurrency.
In "The SCHEME Reference Manual" by Sussman and Steele (AIM-349 for those who are interested) there are the following:
CREATE!PROCESS This is the process generator for multiprocessing....
START!PROCESS This takes one argument, a process id, and starts up that process....
STOP!PROCESS This also takes a process id, but stops the process....
EVALUATE!UNINTERRUPTIBLY This is the synchronization primitive.....
Obviously EVALUATE!UNINTERRUPTIBLY is like the without-preemption macro that people have raised objections to.
-- Fred Gilham gil...@csl.sri.com And then [Clinton] turned to Hunter Thompson, of all people, and said with wholehearted fervor, "We're going to put one hundred thousand new police officers on the street." I was up all night persuading Hunter that this was not a personal threat. -- P. J. O'Rourke
On 9 Oct 2002 07:17:29 -0700, tfb+goo...@tfeb.org (Tim Bradshaw) wrote:
>Emoirically, what has happened in CL is that, even though few (if any) >implementations make use of OS-supported threads, they provide
Corman Lisp supports multiple OS threads in a lisp process, and therefore multiple processors. This will be a topic of my discussion at the international lisp conference.
