Tail Call Optimization: The Musical (2019) [video] | Hacker News Reader

Tail Call Optimization: The Musical (2019) [video]

youtube.com

202 pointsfelipemesquita37 comments

One of my favorite tech presentations ever! So much uplifting enthusiasm, witty and whimsical humour and good taste in the songs, love it. Really happy that it belatedly got on the HN frontpage — it really deserves more views. Go Anjana & Natalia!

Cute! Major props to the two for the execution :)

Sadly, these days Safari is the only engine that does TCO. It also keep track of a decent number of frames (currently 128). For more details on the implementation (called Shadow Chicken), see https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-....

Tail calls are coming to Wasm.

Aside, calling tail calls TCO makes it sound like it is just an optimization, which it is not. Tail calls enable beautiful control flow inside of state machines. It is a new fundamental capability and not an optimization.

It makes a big difference when a language spec (such as Scheme) requires it. If only some implementations have it, and you can't assume it when coding, then it's "just an optimization". https://en.wikipedia.org/wiki/Tail_call#By_language has a list.

Some backstory on the "disastrous meeting" that led to the abandonment of TCO by every browser vendor other than Safari here: https://stackoverflow.com/questions/54719548/tail-call-optim...

This is wonderful, big props to the girl with the less trained singing voice for going through with it.

I am a good singer (as in: I have done it for a paying audience of about 1000 and gotten away with it). That was in a format where singing was expected, and with an audience primed to whatever I was doing.

I was nervous, since I am not used to singing like that (I am a professional bassoon player, working full time in a symphony orchestra). The risk of me bombing was rather small. This thing is different in just about every way.

Would I stand up and sing in a tech conference? Not without vomiting before going on stage (not sure whether that is an exaggeration for comic effect). It requires more than just a little chutzpah.

Yeah, from a mental perspective it's probably closer to stand-up comedy than a singing performance. Also you've got to enjoy it because otherwise, what's the point.

One of the funniest and clearest explanation I've ever seen! That's a must-see talk for all JS developers! Congrats Anjana and Natalia! :)

That was awesome. I imagine a huge amount of time was spent in putting that together, and it was well worth it. Who knew TCO could be so approachable?

Yep Tail Call "Optimization" is nice. But what about recursive functions that cannot be tail call "optimized"?

First example that comes to mind is the Tower of Hanoi algorithm:

  def toh(ndisk, source, via, target):
    if ndisk > 0:
      toh(ndisk - 1, source, target, via)
      target.append(source.pop())
      toh(ndisk - 1, via, source, target)

The function calls itself 2 times. Same thing is the fibonacci function which relies on the 2 previous results.

Here, you'll certainly need memoization and other techniques to not blow up the stack.

You can generally get around that with CPS.

Continuation Passing Style[1] for those like me who are bad with acronyms :)

[1] - https://en.wikipedia.org/wiki/Continuation-passing_style

I didn't know that nodejs supports TCO under the flag (like on video), but unfortunately it was only for versions from 6 to 8. Curious why did they removed it

In a practical working environment it creates more problems than it solves.

It's an optimization that effectively turns non-working code into working code, in ways that aren't always obvious or predictable and possibly in different ways across different compilers/interpreters.

I'd rather the code blow up in my face immediately than spend time wondering why it gets optimized on engine X and not on engine Y, or why seemingly trivial code changes cause the function to have drastically different runtime behavior.

Clojure did this right. No TCO, loop/recur construct instead.

As a side note at the cost of being snarky, it's also probably a good thing that developers who get overexcited about recursion are being encouraged to use proper functional idioms instead of abusing it.

I feel like tail calls are pretty obvious, the c++ grammar even explicitly calls them out.

This is a magic vs. no-magic thing. TCO is a magical thing that implicitly changes the behavior of code with the same syntax. The code says the stack should blow up, but the compiler saves you from it.

I'll side with the Python teaching that explicit is better than implicit. If the code says the stack will blow, then the compiler/runtime should not try to avoid that.

There's nothing magical about a language that says that a tail-call will reuse the same frame/record/instance. It's only magical and unreliable when it's not in the language spec.

And a well-defined TCO guarantee would probably not rank very high on the already long list of things that make it ... a bit tricky to discern the performance of a function from looking at the text of the function body.

It's not any more "magic" than garbage collection. The runtime figures out when memory is no longer required and frees it, through perfectly well-defined and easy-to-model rules. The code doesn't "say" the stack will blow because a finite stack isn't a language guarantee - it's simply an inconvenient fact of life.

Eh, kinda. They are obvious modulo a lot of things, such as what definition of tail call your compiler is using and what optimizations it performs.

Your comment piqued my curiosity and I made a little experiment :)

The following function:

   int rec(int n) {
       if (n < 1) return 0;
       return 1 + rec(n - 1);
   }

will get TCOd by gcc but not by clang (!!)

I don't know, probably I'm not smart enough for TCO, but I just don't want to work like that. It's a minefield.

That's not a tail recursive call.

That's precisely the point.

I'm confused, how are you testing TCO by giving the compiler a non-tail call?

Would you mind sharing the compiler versions and flags used? I tried to look at it in godbolt, but gcc 10.2 -O and clang 11.0 -O look pretty much the same. On the other hand, I know pretty little about C and its compilers ;)

clang 11.0, gcc 7.4, O2. I did that with whatever was already installed on my machines, YMMV.

However, for -O3 on ARMv8, LLVM generates pretty good if slightly inscrutable code [1]:

  rec:                                         // @rec
    bic     w0, w0, w0, asr #31
    ret

That's taking the sign bit, replicating it to 32b and then using it as a not'd mask.

  negative numbers:
     w0, asr #31     => -1
     bic w0, w0, -1  => and w0, w0, 0          => ret 0

  positive numbers:
     w0, asr #31     => 0
     bic w0, w0, 0   => and w0, w0, 0xffffffff => ret w0

gcc is also pretty good [2]:

  rec:
        cmp     w0, 0
        csel    w0, w0, wzr, gt
        ret

[1] https://godbolt.org/z/q9hM7z

[2] https://godbolt.org/z/6rbE5e

It doesn't get TCOd, the compiler simply recognizes what it does and optimizes it. It does literally same thing with the code below.

  int count(int n) {
      int res = 0;
      for (int i=0; i < n; i++) res++;
      return res;
  }

I think I mostly agree. When TCE isn’t guaranteed, it seems pretty bad to have code that runs fine in one engine but blows up the stack in another. When it is guaranteed it’s still hard because modifications to code may break TCE and so as well as knowing what those things are (eg wrapping in a try block), you need to be careful about every change that breaks TCE to make sure that the code isn’t relying on TCE. Also I think JS might have extra problems due to eg arguments.caller.

In languages which do have guaranteed TCE like scheme or ML variants, I think I would rather see some way to explicitly say “this is a tail call which should be eliminated” or “all recursive calls to this function should be tail calls” and then have the compiler complain if you have a call which should be eliminated but isn’t in tail position. I think the reason for clojure not doing TCE is that, in general[1], it is a global optimisation (not possible by simple syntax transformation) that the jvm doesn’t do. So clojure didn’t really have a choice in whether or not to have TCE.

[1] it is more possible to transform recursive or mutually recursive code into iterative code, but the latter becomes hard in the face of a dynamic language where functions can be redefined and impossible to do locally for all tail calls.

Clojure does not optimize tail calls because JVM does not support it.

Thought there's extension enabling JVM tail optimization?

Kind of. This comment summed it up well: https://news.ycombinator.com/item?id=26298891

Proper Tail Calls (PTC) were a problematic JS feature, and calling it "Optimization" is a huge misnomer. Only JavascriptCore (Safari) ever enabled it.

In many cases PTC causes tail calls to be slower, and it messes up stack traces. This would happen even if a developer doesn't want/need tail calls. So it was a feature that would degrade performance and debuggability of existing websites to allow new code to use a more recursive style of programming.

The main performance problem comes when you have tail calls that need to grow the stack. The engine will need to do work to adjust the stack frame.

In languages like C++, the compiler chooses to do tail calls when it improves performance, but with tail calls as a language feature, engines have no choice in the matter and had to do it even when they would significantly increase call overhead.

On top of this, there there were a number of implementation issues and corner cases. For example, most engines have some extra code layer for marshalling cross-site function calls that couldn't be removed. I also remember there being issues with Windows x64 ABI/stack frames. Tail calls from interpreter into JIT code were another implementation headache.

All this added up to have JS engines basically boycott the feature.

How did I miss this in 2019? It is so excellent!

I see Broadway is reviving a '70s production again. ;) TCO is about the same vintage as Chicago.

Reply on news.ycombinator.com