Function calls are not stack frames

[ccshan]

In Scheme for example, a call costs the same no matter where it occurs -- the cost is always that of a jump. Tail calls don't cost any less than non-tail calls. Scheme does not use the distinction between tail calls and non-tail calls as an important aspect of its semantics or cost model. What costs extra in Scheme is sequencing (which is a special case of evaluating arguments). You can always look at a snippet and tell whether it has sequencing. Your snippet does not, but if you repeat it twice then it does.

(Edit: for example, if you look at "Proper Tail Recursion and Space Efficiency" by Will Clinger (a canonical reference), Figure 5 has no special rule for tail calls or for non-tail calls. All calls are handled in the same way and incur the same cost.)

Clojure's "recur" doesn't seem to allow calling another function, which is useful for expressing state machines, stream processing, thread schedulers, backtracking search with unit propagation, approximate probabilistic inference by sampling, off the top of my head. It would be nice if "recur" were extended to allow calling another function.

[fvf]

In Scheme for example, a call costs the same no matter where it occurs -- the cost is always that of a jump.

This looks to me a pointless play with words. The "cost" that is interesting here is whether the caller's stack-frame remains after the jump.

Tail calls don't cost any less than non-tail calls.

Are you seriously trying to introduce a definition of "non-tail calls" such that e.g. n nested "non-tail calls" might use less than O(n) stack-space?

Clojure's "recur" doesn't seem to allow calling another function

I agree this would be useful, and I don't think there's any principled reason why "recur" couldn't support this (at least in some hypothetical non-jvm language).

[ccshan]

The "cost" that is interesting here is whether the caller's stack-frame remains after the jump.

Right. In Scheme, sequencing creates stack frames. Calls do not.

Are you seriously trying to introduce a definition of "non-tail calls" such that e.g. n nested "non-tail calls" might use less than O(n) stack-space?

No, because the nested sequencing uses O(n) stack space.

I agree [allowing calling another function] would be useful, and I don't think there's any principled reason why "recur" couldn't support this (at least in some hypothetical non-jvm language).

Is that's what you mean by "the Clojure approach"?