Call me maybe: talking about Tail Recursion Optimization

1 files changed, 178 insertions, 0 deletions

diff --git a/content/posts/call-me-maybe.md b/content/posts/call-me-maybe.md
new file mode 100644
index 0000000..cbe22d7
--- /dev/null
+++ b/content/posts/call-me-maybe.md
@@ -0,0 +1,178 @@
+Title: Call me maybe
+Date: 2019-01-09
+Category:
+Tags:
+Slug: call-me-maybe
+Lang: en
+Summary: Recursion, stacks and optimizations.
+
+Do you remember what happens when you call a function in your program?
+
+What happens when you make too many nested calls?[^1]
+
+When you call your functions, there some stuff going on in the memory, some
+variables, the program counter and all that, that must be stored somewhere to
+be able to come back to the place you called the function when the function
+ends. Right?
+
+The place where all that is stored is the stack. You already know all this.
+When you call many nested functions, the stack goes pushing more and more data,
+and there's no chance to pop it, so it overflows.
+
+This can happen anytime but there's more risk for that when you call functions
+recursively, because they call themselves many times by definition. In a
+non-recursive program it can happen too, but devices can handle big levels of
+nesting so it's more unlikely to happen (in small devices like microcontrollers
+or so, you have to take care of this too).
+
+This doesn't mean recursive functions will result in a stack overflow always.
+That will only happen when the nesting level is bigger than the stack size.
+
+> You are so stupid the recursive function that calculates your stupidity
+> causes a stack overflow.  
+> — Heard in a computer science class
+
+But this is not always true. There are some optimizations that can change this
+behaviour and allow you to create stack-safe recursions. Let's talk about
+**tail-call optimization**.
+
+Some programming languages implement tail-call optimization, that, if used
+correctly, avoids stack overflows in recursive calls and increase performance.
+First of all, in order to be able to make a tail-call optimization, the
+function **must** have a call as its last action (tail-call). This means **it
+requires to be ordered in an specific way**. Let's see it with an
+(oversimplified) example (in Python, but don't pay attention to the language):
+
+
+    ::python
+    def factorial (a):
+        """ This function does not provide a tail-call, because the last thing
+        to execute in it is a multiplication, not a call """
+        if a == 1:
+            return 1
+        return a * factorial(a-1)
+
+    def factorial_tail (a, acc=1):
+        """ This function provides a tail-call, the last thing happening on it
+        it's a function call."""
+        if a == 1:
+            return acc
+        return factorial_tail(a-1, acc=acc*a)
+
+
+As the comments say, the first function is not performing a tail-recursion, but
+the second is. But, what's the difference?
+
+The main point is the first function, `factorial`, needs to go back in the call
+stack to retrieve previous step's `a` value, while the second function doesn't.
+That's why the second can be optimized and the first not.
+
+The optimization exploits this behaviour in a really clever way to avoid the
+stack overflows I told you before. Tail call optimization just changes the
+input parameters of the function and calls it again, replacing the original
+call with the new call with different input arguments. This can be made because
+the function is written in a way that doesn't need anything from the previous
+step.
+
+Imagine that we introduce a `3` in the first and the second function, let's
+compare the execution. Let's check `factorial` first:
+
+- Call `factorial(3)`
+    - Call ` factorial(2)`
+        - Call `factorial(1)`
+        - Return `1`
+    - Return `2 * 1`
+- Return `3 * 2`
+
+Now with the `factorial-tail` function but without any optimization:
+
+- Call `factorial-tail(3)`
+    - Call `factorial-tail(2, acc=3)`
+        - Call `factorial-tail(1, acc=6)`
+        - Return 6
+    - Return 6
+- Return 6
+
+See the difference?
+
+The `factorial-tail` call doesn't need anything from the previous step, the
+last `factorial-tail(1, acc=6)` function call's result is the same as the
+result of the `factorial-tail(3)` function. That changes everything!
+
+What tail call optimization does is just change the call arguments and keep
+running the same code. There's no need to store anything on the stack, just
+change the function call with the tail call.
+
+Let's optimize the second call now:
+
+- Call `factorial-tail(3)`
+- Replace the call with `factorial-tail(2, acc=3)`
+- Replace the call with `factorial-tail(1, acc=6)`
+- Return 6
+
+This can be stretched further! It can involve different functions! In any place
+where a tail-call is made, even if the called function is a different function,
+this kind of optimization can be done, reducing the stack size and increasing
+the performance.
+
+If you want to read more about this, there's [a great wikipedia page on the
+subject][wikipedia] and you there's [a really good explanation in the book
+Programming in Lua][lua].
+
+
+
+But how is all this handled by the programming languages? You may ask.
+
+The answer is there's not a clear answer, all of them have their own style of
+dealing with this. Let me give you some examples.
+
+**Python**, just to point out the language I chose for the example is no the
+best example of this, has no tail recursion elimination. Guido and the
+Pythonists[^2] argue that tail call optimization alters the stack traces (which
+is true) and that they don't like the recursion as a base for programming, so
+they try to avoid it. In CPython there's no tail call optimization, but they
+don't forbid (they can't!) any other Python implementation to implement that
+particular optimization. There's a really [interesting post by Guido Van Rossum
+about this][guido].
+
+**Lua**, as you've seen in the [previous link][lua], implements proper tail
+calls (as they call them there) and there's nothing the programmer needs to do
+to make sure they are optimized. The only thing is to put the tail calls
+correctly.
+
+**Scala** implements tail recursion optimization at compile time so the
+compiler transforms the recursive call with a loop in compilation time. That's
+interesting because there's a compile time check too. There's an annotation
+called `@tailrec` that can be used to make sure that your function is going to
+be optimized. If the compiler is not able to optimize it will throw an error if
+it has the `@tailrec` annotation. If it doesn't have it, it will simply make a
+standard recursion. In the [annotations tour of the Scala language][scala] has
+some words about `@tailrec`.
+
+**Clojure** is a really interesting case too. Clojure doesn't implement
+tail-call optimization, but it has one (and only one) special form for non
+stack consuming looping: `recur`. This special form rebinds the recursion
+point's bindings or arguments and jumps back to the recursion point. The
+*recursion point* can be a `loop` special form or a function definition. So,
+it's just an explicit call to the tail recursion optimization. Tail call must
+be done correctly too, `recur` is only allowed in a tail call and the compiler
+checks if it's located in the correct place. Also, it has some specific rules
+that must be taken in consideration (multiple arity functions and so on), that
+is better to [read in the documentation][clojure].
+
+
+
+[^1]: Some help: what's the name of the website you check when you don't know
+  how to solve your programming problem?
+
+[^2]: My next music band name.
+
+[wikipedia]: https://en.wikipedia.org/wiki/Tail_call
+
+[lua]: https://www.lua.org/pil/6.3.html
+
+[guido]: https://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
+
+[scala]: https://docs.scala-lang.org/tour/annotations.html
+
+[clojure]: https://clojure.org/reference/special_forms#recur