Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Object-Oriented Languages Need Tail Calls (2011)

eighty-twenty.org

Post reply on HN
Print view View original

61–70 of 72 posts

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#61

Post by tweakism »

Spivak wrote: post #57
nybble41 wrote: post #56

Earlier quoted context omitted.

Despite the name "tail call optimization", the proper implementation of tail calls is not "just" an optimization. Preserving a stack frame for a function which has nothing left to do is incorrect behavior on the part of the compiler which negatively impacts both the time and space complexity of the resulting object code. The code, as written, does not require a stack frame. If the compiled object code crashes it is n…

> nothing left to do is incorrect behavior on the part of the compiler But it's not though. By this token failing to optimize anything could be considered incorrect behavior. Obviously not turning on optimizations makes your program take longer and use more memory. When a function call is made its variables are pushed onto the stack and popped when the function returns. Doing something different when the compiler det…

You suggest literally the same solution that the person you were arguing with suggested!

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#62

Post by sitkack »

adrianratnapala wrote: post #31
Jach wrote: post #28

Earlier quoted context omitted.

Probably because people have concluded that programmers suck at explicitly specifying optimizations, so much so that things like "inline" don't guarantee inlining in certain languages. Furthermore tail recursion elimination can happen as an optimization even when the source isn't clearly tail recursive. For example, GCC can optimize this: int factorial(int x) { if (x > 1) return x * factorial(x-1); else return 1; } t…

I think mikeash's point is that sometimes tail-recursion is not just an optimisation. For example it means I won't overflow my stack even if this thing recurses 10^7 times. Right now, a programmer needing such guarantee must write explictly iterative code. But with explicit tail calls, she can write it recursively if she wants and get a compiler error if something makes it impossible to do the tail-call transformatio…

Everytime I have used a tail call, it was because I wanted the control flow, not the optimization. Optimization is a misnomer for such a powerful construct. I think having an explicit `tailcall f(args)` would go a long way towards assuaging the non-tailers fears.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#63

Post by mikebenfield »

Spivak wrote: post #51
mikebenfield wrote: post #46

Earlier quoted context omitted.

> because if you need "special syntax" to express the fact that your recursively defined function can technically be evaluated in constant stack space, you probably should be writing it as an iterative function to begin with. Why? I find recursive functions are often simpler to understand and write than iteration. Why does the compiler need to stop me from doing so? You write "technically" as though it were just an o…

It is an obscure technicality: your code only works because a compiler optimization makes it work. If a different compiler executed your code exactly as written it would crash. Or another way, two pieces of code that are logically equivalent will succeed or crash depending on whether it's written in such a way that the compiler can recognize an optimization. I'm in favor of having special syntax because compilers sho…

> your code only works because a compiler optimization makes it work. If a different compiler executed your code exactly as written it would crash.

But it's completely arbitrary that you consider this "a compiler optimization" as opposed to "the way the language behaves." The languages you're used to work the way you describe: if the stars are aligned, a particular compiler may do TCO as an extra optimization.

But there is absolutely no reason it has to be this way. It is perfectly possible for a language standard to mandate that TCO must happen and to specify in an easily understood way when it must happen. As Scheme did over 40 years ago.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#64

Post by ajross »

mikebenfield wrote: post #46
ajross wrote: post #25

Earlier quoted context omitted.

> Why don't languages give tail calls their own syntax rather than making it an optimization? Grumpy old man answer: because if you need "special syntax" to express the fact that your recursively defined function can technically be evaluated in constant stack space, you probably should be writing it as an iterative function to begin with. The whole point about recursion as a software engineering paradigm is that it's…

> because if you need "special syntax" to express the fact that your recursively defined function can technically be evaluated in constant stack space, you probably should be writing it as an iterative function to begin with. Why? I find recursive functions are often simpler to understand and write than iteration. Why does the compiler need to stop me from doing so? You write "technically" as though it were just an o…

> Why? I find recursive functions are often simpler to understand and write than iteration.

For simple recursive algorithms, that's true. And those tend to overlap well with ones which don't require assisted tail call tagging or whatever.

Those that do, however, tend to be pretty complicated. And the set of programmers who can understand an interative implementation of them is IMHO rather larger than that which can get their heads around the tail call analysis to know how (and when!) to make it work.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#65

Post by cryptonector »

jcelerier wrote: post #37
steego wrote: post #7

Earlier quoted context omitted.

> On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object. Is that really a concern? If you're writing a loop, do you expect your tools to show you a trace of every iteration in the…

> If you're writing a loop, do you expect your tools to show you a trace of every iteration in the loop? Of course not, because that would be silly. If you really want to trace each iteration, you can add your own tracing. At least you can know at which iteration you are. If iterate over 12 elements and my loop counter is at 134753745, I can pinpoint what went wrong much more easily.

No, that's only if you have a loop counter. And you can have a "loop" counter with function calls too.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#66

Post by adrianratnapala »

Jach wrote: post #38
adrianratnapala wrote: post #31

Earlier quoted context omitted.

I think mikeash's point is that sometimes tail-recursion is not just an optimisation. For example it means I won't overflow my stack even if this thing recurses 10^7 times. Right now, a programmer needing such guarantee must write explictly iterative code. But with explicit tail calls, she can write it recursively if she wants and get a compiler error if something makes it impossible to do the tail-call transformatio…

There's an interesting idea here that I wonder if any non-academic language has tried: annotating your expected big-O time and space complexities for a function. I wouldn't expect much compiler support except for trivial cases though due to the halting problem... AFAIK academic attempts at automated program analysis go back to Knuth and his students in the 70s, no idea what the state of the art looks like.

I expect the trivial cases are the common ones for big-O.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#67

Post by ernst_klim »

Spivak wrote: post #52
goialoq wrote: post #42

Earlier quoted context omitted.

How is a keyword (such as OCaml's 'rec') less clear than rewriting the whole function in an iterative form, with junk like temporary loop variables? > mapping more obviously to the behavior of actual machines we use to execute our code. There's a reason we usually don't write in assembly.

Should the compiler do what you mean or do what you say? Is it good design to have a system where your code only works because the compiler was able to recognize an optimization? Why not make it explicit?

>Why not make it explicit

Because we want programming languages to hide the hardware complexity behind elaborated semantics. Programming languages are for humans, not for machines.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#68

Post by pjmlp »

catnaroek wrote: post #58
denisw wrote: post #34

Earlier quoted context omitted.

You don't need VM support for tail self-calls (which is exactly what Clojure supports with `recur`), but you sure do for optimizing tail calls to other functions. There is no way in the JVM to say "replace my stack frame with a new one for that other method and execute that", especially not one that gives you a useful stacktrace for debugging.

> There is no way in the JVM to say "replace my stack frame with a new one for that other method and execute that" Nor does there need to be one, because translating function calls to jumps is the (AOT) compiler's business, not the VM's.

The CLR has byte codes for tail calls, properly named .tail..

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#69

Post by pjmlp »

catnaroek wrote: post #35
_pmf_ wrote: post #33

Earlier quoted context omitted.

I don't think it's that easy. Clojure code calls into Java libraries, and these are regular Java functions so you cannot reuse the same stack frame for these. Pure Clojure code, on which you could perform arbitrary transformations, is quite rare (does not exist at the moment, since the core datastructures are written in Java).

> Clojure code calls into Java libraries, and these are regular Java functions so you cannot reuse the same stack frame for these. Somehow, programs written in can call routines written in C (of all languages!) without any problems. So I stand by what I previously said: the problem is political, not technical.

They do so, by having a FFI marshaling layer that creates a stack frame the way C expects it, which is in full control of the language runtime, something that languages that pretend to be Java cannot do on the JVM.

Eventually one could do some tricks with invokedynamic, but I doubt the performance impact would be worthwhile.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#70

Post by rurban »

pmontra wrote: post #41

Ruby's got TCO since 1.9 but it must be enabled at runtime in a pretty ugly way [1]. I'm also working on Elixir which has TCO and it's the basis for running server processes: the server function calls itself passing the server state as argument. I don't see why OO languages shouldn't do the same. The argument about losing the stack trace is pretty weak. Nobody wants a million stack frames to debug. If the program die…

Yes. The same argument can be made against fork(), that fork makes debugging too hard. And we don't know if the value we want to inspect is a common one (before cow) or an already copied. So do we forbid fork()?
Post reply on HN