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

31–40 of 72 posts

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

#31

Post by adrianratnapala »

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…

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

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

#32

Post by adrianratnapala »

catnaroek wrote: post #30
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…

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.

My way of saying the same thing is that there is surprisingly little difference between the recursive and iterative models when you start breaking things down.

Indeed, if I were to add an explicit tail syntax to some language, it would probably involve the "goto" keyword.

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

#33

Post by _pmf_ »

catnaroek wrote: post #29
dghf wrote: post #27

Earlier quoted context omitted.

> Why don't languages give tail calls their own syntax rather than making it an optimization? Clojure does exactly that: (defn gcd [x y] (if (zero? y) x (recur y (quot x y))) You can also recur with TCO to an explicitly labelled point within the function (effectively creating an inner, anonymous function): (defn factorial [n] (loop [n n, fac 1] (if (zero? n) fac (recur (dec n) (* fac n))))) As I understand it, this s…

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

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

#34

Post by denisw »

catnaroek wrote: post #29
dghf wrote: post #27

Earlier quoted context omitted.

> Why don't languages give tail calls their own syntax rather than making it an optimization? Clojure does exactly that: (defn gcd [x y] (if (zero? y) x (recur y (quot x y))) You can also recur with TCO to an explicitly labelled point within the function (effectively creating an inner, anonymous function): (defn factorial [n] (loop [n n, fac 1] (if (zero? n) fac (recur (dec n) (* fac n))))) As I understand it, this s…

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

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

#35

Post by catnaroek »

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

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

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

#36

Post by phkahler »

I'm not a fan of this style of coding. It's not just the stack space. When you call methods all over the place it can result in inefficient code. And yes, I understand that I wrote "can" in that sentence. We're talking about a case where the author wants the compiler to be even smarter than it already is. I guess that's my point. Using these kinds of abstractions results in a reliance on the compiler to make things efficient. OTOH using abstractions can make things simpler and more understandable for the programmer. But there's that word "can" again.

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

#37

Post by jcelerier »

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

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

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

#38

Post by Jach »

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…

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.

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

#39

Post by pjmlp »

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…

In Scheme it isn't just an optimization, it is an actual semantic requirement.

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

#40

Post by phkahler »

rbehrends wrote: post #5

There are a number of problems with this argument, but the biggest one is that most such calls will not actually be tail-recursive. The very specific `adjoin` example that has been provided only works with `contains` not being in a tail position because `or` is assumed to use short-circuit evaluation, and because the author is apparently willing to live with a set membership test that has linear time complexity. We c…

"is wrong, simply because efficient and actually usable implementations may exhibit totally different requirements w.r.t. tail recursion and what should be in an interface."

Thank you so much for that!

Post reply on HN