Building a stack in Erlang

Question

I'm still new to Erlang and trying to get my head around not being able to change variables. Lets say I create a stack and want to add a new element. How will I update the stack if I can't assign new values to my list? Will I just have to create a new list each time?

For example I was thinking a Push could look something like

List = [X|List].

and then a Pop would be

[Head|Tail] = List
Head
List = Tail

Of course this won't work because I can't change the value of List and there is my problem. Any help is appreciated.

Answer 1

Erlang cannot have side-effects inside a function, a feature common amongst functional programming languages. Changing a variable state is a side-effect. All change of state in Erlang is hidden by processes and message passing, in what is called the actor model.

The common way to "change" a variable is for a function to call itself with the changed variable, which is called recursion. For example, to sum all elements of a list:

sum([]) -> 0;
sum([H|Tail]) -> H + sum(Tail).

Even better is to make your functions tail recursive, which means that they call themselves as the very last instruction in the function body. That will save memory since not all function calls need to be kept on the stack (tail-call optimization). The same example but using tail recursion:

sum([], Acc) -> Acc;
sum([H|Tail], Acc) -> sum(Tail, Acc + H).

sum(L) -> sum(L, 0).

In this example I introduced an accumulator variable to pass along intermediate results.

It is not always obvious how to make a program side-effect free, especially if you try to think of problems in procedrual terms (as in C or Java). It needs practice and possibly a will to understand functional programming on a more theoretical level.

A purely functional programming language cannot have any side-effects at all; the return value of a function must be based only upon the input arguments of the function, and the only output from a function must be the return value. This is not the case for Erlang. The recieve clause and the ! operator are used for input and output inside a function; side-effects. External state can be held as processes to which you can send messages and get replies.

Here is an example of how to create a variable whose value can be changed by message passing (try to figure out if var_proc is tail-recursive!):

var_proc(Value) ->
    receive
    {get, Pid} ->
            Pid ! {value, Value},
            var_proc(Value);
        {set, New} -> 
            var_proc(New)
    end.

var_start(Init) ->
    spawn(?MODULE, var_proc, [Init]).

var_set(Pid, Value) ->
    Pid ! {set, Value}.

var_get(Pid) ->
    Pid ! {get, self()},
    receive
    {value, Value} -> Value
    end.

Here is an example of how to use it (I have called the module "sum"):

13> V = sum:var_start(6).
<0.72.0>
14> sum:var_get(V).
6
15> sum:var_set(V, 10).
{set,10}
16> sum:var_get(V).    
10

More examples and some motivations can be found in the Concurrent Programming chapter in the Erlang documentation.

Answer 2

For a stack data structure in a functional programming language like Erlang, you would normally not go into the trouble of creating a separate process to contain and do operations on it with messages, unless you wanted multiple processes to access it simultaneously.

You are expected to assign a new variable every time, to contain the modified version of the stack and use that from there on:

new() -> [].

push(Value, OldStack) -> [Value|OldStack].

pop([]) -> empty;
pop([Value|RestStack]) -> {Value, RestStack}.

You use it like this:

S0 = new(),
S1 = push(a, S0),
S2 = push(b, S1),
S3 = push(c, S2),
...
case pop(SN) of
   empty -> stack_was_empty;
   {Element, SN1} ->
     do_something_with(Element),
     SN2 = push(b, SN1),
     ...
...