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

41–50 of 72 posts

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

#41

Post by pmontra »

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 dies we check the last values of the variables and that's it.

[1] http://rpanachi.com/2016/05/30/ruby-recursion-stack-size-tai...

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

#42

Post by goialoq »

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…

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.

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

#43

Post by ajross »

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.

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 recursive solutions into iterative ones at the compiler level.

It's true that it's more abstracted than machine code. It's absoultely not true that it's equivalently complicated to tail recursion detection.

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

#45

Post by cryptonector »

One would think that by now tail call optimization (TCO) would be understood to be absolutely necessary. TFA makes a very good case, but it's hardly the first or only example of someone making a convincing argument for TCO.

Even in jq we found that adding TCO enabled a number of interesting possibilities. For example, the range() builtin in jq can be implemented as a tail-recursive function (and the version that takes two or three arguments is). There are a number of builtins in jq 1.5 which are made possible and practical only by having TCO. Before we added TCO it just didn't seem that interesting, but it's proven to be quite an enabler.

I can't think of a language that shouldn't have TCO. C/C++ absolutely should have it (and many compilers do). Java should have it (but doesn't). Lisps badly need it and generally have it -- the same goes for all functional (or mostly functional) languages. Python needs it but apparently lacks it[0]. And so on.

Yes, tail calls obscure stack traces by eliding reused frames. This could be ameliorated by leaving a flag in reused frames that could be shown on stack traces to indicate that there are missing frames. Or perhaps syntactic sugar could be used to control which tail calls are to get optimized (since often it does not matter).

[0] https://stackoverflow.com/questions/13591970/does-python-opt...

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

#46

Post by mikebenfield »

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…

> 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 obscure technicality that it's possible to implement a function call without taking up excessive stack space, but to my mind it's a fundamental fact.

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

In what sense is this true? Recursive function: update these variables (in registers or memory) and jump back up to this instruction. Iteration: update this variable and jump back up to this instruction.

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

#48

Post by goialoq »

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

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

#49

Post by sevensor »

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

This is an interesting point -- structured programming has made source code vastly easier to reason about, but at the cost of turning some obvious control structures into optimizations. The upshot is that we don't have some of the really terrible control structures that were enabled by goto. I once had the pleasure of reading through some old Fortran code that freely jumped into various points in the middle of a loop, from outside the loop. Took me ages to figure out what it was doing.

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

#50

Post by andreasgonewild »

mikeash wrote: post #26
cr__ wrote: post #18

Earlier quoted context omitted.

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.

That, or some sort of Forth; the separate keyword also enables calling anonymous functions recursively:

https://github.com/andreas-gone-wild/snackis/blob/master/sna...

Post reply on HN