Hacker News Reader

Comment by andolanra | Hacker News Reader

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.

View on HN

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.

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.

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.

Reply on news.ycombinator.com