Erlang: Functions (Part 2).
People are really bad at following instructions and that's where machines beat us easily. Functions are a great way of organizing repetitive steps into things the machine could execute and a human could easily understand and operate with.
Functions shine when it comes to some mass processing. And by saying that I mean loops: what if I want to repeat some tedious work N times? What if I want a machine to work on some task... forever? That's all loops. We could have some function that crops images. It would be stupid to crop each image in a directory ourselves. Instead what we want is to get a collection of all images and then create some kind of a loop over it repeating our function that operate on a single image. That would work, right?
In imperative languages like C you would have a special construct allowing to define loops. In fact, you would have a few variations of loops each serve a different purpose. Erlang is a functional language and as in many functional languages there is no special syntax for loops. Instead, as a developer you're encouraged to use a property of functions to create such control flows like loops. Let me show you an example.
-module(lesson2).
-export([loop/0]).
loop() -> loop().
This tiny piece of code demonstrates us a new concept: we could call the newly defined function right away within the function's body. That's right, you could not only call other functions (defined locally or in other modules) but also call self. Defining something in terms of self is called a recursion. (Note: this might be a very simplified and incomplete definition but it's OK for now)
Recursion is an extremely complicated topic itself and we would get back to it over and over in the following articles. Not to confuse you, recursion is way more complex and powerful than just my naive example of iterating over a collection of files or creating loops. You would learn and master it during your career so get patient.
If you try and execute the above loop example the erl would stuck in an infinite loop. From the user point of view it would look like nothing is happening; unless the REPL would not proceed with the read step as usual. That's because the evaluation process is incomplete and in fact it can't be completed at all. That's how we designed it. Sometimes it could be something what we did on purpose but in some cases it could be done by mistake. If that's the case use ^G (CTRL+G) to terminate the erl session and start a new one over.
Now let's have some fun with the loop function and rewrite it like this:
-module(lesson2).
-export([loop/1]).
loop(0) -> done;
loop(N) ->
io:fwrite("N = ~w~n", [N]),
loop(N - 1).
The loop function is now unary, hence accepting an argument. We assume in the case of the loop function this argument is an integer. Here we define 2 clauses; the first clause is waiting for the argument to be equal 0. If that's the case, an atom done is returned immediately. Otherwise, the second clause is executed. You could see its body consists of 2 expressions.
The first expression is a function call; we're calling the fwrite function defined in the io module and provide 2 arguments. The first one is the format string (you could think about it as a template), the second argument is a list of things (data) to substitute in to the format string. We use here 2 special control sequences: ~w which is to be replaced with the data from the second argument, and ~n which is to be replaced with the new line. If you want to learn more about fwrite you could find it here.
The second expression is again a function call but this time we're calling the loop function itself, creating a recursion. You could also notice we provide a decremented N value as an argument of the loop function. If you now try it in erl you would see this:
1> lesson2:loop(3).
N = 3
N = 2
N = 1
done
In the example above the loop(0) clause is called a base case. The base case is something that terminates a recursion; in the case of the loop function it does work since the first clause is defined in terms of a simple constant value (done) and has no other recursive calls. Any proper non-infinite recursion has one to N base cases; unless you want to form an infinite loop it's essential to reach one of the existing base cases. That's why we tried to call the loop function with the decremented N value: for any positive N we would eventually reach 0 and terminate the recursion. This example of course only works for positive integer values: try it with some negative integer and this function would immediately enter an infinite loop.
It might be extremely hard to understand recursion when you first met with that concept. For those of you who experience such problems it's recommended to try and trace the execution from the entry point till the exit point step by step, substituting some real arguments to the recursive calls. To simplify tracing try and use io:fwrite at least until you master some better instruments.
The ability of expressing bigger things in terms of smaller pieces is an amazing property of functions. Combining this property with recursion we could achieve incredible and unexpected things. Remember the successor function mentioned in the previous article? That's just a thing that adds 1 to its argument. This might be considered a very small and non-important thing but it has long-term consequences (a note: we will discuss it once again in detail when discussing functions and their relation with types).
succ(X) -> X + 1.
pred(X) -> X - 1.
add(A, 0) -> A;
add(A, B) -> succ(add(A, pred(B))).
The successor function has it's opposite sibling that decrements its only argument called the predecessor function. Here we define both the successor and predecessor functions so to reuse them later. Then we define the addition function using recursion. The first clause is a base case terminating the recursion; it simply says if its second argument is zero then the result is the A variable itself.
Now, in the second clause we return the result of the succ function; Erlang provides you with the eager evaluation model, so to compute the succ function it would first need to evaluate its argument, which is the result of the add function in our case. Aha! That's the recursion! If you take a look you would see we're decrementing the B variable when calling the add function. The idea is that eventually B reaches 0 (the base case of the addition) so that would terminate the recursion. Please also note it does only work for positive integer B. Any negative B values would lead you to an infinite loop.
To understand it better we could try and illustrate the evaluation by simplifying expressions. Let me first show you one step of the evaluation assuming we're calling the add function like this: add(4, 3). In this case the initial clause would be skipped since the second argument doesn't match 0. So the second clause is chosen. A is now 4, B is now 3. If we replace the body with the real values we would get succ(add(4, pred(3))). Erlang is eager (remember?) so we can't evaluate the succ function right away, we would first need to answer what add(4, pred(3)) is. The add function also can't be evaluated right away since it depends on the pred(3) which is a simple function. It has no recursion and could be evaluated easily, the answer is 2. Now we have succ(add(4, 2)) and we could enter the add function for the second round. That's one step.
If we continue our mental experiment step by step we would have something like this:
add(4, 3)
succ(add(4, pred(3)))
succ(add(4, 2))
succ(succ(add(4, pred(2))))
succ(succ(add(4, 1)))
succ(succ(succ(add(4, pred(1)))))
succ(succ(succ(add(4, 0))))
succ(succ(succ(4)))
succ(succ(5))
succ(6)
7
Each time we call the add function with some non-zero integer values we replace it with the second clause body. It happens over and over until we reach the step #6: since at this stage the second parameter is 0 the first clause is chosen so the result is the first argument as is. Then the evaluation wraps up, the very inner succ is evaluated each step leading you to the final answer. Mastering such reasoning is hard but essential for your career; just give it some practice and you would see how it's getting better and better.
Now, as you could see the addition is just A plus 1 repeated B times. For instance, if A is 5 and B is 3 then this could be 5 + 1 + 1 + 1. Knowing that we could try and define the multiplication function in the same way. We could notice that A * B could be thought as a sum of B repeated A times (or vice versa, a sum of A repeated B times, it doesn't really matter).
mul(_, 0) -> 0;
mul(A, B) -> add(A, mul(A, pred(B))).
This function is similar (or even the same) as the addition function, except in the second clause we're calling the add function instead of the succ function. Also, just to remind you, the underscore symbol _ is a special pattern that would match any value. It's commonly used when we don't need a value but still have to specify an argument in some particular position. In this case we don't care about the first argument since the result of the multiplication by zero is always zero.
Now we could define the exponentiation function (usually called "power" or just "pow") and even tetration.
pow(_, 0) -> 1;
pow(A, B) -> mul(A, pow(A, pred(B))).
tet(_, 0) -> 1;
tet(A, B) -> pow(A, tet(A, pred(B))).
You could notice a common pattern here; each new function you define is defined in terms of the previous one. So, for instance, the tet function is based on the pow and pow is based on the mul, and so on. The difference here would be the add function since it's based on the unary version of the succ, while other functions like mul and pow are binary. To address this we could start thinking about the succ function as a binary one which always ignores its first argument. Another difference is the base cases but starting since the pow function they're the same. It means we could try and define a generic function combining the cases all together.
hyper(0, _, B) -> B + 1;
hyper(1, A, 0) -> A;
hyper(2, _, 0) -> 0;
hyper(_, _, 0) -> 1;
hyper(N, A, B) -> hyper(N - 1, A, hyper(N, A, B - 1)).
So, this is an implementation of the hyperoperation function. I'm not using the succ and pred functions on purpose here, so just not to overwhelm the example with details. But you get the idea. The very first clause is zeration (another name of the successor function); then the next 2 clauses are base cases of addition and multiplication; then a generic clause which is a base case of all operators starting since exponentiation; and finally there is a clause which is defined in terms of the previous hyper operator forming the recursion.
That's it, we now have a generic function that defines an infinite sequence of arithmetic operations. What's also cool is that when writing functions in Erlang you almost literally translate mathematical notations into the code. Let's call the hyper function to see its result.
1> lesson2:hyper(4, 2, 4).
65536
Recursion is a great way of creating new things. Combined with the power of functions it takes you as a developer to new heights. In the following article we would learn more examples of recursion, especially recursion on complex types as lists.
P.S.: Don't forget to inspect and download the sources.
July 14, 2020