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

51–60 of 72 posts

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

#51

Post by Spivak »

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…

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 shouldn't really be in the business of 'do what I mean not what I say'.

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

#52

Post by Spivak »

goialoq wrote: post #42
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…

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?

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

#53

Post by mannykannot »

_pmf_ wrote: post #33
catnaroek wrote: post #29

Earlier quoted context omitted.

> As I understand it, this syntax was developed because of limitations of the JVM w/r/t TCO. This doesn't make sense. Tail calls don't need any virtual machine support whatsoever: they're translated into jumps by the compiler . The real problem is a lack of willingness to translate functions into anything other than JVM methods, because “compatibility“, but that is a political issue, not a technical one.

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).

If I understand your point correctly, it is not a problem. If your TCO-ed recursive function calls Java functions, they will expand the stack temporarily, but it will all be popped back to your stack frame by the time they return. It is no different than if you made the same calls from an equivalent non-recursive function.

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

#55

Post by Peaker »

Jach wrote: post #28
mikeash wrote: post #15

Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive…

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…

This optimization changes factorial from:

5 * (4 * (3 * (2 * 1)))

to:

(((1 * 5) * 4) * 3) * 2

It relies on the commutative and associative nature of integer multiplication.

This means it's quite a brittle optimization -- it shouldn't really work for floats, for example, which aren't associative at multiplication. And it wouldn't work on any operation for which the compiler does not know the associativity.

So while it seems general -- it's quite specific and not widely applicable.

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

#56

Post by nybble41 »

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…

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 not because it was executed "exactly as written", but because the compiler inserted something beyond what was written.

The Scheme approach of mandating the use of tail calls for every call which occurs in "tail position" is the correct one, in my opinion.

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

#57

Post by Spivak »

nybble41 wrote: post #56
Spivak wrote: post #51

Earlier quoted context omitted.

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…

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 detects certain properties of your code is the definition of an optimization that at least in theory shouldn't be relied on to produce correct code.

A more correct design, I think, would be having a 'replace' keyword for function calls instead of return that causes it to replace the stack of the caller. Then the behavior is no longer an optimization but behavior. Now you have the best of both worlds. The compiler can even warn you about when you might want to use replace rather than return.

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

#58

Post by catnaroek »

denisw wrote: post #34
catnaroek wrote: post #29

Earlier quoted context omitted.

> As I understand it, this syntax was developed because of limitations of the JVM w/r/t TCO. This doesn't make sense. Tail calls don't need any virtual machine support whatsoever: they're translated into jumps by the compiler . The real problem is a lack of willingness to translate functions into anything other than JVM methods, because “compatibility“, but that is a political issue, not a technical one.

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.

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

#59

Post by catnaroek »

ajross wrote: post #43
catnaroek wrote: post #30

Earlier quoted context omitted.

Structured looping constructs are rather removed from how a machine works - not that this is inherently a bad thing. The way it actually works in a physical machine is via jumps into code that has already run, i.e. self-reference, i.e. recursion.

A loop can be turned into branch-based code with an absolutely trivial transformation (e.g. evaluate the test, branch to the end if false, branch back to the start at the end), I don't quite know what you mean by that. 3GL compilers were available with working looping syntax within years of the first programmable computers. FIVE decades later, and as this thread proves, we still don't have general algorithms to turn…

> It's absoultely not true that it's equivalently complicated to tail recursion detection.

Tail recursion doesn't need to be “detected”. The correct implementation of all tail calls, recursive or otherwise, is to overwrite the current activation record, rather than save it.

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

#60

Post by btilly »

goialoq wrote: post #48
btilly wrote: post #2

This is an old debate. On the one hand with tail calls you can write recursive code and find that it runs fast without excessive memory. 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 t…

The OP addresses that concern with a link to https://www2.ccs.neu.edu/racket/pubs/cf-toplas04.pdf

That is a different concern.

That paper is about implementing security models based on what is supposed to be in the stack. My concern is about emitting a debugging stack backtrace on error.

If you are concerned with a security model, it is nice to know that you can remove the stack and prove that the security model is satisfied. But you can't provide a programmer with a record of stack frames that you do not have.

Post reply on HN