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

21–30 of 72 posts

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

#21

Post by jcdavis »

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…

Scala sort of has this with the @tailrec annotation. The compiler will always attempt TCO, but the annotation makes failure to do so a compilation error. (Its not a perfect situation though, since there can still be functions assumed to be tail recursive without @tailrec, and whose behavior can change without warning)

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

#22

Post by stormbrew »

willtim wrote: post #17
Rusky wrote: post #14

Earlier quoted context omitted.

But you can't ever turn it off if you rely on it for loops, which defeats the whole point.

You can turn it off, you just can't process large data sets, as you'd run out of stack space. But who wants to debug with large data sets?

People who are debugging behaviour with large data sets perhaps? :P

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

#23

Post by stormbrew »

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…

Definitely. I think, especially, in the case of retrofitting it into an existing language this is the way to go.

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

#24

Post by javajosh »

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

We even already have a common keyword suitable for this: 'goto'.

heck you don't even need goto, just a labelled break, which is extremely well supported across languages (great comment btw i lol'd)

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

#25

Post by ajross »

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…

> 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 a clearer way to express the problem and thus less likely to be mistakenly implemented. Special syntax is the opposite of clear.

Iteration ain't that hard either folks, and it has the notable advantage of mapping more obviously to the behavior of actual machines we use to execute our code.

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

#26

Post by mikeash »

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

This is how Clojure does it. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/trampoline

Nice. When I wrote that, I was sure there would be some language that had already done it, and I was about 90% sure it would be some sort of Lisp.

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

#27

Post by dghf »

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…

> 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 syntax was developed because of limitations of the JVM w/r/t TCO.

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

#28

Post by Jach »

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;
    }
to this:

    int factorial(int x) {
       int result = 1;
       while (x > 1) result *= x--;
       return result;
    }
(See http://ridiculousfish.com/blog/posts/will-it-optimize.html for other fun optimizations.)

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

#29

Post by catnaroek »

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

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

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

#30

Post by catnaroek »

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

> 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.
Post reply on HN