I believe these instructions are called "prefetch", which is different
  from prediction.  "prediction" usually applies to branch prediction, but
  I'm talking about a similar automatic heap cache line prefetch or priming
  (when the memory is known to be written first) when a function call is
  coming up in the instruction stream.

  these instructions are fun to watch do weird things with one's ideas
  about cache line costs, but using them requires their actual presence and
  some computation for the effect you get for free from reusing the same
  memory the way a stack works.  most stacks are amazingly shallow and the
  cache hit rates for stacks (including temporaries in call frames) are
  typically >99.9%.  to get that good hit rates for a heap allocation
  scheme that walks over fresh memory while allocating and causes much
  scattering of allocated call frames unless the heap is optimized like a
  stack, you have to do a huge number of more or less explicit cache line
  prefetching in the absence of lots of prefetch instructions that add to
  the computational load without necessarily having any effect.

Athlons also has data prefectch in several variants (write or read only).
Please look at http://www.amd.com/products/cpg/athlon/techdocs/index.html
if you are interested.

Garbage Collection is Fast, but a Stack is Faster
By James S. Miller and Guillermo J. Rozas

AI memo 1462, March 1994, 37 pages    

Prompted by claims that garbage collection can outperform stack
allocation when sufficient physical memory is available, we present a
careful analysis and set of cross-architecture measurements comparing
these two approaches for the implementation of continuation (procedure
call) frames.  When the frames are allocated on a heap they require
additional space, increase the amount of data transferred between
memory and registers, and, on current architectures, require more
instructions.  We find that stack allocation of continuation frames
outperforms heap allocation in some cases by almost a factor of
three.  Thus, stacks remain an important implementation technique for
procedure calls, even in the presence of an efficient, compacting
garbage collector and large amounts of memory.

They use a very reduced model of stack and heap allocation that shows
that the irreducible minimum amount of overhead for stack allocation
is smaller than that for heap allocation.  In addition, they benchmark
the results on a real machine.

In a particular _implementation_ of a language, a properly tail
recursive implementation will produce correct results for all programs
which produce results under a non-tail-recursive implementation.
Furthermore, there exist programs that will not run to completion in a
non-tail recursive implementation (because of stack overflow) that
will produce a result in a tail-recursive language.

Behaviorally, yes, they differ, but this is a strictly implementation
issue, not a semantic one.

It maps expressions of the form (<expr 0> <expr>*) to mean function
invokation.  

1.  Some programs that will not run without tail recursion will run.

2.  Performance may be increased or reduced.  (It is often increased
    when locality is improved, it is often decreased when the
    underlying language makes it difficult to discard vacuous
    continuation frames, as when you compile scheme to C.)

3.  Debugging becomes more difficult because backtrace information is
    lost.

However, it has no effect on the results of the computation:  the
answers will always agree.  It also has no adverse effect on the range
of runnable programs.  All programs that ran without tail recursion
will continue to run.

I don't advocate requiring proper tail recursion *or* first-class
continuations in CommonLisp, but I would greatly favor a CommonLisp
implementation that allowed me to turn on proper tail recursion.  I've
never seen a CommonLisp with first-class continuations, and I rarely
use them when I am programming in Scheme.

Scheme wasn't designed as a `one-size-fits-all' language, so it isn't
surprising that many people find it unsuitable for whatever issue they
are currently dealing with.

  this is a very narrow definition of "semantics", and I don't think
  it's useful to discuss such definitions, so suffice to say that I do
  not respect the view that the only semantics are those that can be
  described by denotational semantics.

| Certainly if full proper tail-recursion is too expensive to implement,
| but no tail-recursion whatsoever is undesirable, self-tail-recursion
| is an attractive alternative.  Indeed, many Scheme implementations
| only provide self-tail recursion.

  I still have the impression that I'm not getting through with the
  distinction between _requiring_ a particular implementation of tail
  calls and _allowing_ it as and when desired.  there is _nothing_
  whatsoever that affects "allows" if one argues against "requires".
  I have no interest in countering arguments against "allows", as I
  have explicitly argued _for_ "allow", already.

  among the reasons I'm no fan of Scheme is that the _requirements_ in
  its language design are very serious mistakes, and they affect the
  way Scheme people think about language design so adversely that it
  is sometimes impossible to penetrate the view that "if it isn't
  required in the standard, you can't trust smart people to do it".
  e.g, I don't see anyone (except Scheme people who knock down
  strawman arguments) even bring up "no tail-recursion whatsoever".

  it's a cheap argument, but it accurately reflects my sentiments
  towards most of what distinguishes Scheme from everything else: if
  it's so smart, other smart people will want to do it, but if they
  don't, maybe it wasn't so smart to begin with.  this is the best
  simple answer to the sentiment nearly unique to Scheme: "why does
  language X _lack_ random feature Y (from Scheme)", which is raised
  in nearly those words in c.l.l from time to time.

  as an even cheaper argument, I'd summarize Scheme by saying that all
  its good ideas have been absorbed elsewhere and the only stuff left
  to brag about is that which wasn't smart to begin with, which tends
  to reinforce the silliness of the Scheme superiority.

  in contrast to this, Common Lisp doesn't suffer from a need to feel
  superior, mostly because it has so much "impure" and historic stuff
  in it that any "superiority" would be ridiculous, anyway, but it has
  a unique blend of pragmatic and elegant design that means you can
  always attack specifics, but you can't attack the design without
  implicitly or explicitly arguing for a _worse_ design.  that's why
  the language specification doesn't _require_ a smart feature that
  isn't smart across the board and always, but also doesn't disallow
  it (like some other languages do through sheer incompetence).

Cross-tail-recursion, OTOH, permits a pass-the-baton
style way of writing procedures that would be
prohibitively expensive to run as is in a non-TCO
world, and very difficult (impossible even?) to
rewrite iteratively.  This is why TCO is appealing.
Self-TCO is small potatoes and not worth doing
implementational gyrations over.

You are certainly free to broaden the definition of `semantics' to
include the concrete behavior of particular implementation techniques,
but you will run the risk of confusing people who are used to the
standard definition of semantics.

In general, I disagree.  Allowing only useful options is much better
than allowing all possible options; options contain bugs and require
time to learn about.

In the tail-call optimization case, I can't imagine why you'd want to
give the user the option to turn off tail-call optimization if it were
only a win for your particular implementation.  (I think most
implementations that compile directly to machine code and can do
tail-call optimizations lose nothing by tail-call optimizations.)

In the case of allowing an option under *implementor* control, I'm
still not sure I agree.  Every degree of freedom for a language
implementor is something language users must contend with changing
unpredictably.

  consider full and accurate backtraces during debugging, profiling
  that reports correct call trees, and simply correct error messages.

  programmers prefer to be able to control optimization levels for a
  number of reasons.  Scheme doesn't have a standard way to express
  such preferences, either.  in other words, Scheme is not an option.
  (sorry, I had to.)

One could even argue that it doesn't fit Common Lisp at all, since
e.g. the behavior of modifying the symbol-function of a function will
depend on the compilation technique.

IIRC from my reading of the GC literature, Ungar introduced the notion
of a fixed "nursery" area [that may not have been his term for it] for
allocation in generational copying collectors, with the size chosen to
be the size of the secondary data cache (or slightly smaller). When you
fill up the nursery area, you do a minor collection, copying all of the
live data out into the main heap, then immediately reusing the *same*
nursery area for subsequent allocation. This causes the nursery area
to stay "hot" in the cache, much like a stack would.

Using such techniques, people [Appel, in particular] have claimed that
heap allocation can be as cheap as stack allocation, on average. (Yes,
I know others have disputed that as well.)

-Rob

p.s. Conversely, Henry Baker's "CONS Should Not CONS Its Arguments, Part II:
Cheney on the M.T.A." <URL:ftp://ftp.netcom.com/pub/hb/hbaker/CheneyMTA.html>
shows how to use the normal C stack *as* the nursery area of a generational
collector -- by writing in a CPS style that "never returns", allocating in
normal C stack-local variables, and limiting stack growth by periodically
combining a "longjmp" to trim the stack with a minor garbage collection.
Again, you get the same result: a copying collector that keeps its
generation-zero allocation area hot in the cache.

Sure, and all subroutine calls and returns and random GOTOs can be converted
into one huge case statement inside a loop, too [with a manual stack to hold
the case indices for the returns]. I believe it was Bill Wulf who pointed
this out decades ago in a paper titled "Global Variable Considered Harmful".
That still doesn't make me want to do it very often.

The problem is that readability *does* matter, and both pass-the-baton-style
tail-call-optimized programs and CPS-style programs have their place, where
they're the most natural & readable style of doing some task. In particular,
having written a couple of lexical analyzers in Scheme in the pass-the-baton
style, I find that I really like it for that sort of thing. Sadly, it doesn't
really translate well to non-TCO environments.

Does that mean that I will always choose to accept the *other* pains of
writing in Scheme just for the benefits of TCO?  Not at all, if by using
some other environment (such as CL) I can gain *more* convenience and/or
readability for the whole task than what's been lost by having to rewrite
some pass-the-baton or CPS pieces. But the presence of cross-routine TCO
*is* one (but just one) of the considerations that affects my choice of
language for a given task...

-Rob

  (define (myfun ...)
    .
    .
    .
    (myfun ...))

If procedure A's last call is to proc B_1, whose
last call is to proc B_2, etc., then these calls
to the B_i can each afford to not store information
about their immediate caller, as they can directly
return to the caller of proc A.

This suggests a programming style whereby each proc
takes care of what should be called next, thus
obviating the need for a centralized clearinghouse
(like Kragen's suggestion) whose duty is to wait for
returning procs and then dispatch on "what to do
next".  It is a way of developing an overall order by
having each element take care of just its private
contribution to that order by checking up with its
neighbor.  A handy decentralization tactic much used
by Ms Nature and human imitations of her (e.g., life
and Life).

Of course such a decentralized program will run
semantically correctly "as is" in a non-TCO
world too, but the pragmatics differ considerably.
(I'm using the terms "semantics" and "pragmatics" in
Joe Marshall's sense; pl translate appropriately if
these terms mean something else to you.) In a TCO
world it will incur no stack penalty.  In a non-TCO
world it will, and that may be enough in many
situations to make this approach a non-option.

As my example limns, cross-tail-recursion, unlike
self-tail-recursion, may not involve recursion at all,
in the sense of a procedure calling itself, directly
or indirectly.  That's why I've tried to be consistent
in using "tail-call optimization" instead of
"(proper) tail-recursion".  I guess I should
have used "cross-tail-call-optimization", but I didn't
want to frighten the horse.

My point is only that first class continuations can be nice to have, but are
not necessary for the production of high-performance tail-pure language
design.

- DM

Granted, C/C++ threads are too heavyweight to do this sort of thing,
but in languages like Lisp, threads can be extremely lightweight and
cheap, to the point where every UI element has its own thread
associated with it and most of the UI behavior is implemented by
message passing.

However, to play the devil's advocate, I have also had the experience of
using continuations in a manner that permits the reestablishment of an old
environment, long after that environment had expired. What happend in the
interrim were side effects that could not be unwound before restarting the
continuations and disaster struck in several instances. These side effects
so altered the global "world" environment that it made no sense to restart
the continuation environment. So in this sense, one has "continuations
considered harmful..."

I have the utmost respect for the collective judgement of the team that
created the CLTL2 and ANSII Standards. And so I have wondered whether this
sort of problem with continuations being reinstated after the global "world"
state has been irreversibly changed, whether this problem was in the minds
of this group when they decided to elide first-class continuations in CL?

Perhaps in their collective judgement this was a problem to be left to
individual implementors of applications that would need such a capability --
one to be solved in some other more CL-like manner?

- DM

But are you just using continuations here to hand-craft some sort of threads?
Couldn't you do the same thing *without* first-class continuations if the
implementation provided sufficiently-flexible Lisp-level threads?

-Rob

(whether or not a *particular* GUI environment allows you this
level of flexibility would have to be determined by the GUI
environment, I suppose).

Do keep in mind that a slave event loop doesn't require
that this happen. The slave can quite easily act with the
same authority as the primary event loop, albeit you would
have to take care to make certain that inconsistent states
might not pop up (I myself always confined myself to
APPLICATION_MODAL functionality as a general rule, so can't
offer an opinion on the more general use without going out
of my scope).

Do keep in mind that the callback/event handler abstraction
of Xt generally allows one to avoid having the very ugly
type of program where you're listening to events on the
loop itself. Rather you establish callbacks which are
dispatched from a general mechanism; ergo, the author of the
slave event loop only needs to make certain that events
continue to be processed and never has the responsibility
of determining what events mean what.

(the same can't be said of other gui models, of course,
so your point is quite apt in those contexts).