I’ve got this class which I have to implement in Erlang… |
I’m sure it’s a nice class :-) |
But Erlang doesn’t have a “class” concept! What am I to do? How do I implement it in Erlang? |
It depends. What kind of class is it? |
What kinds are there? I’m used to a uniform class concept. |
It may not be as uniform as you think. |
Sure it is. The keyword ‘class’, then a class name, an optional inheritance description, a curly opening brace, then a bunch of definitions… and then a closing brace. |
Semantics matter more than syntax. The syntactic similarities may hide significant semantic differences. |
Such as? |
For instance, some classes are thread-safe, while others are not. Only some classes are serializable; only some are immutable. Some don’t have any state, and a few are singletons. For some classes, object identity matters, for others it doesn’t. And only some classes are genuinely designed for inheritance. Finally, a mutable object may be shared, or there may be just a single reference to it. |
And these differences matter? |
Even under normal circumstances, they matter to some degree. In a concurrent and possibly distributed setting, they matter a great deal. |
So, what properties determine how I can best represent a concept in Erlang? |
First and foremost: immutability. Does the object have mutable state, or does it contain the same information throughout its lifetime? Numbers, Java strings, and read-only collections are examples of immutable objects. |
OK, let’s take an example: the text-book “Point” class. Immutable version first — how would you represent a Point with translation and scaling operations? |
Immutable objects are represented as terms. Operations on those objects are represented as functions. A Point, for instance, could be represented as a pair — a 2-tuple make_point(X, Y) -> {X,Y}.
scale(T, {X,Y}) -> {T*X, T*Y}.
translate({DX,DY}, {X,Y}) -> {X+DX, Y+DY}.
x_part({X,_}) -> X.
y_part({_,Y}) -> Y.
|
That means that objects with the same data will be indistinguishable.
I guess a good thing about that is that I won’t need to implement a comparison function ( But what if I want immutable objects with object identity? |
Then use make_point(X, Y) -> {make_ref(), X,Y}.
x_part({_,X,_}) -> X.
y_part({_,_,Y}) -> Y.
same({ID1,_,_}, {ID2,_,_}) -> ID1 =:= ID2.
|
I see. By the way: you just added a field to the data type by extending the tuple. I take it that that’s a normal thing to do… but if you need to do that repeatedly, you may end up with tuples of size 10, 20 or more. That must be confusing — you’d need to be careful to remember the exact position of each field. |
An alternative is to use records (which are tuples under the hood, but with syntactic sugar so that you can ignore all the fields that aren’t relevant in a given context). You’d usually consider switching from raw tuples to records once you get to around 4 or 5 fields. |
How would the Point-with-object identity example look if we were using records, then? |
Like so: -record(point, {id, x, y}).
make_point(X, Y) -> #point{id=make_ref(), x=X, y=Y}.
x_part(#point{x=X}) -> X.
y_part(#point{y=Y}) -> Y.
same(#point{id=ID1}, #point{id=ID2) -> ID1 =:= ID2.
Alternatively, the operations can be written in record-access rather than pattern-matching style: x_part(P) -> P#point.x. y_part(P) -> P#point.y. same(P1, P2) -> P1#point.id =:= P2#point.id. |
That looks a bit shorter to me. Why bother with pattern matching in this case? |
Consider the case where more than one value is extracted from the same record, or is used more than once: scale1(T, #point3d{x=X, y=Y, z=Z}) -> #point3d{x=T*X, y=T*Y, z=T*Z}.
scale2(T, P) -> #point3d{x=T*P#point3d.x, y=T*P#point3d.y, z=T*P#point3d.z}.
distance_from_origin1(#point{x=X, y=Y}) -> math:sqrt(X*X + Y*Y).
distance_from_origin2(P) ->
X = P#point.x,
Y = P#point.y,
math:sqrt(X*X + Y*Y).
Both length and clarity suffer when the record-access style is used, in these cases. |
What if I want a mutable version of Point? |
That depends. Will it be referred to by multiple entities, so that if one of them modifies the Point, that change will be visible by the others? |
For the time being, let’s say it’s a “no” — that the object only has one referrer. |
Then we can just use the same immutable Point implementation. Instead of modifying the Point object, we can replace it with a derived version, and no-one can tell the difference. |
And for a mutable object which is known by more than one entity? Shared state, you might call it. |
Then we need a level of indirection. |
OK, so instead of storing the data, you store a reference to the data. And then you store the actual data somewhere else. |
Yes. (That effectively reduces the “multiple entities” back into a single one.) The “somewhere else” could be another functional (immutable) data structure, but more often, the reference in question is a reference to a table or a process. |
Ah. So now we’re getting beyond a single, purely-functional process. |
We are, and this is where things start to get interesting. An important part of Erlang program design is figuring out which state there is to keep track of, and where the different pieces of state should be put. |
In a typical OOP language, state lives in the instance fields of objects, and the static fields or global variables or whatever the language’s got. Oh, and of course in the local variables on the program stack. |
In Erlang, the local variables on the stack are the primary place for state. Pure functional language have just that. But Erlang’s also got the process dictionary, ETS tables, and (for special purposes) the global registries of named processes and tables. And, of course, processes — one of the possible raison d’être’s of a process is “to hold some state”. |
When do you use what? What kinds of state go where? |
You normally keep it in local variables. Constants can stay in code. Shared mutable state, however, usually take the form of either processes or tables. (More rarely, the process dictionary comes into use.) For singletons and truly global mutable state, you use named processes and tables. Tables are also used for some kinds of mutable data which aren’t shared — which could in principle just be stored in functional data structures. |
Which kinds of data is that? |
Collections which often grow large, or which have elements which are typically more or less constant over a long time, fit well into ETS tables. It also helps if the data has a primary key. |
What are the advantages of tables? |
One advantage is certainly constant lookup time (in unordered tables) when the primary key is known. And the reason tables are a good place to put large or slowly-mutating data sets is that it keeps it out of a process’s heap, out of the way of the garbage collector. The major difference between normal functional data structures and ETS table is that tables perform destructive (in-place) updates. That means that you can’t keep the old version of the table around — on the other hand, it means that you don’t need to thread the current value of the data structure, which may at times lead to a simpler program structure. Also, tables can be named, and they can (if needed) be accessed — safely — by more than one process. |
What of the drawbacks? |
There are a few — tables don’t fit all kinds of data and access patterns; as just mentioned, they’re not persistent, but updated destructively; they can’t be serialized or used across nodes in a distributed system; and there’s a limit to how many of them you can have at the same time. And because they’re separate from the process heaps, data must be copied into and out of them, so data access is a bit less direct than for data on the heap. |
Suppose I have some shared mutable state. How do I determine where to put it? |
The primary question is: Is it shared within a thread of execution, or between threads? If it is shared just within a single process, then it’s probably fit to put into a table. Especially if there’s more than one of the items in question. |
And if I’m sharing it between processes? |
If data is shared between processes, then you need a process to hold it (which may be one of the existing processes, when that makes sense). That process will then handle get- and set-requests, or whatever operations are suitable. A process which holds many items in that way can of course do so by storing them in one or more tables. |
So, for our shared mutable Point example: if it’s shared within a process, I can a) share a reference to it and keep the mutable value in a separate data structure; b) that data structure can be an ETS table. Or c) — which works also for sharing between processes - I can make the Point into a process of its own, with getter and setter calls etc. |
Or d) you decide that a single point is too light-weight to make into a process of its own, so you make a Point server process which keeps track of the state of whole lot of points. |
But if there are many Points users, but only one such Point server, it might turn into a bottleneck. You mentioned that multiple processes can access one table? |
Yes; a table can be private to a process, or other processes can be allowed to either just read from it, or have both read and write access to it. For information that is read-heavy, for instance, it may make sense to allow other processes to read directly from the table, rather than to force the process owning the table to service all of the requests pertaining to the table sequentially (which might make that process a bottleneck in the system). |
And when wouldn’t I want to do that? |
Whether such an approach makes sense, depends on whether the kinds of transactions which are needed are supported by the ETS tables. All ETS operations on individual rows are atomic. You can even do an atomic addition or subtraction on a single cell, or adjust multiple cells in the same row by constant offsets. |
So in such cases I need not worry about race conditions, even if multiple processes access the table concurrently. |
No; ETS is thread-safe and provides explicit atomicity guarantees. But transactions which involve more than one row, and most kinds of transactions which involve both reads and writes, cannot be done atomically. So if you need such operations, you probably can’t let the table be accessed by more than one process. |
| We’ve talked about how to deal with single classes. But how about class hierarchies? Polymorphism? I don’t see how that translates into Erlang concepts. | I’d like us to consider two different flavours of polymorphism: the kind where the class hierarchy is fixed (“closed”), and the kind where the hierarchy is meant to be extended with new subclasses, possibly outside our control.
| All right. In at least certain cases, the set of subtypes are fixed — tree representations, for instance, or enumerations, or a strategy pattern with a fixed set of strategies. | Indeed. When you have functions operating on polymorphic data, rather than methods as part of classes, the difference matters — because one function will may have to know about all of the subtypes.
| Yes… that bothers me, though; that means that you can’t add a subtype without having to add knowledge of that type to all of the functions which operate on that type hierarchy. | If you were to add the same subtype in an OOP language, you’d have to write all of the methods of that class (except where you can use the derived version). It’s the same amount of knowledge you need to add in either case.
| Right, but in one case it’s scattered all over the place, while in the other it’s local — collected in one place.
| Try considering the opposite case, though: Adding an operation — a function or a method. Then the roles change: In the functional language, you write a new function in one place, whereas in OOP you need to add the method in many classes — the new functionality ends up being scattered all over the place.
| Ah. It is like two views of the same… like a table where rows are subtypes and columns are operations; the OOP language presents the table row-by-row while the functional language presents it column-by-column. | I suppose you can use that analogy, yes.
Note that in both kinds of language, you can change the direction if you want to -- it just fits a little less naturally into the language.
| I think it’s time for an example; this sounds like the kind of thing I’d rather have demonstrated than explained. | Probably a good idea.
For an illustrative example, I suggest that we look at a calculator example -- where we model and evaluate mathematical expressions.
a| Here’s the class hierarchy I’d use:
abstract class Expression {}
class Constant extends Expression {
final double c;
}
abstract class BinOp extends Expression {
final Expression left, right;
}
class Add extends BinOp {}
class Mul extends BinOp {}
I’ve omitted the constructors, and saved the operations for later. (And in real life I’d of course need more subclasses.)
a| Here’s how an Erlang equivalent might look:
constant(C) where is_number(C) -> C.
add(L,R) -> {binop, '+', L, R}.
mul(L,R) -> {binop, '*', L, R}.
a| Let’s add an ‘evaluate’ operation…:
In class Expression:
public abstract double evaluate();
In class Constant:
public double evaluate() {return c;}
In class Add:
public double evaluate() {
return left.evaluate() + right.evaluate();
}
In class Mul:
public double evaluate() {
return left.evaluate() * right.evaluate();
}
a| And the Erlang equivalent:
evaluate(C) when is_number(C) -> C;
evaluate({binop, '+', L, R}) -> evaluate(L) + evaluate(R);
evaluate({binop, '*', L, R}) -> evaluate(L) * evaluate(R).
a| Just for illustrating a derived method, let’s also add an operation which calculates the size of the expression tree:
In class Expression:
public abstract int tree_size();
In class Constant:
public int tree_size() {return 1;}
In class BinOp:
public int tree_size() {
return left.tree_size() + right.tree_size();
}
a| In Erlang, I use pattern matching to obtain the same effect:
tree_size(C) when is_number(C) -> 1;
tree_size({binop, _, L, R}) -> tree_size(L) + tree_size(R).
a| So much for adding new operations. Now I want to add a new subtype — subtraction, for instance.
That’s nicely local in OOP:
class Sub extends BinOp {
public double evaluate() {
return left.evaluate() - right.evaluate();
}
}
a|
…Whereas in Erlang, you’d need to add clauses to the existing functions — in this case, just evaluate():
evaluate({binop, '-', L, R}) -> evaluate(L) - evaluate(R);
| But you talked about changing the direction, the ‘major axis’ so to speak — so that in OOP, adding an operation can be done locally, while adding a subtype means scattered additions. | Yes. That means implementing the operation as a single function, perhaps externally to the class hierarchy, and testing the concrete type of the operand. Or, alternatively, using the Visitor pattern.
a| Right — that would be like this, in Java:
static double evaluate(Expression e) {
if (e instanceof Constant) {
return ((Constant)e).c;
} else if (e instanceof Add) {
Add e2 = (Add)e;
return evaluate(e2.left) + evaluate(e2.right);
} else if (e instanceof Mul) {
Mul e2 = (Mul)e;
return evaluate(e2.left) * evaluate(e2.right);
} else {
throw new RuntimeException(
"Unknown expression type: "+e.getClass().getName());
}
}
That pretty much amounts to emulating the functional solution.
a| To similarly emulate the OOP solution in Erlang, we include a method table when we create the objects:
%% The abstract superclass Exp:
-record(exp, {eval, tree_size}).
evaluate (#exp{eval =F}=Obj) -> F(Obj).
tree_size(#exp{tree_size=F}=Obj) -> F(Obj).
%% class Constant:
constant(C) where is_number(C) ->
#exp{data=C,
eval=fun eval_constant/1,
tree_size=fun ts_constant/1}.
eval_constant(#exp{data=Data}) -> Data.
ts_constant(#exp{}) -> 1.
%% abstract class BinOp:
binop(L,R,EvalFun) ->
#exp{data={L,R},
eval=EvalFun,
tree_size=fun ts_binop/1}.
ts_binop(#exp{data={L,R}}) ->
tree_size(L) + tree_size(R).
%% classes Add and Mul:
add(L,R) -> binop(L, R, eval=fun eval_add/1).
mul(L,R) -> binop(L, R, eval=fun eval_mul/1).
eval_add(#exp{data={L,R}}) ->
evaluate(L) + evaluate(R).
eval_mul(#exp{data={L,R}}) ->
evaluate(L) * evaluate(R).
| With these versions, a new operation can be added to the OOP version without changing existing classes, and similarly, a new subtype can be added to the Erlang version without changing existing functions. a| Hybrids exist, too — suppose that we wish to support a number of mathematical functions, but we don’t know the full set yet. Then we can make an extension point only for the relevant subtype:
%% The abstract supertype:
-record(function_exp, {eval, arg}).
make_fun_exp(EvalFun, ArgExp) ->
#function_exp{eval=EvalFun, arg=ArgExp}.
%% New clause in eval():
evaluate(#function_exp{eval=EvalFun, arg=ArgExp}) ->
EvalFun(evaluate(ArgExp));
%% New clause in tree_size():
tree_size(#function_exp{arg=ArgExp}) ->
1 + tree_size(ArgExp);
%% Example subtypes:
sin(Exp) ->
make_fun_exp(fun math:sin/1, Exp).
reciproc(Exp) ->
make_fun_exp(fun (X)-> 1.0 / X end, Exp).
Then we can add subtypes of “Function expression” without changing existing code.
On the other hand, when we add new operations, we may need to add
methods to the #function_exp record — we’ll have to if the subtypes
differ in their behaviour for that operation (like in eval()), but
we can leave the record as-is if the subtypes behave identically with
respect to the operation (like in tree_size()), or if it can be
defined in terms of existing methods.
| So, to sum up, there’s a choice to be made with respect to expected extensions — regardless of the language. | There is. You can choose to be able to extend with new subtypes, or with new operations, or with some kinds of subtypes and some kinds of operations, as long as the two are compatible.
And that choice is independent of the language -- although languages differ in what they encourage.