Hacker News Reader

Comment by pekk | Hacker News Reader

I'm puzzled: if Rust and Clojure won't support TCO and they are both cool, why is there such bitter complaining every time it comes up that Python won't support TCO?

View on HN

I can't speak for Clojure, but Rust's rationale for omitting TCO is based on sound engineering issues (as articulated) whereas Guido's sole reason for omitting it (as far as I've seen) is that you lose stack trace information, which is considered something of a red herring (as you can always selectively disable TCO for debugging, and there are ways of retaining stack information anyway.) Note that the original article here is quite disappointed that they can't include TCO, because it would be a valuable tool and allow for different, efficient styles of programming.

Amusingly, "losing stack trace information" is among the reasons the JVM doesn't do TCO -- it needs to keep it around for the security manager to do its thing. Its especially annoying there because references are held by higher stack frames and prevent GC, and the destructor excuse isn't present.

> it needs to keep it around for the security manager to do its thing

Haha. As if the JVM needed proper tail calls to get owned every other week. :-)

Anyway, the discussion is pretty much moot, because "JVM" doesn't really refer to specific implementation. If one cares about proper tail calls, use an implementation which supports it.

Does the JVM get 'owned every other week'? Or are you thinking of the JRE?

> Haha. As if the JVM needed proper tail calls to get owned every other week. :-)

Correction, the JVM that is made available by Oracle, and most people wrongly think it is the only one.

There are tons of JVM vendors out there.

Which I more or less already said with

> If one cares about proper tail calls, use an implementation which supports it.

Right?

I would say yes, but your remark about getting owned is Oracle specific hence my comment.

I can't answer fully for Clojure's reasons for not supporting TCO, but it will at least be fundamentally rooted in the fact that the JVM, as a platform, does NOT support TCO.

Scala is usually the language brought up as a counter argument here, but Scala has the same limitations as Clojure - the JVM can't do the TCO. Scala's compiler tries, with certain types of tail calls, to optimize via (I believe) a trampoline – it reduces those calls into a loop, so they are no longer a function call.

But, only certain types of calls (specifically, the last line of code in a recursive function must be a call to the hosting function) can be TCO in Scala. There is an annotation, scala.annotation.tailrec, which can be placed above a method you want to tail recurse.

@tailrec does not, however, "force" the compiler to do TCO – it simply forces compilation to fail if the method in question cannot be Tail Call Optimized. It's a developer hook for saying "I realize the compiler tries to do TCO where possible, but I require this method to be trampolined". If it can't be, you'll get a compilation error with details on why the TCO failed.

Scala compiles direct tail recursion the a jump to the start of the function (jumps within a method are possible on the JVM) without any trampoline.

So @tailrec tells the compiler to compile this call to an unconditional jump.

> the JVM, as a platform, does NOT support TCO.

And the x86, as a platform, does?

What, specifically, does the JVM do to make TCO more difficult than it would be in the machine code of your choice?

> And the x86, as a platform, does?

"It's complicated."

http://stackoverflow.com/questions/105834/does-the-jvm-preve...

Yes, the x86 instruction that implements TCO is called JMP. The JVM doesn't have an equivalent instruction; you can only jump around inside a single method, not to the beginning of another method.

> The JVM doesn't have an equivalent instruction; you can only jump around inside a single method, not to the beginning of another method.

OK, why do functions in the source language have to translate directly into methods at the JVM level? Purely for debugging?

The JVM also doesn't (I'm fairly sure) have an indirect JMP instruction, which means you can't compile a polymorphic source-language method call into a JMP inside of a single generated method. Instead you have to use a call to a method. That means that tail-calls to functions passed as parameters (rather than functions that can be statically bound at compile time) can't use JMP.

The “JVM” can use any instruction it wants to use.

If you want a runtime with proper tail calls, use a implementation which supports it.

I'm talking about the bytecode instructions standardized in the "JVM" specification. The "JVM" has to implement the semantics of the instructions found in your bytecode program, or your program won't run. Your bytecode program can only use bytecodes defined in the "JVM" specification, or it won't run on the "JVM".

There is no need or reason to change or add any bytecode instructions to support proper tail calls.

Take standard class files and execute them on a runtime with proper tail calls. Done. Works.

Which JVMs support proper tail calls? Doesn't this violate requirements of the JRE?

For instance oss.readytalk.com/avian. Why should it?

Because the security manager needs to be able to introspect the stack. Avian isn't a JVM; it's "designed to provide a useful subset of Java's features" and can run some Java code.

> Because the security manager needs to be able to introspect the stack.

Not allowing certain “optimizations” in security-sensitive contexts is perfectly fine. In fact, this is exactly what Avian, the CLR (and pretty much everyone else) is doing.

> Avian isn't a JVM; it's "designed to provide a useful subset of Java's features" and can run some Java code.

Now you're talking about legal aspects. Frankly, I'm not interested in discussing those.

Avian is a JVM for all practical purposes. If you disagree, please provide a test-case which runs on HotSpot but not on Avian.

It's actually possible to implement the stack inspection in a tail-call-friendly way (along the lines of Racket's continuation marks IIRC), though AFAIK nobody does it.

JVM interop. You can't call a Scala function from Java unless it's somehow addressable as a Java method, so Scala implements functions in terms of Java methods. The JVM, for better or worse, is largely built around Java's object model - you can do your own weird stuff, but you won't easily be able to interop with Java code or benefit from HotSpot's optimizations.

For better or worse, Scala does do quite a bit of work to go beyond Java's object model.

A debugging switch that, when enabled, turns a valid program into an invalid one is madness.

Python has decided to place very conservative requirements on what an implementation's stack must be capable of. This might indicate a certain lack of ambition but it's a justifiable engineering tradeoff.

There are better alternatives to said debugging switch for examining the stack of tail-call-optimized programs, c.f. Clements and Felleisen's 2004 paper, "A Tail-Recursive Machine with Stack Inspection." The debugging switch is merely the simplest naïve option.

Essentially, your engineering tradeoff boils down to, "It's easier (for implementers) to omit TCO." That is actually a very reasonable and rational position, as simpler implementations are less likely to have bugs and have a lower creation cost. However, I still hold that the advantages of TCO outweigh the concern about its implementation. (Also, I do not believe that Python does place conservative requirements on an implementation's stack, as a conformant Python implementation must also implement generators; I regard this as roughly on par with TCO's complexity.)

Complexity and stack space usage are two very different things. CPython does indeed place (very!) conservative limits on stack depth, and it also implements generators. I haven't looked at the generator implementation, but it has a number of limits that make it easy to implement — the main one is that generators don't have their own stacks, so can't yield from inside a function they call, the way e.g. Lua coroutines or (effectively) Icon generators can.

I'm sorry, I made something of a terminological error. When I said 'complexity', I was referring to complexity of implementation, not algorithmic time or space complexity. My intention was to assert that implementing generators and implementing tail-call optimization are both endeavors of roughly the same order of engineering difficulty (as the mechanism used to implement TCO is quite simple) and not to compare the stack space required by each.

I also should clarify that at this point, it's likely not reasonable to expect Guido or the Python community to ever turn around and decide to implement TCO, as the current engineering effort required to add TCO to all active implementations of Python is much larger in comparison to the engineering required to add it at an earlier stage. I regard this as a failure of the langauge design from the start, but having made their decision I don't fault the Python community for sticking to it.

I was responding to your "I do not believe that Python does place conservative requirements on an implementation's stack", in response to bcoates's statement that it does, nothing about complexity. I was just trying to clarify (my interpretation of) what he said.

Actually, in Python 3.3 they can (sort of). See PEP 380: http://www.python.org/dev/peps/pep-0380/

Thanks! I didn't know this, and it should remove a log-N factor from a lot of algorithms :)

I believe that both C# iterator-functions and python generators are designed with enough limits that they can be implemented as syntax sugar: you lift the generator function's locals into an object and decompose the function body into a state-machine.

> A debugging switch that, when enabled, turns a valid program into an invalid one is madness.

You mean like gcc's -Werror? Or enabling asserts? Both of those seem useful to me.

Since the compiler didn't succeed at compilation, no program was generated at all. Removing asserts is really compiling a different program.

-Werror isn't a "debugging switch". It should be enabled at all times, for development builds and production builds.

If compilation warnings are given, then the responsible thing to do is to assume the program is invalid, at least in certain situations. Fix the code, avoid the warnings completely, and that's that.

There are remarkably few cases where compilation warnings can or should be ignored.

Because Rust and Clojure have have better excuses, maybe?

Rust is supposed to be as fast as C/C++ and TCO will slow it down.

Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines).

Python doesn't support TCO because... it screws up stack traces?

We'll just have to put Rust up against MLton and see if tail calls really are so expensive.

If I understand it correctly, the Rust issue is that tail calls are expensive in the context of LLVM and the calling convention that they are using. MLton (like Manticore, which I work on) uses a different code generation backend and calling convention entirely. And neither of us worry about "destructors" or, in general, things that happen at every return point.

Though, interestingly, in the context of a CPS-converted program, destructors would just be the next continuation called on the way to calling the procedure previously "returned to." Under our (Manticore) calling convention, we would just jump to each of those continuations and wouldn't have to grow stack (though in our case, it's keeping around heap frames, as we're not stack-based), and would have the same next allocation and instruction-level behavior as a tail call.

That said, if you think tail calls are hard to debug, CPS-converted programs would destroy most people's will to live. No stack backtraces, except in debug modes, with 5-10x performance penalties.

I never thought tail calls were hard to debug, but can you can keep text offsets to the original tokens through the CPS transform? Usually with typed languages that's enough information to figure out what went wrong or at least what to log.

Also, I'm not sure why the entire library needs the same calling convention when it's such bad form to expose all of your functions anyway.

You can keep the original tokens. The challenge with debugging such programs is really the integration with the rest of the optimizations. CPS transformation turns your program into a ton of tiny functions. Then, any reasonable optimizer will do a huge amount of inlining. Attempting to do trace-based debugging bounces you from one subexpression in one function to another and so forth. Especially when you consider that Manticore (like MLton) is a whole-program optimizing compiler, you also get little chunks of library functions we've duplicated like map, foldr, etc.

Worse, we liberally remove dead code, including unused arguments, branches of conditionals we can guarantee are never called, etc. And since it's a research compiler, there isn't really a "-O0". You can turn off individual optimization passes, but guessing what combination lead to something getting inlined or not requires some careful study.

As to why they've chosen what they have with LLVM, I don't know enough to judge. Doing something like ML compilers do with a custom calling convention internally and then a C convention externally is pretty expensive, and ends up putting a massive penalty on C calls (oh, you want to call C? let me move the GC pointer out of the way, set up a fake stack frame for you, etc.). Further, doing it makes register allocation more of a challenge. Many ML compilers like to "pin" certain registers with their own values (e.g., the GC local heap limit pointer) so that we can write custom little blobs of assembly that get emitted in the right places without worrying about substituting in what the _real_ heap limit pointer is, etc. That pinning interacts badly with LLVM, as you can see from the Haskell/LLVM master's paper - they basically had to give up on it and just add their pinned values as extra arguments and then stop emitting code that relied on it being in a sane, typical place.

Hope that helps! I've been thinking about these problems and talking only with other people who do the same for so many years I'm starting to forget which parts are and aren't obvious (or even published/documented).

Very helpful, thank you!

I guess another problem would be that people often complain about how slow these kinds of compilers can be, and if you keep around enough to reconstruct good error messages it would probably make it that much slower.

Most of the time in whole-program compilers such at Manticore and MLton (> 60%, though it depends on the particular program) is spent in the combination of parsing the input source files and running GCC over the generated assembly to produce the binary.

Many compilers (including ours) did not keep around that extra information because even in 2007 (when we started) RAM was a bit scarce. The cost associated with keeping that info around between phases is primarily in the extra working set hit and the resulting GC and especially memory paging issues. Given that it's not unreasonable to expect people to have > 1GB of available physical RAM for the compilation process these days, that's something we should consider changing. Though at this point threading that info through the compiler is probably a couple weeks of dedicated effort to get working correctly.

If you don't have any interesting control operators like call/cc, prompt/control, etc. then it should be possible to track stack-like control patterns after CPS conversion through the compiler and through DWARF (or a custom debugging format). Unless I am missing something it seems that the control operators are the problem, not CPS.

Certainly, that's true! As I mentioned in my other far-too-wordy response, though, if you just CPS convert and run a program, it will be far too slow (5x the funcalls != 5x the fun...). So, it's the combination of CPS conversion and later optimizations --- paired with whole-program compilation --- that make it so hard to debug.

> (like Manticore, which I work on)

Nice! I have had envious eyes for Manticore as a modern replacement for Concurrent ML. Are you guys intending for it to be available for general use or more of a research language?

It's still a research language today. Honestly, we would need to make a fairly major push --- which would freeze all resarch work and publications --- to get to a point where it is ready for general use. We're working on some grant proposals along those lines, because frankly without NSF support (in the context of making it ready for wider use in classes such as CMU's new intro curriculum), it's unlikely we can justify the massive amount of work required to take it from something that PL experts to use to something that, say, MLton or SML/NJ users could pick up and use.

I hate to sound mercenary, but frankly if we can't significantly increase the project from the current number of developers (myself and two part-time undergrads), it's difficult to see how we can make it more generally available. Especially when I lose a couple of months of work every time we double the number of processors in a server-class machine, as there's always either a GC bug or some scalability issue still lurking in the runtime...

> Rust is supposed to be as fast as C/C++ and TCO will slow it down.

TCO doesn't slow programs down. If anything, it might even make them a tiny bit faster. But speed isn't the reason you'd want TCO: you want it as a stack optimization so that tail-recursive functions use constant stack space. Furthermore, although the C specification places no TCO requirement on implementors, it's actually a very reasonable optimization even in C. GCC actually does do TCO in some cases (I'm using 4.5.3, and tail-call elimination occurs with -O2 and higher).

> Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines).

This is true. There was a time when TCO support was slated for Java 7. That time has come and gone; unofficially, it looks like it may make an appearance in Java 9 at the earliest.

> Python doesn't support TCO because... it screws up stack traces?

That's the cited reason, but it's horseshit. As others have pointed out on this thread, it's feasible to simply disable TCO when doing debugging if you need a stack trace. Even fancier, there are algorithms to recover the stack even after the calls have been eliminated (see Lua for example).

"TCO doesn't slow programs down. If anything, it might even make them a tiny bit faster." right, but i think they were saying that, in this case, because of dependencies out of the rust team's control, they would have to use a different, slower calling convention to support proper tail calls.

Well, according to a quick perusal of the LLVM documentation, the only llvm calling convention that allows TCO on all platforms seems to be fastcc, whose main purpose is to have calls that are a fast as possible, at the cost of not being compatible with the slower, but more common calling conventions of C. http://llvm.org/docs/LangRef.html#calling-conventions

What does fastcc do when there are more arguments than registers?

These cases are the reason for Pascal-convention according to Walton. https://mail.mozilla.org/pipermail/rust-dev/2012-January/001...

In that case you can clone the function. Internal linkage calls can use the fastcc calling convention while you leave either a whole clone with the non-fastcc calling convention or a non-fastcc wrapper of the fastcc function for calls from external linkage.

"GCC actually does do TCO in some cases (I'm using 4.5.3, and tail-call elimination occurs with -O2 and higher)."

Only sibling call optimization, as cdecl doesn't allow TCO in the general case. Rust will do this too.

Well, technically, "it screws up stack traces" is the usual excuse given for why the JVM doesn't support it.

Python doesn't optimize any tail calls at all. Rust optimizes sibling calls, which includes all self-tail calls. It's only tail calls to a different function that Rust doesn't eliminate.

I imagine the same people who complain about lack of TCO in Python are also complaining about lack of TCO in rust and Clojure.

Who says they are both cool? HN isn't a single person. It is quite possible that group A thinks rust and clojure are "cool", and group B thinks that languages without TCO (including python, clojure and rust) are bad.

Reply on news.ycombinator.com