Introduction
Erlang
Functional
Concurrent
Distributed
“Soft” real-time
OTP (fault-tolerance, hot code update...)
Open source
Typical applications
- Telecoms
- Switches (POTS, ATM, IP, ...)
- GPRS
- SMS applications
- Internet applications
- Twitter (backbone)
- Facebook (chat)
- Online shopping (Klarna AB)
- 3D modelling (Wings3D)
History lesson
- 1981 – Ericsson CSLab formed
- 1986 – Prolog “games”
- 1987 – Erlang name appears
- 1989 – Prototypes show 9–22 fold increase in design efficiency
- 1995 – AXE-N fails after 8 years
- 1998 – AXD301 delivered
- 1998 – Erlang banned; goes open source
- 2007 – Ericsson uses Erlang for new products
Essence
- A simple functional language
- No types. Heresy!
- Dynamically typed
- No share memory
- Open Telecom Platform libraries
- Practically “proven” programming patterns
- Utilities
Sequential aspects
We cover the following aspects. Click on the links for further information.
Data types and variables (Erlang manual)
Function definitions (Erlang manual)
Pattern matching (Erlang manual)
Evaluation strategy
Tail recursion (Learn some Erlang for Great Good!)
Data types
Numbers
- Integers (arbitrarily big)
- Floats
Atoms
start_with_a_lower_case_letter ’Anything_inside_quotes\n\09’
Tuples
{} {atom, another_atom, ‘PPxT’} {atom, {tup, 2}, {{tup}, element}}
- Lists
[] [65,66,67,68] = “ABCD” % bad practice (experts only) [1, true] [1 | [true] ]
Data types (Records)
- Definition
-record(person, {name = “”, phone = [], address}).
- Creation
X = #person{name = “Joe”, phone = [1,1,2], address= “here”}
- Accessing record fields
X#person.name X#person{phone = [0,3,1,1,2,3,4]}
Modeling data
data Tree a = Leaf a | Node (Tree a) (Tree a)
edoc style “types”
- Atoms to indicate which constructor is used at top-level
- Tuples to collect the arguments of the constructor
Example:
Node (Node (Leaf 3) (Leaf 4)) (Leaf 5)
becomes{node, {node, {leaf,3}, {leaf, 4}}, {leaf, 5}}
Variables
- Identifiers
A_long_variable_name
- Must start with an upper case letter
- Can store values
- Can be bound only once!
- Bound variables cannot change values
Functions
- Separate cases by
;
- Finish definition with
.
(often forgotten)factorial(0) -> 1; factorial(N) -> N * factorial(N-1).
Evaluation strategy
Eager evaluation strategy
- It evaluates the arguments of a function first and then applies its definition.
Example
factorial(3)
It applies the definition offactorial(N)
withN = 3
(second clause), thus
factorial(3) == 3 * factorial(3 - 1)
It now evaluates the argument of the function *
,
which implies evaluating factorial(3 - 1)
. For that,
Erlang firstly evaluates the argument of the function
(eager evaluation strategy).
factorial(3) == 3 * factorial(2)
As before, Erlang applies the second clause with N = 2
.
factorial(3) == 3 * (2 * factorial (2 - 1))
Erlang then reduces the argument of factorial
.
factorial(3) == 3 * (2 * factorial (1))
Now, the second clause with N = 1
gets applied as follows.
factorial(3) == 3 * (2 * (1 * factorial (1 - 1))
Finally, we obtain
factorial(3) == 3 * (2 * (1 * factorial (0))
and Erlang can then apply the first clause.
factorial(3) == 3 * (2 * (1 * 1))
By definition of *
, we have that
factorial(3) == 6
as expected.
Pattern matching
The
factorial
definition uses pattern matching over numbers- A zero number (first clause)
- A number different from zero (second clause)
A more involved example.
Function
area
to compute the area of different geometrical figures.area({square, Side}) -> Side * Side ; area({circle, Radio}) -> Radio*Radio*math:pi().
Patterns:
{square, Side}
and{circle, Radio}
{square, Side}
matches{square, 4}
and binds4
to variableSide
{circle, Radio}
matches{circle, 1}
and binds1
to variableRadio
More pattern matching
{B, C, D} = {10, foo, bar}
- Succeeds: binds
B
to10
,C
tofoo
andD
tobar
- Succeeds: binds
{A, A, B} = {abc, abc, foo}
- Succeeds: binds
A
toabc
,B
tofoo
- Succeeds: binds
{A, A, B} = {abc, def, 123}
- Fails
[A,B,C,D] = [1,2,3]
- Fails
Even more pattern matching
[H|T]= [1,2,3,4]
- Succeeds: binds
H
to1
,T
to[2,3,4]
- Succeeds: binds
[H|T] = [abc]
- Succeeds: binds
H
toabc
,T
to[]
- Succeeds: binds
[H|T] = []
- Fails
{A, _ , [ B | _ ] , {B} } = {abc,23,[22,x],{22}}
- Succeeds: binds
A
toabc
,B
to22
- Succeeds: binds
Modules
Basic compilation unit is a module
- Module name = file name (.erl)
Modules contain function definitions
- Like
factorial
andarea
(see above) - Some functions can be exported to be usable from outside of the module
- Like
Let us create the module
math_examples
as follows.-module(math_examples). -export([factorial/1,area/1]). factorial(0) -> 1; factorial(N) -> N * factorial(N-1). area({square, Side}) -> Side*Side ; area({circle, Radio}) -> Radio*Radio*math:pi().
Running the examples.
> c(math_examples). {ok,math_examples} > math_examples:factorial(3). 6 > math_examples:area({square,4}). 16 > math_examples:area({circle,1}). 3.141592653589793
List examples
We want to define different functions working on lists
> c(list_examples). {ok,list_examples} > list_examples:sum([1,2,3,4]). 10 > list_examples:len([0,1,0,1]). 4 > list_examples:append([5,4],[1,2,3]). [5,4,1,2,3]
We will define them recursively (inductively)
- Base case: empty list (
[]
) - Recursive case: a list with at least one element (
[X | XS]
)
- Base case: empty list (
Adding elements from a list
Simplest case (base case)
sum([]) == 0
The inductive case
- Focus on an example
sum([X1,X2,X3,X4]) == X1 + X2 + X3 + X4
We should try to rewrite this equation so that it appears the head of the list (
X1
) and the rest of the list ([X2,X3,X4]
) applied tosum
. Let us associate the sum as follows.sum([X1,X2,X3,X4]) == X1 + (X2 + X3 + X4)
We know that
X2 + X3 + X4
is equal tosum([X2,X3,X4])
. After all, this is the function that we want to define.We can then rewrite the equation above as:
sum([X1,X2,X3,X4]) == X1 + sum([X2,X3,X4])
- We generalize the last equation for the case when the
list has a head element
X
and the rest of the list isXS
sum([X | XS]) == X + sum(XS)
- We can now define the
sum
function as follows.
sum([X|XS]) -> X + sum(XS); sum([]) -> 0.
Why is the base case as second clause?
- We generalize the last equation for the case when the
list has a head element
- Focus on an example
More examples
Computing the length of a list
len([X|XS]) -> 1 + len(XS) ; len([]) -> 0.
- Observe that
X
is not used on the right-hand side. It can be replaced by_
len([_|XS]) -> 1 + len(XS) ; len([]) -> 0.
- Observe that
Append elements to the end of a list
append([X|XS],YS) -> [X | append(XS,YS) ] ; append([], YS) -> YS.
Tail recursion
Programming pattern to increase performance
- It helps compilers when optimizing code!
Inefficient recursive definition
len([_|XS]) -> 1 + len(XS) ; len([]) -> 0.
- Observe the evaluation of
len([1,2,3])
len([1,2,3]) == 1 + len([2,3]) len([1,2,3]) == 1 + (1 + len([3])) len([1,2,3]) == 1 + (1 + (1 + len([]))) len([1,2,3]) == 1 + (1 + (1 + 0)) len([1,2,3]) == 1 + (1 + 1) len([1,2,3]) == 1 + 2 len([1,2,3]) == 3
At the time of reaching the marked line, Erlang needs to keep in memory a long expression
After that line, it starts shrinking the expression
Imaging how it will work for a very big list!
- Observe the evaluation of
More efficiency by tail recursion
Space (constant if we assume elements of the list have the same size)
Efficiency (No returns from recursive calls)
What is the trick?
- Use of accumulators (partial results)
- There are no more computations after the recursive call
We define
len_a
, the tail recursive version oflen
Function
len_a
has an extra parameters capturing the partial result of the function, i.e., how many elementslen_a
has seen so farlen_a([_|XS], Acc) -> len_a(XS, Acc+1); len_a([], Acc) -> Acc.
We define
len
based onlen_a
as followslen(XS) -> len_a(XS, 0).
What about the tail recursive version of
sum
andappend
?Homework!
Hint: the partial result for
sum
consists on the addition of all the numbers that the function has seen so farHint: to implement
append
think about the tail recursive version of a function which reverses a list, i.e.,reverse([1,2,3,4]) = [4,3,2,1]
A note on the use of records and functions
Records are very convenient in several situations
Sometimes, functions require extra arguments but we realize about that later on
For instance, assume we would like to write the following error reporting function
debug(50) -> io:format("Item not found in the stock ~p",[]) ; debug(100) -> io:format("User not registered ~p",[]) ; debug(ErrCode) -> io:format("Unknown error ~p. Shutting down ~n",[ErrCode]).
Now, you would like to show part of your program state when an unknown error happens for debugging purposes
debug(50,_) -> io:format("Item not found in the stock ~p",[]) ; debug(100,_) -> io:format("User not registered ~p",[]) ; debug(ErrCode,State) -> io:format("Unknown error = ~p State = ~p ~n",[ErrCode, State]),
If the function
debug
had 100 cases, you need to modify 100 lines!Use records for those arguments that might get extended in the future!
-record(arg, { number }). debug(#arg{ number = 50}) -> io:format("Item not found in the stock ~p",[]) ; debug(#arg{ number = 100}) -> io:format("User not registered ~p",[]) ; debug(#arg{ number = ErrCode}) -> io:format("Unknown error ~p. Shutting down ~n",[ErrCode]).
If we want to add the state to print out, it is easy: modify the definition of
arg
and only the line that uses that extra information.-record(arg, {number, state}). debug(#arg{number = 50}) -> io:format("Item not found in the stock ~p",[]) ; debug(#arg{number = 100}) -> io:format("User not registered ~p",[]) ; debug(#arg{number = ErrCode, state = State}) -> io:format("Unknown error ~p. Shutting down ~n",[ErrCode, State]).
It is possible to refer to the whole register passed as argument
-record(arg, {number, state}). debug(#arg{number = 50}) -> io:format("Item not found in the stock ~p",[]) ; debug(#arg{number = 100}) -> io:format("User not registered ~p",[]) ; debug(Arg = #arg{number = ErrCode, state = State}) -> io:format("Unknown error ~p. Shutting down ~n",[ErrCode, State]), io:format("The function was called with the record ~p~n",[Arg]),
Pattern matching happens at the level of the argument (it is a record) and the record's components
This would be particularly helpful when doing the laboration CCHAT