Erlang example programs

Joe Armstrong


This is a collection of Erlang example programs. The document is also available as a postscript or pdf file. All the programs referred to are available in the archive examples-2.0.tgz.

The programs attempt to do useful things, thus you will find complete source code for a number of useful Erlang utilities such as make, find ftp etc. which model the behaviours of the Unix programs with the same names.


This chapter describes how FTP (File Transfer Protocol) could have been implemented if the implementation language had been Erlang. Instead of following RFC 959 we will implemented the core functionality of a file transfer protocol in two Erlang modules ftp_client and ftp_server.

The FTP client

ftp_client exports the following function:

The implementation of these commands is straightforward, firstly,
connect/3, which tries to establish a connection to the FTP server:

     connect(Host, User, Password) ->
         {ftp_server, Host} ! {connect,self(),User,Password},
             {ftp_server, Reply} -> Reply;
             Other -> Other
         after 10000 ->

This just sends a connect request to the server and waits for a reply.

pwd/1, cd/2, ls/1, get/2 and quit/1 are all implemented as remote procedure calls:

     pwd(Handle)       -> remote(Handle, pwd).
     cd(Handle, Dir)   -> remote(Handle, {cd, Dir}).
     ls(Handle)        -> remote(Handle, ls).
     get(Handle, File) -> remote(Handle, {get, File}).
     quit(Handle)      -> remote(Handle, quit).


     remote(Handle, Op) ->
         Handle ! {self(), Op},
             {ftp_server, Any} ->
         after 1000 ->

which just sends a message to the server and waits for a reply.

The other commands lcd/1, lpwd/0 and lls/0 are purely local:

     lcd(Dir)          -> file:set_cwd(Dir), lpwd().
     lpwd()            -> cwd().
     lls()             -> element(2, file:list_dir(cwd())).

Finally put/2 reads the file locally as an atom action and then calls remote/2 to store the file on the remote FTP server.

     put(Handle, File) ->
         case file:read_file(File) of
             {ok, Contents} ->
                 remote(Handle, {put, File, Contents});
             Other ->

The FTP server

The FTP server is started by evaluating ftp_server:start/0:

     start() ->
         case (catch register(ftp_server, 
                              spawn(?MODULE, internal, []))) of
             {'EXIT', _} ->
             Pid ->

which calls:

     internal() ->
         case file:consult("users") of
             {ok, Users} ->
                 process_flag(trap_exit, true),
                 loop(Users, 0);
             _ ->

internal() reads the password file called user, a typical file might be:

     {"joe", "zapme"}.

which contains valid {User, PassWord} pairs.

The main loop of the server is:

     loop(Users, N) ->
         {connect, Pid, User, Password} ->
           io:format("connection request from:~p ~p ~p~n",
                     [Pid, User, Password]),
           case member({User, Password}, Users) of
             true ->
               Max = max_connections(),
                 N > Max ->
                   Pid ! {ftp_server, 
                            {error, too_many_connections}},
                   loop(Users, N);
                 true ->
                   New = spawn_link(?MODULE, handler, [Pid]),
                   Pid ! {ftp_server, {ok, New}},
                   loop(Users,  N + 1)
             false ->
               Pid ! {ftp_server, {error, rejected}},
               loop(Users, N)
         {'EXIT', Pid} ->
           io:format("Handler ~p died~n", [Pid]),
           loop(Users, lists:max(N-1, 0));
         Any ->
           loop(Users, N)

Here Users is the content of the password file and N is the current number of active connections to the server. When a connect request arrives at the server, the server checks to see if the username and password are correct and that the maximum number of simultaneous connections has not been exceeded. If everything is OK the connection is accepted and a new process spawn_link'ed to handle the connection, otherwise the connection is rejected.

The other point to note about the server loop is that if the server receives an exit signal it decrements the number of active connections, this can only happen if a handler process dies (note the main loop of the server was set to trap exits).

The individual handlers just perform the remote operations that were requested by the client:

     handler(Pid) ->
             {Pid, quit} ->
                 Pid ! {ftp_server, ok};
             {Pid, Op} ->
                 io:format("got:~p ~p~n",[Pid, Op]),
                 Pid ! {ftp_server, do_op(Op)},


     do_op({cd, Dir})        -> file:set_cwd(Dir), cwd();
     do_op(ls)               -> element(2, file:list_dir(cwd()));
     do_op(pwd)              -> cwd();
     do_op({get_file, File}) -> file:read_file(File).

That's it.


On my linux box at home I had the following problem:

The fix: as root give the following commands:

/sbin/ifconfig dummy up
/sbin/route add -host dummy

These can be added to /etc/rc.d/rc.local (I think).


The ftp client (39 lines) and ftp server (64 lines) were kept deliberately simple, so as not to obscure the essence of an FTP client/server. Here are a few simple ideas for extensions that could be added to the system.


This chapter describes find and ermake which are Erlang versions of the familiar Unix utilities with similar names.


find exports the following functions:

find:files/3 is pretty straightforward:

     files(Dir, Re, Flag) -> 
         Re1 = string:re_sh_to_awk(Re),
         find_files(Dir, Re1, Flag, []).

This calls

     find_files(Dir, Re, Flag, L) -> 
         case file:list_dir(Dir) of
             {ok, Files} -> find_files(Files, Dir, Re, Flag, L);
             {error, _}  -> L

And finally

     find_files([File|T], Dir, Re, Recursive, L) ->
         FullName = Dir ++  [$/|File],
         case file_type(FullName) of
             regular ->
                 case string:re_match(FullName, Re) of
                     {match, _, _}  -> 
                         find_files(T, Dir, Re, Recursive, [FullName|L]);
                     _ ->
                         find_files(T, Dir, Re, Recursive, L)
             directory -> 
                 case Recursive of
                     true ->
                         L1 = find_files(FullName, Re, Recursive, L),
                         find_files(T, Dir, Re, Recursive, L1);
                     false ->
                         find_files(T, Dir, Re, Recursive, L)
             error -> 
                 find_files(T, Dir, Re, Recursive, L)
     find_files([], _, _, _, L) ->

In addition we need something that classifies the file type:

     file_type(File) ->
         case file:file_info(File) of
             {ok, Facts} ->
                 case element(2, Facts) of
                     regular   -> regular;
                     directory -> directory;
                     _         -> error
             _ ->

The other utility function in find.erl is out_of_date/3, this is as follows:

     out_of_date(Dir, In, Out) ->
         case file:list_dir(Dir) of
             {ok, Files0} ->
                 Files1 = filter(fun(F) -> 
                                    suffix(In, F) 
                                end, Files0),
                 Files2 = map(fun(F) -> 
                                  sublist(F, 1, 
                             end, Files1),
                 filter(fun(F) -> update(F, In, Out) end,Files2);
             _ ->

Which calls:

     update(File, In, Out) ->
         InFile  = File ++ In,
         OutFile = File ++ Out,
         case is_file(OutFile) of
             true ->
                 case writeable(OutFile) of
                     true ->
                         outofdate(InFile, OutFile);
                     false ->
                         %% can't write so we can't update
             false ->
                 %% doesn't exist

This calls the predicates is_file and writeable:

     is_file(File) ->
         case file:file_info(File) of
             {ok, _} ->
             _ ->

     writeable(F) ->
         case file:file_info(F) of
             {ok, {_,_,read_write,_,_,_,_}} -> true;
             {ok, {_,_,write     ,_,_,_,_}} -> true;
             _ -> false

and then checks if the file needs to be updated by calling outofdate:

     outofdate(In, Out) ->
         case {last_modified(In), last_modified(Out)} of
             {T1, T2} when T1 > T2 ->
             _ ->

Finally we need the last modified date of the file:

     last_modified(F) ->
         case file:file_info(F) of
             {ok, {_, _, _, _, Time, _, _}} ->
             _ ->
                 exit({last_modified, F})


ermake is a make utility for Erlang. ermake exports the following functions:

Makefile format

A typical makefile looks like:


JAMS = a.jam, b.jam, c.jam.

all when $(JAMS) ->

Entries in the the makefile may span several lines. Each entry is terminate by a dot followed by a whitespace. Three different types of entity are permitted.

In addition the notation $(VAR) means the value of the variable VAR, $> means the root name of the current target, and the pre-defined variable MAKEDIR contains the root directory of the ermake program.

The file suffix_rules is as follows:

     Suffix .erl.jam ->
     Suffix .tex.dvi ->
             unix:cmd("latex $>.tex").
     Suffix .ehtml.html ->

How make works

Make is a fairly complex program which is built from three modules:

ermake.erl is a long and complex program (232 lines). Rather than explain all the details I'll just give a brief overview of how it works. Once the principles of make have been understood the details are easy to understand.

We start with a simple example. Suppose we have a makefile consisting of the following:

all when a,b ->

a when d,e ->

b when x ->

c when y ->

The initial target in this makefile is the goal all. The first step in generating the makefile dependencies is to generate the set of pairs {I, J} where I depends upon J. For the above makefile this is the set:

L = [{all, a}, {all, b}, {a, d}, {a, e}, {b, x}, {c, y}]

This can be read as all depends upon a, all depends upon b, etc.

Now we compute the transitive closure of the dependency graph as follows:

transitive:closure([all], L).                          

This is the set of all targets that are reachable from the start symbol all. Note that the symbols c and y cannot be reached.

Next we remove any pairs from the dependency graph that cannot be reached, this results in the list:

L1 = [{all, a}, {all, b}, {a, d}, {a, e}, {b, x}]

The makefile ordering is now found by first reversing the order of each pair and then performing a topological sort of the result:

> L2 = lists:map(fun({I,J}) -> {J, I} end, L1).
> topological_sort:sort(L2).

Yielding the final order in which things have to be made, namely:


Now that we know the order all we have to do is look back to the original rules to figure out which rule to apply.

Computing the order in which to build the targets is performed by ermake:make_everything/2:

     make_everything(Targets, Rules) ->
         Ps = [{T, D} || {make, Ts, Ds, _} <- Rules, T <- Ts, D <- Ds],
         %% trace all the rules we can reach from the root set
         L0 = transitive:closure(Targets, Ps),
         L = delete(true, L0),
         %% keep those rules that are mentioned in targets or destinations
         Ps1 = filter(fun({D,T}) ->
                             member(D, L) or member(T, L)
                     end, Ps),
         %% reverse the order to build the bottom up tree
         Ps2 = map(fun({I,J}) -> {J, I} end, Ps1),
         %% order the result
         case topological_sort:sort(Ps2) of
             {ok, Order0} ->
                 Order = delete(true, Order0),
                 %% Order is the absolute order to build things
                 Cmds = map(fun(I) -> select_rule(I, Rules) end, Order),
                 foldl(fun do_cmd/2, [], Cmds),
             {cycle, Cycle} ->

[Note: ermake also handles make rules where the when alternative is omitted, to handle these then pseudo dependent true is created, this has to be removed from the closure and topologically ordered sets]

The transitive closure was computed by:

     closure(RootSet, Pairs) ->
         closure_list(RootSet, Pairs, RootSet).
     closure(Start, [], L) ->
     closure(Start, Pairs, Reachable) ->
         {Next, Rest} = next(Start, Pairs),
         closure_list(Next, Rest, Next ++ Reachable).
     closure_list([], Pairs, Reachable) ->
     closure_list([H|T], Pairs, Reachable) ->
         Reachable1 = closure(H, Pairs, Reachable),
         closure_list(T, Pairs, Reachable1).
     next(Start, Pairs) ->
         next(Start, Pairs, [], []).
     next(Start, [], Reach, NoReach) ->
         {Reach, NoReach};
     next(Start, [{Start,Next}|T], Reach, NoReach) ->
         next(Start, T, [Next|Reach], NoReach);
     next(Start, [H|T], Reach, NoReach) ->
         next(Start, T, Reach, [H|NoReach]).

And the topological sort by:

     sort(Pairs) ->
         iterate(Pairs, [], all(Pairs)).
     iterate([], L, All) ->
         {ok, remove_duplicates(L ++ subtract(All, L))};
     iterate(Pairs, L, All) ->
         case subtract(lhs(Pairs), rhs(Pairs)) of
             []  -> 
                 {cycle, Pairs};
             Lhs -> 
                 iterate(remove_pairs(Lhs, Pairs), L ++ Lhs, All)
     all(L) -> lhs(L) ++ rhs(L).
     lhs(L) -> map(fun({X,_}) -> X end, L).
     rhs(L) -> map(fun({_,Y}) -> Y end, L).
     %% subtract(L1, L2) -> all the elements in L1 which are not in L2
     subtract(L1, L2) ->  filter(fun(X) -> not member(X, L2) end, L1).
     remove_duplicates([H|T]) ->
       case member(H, T) of
           true  -> remove_duplicates(T);
           false -> [H|remove_duplicates(T)]
     remove_duplicates([]) ->
     %% remove_pairs(L1, L2) -> L2' L1 = [X] L2 = [{X,Y}]
     %%   removes all pairs from L2 where the first element
     %%   of each pair is a member of L1
     remove_pairs(L1, L2) -> filter(fun({X,Y}) -> not member(X, L1) end, L2).

The remainder of ermake.erl fills in the details not covered here.


Parser Tutorial

Parsing with yecc and leex

Making a parser is something which I do sufficiently infrequently that each time I've figured out how to do it I immediately forget all the nitty gritty details.

For my example I will make a compiler for a language called ecc. Ecc stands for Erlang Compiler Compiler and is an experiment in automatic compiler generation.

[Note: leex.erl has not yet been officially released, but an inoffical copy has been included in this directory so that you can run the examples. You should be aware of the fact that the leex input grammar may be subject to change without notice]


In our example we use four files:

To run the example in this tutorial do as follows:

  1. Copy all the files in this directory to a temporary directory
  2. Give the commands:

An example program

This is an example program written in the language ecc:

     COMPILER ebnf.
       small   = "abcdefghijklmnopqrstuvwxyz";
       alpha   = small + big;
       dig     = "0123456789";
       blank   = CHR(9) + CHR(10) + CHR(32);
       noQuote = ANY - '"'.
       FROM "(*" TO "*)" NESTED.
       Nonterminal = small {alpha | dig};
       Terminal    = big {alpha | dig};
       White       = blank {blank};
       String      = '"' { noQuote } '"'.
       White + Comment.
        ebnf       = {production} ".";
        production = Nonterminal "=" expr ";" ;
        expr       = term {"|" term};
        term       = factor {factor};
        factor     = "{" expr "}" 
                   | "[" expr "]"
                   | "(" expr ")" 
                   |  Nonterminal | Terminal | String.
     END ebnf.

A sample session

Here is an example of how to build the parser and some sample output from the parser.

> erl
Erlang (JAM) emulator version 4.5.3
Eshell V4.5.3  (abort with ^G)
1> c(ecc_parse).
2> ecc_parse:make().
Parsing input file ...
Computing states and goto table ...
Computing parse actions ...
Writing file ...
./ecc_yecc.erl:589: Warning: function return_error/2 not called
./ecc_yecc.erl:589: Warning: function simplify/1 not called
Parsing file ecc.xrl, contained 20 rules.
NFA contains 131 states, DFA contains 62 states, minimised to 40 states.
Writing file ecc_lex.erl, ok
./ecc_lex.erl:687: Warning: function remove_brackets/1 not called
3> ecc_parse:file("ebnf").
Parsing ebnf.ecc

The yecc grammar

The yecc grammar which describes the language is in the file ecc.yrl. The interesting part of the grammar is the following:


form lhs  factor 
nested syntax char_prods charline char_rhs char_prim 
ignore moreignore expr term.

atom var string quote '|'  '=' '}' '{' '(' ')' '[' ']'
'IGNORE' 'PRODUCTIONS' 'END' 'NESTED' 'EOL' 'CHR' 'ANY' integer comment
'+' '-' ';'.

Rootsymbol form.

form -> 'COMPILER' atom                 : {compiler, unwrap('$2')}.
form -> 'CHARACTERS' char_prods         : {characters, '$2'}.
form -> 'COMMENTS' 'FROM' string 
                  'TO' string nested    : {comments,unwrap('$3'),unwrap('$5'),
form -> 'TOKENS' syntax                 : {tokens, '$2'}.
form -> 'IGNORE' ignore                 : {ignore, '$2'}.
form -> 'PRODUCTIONS' syntax            : {syntax, '$2'}.
form -> 'END' atom                      : {theend, '$2'}.
form -> comment.

nested -> 'NESTED'                      : nested.
nested -> 'EOL'                         : eol.
nested -> '$empty'                      : not_nested.

%% Character syntax

char_prods -> charline ';' char_prods   : ['$1'|'$3'].
char_prods -> charline                  : ['$1'].

charline -> atom '=' char_rhs           : {unwrap('$1'), '$3'}.

char_rhs -> char_prim '+' char_rhs      : {plus, '$1', '$3'}.
char_rhs -> char_prim '-' char_rhs      : {minus, '$1', '$3'}.
char_rhs -> char_prim                   : '$1'.

char_prim -> 'CHR' '(' integer ')'      : {chr, unwrap('$3')}.
char_prim -> string                     : {string, unwrap('$1')}.
char_prim -> quote                      : {string, unwrap('$1')}.
char_prim -> atom                       : {atom, unwrap('$1')}.
char_prim -> 'ANY'                      : any.

ignore -> var moreignore                : [unwrap('$1')|'$2'].

moreignore -> '+' ignore                : '$2'.
moreignore -> '$empty'                  : [].

syntax -> production ';' syntax         : ['$1'|'$3'].
syntax -> production                    : ['$1'].

production -> lhs '=' expr              : {prod, '$1', '$3'}.

lhs -> var                              : unwrap('$1').
lhs -> atom                             : unwrap('$1').

expr -> term                            : '$1'.
expr -> term '|' expr                   : {alt, '$1', '$3'}.

term -> factor                          : '$1'.
term -> factor term                     : {seq, '$1', '$2'}.

factor -> atom                          : {nt, unwrap('$1')}.
factor -> var                           : {ta, unwrap('$1')}.
factor -> string                        : {ts, unwrap('$1')}.
factor -> quote                         : {tq, unwrap('$1')}.
factor -> '[' expr ']'                  : {one, '$2'}.
factor -> '{' expr '}'                  : {star, '$2'}.
factor -> '(' expr ')'                  : {bracket, '$2'}.

The leex grammar

The leex grammar which describes the language is in the file ecc.xrl. The interesting part of the grammar is the following:


Dig = [0-9]
Big = [A-Z]
Small = [a-z]
WS = [\000-\s]

COMMENT = \(\*\(*([^*)]|[^*]\)|\*[^)])*\**\*\)
STRING = "(\\\^.|\\.|[^"])*"
QUOTE = '(\\\^.|\\.|[^'])*' 


({Small}({Small}|{Big}|{Dig}|_)*) : {token, {atom,YYline, YYtext}}.

({Big}({Small}|{Big}|{Dig}|_)*) : {token, special(YYtext, YYline)}.

({Dig}{Dig}*)   : {token, {integer, YYline, list_to_integer(YYtext)}}.

{STRING} :              %% Strip quotes.
                        S = lists:sublist(YYtext, 2, length(YYtext) - 2),

{QUOTE} :               %% Strip quotes.
                        S = lists:sublist(YYtext, 2, length(YYtext) - 2),

{COMMENT} : .   

=  : {token, {'=', YYline}}.
\+ : {token, {'+', YYline}}.
\- : {token, {'-', YYline}}.
\; : {token, {';', YYline}}.
}  : {token, {'}', YYline}}.
{  : {token, {'{', YYline}}.
\[ : {token, {'[', YYline}}.
\] : {token, {']', YYline}}.
\( : {token, {'(', YYline}}.
\) : {token, {')', YYline}}.
\| : {token, {'|', YYline}}.
\: : {token, {':', YYline}}.

(.|\n) : skip_token.

\.[\s\t\n] : {end_token,{'$end', YYline}}.


A numerical diversion

This chapter describes a number of simple numerical algorithms which make use of Erlang bignums.


lin exports the following functions:

Some of these are pretty simple, pow(A, B, M) computes A^B mod M. To compute this we proceed as follows: if B is even we compute pow(A, B div 2, M) and square the result (modulo M). If B is odd and greater than one we compute P = pow(A, (B-1)div 2, M) and then P*P*A mod M:

     pow(A, 1, M) ->
         A rem M;
     pow(A, 2, M) ->
         A*A rem M;
     pow(A, B, M) ->
         B1 = B div 2,
         B2 = B - B1,
         %% B2 = B1 or B1+1
         P = pow(A, B1, M),
         case B2 of
             B1 -> (P*P) rem M;
             _  -> (P*P*A) rem M

gcd is also easy:

     gcd(A, B) when A < B -> gcd(B, A);
     gcd(A, 0) -> A;
     gcd(A, B) ->
         gcd(B, A rem B).

As are conversions between strings and integers:

     str2int(Str) -> str2int(Str, 0).
     str2int([H|T], N) -> str2int(T, N*256+H);
     str2int([], N) -> N.
     int2str(N) -> int2str(N, []).
     int2str(N, L) when N =< 0 -> L;
     int2str(N, L) ->
         N1 = N div 256,
         H = N - N1 * 256,
         int2str(N1, [H|L]).

solve/2 requires some thought, before launching into the code we give some examples:

Solve 12x - 5y = 1 for integer x and y, solution x = -2 and y = -5 (check 12.-2 -5.-5 = 1 as required.

Solve 28x - 25y = 1 for integer x and y, solution x = -8 and y = -9 (check 28.-8 - (25.-9) = 1 as required.

These solutions are computed as follows:

> lin:solve(12,5).          
> lin:solve(28,25).    

To see how to solve these congruences we give a simple example

        solve            12x - 5y = 1          (1)
        or               (2*5 + 2)x - 5y = 1
        regrouping       2x + 5(2x - y) = 1

        let a = 2x - y                         (2)

        then             2x + 5a = 1           (3)
        or               2x + (2*2 + 1)a = 1
        regrouping       2(x + 2a) + a   = 1

        let b = x + 2a                         (4)

        then             2b + a = 1            (5)
        A solution to this is b = 1, a = -1

        Then from (4) x = b - 2a = 1 - 2(-1) = 3    (6)
        and  from (2) y = 2x - a = 2*3 -(-1) = 7.   (7)

        So a solution is (x, y) = (3, 7)

        Check 12*3 - 5*7 = 1 as required

This gives us the key idea as to how to solve linear congruences.

In order to solve 12x - 5y = 1 (equation 1) we make a substitution (equation 2) to reduce this to a simpler form, then we have to solve the simpler sub problem which is 2x + 5a = 1 (equation 3) . This is a simpler problem because the magnitude of the arguments are less. Eventually the process terminates when a trivial subproblem (equation 5) is encountered. Having found the solution to the sub-problem we back substitute (equations 6 and 7) to obtain the final result.

Note that some linear congruences are not solvable; Ax - By = 1 is not soluble if A mod B = 0

The above algorithm is easily encoded as:

     solve(A, B) ->
         case catch s(A,B) of
             insoluble -> insoluble;
             {X, Y} ->
                 case A * X - B * Y of
                     1     -> {X, Y};
                     Other -> error
     s(A, 0)  -> throw(insoluble);
     s(A, 1)  -> {0, -1};
     s(A, -1) -> {0, 1};
     s(A, B)  ->
         K1 = A div B,
         K2 = A - K1*B,
         {Tmp, X} = s(B, -K2),
         {X, K1 * X - Tmp}.

Fortunately Erlang has bignums so that:

> lin:solve(2812971937912739173,2103789173917397193791739173). 

Finally inv(A, B) which computes C such that A*C mod B = 1 if such an inverse exists.

     inv(A, B) ->
         case solve(A, B) of
             {X, Y} ->
                 if X < 0 -> X + B;
                    true  -> X
             _ ->


Many applications require the use of large prime numbers. The module primes.erl can be used to generate large primes and for primality testing.

primes.erl exports the following:

make(N) is easy:

     make(N) -> new_seed(), make(N, 0).
     make(0, D) -> D;
     make(N, D) ->
         make(N-1, D*10 + (random:uniform(10)-1)).


     new_seed() ->
         {_,_,X} = erlang:now(),
         {H,M,S} = time(),
         H1 = H * X rem 32767,
         M1 = M * X rem 32767,
         S1 = S * X rem 32767,
         put(random_seed, {H1,M1,S1}).

is_prime(N) is more interesting. We use a probabilistic method for primality testing which is based on Fermat's little theorem.

Fermat's little theorem states that if N is prime then A^N mod N = A. So to test if N is prime we choose some random A which is less than N and compute A^N mod N. If this is not equal to A then N is definitely not a prime. If the test succeeds then A might be a prime (certain composite numbers pass the Fermat test, these are called pseudo-primes), if we perform the test over and over again then the probability of mis-classifying the number reduces by roughly one half each time we perform the test. After (say) one hundred iterations the probability of mis-classifying a number is approximately 2^-100. So we can be fairly sure that the classification is correct. The classification code is as follows:

     is_prime(D) ->
         is_prime(D, 100).
     is_prime(D, Ntests) ->
         N = length(integer_to_list(D)) -1,
         is_prime(Ntests, D, N).
     is_prime(0, _, _) -> true;
     is_prime(Ntest, N, Len) ->
         K = random:uniform(Len),
         %% A is a random number less than N 
         A = make(K),
             A < N ->
                 case lin:pow(A,N,N) of
                     A -> is_prime(Ntest-1,N,Len);
                     _ -> false
             true ->
                 is_prime(Ntest, N, Len)

make_prime(K) is now easy. We generate a random integer N of K decimal digits and test to see if it is a prime. If it is not a prime we test N+1 etc. until we finally get a prime.

This process is known to terminate.

[aside] 'Bertrand's Postulate' is that for every N > 3 there is a prime P such that N < P < 2N - 2. Tchebychef proved this result in 1850 and Erdos shocked the world with a simple proof in 1932.

     make_prime(K) when K > 0 ->
         N = make(K),
         if N > 3 ->
                 io:format("Generating a ~w digit prime ",[K]),
                 MaxTries = N - 3,
                 P1 = make_prime(MaxTries, N+1),
             true ->
     make_prime(0, _) ->
     make_prime(K, P) ->
         case is_prime(P) of
             true  -> P;
             false -> make_prime(K-1, P+1)

Since generating large primes can take a long time we print out a string of dots so we have something to watch while the program runs!

> L1 = primes:make_prime(40).
Generating a 40 digit prime ........
69> L2 = primes:make_prime(40). 
Generating a 40 digit prime ........
70> primes:is_prime(L1*L2).

[note: in 1912 Carmichael discovered that certain composite numbers N have the property that A^N mod N = A for all A less than N. The smallest such Carmichael number is 561 = 3 * 11 * 17.

> primes:is_prime(561).

So our primality test will fail if N is a Carmichael number. Fortunately Carmichael numbers are exceedingly rare, and it is an open problem whether there exist infinitely many Carmichael numbers. The largest known Carmichael number has 3710 digits so if you stick to bigger numbers than this you probably won't run into problems!]


This section illustrates the principles behind public key cryptography, I will start with a few definitions and then a simple example.

Definitions: The RSA public keys system is characterized by two two-tuples of integers {N, A} and {N, B} one tuple is called the public key and may be openly published in a catalogue, the other is called a private key and is kept secret.

To encrypt the message M with the public key {N, A} we compute E = M^N mod A (E is now the encrypted message), to decrypt the message we compute E^B mod N which amazingly gets you back to where you started!

Example: (from the Erlang) shell

1 > A = 117298167.
2 > B = 412261863.
3 > N = 2315306317.
4 > M = "cat".              
5 > I = lin:str2int(M).
6 > E = lin:pow(I, A, N).
7 > D = lin:pow(E, B, N).
8 > lin:int2str(D).

In lines 1-3 we define the variables used in the public key {A, N} and the private key {B, N}. The secret message "cat" is encoded into an integer (lines 4-5), line 6 encodes the message, line 7 decodes the message and line 8 decodes it.

Warning in some countries writing a program that evaluates M^A mod N might be illegal. Check with your local policeman before doing this!
All that remains is to figure out how to compute suitable values for the public and private keys.

The "book [Cryptography, Theory and Practice, Douglas R. Stinson, CRC Press, 1995]" says ...

  1. Bob generates two large primes p and q.
  2. Bob computes n = pq and phi(n) = (p-1)*(q-1).
  3. Bob chooses a random b(0 < b < phi(n)) such that gcd(b, phi(n)) = 1
  4. Bob computes a = b^(-1) mod phi(n) using the Euclidean algorithm
  5. Bob publishes n and b in a directory as his public key.

The implementation follows in a straightforward manner from the specification:

     make_sig(Len) ->
         %% generate two <Len> digit prime numbers
         P = primes:make_prime(Len),
         io:format("P = ~p~n", [P]),
         Q = primes:make_prime(Len),
         io:format("Q = ~p~n", [Q]),
         N = P*Q,
         io:format("N = ~p~n", [N]),
         Phi = (P-1)*(Q-1),
         %% now make B such that B < Phi and gcd(B, Phi) = 1
         B = b(Phi),
         io:format("Public key (B) = ~p~n", [B]),
         A = lin:inv(B, Phi),
         io:format("Private key (A) = ~p~n", [A]),
     b(Phi) ->
         io:format("Generating a public key B "),
         K = length(integer_to_list(Phi)) - 1,
         B = b(1, K, Phi),
         io:format("~n", []),
     b(Try, K, Phi) ->
         B = primes:make(K),
             B < Phi ->
                 case lin:gcd(B, Phi) of
                     1 -> B;
                     _ -> b(Try+1, K, Phi)
             true ->
                 b(Try, K, Phi)

Which we can test as follows:

> rsa_key:make_sig(20). 
Generating a 20 digit prime .....................
P = 73901624116374075313
Generating a 20 digit prime ....................
Q = 78532450632904297229
N = 5803675647610596726269859097648983207677
Generating a public key B ...
Public key (B) = 761323469064175805955496463001193982357
Private key (A) = 3282348550950508596270008789422146776573


A Simple Operating System

This chapter describes a simple operating system called sos which is designed for running simple Erlang programs. sos has been designed for fast loading from the command line prompt and makes no use of the standard Erlang libraries. It can be studied as an example of a complete Erlang application which makes very few assumptions about its environment.

sos exports the following functions:

These functions can be used by simple Erlang programs.

Example programs

All our example are normal Erlang modules which must export the function main().

The simplest of all programs is sos_test1.

     main() ->
         sos:write("Hello world\n").

To run this we must first compile sos_test1 using the compiler in the Erlang development environment. Once we have done this then we can run the program as follows:

unix> sos sos_test1
Hello world

We can time this as follows:

> time sos sos_test1
Hello world
0.09u 0.04s 0:00.37 35.1

Which tells us that it took 0.09 seconds to load and run the program.

Here are few more simple programs, sos_test2 tests that autoloading works:

     main() ->
         X = lists:reverse("Hellow world"),


> sos sos_test2
dlrow wolleH

sos_test3 is an Erlang program which copies everything it sees on standard input to standard output (This is how to write a unix pipe process)

     -import(sos, [read/0, write/1]).
     main() ->
     loop() ->
         case read() of
             eof ->
             {ok, X} ->

For example:

> cat sos.html | cksum
2409969489      23031
> cat sos.html | sos sos_test3 | cksum
2409969489      23031

sos_test4 tests error handling:

     main() ->
         sos:write("I will crash now\n"),
         1 = 2,
         sos:write("This line will not be printed\n").

So for example:

> sos sos_test4
I will crash now


The shell script sos which starts everything is as follows:

     erl -boot /home/joe/erl/example_programs-2.0/examples-2.0/sos  -environment `printenv` -load $1

This just starts an erlang system from the bootfile sos.boot, the bootfile and the sos shell script are created by evaluating make_scripts/0

     make_scripts() ->
         {ok, Cwd} = file:get_cwd(),
         Script =
                 "$ROOT/lib/" ++ lib_location(kernel) ++ "/ebin",
                 "$ROOT/lib/" ++ lib_location(stdlib) ++ "/ebin"]},
         file:write_file("sos.boot", term_to_binary(Script)),
         {ok, Stream} = file:open("sos", write),
         io:format(Stream, "#!/bin/sh~nerl -boot ~s/sos "
                   " -environment `printenv` -load $1~n",
         unix:cmd("chmod a+x sos"),
     lib_location(Lib) ->

make_scripts/0 must be evaluated from within the Erlang development environment since it calls code filename and file which are not available to sos programs. Exactly how this function works is beyond the scope of this paper, the gory details can be found in the full version of the Erlang/OTP documentation.

The important point to note about the script is the last line,
{apply, {sos,main,[]}} this is function which is called when the system is started.

The sos main program

When the system is started using the bootfile described in the last section the function sos:main() is evaluated and when this terminates the system will halt:

     main() ->
                     fun start_io/0, fun handle_io/2),
                     fun handle_code/2),
                     const(0),  fun handle_error_logger/2),
                     const([]), fun handle_halt_demon/2),
                     fun start_env/0, fun handle_env/2), 
         Mod = get_module_name(),

This starts five servers (io, code...), loads the error handler, finds the name of the module which is to be run, loads this module and then runs the code in the module.

run(Mod) spawn links Mod:main() and waits for it to terminate. When it terminates stop_system is called:

     run(Mod) ->
         Pid = spawn_link(Mod, main, []),
         on_exit(Pid, fun(Why) -> stop_system(Why) end).

Main starts a lot of different servers, before going into the details of how the individual servers work we explain the generic framework that is used to build client-servers.

Server support

To create a server we call make_server(Name, Fun1, Fun2). Name is the global name of the server, Fun1() is expected to return State1 the initial state of the server. Evaluating Fun2(State, Query) should return {Reply, State1} if called with a remote procedure call or simply State1 if called with a cast. make_server is:

     make_server(Name, FunD, FunH) ->
                     fun() -> 
                            Data = FunD(),
                            server_loop(Name, Data, FunH) 

The server loop is simple:

     server_loop(Name, Data, Fun) ->
             {rpc, Pid, Q} ->
                 case (catch Fun(Q, Data)) of
                     {'EXIT', Why} ->
                         Pid ! {Name, exit, Why},
                         server_loop(Name, Data, Fun);
                     {Reply, Data1} ->
                         Pid ! {Name, Reply},
                         server_loop(Name, Data1, Fun)
             {cast, Pid, Q} ->
                 case (catch Fun(Q, Data)) of
                     {'EXIT', Why} ->
                         exit(Pid, Why),
                         server_loop(Name, Data, Fun);
                     Data1 ->
                         server_loop(Name, Data1, Fun)
             {eval, Fun1} ->
                 server_loop(Name, Data, Fun1)

To query the server we use rpc (short for Remote Procedure Call) which is:

     rpc(Name, Q) -> 
         Name ! {rpc, self(), Q},
             {Name, Reply} ->
             {Name, exit, Why} ->

Note how the code in the server loop and rpc interacts. The handler fun in the server is protected by a catch if an exception is raised in the server a {Name,exit,Why} message is sent back to the client. If this message is received by the client an exception is raised by evaluating exit(Why) in the client.

The net effect of this is to raise an exception in the client. Note that in the case where the client sent a query to the server that the server could not process the server continues with its old state.

Thus remote procedure calls function as transactions as far as the server is concerned. Either they work completely, or the server is rolled back to the state it was in before the remote procedure call was made.

If we just want to sent a message to the server and are not interested in the reply we call cast/2:

     cast(Name, Q) ->
         Name ! {cast, self(), Q}.

Amazingly we can change the behaviour of a server by sending it a different fun to use in the server loop:

     change_behaviour(Name, Fun) ->
         Name ! {eval, Fun}.

Recall that when we started the server the initial data structure is often a constant. We can define const(C) which returns a function which when evaluated evaluates to C.

     const(C) -> fun() -> C end.

Now we will turn our attention to the individual servers.

Code server

Recall that the code server was started by evaluating:

                fun handle_code/2),

load_module(Mod) is implemented as a remote procedure call to the code server:

     load_module(Mod) -> rpc(code, {load_module, Mod}).

The global state of the code server is simple [Mod] that is, a list of all modules which have been loaded (the initial value of this is [init, erl_prim_loader] -- these are preloaded i.e. compiled into the Erlang run-time systems kernel); for details read the Erlang/OTP documentation).

The server handler function handle_code/2 is thus:

     handle_code({load_module, Mod}, Mods) ->
         case member(Mod, Mods) of
             true ->
                 {already_loaded, Mods};
             false ->
                 case primLoad(Mod) of
                     ok ->
                         {{ok,Mod}, [Mod|Mods]};
                     Error ->
                         {Error, Mods}

and primLoad does the loading:

     primLoad(Module) ->
         Str = atom_to_list(Module),
         case erl_prim_loader:get_file(Str ++ ".jam") of
             {ok, Bin, FullName} ->
                 case erlang:load_module(Module, Bin) of
                     {module, Module} ->
                     {module, _} ->
                         {error, wrong_module_in_binary};
                     Other ->
                         {error, {bad_object_code, Module}}
             error ->
                 {error, {cannot_locate, Module}}


log_error(What) logs the error What on standard output, this is implemented as a cast:

     log_error(Error)  ->  cast(error_logger, {log, Error}).

the corresponding server handler function being:

     handle_error_logger({log, Error}, N) ->
         erlang:display({error, Error}),
         {ok, N+1}.

Note that the global state of the error handler is an integer N meaning the total number of errors which have occurred.

Halt demon

The halt demon is called when the system is halted. Evaluating on_halt(Fun) sets up a condition such that Fun() will be evaluated when the system is halted. Halting the system is done by calling the function stop_system():

     on_halt(Fun)     -> cast(halt_demon,{on_halt,Fun}).
     stop_system(Why) -> cast(halt_demon,{stop_system,Why}).

The server handler code for this is:

     handle_halt_demon({on_halt, Fun}, Funs) ->
         {ok, [Fun|Funs]};
     handle_halt_demon({stop_system, Why}, Funs) ->
         case Why of
             normal -> true;
             _      -> erlang:display({stopping_system,Why})
         map(fun(F) -> F() end, Funs),
         {ok, []}.     

IO server

The IO server allows access to STDIO, read() reads a line from standard input and write(String) writes a string to standard output:

     read()   -> rpc(io, read).
     write(X) -> rpc(io, {write, X}).

The initial state of the IO server is obtained by evaluating start_io():

     start_io() -> 
         Port = open_port({fd,0,1}, [eof, binary]),
         process_flag(trap_exit, true),
         {false, Port}.

And the IO handler is:

     handle_io(read, {true, Port}) -> 
         {eof, {true, Port}};
     handle_io(read, {false, Port}) ->
             {Port, {data, Bytes}} ->
                 {{ok, Bytes}, {false, Port}};
             {Port, eof} ->
                 {eof, {true,Port}};
             {'EXIT', Port, badsig} ->
                 handle_io(read, {false, Port});
             {'EXIT', Port, Why} ->
                 {eof, {true, Port}}
     handle_io({write,X}, {Flag,Port}) -> 
         Port ! {self(), {command, X}},
         {ok, {Flag, Port}}.

The state of the IO server is {Flag, Port} where Flag is true if eof has been encountered, otherwise false.

Environment server

The function env(E) is used to find the value of the environment variable E:

     env(Key) -> rpc(env, {lookup, Key}).

The server is:

     handle_env({lookup, Key}, Dict) -> 
         {lookup(Key, Dict), Dict}.

The initial state of the server is found by evaluating:

     start_env() ->
         Env = case init:get_argument(environment) of
                   {ok, [L]} -> 
                   error -> 
                        fatal({missing, '-environment ...'})
         map(fun split_env/1, Env).

Global process support

We need a few routines for keeping processes alive and registering global names.

keep_alive(name, Fun) makes a registered process called Name it is started by evaluating Fun() and if the process dies it is automatically restarted.

     keep_alive(Name, Fun) ->
         Pid = make_global(Name, Fun),
                 fun(Exit) -> keep_alive(Name, Fun) end).

make_global(Name, Fun) checks if there is a global process with the registered name Name. If there is no process it spawns a process to evaluate Fun() and registers it with the name Name.

     make_global(Name, Fun) ->
         case whereis(Name) of
             undefined ->
                 Self = self(),
                 Pid = spawn_fun(fun() ->
                     {Pid, ack} ->
             Pid ->

Support for processes

spawn_fun(Fun) and spawn_link(Fun) spawns (and links) a new process and evaluates Fun() within the newly spawned process.

     spawn_fun({'fun',Mod,Arity,Chksum,Env}) ->
         spawn(?MODULE, internal_call, 

     spawn_link_fun({'fun',Mod,Arity,Chksum,Env}) ->
         spawn(?MODULE, internal_call, 

You are not expected to understand how the above two routines work!

on_exit(Pid, Fun) links to Pid. If Pid dies with reason Why then Fun(Why) is evaluated:

     on_exit(Pid, Fun) ->
         spawn_fun(fun() -> 
                          process_flag(trap_exit, true),
                              {'EXIT', Pid, Why} ->

every(Pid, Time, Fun) links to Pid then every Time Fun() is evaluated. If Pid exits, this process stops.

     every(Pid, Time, Fun) ->
         spawn_fun(fun() ->
                           process_flag(trap_exit, true),
                           every_loop(Pid, Time, Fun)

     every_loop(Pid, Time, Fun) ->
             {'EXIT', Pid, Why} ->
         after Time ->
                 every_loop(Pid, Time, Fun)


get_module_name() gets the module name from the command line.

     get_module_name() ->
         case init:get_argument(load) of
             {ok, [[Arg]]} ->
             error ->
                 fatal({missing, '-load Mod'})

Finally a few small utilities, such as might be found in lists, are included here so as to make sos "self contained" ..

     lookup(Key, [{Key,Val}|_]) -> {found, Val};
     lookup(Key, [_|T])         -> lookup(Key, T);
     lookup(Key, [])            -> not_found.
     member(X, [X|_]) -> true;
     member(H, [_|T]) -> member(H, T);
     member(_, [])    -> false.
     map(F, [H|T]) -> [F(H)|map(F, T)];
     map(F, [])    -> [].
     reverse(X) -> reverse(X, []).
     reverse([H|T], L) -> reverse(T, [H|L]);
     reverse([], L)    -> L.
     module_name(Str) ->
         case (catch list_to_atom(Str)) of
             {'EXIT', _} ->
             Mod -> Mod

And something to report errors:

     fatal(Term) ->
         log_error({fatal, Term}),
         stop_system({fatal, Term}).


Sos uses its own error handler (not the standard handler) this is as follows:

     undefined_function(sos, F, A) ->
     undefined_function(M, F, A) ->
         case sos:load_module(M) of
             {ok, M} ->
                 case erlang:function_exported(M,F,length(A)) of
                     true ->
                         apply(M, F, A);
                     false ->
             {ok, Other} ->
             already_loaded ->
             {error, What} ->
     undefined_global_name(Name, Message) ->

We bomb if the undefined function is in sos itself.

If the error handler is called for any other module we call sos:load_module to try and load the module.

     undefined_global_name(Name, Message) ->

Transformed from examples-2.0.tex by latex2html.erl and edited by hand to fix problems