Lambda the Ultimate

I have been thinking about this a little lately. A stack trace might include a line like:

... 768 stack frames omitted ...

It's trivial to count the number of tail calls at run time, and maybe worth it for usability.

And: you're not required to throw away all those stack frames eagerly. You can mark them as tail calls, then throw them away later if you need the memory. Then the problem is determining which stack frames are important enough to display and which are just loops.

(I have no idea whether any Schemes do this.)

scheme has to make tail calls direct or it's not scheme. so there wouldn't be any stack frame (that's the whole point of tail calls).

or i'm completely confused about this, i guess.

[later] bleagh; i completely mis-read the post i was replying to. sorry.

Henry Baker's Cheney on the M.T.A. algorithm does pretty much exactly what you describe for lazy stack frame collection, and Chicken Scheme implements that approach. Summarizing, it just keeps pushing the C stack, never returning, but the stack is garbage-collected when it fills up.

To address Andrew's objection, afaik this approach is observationally equivalent (modulo GC pauses, perhaps) to an eager tail recursive implementation, so it's a valid way to implement Scheme.

I don't know of any implementations that tell you how many frames have been optimized from the stack history, though. That might not be very useful, because the tail calls could be from anywhere to anywhere, so knowing how many there are wouldn't tell you much. Imperative languages don't tell you the sum of all iterations of loops you might have gone through to reach a certain point, either.

Imperative languages don't tell you the sum of all iterations of loops you might have gone through to reach a certain point, either.

Man, it would be cool if they did, though...

IIRC, MIT Scheme can be configured to keep a fixed-size FIFO buffer of tail call frames. Since the buffer is bounded in size this does not violate the TCO requirement.

This is entirely anecdotal, but most Schemers I've talked to don't seem to have found the lack of tail call history to be the debugging impairment that one might initially fear it to be. In the rare cases where such information is needed in specific parts of the code, it is customary to wrap the tail call in a call to the identity function.

MIT Scheme can be configured to keep a fixed-size FIFO buffer of tail call frames

The problem with this approach is that any loops implemented using tail recursion (which in Scheme means all loops) will quickly fill even the largest FIFO buffer. One can do better than that: I've been working on a stack tracer for SISC that compacts the FIFO buffer by detecting repetitions in tail call sequences. Early results are encouraging.

Sourceforge has rearranged all their mailing-list archive links. The thread Matthias linked to is now available at https://sourceforge.net/mailarchive/message.php?msg_id=2043767.

It is a tail recursion optimisation, but not a tail call optimisation (as the recipe's title suggests).

It is of course a little more heavyweight than a cute goto. Unfortunately the language does not provide any. O.K. it provides one but Python sells it as an april fools joke. What really annoys me about the goto implementation is that it retokenizes the module that uses it. This strikes me excessive and nocent.

Kay

When you type "import this" into Python, part of the output is: "Flat is better than nested." It seems to me that Guido's stance on tail call optimization comes from that more general principle. It's not a historical coincidence.

Optimized tail calls result in a flatter call stack, so...? ;)

[P.S. Where do I sign up for Alan's alternative universe?]

You know, it's hard to be sure, but I think it means "flat for the user-programmer's brain" rather than "flat in terms of the C stack at run time, as a performance optimization". :)

Two books that deal specifically with Lisp implementations are SICP, and Lisp in Small Pieces (LiSP, available in paper only, afaik). The latter is focused on pretty much nothing other than implementing various Scheme-like Lisps with different properties, and covers about a dozen implementations, using various techniques. It also introduces some denotational semantics.

EOPL might also be helpful. These are all linked from the Getting Started thread.

I've had several people suggest Lisp in Small Pieces, and I'm going to get it.

A friend of mine and I played around with it the other day, and it did work for 3 and 4 mutually-recursive procedures, none of which called themselves. So my comment above is not correct.

I'm still skeptical that this implements true tail recursion, but the counterexample isn't nearly as simple as I thought it would be.

The code as posted recurses on itself, instead of on the called procedure, so mutually-recursive procedures will not be optimized correctly.

@tail_call_optimized
def even(n):
  if n == 0:
    return True
  else:
    return odd(n-1)

@tail_call_optimized
def odd(n):
  if n == 0:
    return False
  else:
    return even(n-1)

>>> print odd(1)
False
>>> print even(1)
True

- return g inside the exception thrown
- have a local variable inside the while loop that is initialized to g
- when catching the exception, set this local variable to the g from the exception

Fixed version and more write-up here.

In order to let this work the passed function g must be prepared. Instead of recurse into g(...) in g's function body the call must be replaced by TailPromise(g,...) isn't it? So it seems to be more a design pattern for recursive functions: turning them into non-recursive ones explicitely in the implementation and evaluate them as if they would be recursive by means of returning the TailPromise wrapper and the trampoline function. This might not be exactly what I expect from a decorator solution where the implementation of a function is left unchanged.

Kay

The else: return TailPromise(g,args,kwargs) part takes care of that. This is actually almost the same as the other implementation. But it uses a promise instead of an exception. The tail call position makes sure it doesn't matter what or how you return.

Because the TailPromise has (faked) lazily-evaluated semantics, it should work as a standin for the real return value in non-tail situations. Also, because it inspects the return type rather than the stack, it should work in mutually-recursive tail situations (multiple functions tail-calling each other).

It is very similar to the other implementation, though, and I wouldn't have ever thought of doing something like it without seeing the first one.

http://en.wikipedia.org/wiki/Trampoline_%28computers%29

trampoline is a general optimization technique used to implement tail-calls in non-tail call implementations. I think it's as old or older than first attempts at native code compiling in functional languages during the 70s...

This one don't work too good neither. Again, try:

@tail_recursion
def even(n):
   if n == 0:
      return True
   else:
      return odd(n-1)

@tail_recursion
def odd(n):
  if n == 0:
     return False
  else:
     return even(n-1)

Then calculate even(2) to be False. Comment the decorators out and it works. This would be a problem even with non-mutually recursive procedures, because you could have something like

@tail_recursion
def foo(n):
  if blah:
     return foo(bar(n))
  else
     return baz(n)

and the tail decorator could interfere with the call to baz(n), even if baz(n) is not recursive.

Comment the decorators out and it works.

It works when you comment out one decorator - with the expected bound stack size. Commenting out both doesn't work for large n of course.

About foo. I don't see a problem here unless bar() calls foo again as in the following code:

@tail_recursion
def even(n):
    if n == 0:
        return True
    elif n == 1:
        return False
    else:
        return even(odd(n-2))

def odd(n):
    if n == 0:
        return False
    else:
        return even(n-1)

The decorator is more brittle than Crutchers due to its dumbed down lookup procedure. Not sure I want to investigate this issue any further since I never used it in my work and I don't know anyone who did. However I will place a warning in the recipe.