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

https://www.youtube.com/watch?v=-PX0BV9hGZY

202 35 5 years ago

progre• 5 years ago

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

bjoli• 5 years ago

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.

amelius• 5 years ago

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.

mourner• 5 years ago

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!

jpetitcolas• 5 years ago

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! :)

saagarjha• 5 years ago

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

sitkack• 5 years ago

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.

cben• 5 years ago

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.

wffurr• 5 years ago

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

leoc2• 5 years ago

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

YesThatTom2• 5 years ago

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

vasergen• 5 years ago

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

qsort4• 5 years ago

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.

swiley• 5 years ago

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

dan-robertson• 5 years ago

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.

ollran• 5 years ago

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

MikeHolman• 5 years ago

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.

booleanbetrayal• 5 years ago

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?

linkdd2• 5 years ago

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.

moonchild• 5 years ago

You can generally get around that with CPS.

linkdd2• 5 years ago

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

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

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

Related Stories