Since I’m spelunking around the new-languages caverns these days, I really ought to mention the long-ongoing and very interesting Fortress, brain-child of our own Guy Steele, who knows one or two things about designing languages.
The project has lots of releases and a very decent blog. I’d meaning to write about this for a while, but it was brought to top-of-mind by Guy’s latest piece there, Why Object-Oriented Languages Need Tail Calls. I’m not so full of myself as to suppose this is provoked by my recent muttering about tail calls.
I’m having a little trouble following the argument because I’ve never studied Fortress, but if I’m reading it correctly, I’d have to ask: wouldn’t a construct like Clojure’s recur meet Cook’s requirements?
Anyhow, it’s a good read.
Contributions
Comment feed for ongoing:
From: Guy Steele (Dec 03 2009, at 12:17)
Thanks, Tim, for the nice mention of Fortress. I was unaware of your post about tail-recursion when I wrote my piece, but it's a subject that seems still to be in the air more than 30 years after Sussman and I first wrote about it.
As for your complaint that you don't like the same piece of syntax to do what you think of as two wildly different things, I have two responses: (1) [theoretical flaming :-)] To me, a function/method/subroutine call always does the SAME thing---transfer control to a function or method or subroutine,
passing arguments as appropriate. Whether control needs to come back again is NOT the job of a function call; it's the job of whatever construct surrounds it. We get confused about this because of a clever and now commonplace optimization that combine these two steps into a single hardware instruction. (2) [practical attitude :-) :-)] But I sympathize completely with your position, and it's perfectly reasonable to want a distinguishing syntax for tail calls in your language of choice. In point of fact, Bill Joy and I lobbied for proper tail call implementation in Java in 1996, before we had completed "The Java Language Specification", and Sun management at the time promised to to it ASAP. I guess the "P" in "ASAP" never happened---more's the pity---but at that time I had proposed that tail calls in Java be flagged with a keyword, and I suggested that the already-reserved keyword "goto" be used for this purpose. With this design, if you want to call method "foo" as the last thing you do but retain your stack frame for whatever reason (security, debugging info, ...), you say "return foo(x,y,z);", or maybe just "foo(x,y,z);" if the return type of "foo" is void. But if you really want a tail call, you say "goto foo(x,y,z);" and there can be no doubt about what you mean.
François-René Rideau made the following comment last April on the subject:
"[I]n programs for which proper tail calls matters, the choice is conspicuously not between proper tail calls and improper tail calls, it is a choice between proper tail calls and explicit central stateful loops. And the absence of debugging information is constant when you transform tail calls into stateful loops." http://fare.livejournal.com/142410.html
And this is why the loop-recur feature of Clojure, though perfectly wonderful for a lot of iterative situations, does not address Cook's concern: it requires the iterative program structure to be "central", that is, all in one place textually, and therefore fails in precisely the same way as the abstract data type approach (using this terminology as Cook does): it prohibits the kind of code refactoring and separation of concerns that the object-oriented version is trying to support.
[link]
From: John Cowan (Dec 03 2009, at 13:22)
Trampolining can do anything that proper tail-calling can do; indeed, the first implementations of Scheme had at their core such a trampoline.
However, basing tail calls on explicit trampolines means that you essentially have an interpreter rather than a compiler: you construct a stack frame, make an indirect call to a procedure, destroy the stack frame, and repeat. Scheme compilers that aren't constrained by having to compile into C simply shuffle the correct values into the correct registers or stack locations and do a direct GOTO to a known location.
Indeed, Scheme compilers actually throw away all information about recursion vs. iteration to start with, transforming everything into recursive calls on anonymous procedures. By then putting all their energy into compiling a tiny number of constructs (if, assignment, procedure definition, procedure call, variable reference, constant reference) very cleverly, instead of into compiling a huge number of constructs more or less crudely, excellent results can be achieved. As long ago as 1975, the first Scheme compiler (by Guy Steele, not accidentally) was able to identify a particular pattern of recursive calling that amounted, given proper tail calling, to a simple while-loop (*whether or not* the user had written it as such), and then generate the exact same machine code that a compiler for a C-like language would produce for an explicit while-loop.
Quux's current point, though, is a different one: with a guarantee of proper tail calling, you can get the benefits of tail-recursion even when the "recursive" call is done through an interface, and so potentially to a method in a different class altogether. Simple tail-call optimization doesn't handle this case, and doing this with a while-loop requires the loop to know how to "get the next instance" for arbitrary classes sharing your interface.
[link]
From: Fred Blasdel (Dec 03 2009, at 15:35)
No, Clojure's recur (nor any other explicit helper it could implement) cannot hope to address the core issue.
The point is to eliminate stack frames and all their copied state everywhere you can. Focusing on the 'call' is distracting you from where the benefit really comes from.
Recursion-loving functional partisans benefit greatly from it, and aren't afraid to say it -- their favorite programming idioms are intractable without it.
UML-loving Enterprise Architects partisan to what they call OOP also benefit greatly from it! Just because they're not calling themselves doesn't mean that they aren't often calling their next 'abstraction' in the tail position. Unfortunately, they are also the most vociferous opponents of anything resembling TCO.
[link]
From: Matt Brubeck (Dec 04 2009, at 06:34)
The Lambda the Ultimate thread on Steele's post is worth reading. One commenter compares TCO to garbage collection, since it's a way to release resources automatically when they are no longer reachable.
Continuing that analogy, programming in a language without TCO is like programming in a language without GC: It forces the programmer to modify code (e.g. by trampolining it) to explicitly manage resources that could be managed automatically in a language with TCO.
[link]
From: MenTaLguY (Dec 04 2009, at 06:37)
I guess the simplest possible way of putting it: TCO lets you split "do-this-next" across abstraction boundaries in an efficient way, even when the chain of "nexts" might be arbitrarily long.
Without TCO there are some things you have no hope of refactoring into another function or class or library in any simple way.
[link]