程序代写代做代考 concurrency data structure Erlang distributed system Java prolog Haskell Advanced Programming – Introduction to Erlang

Advanced Programming – Introduction to Erlang

Advanced Programming
Introduction to Erlang

Ken Friis Larsen
kflarsen@diku.dk

Department of Computer Science
University of Copenhagen

October 2, 2018

1 / 39

Today’s Buffet

I Erlang the language

I Kahoot!

I Concurrency-oriented programming

I (Distributed systems with Erlang)

These are slides that should have been lecture notes, but for now they are

condemned to be neither.

2 / 39

Erlang — The Man

I Agner Krarup Erlang

I 1878–1929

I Invented queueing theory
and traffic engineering,
which is the basis for
telecommunication
network analysis.

3 / 39

Erlang Customer Declaration

Erlang is a:

I a concurrency-oriented language

I dynamically typed

I with a strict functional core language

Time to Kahoot!

4 / 39

Fundamental Stuff

I Integers and floating-points works as expected:

1> 21+21.
42
2> 3/4.
0.75
3> 5 div 2.
2

I We have lists:

4> [21,32,67] ++ [100,101,102].
[21,32,67,100,101,102]

I Strings are just lists of characters, and characters are just
integers:

5> “Sur” ++ [112, 114, $i, $s, $e].
“Surprise”

5 / 39

Tuples and Atoms

I Erlang uses curly braces for tuples:

1> {“Bart”, 9}.
{“Bart”,9}

I Atoms are used to represent non-numerical constant values
(like enums in C and Java). Atom is a sequence of alphanumeric
characters (including @ and _) that starts with a lower-case
letter (or is enclosed in single-quotes):

2> bloody_sunday_1972.
bloody_sunday_1972
3> [{bart@simpsons, “Bart”, 9}, {’HOMER’, “Homer”, 42}].
[{bart@simpsons,”Bart”,9},{’HOMER’,”Homer”,42}]

6 / 39

Names and Patterns

I Names (variables) start with an upper-case letter.
I Like in Haskell and Prolog we use patters to take things apart:

1> Homer = “Homer”.
2> P = {point, 10, 42}.
3> [ C1, C2, C3 | Tail ] = Homer.
“Homer”
4> C2.
111
5> Tail.
“er”
6> {point, X, Y} = P.
{point,10,42}
7> X.
10
8> Y.
42

7 / 39

List Comprehensions

1> Digits = [0,1,2,3,4,5,6,7,8,9].
[0,1,2,3,4,5,6,7,8,9]
2> Evens = [ X || X <- Digits, X rem 2 =:= 0]. [0,2,4,6,8] 3> Cross = [{X,Y} || X <- [1,2,3,4], Y <- [11,22,33,44]]. [{1,11}, {1,22}, {1,33}, {1,44}, {2,11}, {2,22}, ... ] 4> EvenXs = [{X,Y} || {X,Y} <- Cross, X rem 2 =:= 0]. [{2,11},{2,22},{2,33},{2,44},{4,11},{4,22},{4,33},{4,44}] 8 / 39 Maps 1> M = #{ name => “Ken”, age => 44}.
#{age => 44,name => “Ken”}
2> ClunkyName = maps:get(name, M).
“Ken”
3> #{name := PatternName} = M.
4> PatternName.
“Ken”
5> #{name := Name, age := Age} = M.
#{age => 44,name => “Ken”}
6> {Name, Age}.
{“Ken”, 44}
7> Wiser = M#{age := 45}.
#{age => 45,name => “Ken”}
8> WithPet = M#{pet => cat}.
#{age => 44,name => “Ken”,pet => cat}

9 / 39

Functions

I Remember the move function from Exercise Set 0 (Haskell)?
move :: Direction -> Pos -> Pos
move North (x,y) = (x, y+1)
move West (x,y) = (x-1, y)

I In erlang:
move(north, {X, Y}) -> {X, Y+1};
move(west, {X, Y}) -> {X-1, Y}.
(note that we use semicolon to separate clauses, and period to
terminate a declaration).

I Or naming a function literal:
Move = fun(Dir, {X,Y}) ->

case Dir of
north -> {X, Y+1};
west -> {X-1, Y}

end
end.

10 / 39

Modules

If we want to declare functions (rather that naming literals) then we
need to put them in a module.
Modules are defined in .erl files, for example erltest.erl:

-module(erltest).
-export([move/2, qsort/1]).

move(north, {X, Y}) -> {X, Y+1};
move(west, {X, Y}) -> {X-1, Y}.

qsort([]) -> [];
qsort([Pivot|Rest]) ->

qsort([X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([X || X <- Rest, X >= Pivot]).

11 / 39

Compiling Modules

I Using the function c, we can compile and load modules in the
Erlang shell:

1> c(erltest).
{ok,erltest}

I We can now call functions from our module:

2> erltest:qsort([101, 43, 1, 102, 24, 42]).
[1,24,42,43,101,102]

I Or use them with functions from the standard library:

3> Moves = [{north, {1,1}}, {west, {43,42}},
{north, {23,22}}].

4> lists:map(fun({Dir,Pos}) ->
erltest:move(Dir, Pos) end,

Moves).
[{1,2},{42,42},{23,23}]

12 / 39

Student Activation: Define your favourite function

Make a module, fib, with your
favourite (recursive) function.

13 / 39

Exceptions

I We can catch exceptions using try:

try Expr of
Pat1 -> Expr1;
Pat2 -> Expr2;

catch
ExPat1 -> ExExpr1;
ExPat2 -> ExExpr2;

after
AfterExpr

end

I And we can throw an exception using throw:

throw(Expr)

14 / 39

Exceptional Moves

-module(exceptional_moves).
-export([move/2,ignore_invalid/2]).

move(north, {X, Y}) -> {X, Y+1};
move(west, {0, _}) -> throw(invalid_move);
move(west, {X, Y}) -> {X-1, Y}.

ignore_invalid(Dir, Pos) ->
try move(Dir, Pos)
catch

invalid_move -> Pos
end.

15 / 39

Algebraic Data Types

I In Erlang we use tuples and atoms to build data structures.

I Representing trees in Haskell

data Tree a = Leaf | Node a (Tree a) (Tree a)
t = Node 6 (Node 3 Leaf Leaf) (Node 9 Leaf Leaf)

I Representing trees in Erlang

T = {node, 6, {node, 3, leaf, leaf},
{node, 9, leaf, leaf}}.

16 / 39

Traversing Trees

I in Haskell:

contains _ Leaf = False
contains key (Node k left right) =

if key == k then True
else if key < k then contains key left else contains key right I in Erlang: contains(_, leaf) -> false;
contains(Key, {node, K, Left, Right}) ->

if Key =:= K -> true;
Key < K -> contains(Key, Left);
Key > K -> contains(Key, Right)

end.

17 / 39

Binary Data

I Erlang have outstanding support for working with raw
byte-aligned data (binaries)

I <> is an n-byte value
I 8-bit: <<111>>
I 32-bit: <<0,0,0,0>>
I 40-bit: <<"Homer">>

I Bit Syntax is used to pack and unpack binaries, here we can
specify the size and encoding details (like endianess, for
instance) for each element of the binary
I General form:

<>

where each element E have the form:

V:size/type

where V is a value and size and type can be omitted.

18 / 39

8-Bit Colour

I Suppose we need to work with 8-bit colour images, encoded in
RGB format with 3 bits for the red and green components and
2 bits for the blue component.

I Pack and unpack functions:

pack8bit(R,G,B) ->
<>.

unpack8bit(<>) ->
{R, G, B}.

19 / 39

Concurrency-Oriented Programming

I The world is concurrent

I Thus, when we write programs that model or interact with the
world concurrency should be easy to model.

20 / 39

Parallelism 6= Concurrency

I Parallelism
I use multiple CPUs to perform a computation
I maximise speed

I Concurrency
I Model and interact with the world
I minimise latency

21 / 39

Concurrency In Erlang

I Processes are lightweight and independent

I Processes can only communicate through message passing

I Message passing is fast

I Message passing is asynchronous (mailbox model)

22 / 39

Processes

I Processes can only communicate through message passing

I All processes have a unique process ID (pid)

I Any value can be send (serialization)

I We can send messages:

Pid ! Message

(we can get our own pid by using the build-in function self/0)

23 / 39

Receiving messages

I Mailbox ordered by arrival – not send time
I We can receive messages:

receive
Pat1 -> Expr1;
Pat2 when … -> Expr2;

after
Time -> TimeOutExpr

end

times-out after Time milliseconds if we haven’t received a
message matching one of Pat1, Pat2 with side condition, . . . .

24 / 39

Spawning Processes

I We can spawn new processes:

Pid = spawn(Fun)

or

Pid = spawn(Module, Fun, Args)

25 / 39

Concurrency Primitives, Summary

I We can spawn new processes:
Pid = spawn(Fun)

(we can get our own pid by using the build-in function self)
I We can send messages:

Pid ! Message
I We can receive messages:

receive
Pat1 -> Expr1;
Pat2 -> Expr2;

after
Time -> TimeOutExpr

end

where we get a time-out after Time milliseconds if we haven’t
received a message matching one of Pat1, Pat2, . . . .

26 / 39

Student Activation: Make It Concurrent

Let’s make a concurrent (parallel)
version of the recursive function

from fib (the one we made earlier).

27 / 39

Dealing With State

I Functions are pure (stateless).

I Processes are stateful.

I We organise our code as micro-servers that manage a state
which can be manipulated via a client API.

28 / 39

Client–Server Basic Set Up

I We often want computations to be made in a server process
rather than just in a function.

I That is, we start with something like the following template:
start() -> spawn(fun loop/0).
request_reply(Pid, Request) ->

Pid ! {self(), Request},
receive

{Pid, Response} -> Response
end.

loop() ->
receive

{From, Request} ->
From ! {self(), ComputeResult(Request)},
loop();

{From, Other} ->
From ! {self(), {error,Other}},
loop()

end.
29 / 39

Example: Move Server

start() -> spawn(fun loop/0).

move(Pid, Dir, Pos) -> request_reply(Pid, {move, Dir, Pos}).

request_reply(Pid, Request) ->
Pid ! {self(), Request},
receive

{Pid, Response} -> Response
end.

loop() ->
receive

{From, {move, north, {X, Y}}} ->
From ! {self(), {X, Y+1}},
loop();

{From, {move, west, {X, Y}}} ->
From ! {self(), {X-1, Y}},
loop()

end.

30 / 39

Student Activivation: Count Server

I Let’s make a server that can keep track of a counter

I What is the client API?

I What is the internal state?

31 / 39

Example: Phone-Book, Interface

start() -> spawn(fun() -> loop(#{}) end).

add(Pid, Contact) ->
request_reply(Pid, {add, Contact}).

list_all(Pid) ->
request_reply(Pid, list_all).

update(Pid, Contact) ->
request_reply(Pid, {update, Contact}).

32 / 39

Example: Phone-Book, Impletemtation 1

loop(Contacts) ->
receive

{From, {add, Contact}} ->
{Name,_,_} = Contact,
case maps:is_key(Name, Contacts) of

false ->
From ! {self(), ok},
loop(Contacts#{Name => Contact});

true ->
From ! {self(), {error, Name, is_already_there}},
loop(Contacts)

end;

33 / 39

Example: Phone-Book, Implementation 2

{From, list_all} ->
List = maps:to_list(Contacts),
From ! {self(),

{ok, lists:map(fun({_, C}) -> C end, List)}},
loop(Contacts);

{From, {update, Contact}} ->
{Name,_,_} = Contact,
NewContacts = maps:remove(Name, Contacts),
From ! {self(), ok},
loop(maps:put(Name, Contact, NewContacts));

{From, Other} ->
From ! {self(), {error,unknow_request, Other}},
loop(Contacts)

end.

34 / 39

Distributed Programming

I Simple definition: A distributed system is a system that involves
at least two computers that communicate.

I Two models:
I Closed world: Distributed Erlang, Java’s RMI, .NET Remoting
I Open world: IP Sockets

I Why distribute a system?
I Inherently
I Reliability
I Scalability
I Performance

35 / 39

Distributed Programs in Erlang

I Distributed Erlang for tightly coupled computers in a secure
environment.
I spawn(Node, Fun) to spawn a process running Fun on Node
I {RegAtom, Node} ! Mesg sends Mesg to the process registered

as RegAtom at Node.
I monitor_node(Node, Flag) register the calling process for

notification about Node if Flag is true; if Flag is false then
monitoring is turned off.

I Sockets for untrusted environments:
I To build a middle-ware layer for Erlang nodes
I For inter-language communication.

See the documentation for gen_tcp and gen_udp

36 / 39

http://www.erlang.org/doc/man/gen_tcp.html
http://www.erlang.org/doc/man/gen_udp.html

Setting Up Some Erlang Nodes

I To start nodes on the same machine, start erl with option
-sname

I To start nodes on different machines, start erl with options
-name and -setcookie:
I On machine A:

erl -name bart -setcookie BoomBoomShakeTheRoom

I On machine B:

erl -name homer -setcookie BoomBoomShakeTheRoom

I rpc:call(Node, Mod, Fun, Args) evaluates Mod:Fun(Args)
on Node. (See the the manual page for rpc for more
information.)

37 / 39

http://www.erlang.org/doc/man/rpc.html
http://www.erlang.org/doc/man/rpc.html

Common Erlang Pitfalls

I Variables starts with an upper-case letter, atoms starts with a
lower-case letter.

I if expressions (you need to understand what a guard
expression is).

I Misunderstanding of how patterns works.

I Functions starts processes, processes runs functions, functions
are defined in modules.

I Not realising when to use asynchronous communication and
when to use synchronous communication.

38 / 39

Summary

I Parallelism is not the same as concurrency.

I Share-nothing (that is, immutable data) and message passing
takes a lot of the pain out of concurrent programming.

I Study phonebook.erl for a short tour of Erlang.

I Learning opportunity: See if you can make the code shorter or
simpler by using map syntax rather than library functions.

39 / 39