Ezra's Research

> Efficient tail calls (or space-consuming ones) really should be part of the official "cost model" of the language

I believe Scheme does this, so you can tell in advance.

"I believe Scheme does this"

Indeed! Scheme requires it, as part of the language definition.

That's the kind of thing I mean by carrying the cost model alongside the semantics.

Most of my observations were spurred by people in the Scheme community, like Dave Herman.

> Efficient tail calls (or space-consuming ones) really should be part of the official "cost model" of the language

"Efficient" tail-calls is not a matter of whether some operation takes an extra 10% of CPU effort or somesuch. It's about whether a certain kind of functions (e.g. those employing O(N) tail-calls) can be considered to be "working" or not. You may claim that whether a program blows its stack has nothing to do with semantics, but I chose to include this fact in what I consider the semantics (and "side-effects") of my programming constructs. I don't see how you can reasonably claim otherwise.

> It's about whether a certain kind of function can be considered to be 'working' or not.

I don't think we're in disagreement, Frode!

> I don't think we're in disagreement, Frode!

Then I don't understand how you can write this, which I understand to contradict what I wrote completely:

> The semantics of the call doesn't change; the result and the side-effects are the same (that's what's usually meant by "semantics" anyway). The cost, on the other hand, might be quite different depending on whether a stack frame is needed.

I was trying to say that I believe the semantics do change, because whether the stack is blown or not I consider an important aspect of the semantics of my programs.

I believe the point that Ezra was trying to make is that semantics describe what the program does given infinite resources - the cost model describes how much resources it will really need. They're both very important, of course - but they're also seperate concepts.

I don't think I called for preservation of stack frames. I think that TCO does affect program semantics, to wit: If you know TCO is in effect, you can recursively iterate through an arbitrarily long input. Otherwise not. That feels semantic to me.

What I in fact argued, and still believe, is that Clojure's "recur" form is a good thing because it makes this semantic explicit in the text of the program.

clojure's loop/recur has little to do with TCO, it's just clojure's syntax for a loops.

If I remember the concepts right, recur doesn't let you do everything you can do with tail calls.

The case I have in mind is two (or more) mutually recursive functions, where they tail-call each other, not just themselves - as far as I understand it, recur can't do this.

As a separate point, isn't "semantics" usually used to describe such things as what parameters to give and what return value(s) to expect back, leaving the implementation as a black box?
Wether it uses tail recursion or recur or loops or whatever, how much stack or other memory it uses, etc, wouldn't be part of the semantics then, would it?
Or have I completely misunderstood this?

@bd_:The discussion on recursion is reduced to arguing over the semantics of "semantics". How ironic. Anyhow, I don't see how classifying stack usage as "semantics" or "cost model" changes anything. (And, I would suggest strongly that "cost model" is a subset of "semantics" in this case, rendering the distinction mooter still.)

"Most languages have no reason to use up space on every function call; only calls whose result will be fed to another expression need to use space."

Both of these statements seem incorrect. First, no matter what language you are using, a function call will need to take up space if you need to either pass arguments or return control flow to the current point. Unless you want to do a heap allocation every time, using the stack is the best way. Of course they have a reason.

Second, the reason for calling a function is presumably to make use of the result of its computation, pure functions anyway. Tail-recursive functions often produce useful results, but they don't require growing stack space. All tail-calls do is re-use the stack frame from the previous function call for storing arguments to the next function call. It has nothing to do with the result of the call being made, but instead whether their is state in the current stack frame that needs to be maintained for later usage. (The arguments to and stack variables allocated in the currently executing function.)

You make a good point about separating semantics from the cost model, but I think rather than arguing linguistic fine points what it comes down to is what is important for a developer to be aware of. In this case, stack overflows are quite easy to produce if you are using recursion without tail-call functionality, so whatever you want to call it, a developer should know about it. This is why the tail position checking of the recur form seems like a good thing to me.

E[X]: Clojure has the trampoline function to support mutual recursion.

"All tail-calls do is re-use the stack frame from the previous function call for storing arguments to the next function call." still seems incorrect. Consider a tail call to a function with more arguments than the calling function: in most languages it's going to need a new activation record to accommodate the additional arguments.

Rather than consider TCO as "reusing" a stack frame, it's probably better simply to say that a function's stack frame is removed just prior to its tail calls, rather than waiting for its tail calls to return. Whether tail calls get their own stack frames or reuse their caller's stack frame is really an entirely different optimization.

TCO is basically just optimal garbage collection of stack frames: as early as the frame is unneeded (i.e., right before a tail call) it is collected.

There are lots of ways to run out of space. No one has so far argued that the amount of available heap space should be integrated into the semantics of a language. Anyway, language designers don't know how much memory will be available on next year's machines, so formalizing the space limitation as a "side-effect" (the effect of dying when you run out of space) would be tough.

That's why I think it's useful to look at the tail-call implementation as a cost model, similar to but distinct from the "semantics" per se.

Tim: your point that it might be better to write "recur" in order to get efficient tail recursion, instead of the procedure's own name, is a fair one. For my money, I'd still like *all other tail calls* to be efficiently implemented too. And that would mean I can write mutually-recursive functions too. Still, Tim, I think your statements about tail-call elimination "magically transforming one thing into another" are FUD.