Ezra: Function calls are not stack frames

I don't have much to add to this but Ezra's saying things that are true:

Tim Bray is spreading more misinformation about tail recursion. He describes it this way:

It looks like a subroutine call, but in the case where it occurs as the last thing in the routine, it magically, silently, and automatically gets turned into, now how did I put it? “A highly controlled and structured GOTO.”

A tail-call is a subroutine call. The efficient implementation does not magically transformed into something else; if it doesn't create a stack frame on such a call, it's because one simply isn't relevant.

It's worth reading Ezra's whole post. I especially appreciate his point about confusing semantics with cost model.

Linguistic tools for diagnostics

I've written before about how the stack gets misunderstood as a history thanks to non-tail-recursive languages. Of course, stack traces are indispensable: they're essential for debugging, and they're also useful for reporting crash information from live applications.

But this conflates two very different language requirements in one feature: the need for nested (unbounded, if your language isn't broken) function application, and the need for diagnostics of dynamic errors.

The first is what continuations and stacks are all about, of course: functions can't call each other function calls can't be nested in compound expressions without the language runtime keeping track of the work it has left to do. But the second is an independent need: there's all sorts of diagnostic information that's potentially useful, and the stack just happens to be one source of information that's already there.

Now, as it turns out, it's a pretty useful source of information. And if you happen not to have proper tail recursion, it's even more useful, since it provides a path through the function call graph. But I've been finding stack traces in Scheme less informative, because with proper tail calls, there's less function-call history in the continuation.

I recognize that sometimes the "complexity budget" in language design necessitates using one feature to satisfy multiple requirements. But I'd like to see more investigation of linguistic diagnostics designed independently of existing language features. For example, it might be useful to provide configurable tracing facilities that record program history during runtime, where the tuning of how much gets recorded is completely independent of the space semantics of the evaluator. So you have a properly tail recursive semantics with a flexible tracing facility grafted on top.

What classifies a language feature as "purely diagnostic" might be that it is designed not to change the observable behavior of the program, but merely to report some additional information. Contracts-as-projections is an example.

Update: rephrased my rookie characterization of continuations.

JavaScript completion value: pros and cons

In JavaScript the completion value is the result value of a computation, which may result even from evaluating a statement. Simple statements like

{
  2 + 2;
}

have result values (in this case 4), but so do complex statements like

for (var i = 0; i < n; i++)
  f(i);

Notice that if n is less than [edit: or equal to] 0 in this example, there won't be any computation at all, in which case the statement can't really produce any reasonable value.

I've just figured out how to articulate an intuition I've long felt about the completion value. The great thing is that it mitigates some of the awfulness of statements: even imperative code can still produce values! This means you can have some of the syntactic convenience of statements for writing effectful code, while still producing results. But the thing that always made me uncomfortable was how code like the for-loop above screws with the idea of a tail call. Because the for-loop may or may not produce a value, there's a sort of implicit return happening after the loop.

There might be tricks you could pull using something like continuation marks to allow tail position inside of loops, but I think a simpler answer in a JavaScript with proper tail calls would be to say that loops do not preserve tail position. So essentially tail position would include the last statement in a block, the arms of an if statement, and the arms of a conditional expression, and that's pretty much it. Inside a try-block, a loop, or a switch (because of the reliance on break) there simply wouldn't be any tail positions.

Note that a) JavaScript doesn't have tail calls, and b) the only places where you can even observe the completion value of a statement are at a REPL or with eval. But I think JavaScript could have proper tail calls (potentially), and I've always wondered whether the completion value should remain a hack isolated to eval or actually see its way into the design of other features for JavaScript.