Anyway, I have been following this whole thread and I convinced myself
that tail-call merging is not easy,  and that is your problem :) since
there is some demand for it.

Having said so, I will happily continue programming following the
simple rule: first get it right, then get it fast.  If in the process
I have to eliminate tail-calls in favor of looping constructs, too
bad.

Cheers

There are compilers which go through C and achieve tail-call
optimization by introducing a filter program after the C compiler and
before the assembler, doing it essentially as a kind of peephole
optimization.  Which appears to be entirely adequate.

If there was an abundance of people working on d2c then it might be
worth chasing it up as a gcc special case, but we don't have such an
abundance and we need things to work on compilers such as CodeWarrior
and VC++ which are not gcc.

The generated C was not recursive - I could have used Fortran IV
(or whatever fortran has statically allocated activation records).
(Yes - I'm assuming that C libraries for i/o, math, and memory
allocation aren't recursive - I think that it's safe to assume
that they're nicely bounded.)

The control "stack" for the source language was linked continuations,
managed (created, returned, passed around, destroyed) by said generated C.
I did optimize that management for self-tail call situations, but it isn't
clear that that optimization was important.  (It probably made a measurable
difference in performance, but performance was so good that I probably
should have spent that time on other projects.  Unfortunately, that
optimization was one of the first things that I did and it was designed
in so deep that it would have been work to take it out so that I could
do the obvious experiment.  I don't know if it would have been less work
to graft it on afterwards.)

Yes, there was a "top" level routine, not unlike what Corman suggested
for the FSM problem.  This routine accepted returned continuations
from the generated C code and used them to determine what to call next.
("Top" is in quotes because it was actually involved for every continuation
generated.  It was at the top of the implementation's control stack, but
it was used at almost every intermediate level in the application's control
scheme.  Remember, the generated C was not recursive.)  The generated C did
NOT call continuations; it was called with such continuations (by "top"),
and it generated them (and returned them to "top") as necessary.

If you want to think of it in Steele's "goto with arguments terms, all
interesting gotos were implemented by creating and returning a continuation
to the "top", which then called the appropriate C routine.  "Determining
what to do next" was implemented as a call through a function pointer,
much as Corman did in his example.

When a C construct doesn't do exactly what you want, you can either
change what you want or you can use another construct.  (I didn't
use C's loop constructs at all for my language's loops.)  Managing
continuations "by hand" seems extreme, but freed me from the
limitations of C's calling model.  It took a lot less time to write
that management code (including the optimization) than it would have
to write the analysis code that it made unnecessary.

One might argue that I used C as a glorified generic assembler,
one that does register allocation, instruction generation, and some
interesting name management.  I'm not sure what the point of such
an argument would be.

A compiler such as Chicken that actually uses C function calls normally
gets all sorts of speed advantages through being able to use direct
function calls instead of indirect, use the C argument passing mechanism
to pass multiple return values, and so forth.  The C compiler generates
a little extra code for function return that is never actually executed
but that is a small price in space and no price in speed, except in
secondary effects through cache being wasted (and it's reducable through
non-standard "noreturn" compiler directives).  The cost is having to
check for stack overflow at the start of each function and extra code to
recover from that -- basically the technique that your implementation
uses, but in Chicken it is seldom used and can be shared or interpreted
or table-driven with negligable speed penalty.

Mapping source functions directly to C functions as d2c does is not a
viable technique for Scheme because it doesn't allow call/cc but Dylan
doesn't have that.  It also certainly makes tail-call optimization
harder and d2c will probably *never* support tail-call optimization
between top-level functions.

Interestingly, the commercial "Functional Developer" doesn't either,
even though it generates machine code directly.  So, in both Gwydion
"d2c" and Functional Developer this silly code...

   define method countto(i, t)
      if (i = 0) t else countto(i - 1, t + 1) end
   end;

   countto(1000000, 0);

... produces a stack overflow, while this code ...

   define method countto(i)
     local
       method foo(i, t)
         if (i = 0) t else foo(i - 1, t + 1) end
       end;
     foo(i, 0);
   end;

   countto(1000000, 0);

... works fine in both implementations.  The concensus in the Dylan
community seems to be that tail-call optimization is required, but not
for top-level functions.

Another example:

  define method classify(n :: <integer)
    local
      method even?(i)
        if (i = 0) "even" else odd?(i - 1) end
      end,
      method odd?(i)
        if (i = 0) "odd" else even?(i - 1) end
      end;
    even?(n);
  end;

  classify(123456789);

This works fine in Functional Developer.  At the moment it doesn't work
in d2c (stack overflow).  It should.  Dylan programmers have a right to
*expect* this code to be optimized, and I plan to ensure that d2c
fulfils that expectation.

Dylan of course isn't CL, and expectations differ in the two
communities.  As these examples show, Dylan isn't Scheme either.  In
many respects -- including the question of tail-call optimization -- it
lies somewhere between the two.

Now, one can argue that I paid extra because I didn't have decent
register allocation.  However, I don't buy it.

With modern (wide and deep) machines, instructions are almost free.
Stalls are the thing to minimize.  My "top" routine's indirect calls
are worth worrying about - C's stack frames aren't.  (The next architecture
advances will reduce the cost of indirect calls; returns stopped
being an issue 5 years ago.)

For lisps and schemes, library functions take a signficant amount of
time so one would expect that overhead to be negligible.  In my case,
there weren't any library functions to hide behind, but the observed
overhead was negligible.  (It was almost unmeasurable.)

BTW - My project was a skunk works project.  The "real project",
had lots of resources, time, and smart people who worried about
such "overhead", but was never finished, and was slower for the things
it did do.

Of course, one can use this approach to generate assembler directly
if you really need the last 0.2% performance.  Few of us are in a
position where doing so makes economic sense.  Almost all of us
are in a position where algorithms and efficient development matter
more.

However, my tests for "negligible" overhead used programs that used
continuations every few simple statements.  Since these statements
were usually implemented with C that became a few sparc instructions,
the overhead got its chance to shine.  On more realistic code,
continuations were far less common.

My source language didn't have multiple return values, but if it had,
I'd have used the same scheme for returning values that I used for
passing them.

I found that the dumb thing (source vars stored in structs) was almost
as fast as the "smart thing" (trying to use C args or caching struct
fields in C vars and relying on register allocation).  Why?  Modern
machines are more sensitive to stalls than instruction counts.  Indexed
loads/stores are "good enough" if you're doing much with the values.

I think of C's calling mechanism as being like the VAX "call" instruction.
That instruction does a lot of things, and when you need those things,
it's the fast way to get them.  However, when there's a mismatch, ....

When you return to the top level for every continuation you don't need a
check for stack overflow.  Chicken OTOH doesn't return to the top level
every time.  It uses normal C function calls to call the next
continuation and then when it runs out of stack space (generally set to
about the size of the machine's L1 cache seems to be fastest) it uses a
longjump() to dispose of the entire stack at once and return to a top
level driver loop like yours.

Thus on a typical machine which passes C function args in registers
(PowerPC, SPARC, MIPS, Alpha...) the overhead to call a continuation is:

Chicken:

- get the args into the right registers (usually free)
- normal, direct, C function call
- check stack pointer against a global stack limit variable

Trampoline (e.g. yours):

- save the args and continuation address into a struct
- C function return returning the struct (?by reference, or is it a
global?)
- indirect function call
- pull the args out of the struct

On something like the x86 which has few registers and normally passes
arguments on the stack yours is probably pretty good.  The various x86
vendors now throw huge resources at load/store units and accessing L1
cache nearly as fast as registers.

On a RISC, though, your technique will I think really hurt -- it's going
to result in most code being serialized on the load/store unit.

The indirect call in yours will hurt bad on all machines, and probably
worse and worse as time goes on.

Chicken also, incidentally, uses the C stack as the nursery generation
of the heap.  Heap allocations are done with either calloc() or else as
C local variables.  When stack overflow occurs and it is about to be
unwound (using longjump()) a garbage collection is done, transferring
any live data from the stack to the long-term heap.

Converting to CPS and translating this straight to C solves a number
of problems quite elegantly, because you get things like (efficient)
first class continuations, multiple values and tail-recursion (in the sense
that a tail-recursive function doesn't run out of memory, even if it
allocates continuation frames). But I should also note that there are some
caveats (as usual):

1. This system allocates storage at a frightning pace. The generational garbage collection
  helps, but this should be kept in mind.
2. Straightforward CPS-converted code is horribly inefficient. A large part
  of the highlevel-optimizations Chicken performs are used to simplify
  the code back to a more efficient form.
3. As Bruce already points out there are many stack-checks to be done.
  Continuation-procedures (those introduced by the CPS conversion) normally
  don't need those, but you still get a lot of checking overhead.

Direct-style translation into C (as systems like Bigloo, Stalin or KCL and it's
children) will normally generate more efficient code, but of course have awful problems
with call/cc and/or tail-rec. The trampoline (driver-loop) approach
that is used for example in Gambit is somehow in between those two
extremes: I made the experience that it is sometimes able to outperform
direct style compilers in fixnum-/unsafe-mode, but is often slower than Chicken
when the declarations are removed.

To demonstrate the translation concept, I will give an example.
Consider the following code:    

(define (len x)
  (if (null? x)
      0
      (+ 1 (len (cdr x))) ) )

Now if we compile this with "-benchmark-mode", then we get the
following (comments inserted by me):

static void f14(int c,C_word t0,C_word t1,C_word t2){
C_word tmp;
C_word t3;
C_word t4;
C_word t5;
C_word ab[3],*a=ab;
/* Check stack */
if(!C_stack_probe(&a)){
/* Save current continuation and do a minor GC */
C_adjust_stack(3);
C_rescue(t0,2);
C_rescue(t1,1);
C_rescue(t2,0);
C_reclaim(tr3,f14);}
/* We land here if stack is OK, or GC is done */
if(C_truep((C_word)C_i_nullp(t2))){
t3=t1;
((C_proc2)(void*)(*((C_word*)t3+1)))(2,t3,C_fix(0));}
else{
/* Allocate continuation closure */
t3=(*a=C_CLOSURE_TYPE|2,a[1]=(C_word)f28,a[2]=t1,tmp=(C_word)a,a+=3,tmp);
t4=(C_word)C_slot(t2,C_fix(1));
/* Fetch global variable "len" */
t5=*((C_word*)lf[0]+1);
/* Invoke "len"s procedure (in tail position, since this is CPS) */
((C_proc3)(void*)(*((C_word*)t5+1)))(3,t5,t3,t4);}}

/* Continuation code */
static void f28(int c,C_word t0,C_word t1){
C_word tmp;
C_word t2;
C_word *a;
t2=((C_word*)t0)[2];
((C_proc2)(void*)(*((C_word*)t2+1)))(2,t2,(C_word)C_u_fixnum_plus(C_fix(1), t1));}

As can be seen the code is not really for Human eyes. It also wouldn't pass
any programming style contest other than IOCCC. ;-)

Something I meant to mention before but didn't is the ability to use
standard C tools such as gdb and gprof (debugging and code profiling,
for the non-Un*x types).

Direct-style translation to C makes it pretty straightforward to use
standard tools.  Trampoline-style such as in Gambit will surely totally
distroy the usefulness of gprof -- the time in each function might not
be too bad, but the call tree stuff will be useless.

How do you get on with Chicken?  I imagine it's somewhere in between.

I would think of Chicken as a stack-less architecture, which takes advantage of
C stack management code generation to implement the first generation of the
memory manager.  I understand ML is also stack-less (is that right?). I think
that is very interesting, and understand from Baker's papers that you can get
very good performance with such a system. I especially like how it so blows the
minds of most programmers.

I was thinking a about possible syntax for explicitly requesting
tail-call merging. Isn't return-from almost that operator? Every
return-from used to exit a function is in effect a tail call for that
function (?). Maybe return-from could be extended to communicate the
programmer's intention when the result-form is a function call?

Something along the lines of

  return-from name result &key tail-call-merge if-cannot-merge

Where tail-call-merge is a boolean, and if-cannot-merge one of :error,
:warn, or :ignore.

  Since you could wrap the entire function body in a return-from, I think
  this would not be helpful.  Figuring out whether a function call is in a
  tail-call-mergable "position" is not helped by such use of this form.

  (defun foo (x y)
    (when x
      (return-from foo (bar)))
    (if y (baz)
      (return-from foo (bax))))

Here, all of the forms (bar), (baz) and (bax) are in a
tail-call-mergable position, but only (bar) and (bax) explicitly so.

Now, my suggestion was that one can rewrite your typical (tail-)
recursive function:

  (defun member (item list)
    (cond
     ((null list) nil)
     ((eq item (car list)) list)
     (t (member item (cdr list)))))

to this:

  (defun member (item list)
    (cond
     ((null list) nil)
     ((eq item (car list)) list)
     (t (return-from member
          (member item (cdr list))
          :tail-call-merge t
          :if-cannot-merge :error))))

..and be sure your member function either runs in constant space or
compilation will fail. Or the compiler will emit a warning if that is
what you specify. Of course, if the result-form is anything besides a
function call, tail-call-merging will fail.

* Frode Vatvedt Fjeld
| I think you misunderstood me.  I'll try to spell out what I meant more
| clearly.
|
|   (defun foo (x y)
|     (when x
|       (return-from foo (bar)))
|     (if y (baz)
|       (return-from foo (bax))))

  Well, _I_ think I understand your proposal better than you do yourself. :)
  Your proposal changes and improves exactly nothing, but just adds a false
  impression of something that still has be determined the same way it was
  before it was introduced.

(defun foo (x y)
  (return-from foo
    (if x
      (bar)
      (if y
        (baz)
        (bax))))))

| Here, all of the forms (bar), (baz) and (bax) are in a tail-call-mergable
| position, but only (bar) and (bax) explicitly so.

  I do not agree with this.  Figuring out whether a function call is
  tail-call-mergeable is generally not possible through a trivial visual
  inspection.  In the above form, all of the function calls are pretty
  obviously the last call the function will make, and if you cannot see
  whether a function call will yield the return value or not, it certainly
  will not help to have a piece of wrapper code around it that might _lie_.

| Now, my suggestion was that one can rewrite your typical (tail-)
| recursive function: [...] to this: [...] ..and be sure your member
| function either runs in constant space or compilation will fail.

  My argument against your proposal is that you could wrap the entire
  function in this newfangled return-from form and not reduce the problem
  one iota.

| Or the compiler will emit a warning if that is what you specify. Of
| course, if the result-form is anything besides a function call,
| tail-call-merging will fail.

  Now, this is getting so specific it looks like a _real_ kluge.  How about
  if someone provided a compiler-macro for that function?  How about a real
  macro?  Would you really want so much of your code to fail compilation
  even though nothing had materially changed?  In other words, if you had a
  form like you propose, the only place I can see it being really useful is
  at the _outermost_ level, like I have demonstrated above, _not_ at the
  innermost, terminal function call that it _might_ apply to.

  The questions I have tried in vain to raise are: How much knowledge do
  you require to be able to use your idea productively?  What does it mean
  to employ your suggested form around another form?

  Common Lisp does not, in fact, provide you with any information how a
  particular form will be compiled.  A function call may be inlined, which
  you may defeat with your desire for a tail-call-merging request, it may
  be turned into several function calls, most anything can happen between
  source and machine code.  Therefore, if your idea is not able to
  encompass an entire function's body, it is completely useless, because it
  may _have_ to encompass an entire function's body even if you think you
  are giving it a function call.  If you really want to tell your compiler
  that an _actual_ function call should be tail-call merged, you first have
  to know if your compiler will actually generate a non-merged function
  call that _could_ be a merged tail call.

  In other words, it is an idea that fits languages that do not do anything
  "interesting" with the code they compile.  Instead of providing something
  useful, such as important information for your compiler, you are instead
  limiting your compiler's ability to do interesting things with your code.

  If you want to do something useful by changing the language, I suggest
  finding/inventing ways to tell your compiler that you promise never to
  change the definition of some functions, classes, methods, whatever.
  That kind of information would be tremendously useful to the compiler,
  because it can make assumptions that it cannot make today and which
  necessarily means less opportunity for some kinds of optimization.

 (defun bar (x y) (funcall x (1+ y)))
 (defun foo (y)
   (let ((x #'(lambda (x) (return-from foo x)))) ;<-- first RETURN-FROM
     (return-from foo ;<-- second RETURN-FROM
       (bar x y))))

You might think the second RETURN-FROM was requesting tail-calling, but
it simply isn't.  First, it's in no more of a tail call position than it
was if you omitted the RETURN-FROM.  Second, it cannot be tail called
because there is pending state between the RETURN-FROM and the BLOCK
that cannot be disposed of until BAR has finished executing.

If all you mean by "request" is that it should be done "if possible",
then I would say that to an advocate of aggressive tail calling, EVERY
form is a request for tail calling "if possible".  Some things are not
able to be tail called, and if saying that's enough to undo the request,
then you're asking the same of every form.