(Looking at) Functional Programming in Assembly

While Functional Programming usually happens quite far away from Assembly programming, in order to get functional programs performant, quite some tricks are used that have effects that reach down into the dark abyss of Assembly. In this talk I want to focus on the optimizing strategy "Tail Call Elimination", a compiler optimization of particular importance for recursive function calls. Every functional programmer will tell you that writing your code using tail recursion (it doesn't matter whether you know what that is, you'll see then!) or using Haskell's "foldl" is "generally faster than foldr (Terms and Conditions apply)". But even seasoned developers often struggle explaining why and quickly resort to pointing to benchmarks or giving some vague answers around "you need less stack". In this talk I want to introduce you to what recursion is, some of the reasons why it's computationally expensive, what tail recursion is and why it's better, and why tail call elimination makes it even more awesome. We will go through some example programs implemented in Assembly (for those who ask: I'll use x86 and maybe aarch64 examples) where we, step-by-step, transform our function from head recursive to tail recursive and then will go further by eliminating the recursive call altogether.