Erlang: Funs (Part 2).
In the previous article, we saw how Funs could be used in a combination with list functions. Moreover, we implemented some such functions ourselves. In this article, I would like to continue our journey to the world of higher-order functions and show you how they're connected with types and data.
You might remember that funs can be used as arguments to higher-order functions. You pass funs to the higher-order functions to alter their behavior; you write higher-order functions to abstract things out and create generic versions of algorithms. However, you could not only pass funs as arguments but also return funs as a result.
1> F1 = fun() -> fun() -> fun() -> success end end end.
#Fun<erl_eval.44.97283095>
2> F2 = F1().
#Fun<erl_eval.45.97283095>
3> F3 = F2().
#Fun<erl_eval.45.97283095>
4> F3().
success
That's it, F1 is a function that actually contains a nested function in it. If you call F1, you will get another function as a result and so on until eventually you get the very inner result (success). That idea is very similar to the matryoshka doll.
This technique provides us with a few new opportunities: it's tightly connected with the control flow abstractions, so that expert developers could literally redefine the rules (a topic that will be discussed in detail in the next article).
Now consider a function like abs which returns the absolute value of a given number. Here is one possible implementation.
-module(lesson6).
-export([abs/1]).
abs(X) when X < 0 -> -X;
abs(X) -> X.
As we know, each function consists of clauses. The above abs function consists of 2 clauses and each of them defines the X variable in patterns. We intuitively know that these Xs, while sharing the same name, are actually independent and exist each in their own clause. That's possible because there are scopes: each entity we define in Erlang is limited by its scope. Scopes are just areas where entities are considered valid and could refer to something just like how the Xs above in patterns refer to abs parameters and could be each used in their clause providing a contextual meaning for guards and bodies.
The complete set of rules on scoping is quite complicated, so we won't discuss all of them right now. Instead, I'm planning to get back to this topic from time to time and point your attention to how different constructions influence the scoping rules.
Scopes describe the lifetimes of variables and the resources associated with them. A variable exists from where it's defined until the end of the clause it belongs to and can't be rebound. That's it, the scope of a variable is limited to a function clause. That said, all variables in patterns of nested functions are new variables. You could do this.
double(X) ->
F = fun(X) -> X + X end,
F(X).
The X variable first appears in the patterns of the double function and exists in lines 1 and 3. That's the scope of that X. In the second line, we define a nested function which redefines X so that, in its body, the X is now different and has nothing to do with the X from the outer scope. The X defined in the local fun exists only in the line 2. This situation is called variable shadowing.
If you now try to compile the double function it will give you a warning variable 'X' shadowed in 'fun'. So the compiler says "Yes, it's valid Erlang code and I will compile it, but you're probably doing something wrong here". While it's practically possible to write functions in that way, I recommend that you avoid the variable shadowing situations as much as possible.
A combination of all entities available at some given point of your code is called an environment or a context. Variables in a function clause belong to a local context. However, from within the clause, you could actually refer to some variables defined in the outer context if their scopes intersect with your clause. Consider the const function to understand the idea better.
const(X) -> fun() -> X end.
It takes a parameter and converts it into a nullary function that returns the captured value back. The X here is defined in the outer context (so it's not defined locally in the fun that refers to the X). Testing time!
1> DiceRoll = lesson6:const(4).
#Fun<lesson6.0.91742266>
2> DiceRoll().
4
In this same way, we can create and return N-ary functions. Like, for instance, the following one.
make_adder(X) -> fun(Y) -> X + Y end.
And let's use it.
1> Inc = lesson6:make_adder(1).
#Fun<lesson6.0.129297449>
2> Inc(1).
2
3> Inc(5).
6
4> Add3 = lesson6:make_adder(3).
#Fun<lesson6.0.129297449>
5> Add3(10).
13
So far, so good. The make_adder function creates new unary functions dynamically which you then can use as regular functions. The value of X is captured at the time of calling make_adder and saved along with the newly created fun, which is then able to address that X value. We could also think about it as some sort of a hidden parametrization. Moreover, it could be thought of as a partial application, though there is no special syntax for it in Erlang.
If a function captures at least one variable from the outer context, we call it a closure. You can then use a closure locally, or, for instance, return it as a result, as we did in the case of the const and make_adder functions. Note: Please remember that the only condition essential to determine whether a function is a closure is that it captures variables from the outer context. No other conditions are involved.
Closures could help you to create new types, especially complex ones. The good news is, most modern languages support closures so the approach you will learn here is applicable to all of them. But before we start, let's talk about types.
Types can be used in a variety of situations. There are different definitions on what types are, but most commonly types are attributes of data describing a set of possible values and a set of operations you can perform over the values. For instance, consider a boolean. The type describes 2 valid values: (true and false) and a set of operations you can perform over booleans, like not (negation), and, or, and xor.
1> true and false.
false
2> true and true.
true
3> true and 1.
** exception error: bad argument
in operator and/2
called as true and 1
Erlang uses types to check the safety of operations you perform. You can see above that the very last expression ended up with an exception. That's because the and operator awaits two booleans as its operands but an integer is passed as the second operand.
Our interest is mostly in the effects we get from types. For instance, the fact that I could increase or decrease some integer could be used for implementing loop-counters, or a combination of booleans that enable or disable some functionality in your application. In fact, in most cases, we're interested in algorithms we perform over some data, rather than data itself.
The mind-blowing thing here is that data types don't just describe operations; operations describe types as well. It works both ways! By defining the operation a type needs, we define the type itself. But how do we describe data (especially complex ones)? Remember closures? Yes!
We start from a simple type called Pair. A pair holds two values (we will call them X and Y) and allows us to address them independently. So the bare minimum to define a type like this is to implement 3 functions: a constructor and 2 getter methods.
Our first and naive implementation of the constructor is based on the idea that we could create a closure that accepts 1 parameter (in our case called "Idx", a short for index) and returns either X or Y based on the given value of the parameter.
pair_naive(X, Y) ->
fun(Idx) ->
case Idx of
0 -> X;
1 -> Y
end
end.
Let's use it.
1> P = lesson6:pair_naive(42, second).
#Fun<lesson6.2.93778692>
2> P(0).
42
3> P(1).
second
This approach has a few drawbacks. First, we're using an integer-based indexer; it is not informative and is easy to confuse. Secondly, this approach is not really convenient and effective for extending. For instance, if I want to implement the sum function, I would need to call P twice just to get its components. Third, in languages that do not support case statements, you would have to utilize ifs or boolean ternary operators chained in a bloody spaghetti way with some performance concerns on top of it. So it seems like we need a second attempt to implement it. Let's try it out.
This time, the plan is to make our type open by applying all the data we have to some external function, usually called a getter.
pair(X, Y) -> fun(F) -> F(X, Y) end.
first(P) -> P(fun(X, _) -> X end).
second(P) -> P(fun(_, Y) -> Y end).
That's it! We promise to apply both captured X and Y to some F that come as a parameter of the closure. To get the first and second components, we could then just apply funs that return their first or second arguments. The type is now easily extendable.
sum(P) -> P(fun erlang:'+'/2).
OK, it's way better now. But a simple observation leads us to a combined complex approach. Let's try it out.
pair_complex(X, Y) ->
Sum = X + Y,
Product = X * Y,
fun(Msg) ->
case Msg of
x -> X;
y -> Y;
sum -> Sum;
product -> Product;
map -> fun(F) -> F(X, Y) end;
print -> io:fwrite("(~w . ~w)~n", [X, Y])
end
end.
The closure in the pair_complex constructor is often called a dispatch-function. We could also apply some optimizations here as we did for the sum and product functions. However, do it wisely: it's always a trade-off between the initialization stage (plus memory) and the CPU time. If you think sum and product functions would be called quite often for the same instance of a pair, then it might be worth it to precompute and memoize the answers during the initialization stage. On the other hand, if the initialization stage is time critical, it's better not to precompute anything here and make it as lightweight as possible.
The same way you precompute and memoize answers, you could perform some validation checks during the initialization stage and terminate further evaluations if the constraints you define state the values aren't valid for this type.
As a final note, we're one step away from implementing an inheritance mechanism, though I won't do this in this article.
Let's try to test the pair_complex constructor.
1> Pair = fun lesson6:pair_complex/2.
fun lesson6:pair_complex/2
2> P1 = Pair(42, 5).
#Fun<lesson6.7.132746327>
3> P1(sum).
47
4> P2 = (P1(map))(fun(X, Y) -> Pair(X + 1, Y - 1) end).
#Fun<lesson6.7.132746327>
5> P2(print).
(43 . 4)
ok
Seems fun! Choosing this or another approach is up to you and requires some practice. It really depends on your particular situation and requirements, but here are a few pieces of advice. If the type you're developing is a complex one and involves some complicated relations with other types or, for instance, assumes that you develop an inheritance mechanism, or requires you to make some parts of the data to be private (so not exposed to public through the getter function), then go with the pair_complex approach. In all other cases, especially when your type is a simple one, go with the pair approach. For this article, we will just use the pair constructor.
OK, now we have a working type. We can create new pairs, address X and Y components, and have it extended with new operations. The same way you use primitive types to build complex ones, you could use the pair type to build some other new types. For instance, we could build the list type. Let's try it out.
What we're going to implement is called a unidirectional linked list. The type consists of pairs linked together in that way so the X component of a pair holds a single value from the list (the head) and the Y component holds another pair (the tail) that should follow the same rule recursively. We could illustrate it like this.
P1 -Y-> P2 -Y-> P3 -Y-> ...
| | |
X X X
| | |
V V V
1 2 3
By analogy with the pair type, we start from defining the basic functions that would represent the list. We need 3 functions here: one constructs a list (cons) and the other two represent the head and the tail of a list.
That said, because each node in the list is actually a pair, we could just reuse the pair functions for our own purposes.
cons(H, T) -> pair(H, T).
head(L) -> first(L).
tail(L) -> second(L).
Even though those are just wrappers over the pair functions, I do recommend you to go this way instead of directly using pair / first / second. One day you might want to switch to another implementation and that would be easier to do if you have an additional layer of abstraction here.
We're almost there, though it would be convenient to distinguish empty lists (the base case for almost all list algorithms). A naive way would be to reserve an atom that represents empty lists. Such an atom is usually called nil.
P1 -Y-> P2 -Y-> P3 -Y-> nil
| | |
X X X
| | |
V V V
1 2 3
From the engineering point of view, such a solution is OK; it's possible because Erlang allows us to compare atoms. Though, when detecting empty lists, we would really want to make sure that the argument is actually a list (or at least something that looks like a list). We remember the pair is a unary function that accepts a binary function that determines the result of evaluation; each node in our list is represented by a pair. Hence for "normal", non-empty lists, we could implement a binary function that ignores both of its arguments and just returns a false. The nil then could be represented as a special pair (that should be a unary function too), that itself ignores its first argument and returns true.
nil() -> fun(_) -> true end.
is_empty(L) -> L(fun(_, _) -> false end).
Stop for a moment and make sure you understand the trick. Once ready, let's test it.
1> Nil = lesson6:nil().
#Fun<lesson6.7.93778692>
2> C = fun lesson6:cons/2.
fun lesson6:cons/2
3> H = fun lesson6:head/1.
fun lesson6:head/1
4> T = fun lesson6:tail/1.
fun lesson6:tail/1
5> lesson6:is_empty(Nil).
true
6> lesson6:is_empty(C(1, Nil)).
false
7> List = C(1, C(2, C(3, Nil))).
#Fun<lesson6.4.93778692>
8> H(T(List)).
2
9> H(T(T(List))).
3
10> lesson6:is_empty(List).
false
You might notice the lists are actually constructed in the reverse order. Due to that fact, prepending elements is way simpler than appending them; in our implementation, lists are immutable, so appending requires rebuilding the entire list.
OK, it seems like we have all the functions we need to consider our type ready. We could try and build a few list algorithms. We start from the classic.
foldl(F, Acc, L) ->
case is_empty(L) of
true -> Acc;
_ -> foldl(F, F(head(L), Acc), tail(L))
end.
We have already discussed folds in previous articles so I'm not going to explain them to you in detail. Just notice how few details changed compared to the folds we wrote using native lists. Except for the pattern matching, the function is almost the same.
The left fold makes it really easy to implement the reverse function.
reverse(L) -> foldl(fun cons/2, nil(), L).
Now, for convenience reasons, let's implement a conversion between native Erlang lists and our own list type. In real life, you might want to do the same, but instead of converting from / to native types, you would serialize to and parse from some binary or text formats.
from_erlang_list(L) -> reverse(lists:foldl(fun cons/2, nil(), L)).
to_erlang_list(L) -> lists:reverse(foldl(fun(H, T) -> [H|T] end, [], L)).
For the same convenience reasons, we want to have a function called do.
do(F, L) -> to_erlang_list(F(from_erlang_list(L))).
It takes some function F and an Erlang list L, converts that L to our list, and applies it to the F. The result is then converted back to Erlang lists so we could, for instance, display them. Let's test it.
1> lesson6:do(fun lesson6:reverse/1, [1, 2, 3]).
[3,2,1]
So far so good. The next function we're going to implement is concat, a binary function that performs a concatenation of its parameters.
concat(A, B) -> foldl(fun cons/2, B, reverse(A)).
And of course let’s not forget about the filter function!
filter(P, L) ->
reverse(foldl(fun(H, T) ->
case P(H) of
true -> cons(H, T);
_ -> T
end
end, nil(), L)).
Having those tools, we can quickly build some sophisticated algorithms. For instance, let's implement a quick sort algorithm.
qsort(L) ->
case is_empty(L) of
true -> L;
_ ->
Pivot = head(L),
S = fun(F) -> qsort(filter(fun(X) -> F(X, Pivot) end, tail(L))) end,
concat(S(fun erlang:'<'/2), cons(Pivot, S(fun erlang:'>='/2)))
end.
We can now test it.
1> lesson6:do(fun lesson6:qsort/1, [5, 2, 42, 7, 15]).
[2,5,7,15,42]
That's it, a list is sorted if it's empty; for non-empty lists, the algorithm takes the head (called the pivot in the context of the quick sort algorithm) and places it between recursively sorted lists of smaller and larger elements.
That's it for this article. We have discussed how closures help us to create new types and we have just seen how one type could be used as a building block for another one. Though, just to remind you, please always tend to utilize the functions and types provided by the language itself; building your own types as a replacement to the existing ones might be a good idea for learning purposes or when the embedded types lack functionality you need.
P.S.: if you liked this article, please share it with your friends and colleagues. And as always, don't forget to inspect and download the sources.
October 18, 2020