Hacker News Reader

Comment by dewitt | Hacker News Reader

Clojure also doesn't support TCO, and from what I can tell the explicit loop/recur is sufficient, which also has the advantage that it is very clear (i.e., the compiler will tell you) when TCO is not being invoked. With implicit TCO you might think you're getting the benefit, only to have a stack blow up unexpectedly at runtime with an edge-case input.

View on HN

Especially with destructors. Whenever you have a destructor in the frame, you're not in tail-call position. This means that tail-call positions in Rust are going to be few anyway.

Does this mean Rust's `be` keyword can be retired? :)

Yes.

That calls for an interesting optimization: Using escape+liveness analysis you could probably call some of those destructors earlier.

The problem is that TCO in the sense we're talking about isn't really an "optimization". It's a language feature that removes the need for explicit looping constructs by allowing you to write them as higher-order functions instead. This only works if the guy writing the higher-order function can prove that the compiler will successfully "optimize away" the tail call, or if he doesn't care whether the program dies with a stack overflow. If the success of TCO is dependent on which conservative approximation the compiler is using for escape and liveness analysis, then people who care about their programs continuing to run will demand explicit looping constructs anyway.

There are three separate inventions in Scheme that work this way. Closures give you objects without an object construct, tail-call optimization gives you loops without looping constructs, and call/cc gives you threads, exceptions, and backtracking without thread, exception, or backtracking constructs.

(I mention Scheme because all three of these were, as far as I can tell, introduced in Scheme, and only later adopted by other functional languages like ML, although to be fair, TCO at least falls out naturally from combinator-graph reduction.)

In a sense, Scheme is sort of like a functional assembly language: there are lots of object systems, looping constructs, threads, and exception systems in Scheme, and they aren't compatible with each other. It's sort of like the situation with linked lists in C, where every library has its own linked-list type.

It's exactly the opposite of assembly language in another way, though. By making object instantiation and population implicit, both the compiler and the maintenance programmer have to do extra work to figure out what's an object and what's not, and what the object's fields are. The same is true of loops, threads, and exceptions. In assembly, instead, you have the problem of things being too explicit, thus losing the signal in the noise.

That's my take, anyway. I haven't spent that much time programming in either Scheme or assembly, although I did write an almost-Scheme compiler targeting assembly called Ur-Scheme.

The "assembly language" for ML would actually be the lambda calculus. Scheme isn't really defined unless you're talking about some standard, and the semantics of the language are probably just defined in English.

Hmm, it sounds like you're trying to argue with me, but I'm not clear on what you're saying — some quick responses — hope this helps:

① I did not claim Scheme was an "assembly language" for ML. I said that programming in, reading programs in, and compiling programs in Scheme was like programming in, reading programs in, and compiling programs in assembly language in some specific ways, and very unlike it in others. The relationship between Scheme and ML is that some of the central insights of Scheme were adopted by ML.

② ML defines evaluation order. The lambda calculus does not. Typical ML implementations compile to the assembly languages of actual processors. Can you clarify?

③ I think Scheme is sufficiently well defined for this discussion — it's a family of languages originating in some papers by Sussman and Steele in the 1970s, and continuing through the current R7RS work, including a number of compilers. Several of the standards define the semantics of the language symbolically, not just in English.

Doesn't loop/recur only help in directly self-recursive calls, as opposed to mutual recursion or tail calls to function arguments?

That's correct. It should be possible to have an explicit guarantee of TCO while maintaining the ability to write things that aren't trivially reducible to loops...

Which is +- what Scala allows with an annotation.

No, scala's @tailrec annotation only guarantees that calls that can trivially be compiled to loops in fact are. You can't do better on a standard JVM without jumping through hoops (or, rather, trampolines).

Right. In Clojure you'd use an explicit trampoline for stack-free mutual recursion.

Mutual TCO is really uncommon for what it's worth. Of you need it that bad a trampoline should suffice

Direct mutual recursion is somewhat rare (but useful for encoding state machines, for instance). However, using continuation passing style (and tail calls to a continuation argument) to prevent stack overflow is a common idiom in some functional languages (e.g. when mapping over a binary tree).

Erlang uses mutual TCO everywhere. All actors/processes are state machines with the function they're in being their current state. To switch states, you just tail-call a new function (which doesn't have to be from the same module you were in.)

Reply on news.ycombinator.com