Is there a way to explicitly write a elixir function to be tail call optimised?

5
votes

In Clojure for example you can use the recur especial form to explicit the intention to use non-stack-consuming recursive calls, and is verified by the compiler. As it's wrote in the Clojure docs:

"recur in other than a tail position is an error", "recur is functional and its use in tail-position is verified by the compiler"

In elixir you can define a function as a series of clauses, with recursions calls between them. Is there a way to know for sure that the defined function is going to be tail call optimised?

1
recursionoptimizationclojureelixirtail-recursion
Simple answer is calls are TCO in Erlang and Elixir unless you code them in such a way as to prevent it. Basically if you do anything with the return value of the function, for example adding 1 to the return value, then it's not TCO because a stack has to be maintained. - Onorio Catenacci

1 Answers

5
votes

Compiler doesn't optimize a function. It optimizes a call to that function. It may be the call to the same function inside it, it may be a call to different function, it doesn't matter.

...which isn't the case with Clojure, where recur can only return execution to the latest "recursion point" (be it loop or fn) which makes mutual recursion impossible without "help from the outside", such as a trampoline. It's more like a bandaid than a solution, but the problem is too big and a proper solution would require too much.

Yes, there is a way to make sure it gets optimized in Elixir: it needs to be an actual tail call. That's all.

In computer science, a tail call is a subroutine call performed as the final action of a procedure.

This can easily be determined by visually inspecting the code.

If Clojure were to work this way, the following two definitions would be equivalent:

(defn x [] (x))     ; <- StackOverflowError if called
(defn x [] (recur)) ; <- hangs if called

But if you want to enforce this and fail otherwise, you have to do it either:

  • before compilation, e. g. with static code analyis using some markings for "desired TCO"
  • before deployment, e. g. with tests that would trigger stack overflow

The latter seems more practical, easiest with pure functions.

I haven't found any existing solutions that do that.