Why does erlang implement iteration by recursion instead of a loop?

erlang
recursion
loop
#1

Hi everyone. I’m beginner with erlang and have a question. Why does erlang implement iteration by recursion instead of a loop?

2 Likes

#2

Because most funtional languages do so.


In my humble opinion, explicit recusrion with passing around the state is much easier to deal with than to mutate variables from an external scope…

3 Likes

#3

Loop requires mutation.

Recursion does not (all values are immutable) as the function just calls itself with new (different) values.

11 Likes

#4

One perhaps not so obvious reason is how the VM decides that a process has used up its time share and needs to be taken off the scheduler. In the BEAM VM, every function call costs one reduction. The default limit on reductions is 2000. At that point, the VM puts the process in the back of the run queue and lets other processes run (this is subject to prioritization as well, so it is not the full story).

One problem with a traditional loop is that there are no function calls. So it could run infinitely in principle, which would mean a loop could monopolize the scheduler. However, since every loop is effectively implemented by tail calling, there is no way a loop can run without consuming reductions.

In a language such as Go with a more traditional loop construct, you need to add a check inside the body of the loop if you want it to preemptively schedule. This is good for the systems latency, but bad for its throughput if that check is inside a tight loop which is taking of lot of time to compute. So to the best of my knowledge it is not enabled by default in Go.

An alternative path is to check on memory allocation. But a loop does not need to allocate memory either.

19 Likes

#5

Let’s turn that question around: what use is a loop when you have efficient recursion and functional patterns such as reduce?

3 Likes

#6

Yeah… This question remembers me again at the fact that go as well as python are forcing me to think in loops, becuase both don’t to Tail-Call-Optimisations of any kinds and as well have a pretty limited stack size :frowning:

1 Like

#7

One alternative is to think in tail recursion ( à la clojure.core recur) and then convert it to iteration - which may sometimes lead to a cleaner approach to iteration. Then wrap it in a well named higher order function so you can get that loop out of sight (what’s another function call?).


Aside:



Interesting point of view - so lets sell short functions as highly cooperative :lol:

3 Likes

#8

Hi sribe. I don’t sure to efficient recursion. In my knowledge, recursion needs a stack (stack memory is limited) and has to consume iteration times more than twice a normal loop. How is erlang’s recursion different from other languages as c++?

0 Likes

#9

That’s only true without tail call elimination/optimization, which many languages implement even if you could mutate variables. This basically means if your last action in a function is just calling another function without any computation left to do in the current function body the stack entry of the current call will be deleted. So you only grow your stack size if you do recursion in a way when tail call elimination is not possible.

5 Likes

#10

General recursion does require stack frames.

Tail recursive recursion does not require stack frames if the compiler is able to perform tail call optimization.

Elixir/Erlang, Haskell, OCaml, Lisp, Scheme all support tail call optimization.

Most (All?) modern C/C++ compilers support tail call optimization. IIRC this started with the Watcom C/C++ compiler from the late 90s. Even Visual C++ had support for this nearly a decade ago.

Aho and Ullman’s Foundation of Computer Science (The Turtle Book) shows how to go from iteration to recursion and vise versa. I think it is in Chapter 11.

Sussman and Abelson’s Structure and Interpretation of Computer Programs (SICP or The Wizard Book) shows how to go from general recursion to tail recursion via Continuations.

Both books are freely available online!

4 Likes

#11
3 Likes

#12

More or less :slight_smile:

If the last thing you do is call yourself you just reuse the current stack frame – this is pretty good since the compiler will have already worked out stack positions for local variables etc.

4 Likes