程序代写代做代考 data structure compiler html kernel Erlang Concurrent Programming

Concurrent Programming
CS511
1/41

(Lack of) Types
Documenting Types using spec Tail Recursion
Exceptions
Control Structures
2/41

Erlang is Strongly Typed
1 2 3 4 5
1> 6+”1″.
** exception error: an error occurred when evaluating an arithmetic expression
in operator +/2 called as 6 + “1”
Good, but there is no static type-checking…
3/41

Recall from Previous Class
1 2 3 4 5 6 7 8 9
10
drivers_license(Age) when Age < 16 -> forbidden ;
drivers_license(Age) when Age == 16 -> ’learners permit’ ;
drivers_license(Age) when Age == 17 -> ’probationary license’ ;
drivers_license(Age) when Age >= 65 ->
’vision test recommended but not required’ ;
drivers_license(_) -> ’full license’.
4/41

Types
1 2> c1:drivers_license(45).
2 ’full license’
3 3> c1:drivers_license(“hi”).
4 ’vision test recommended but not required’
􏰀 What is going on?
􏰀 Recall the comparison order
number < atom < reference < fun < port < pid < tuple < map < nil < list < bitstring 1 ... 2 drivers_license(Age) when Age >= 65 ->
3 ’vision test recommended but not required’ ;
4 …
5/41

Types
drivers_license(Age) when not(is_number(Age)) -> throw(wrong_argument_type);
1 2 3 4 5
drivers_license(Age) when Age < 16 -> forbidden ;
% the rest follows without change
􏰀 Other type-checking predicates:
is_atom/1, is_function/1, is_boolean/1, is_record/1,…
􏰀 More on exceptions later
9> c1:drivers_license(“hi”).
** exception throw: wrong_argument_type
in function c1:drivers_license/1 (c1.erl, line 6)
1 2 3
6/41

(Lack of) Types
Documenting Types using spec Tail Recursion
Exceptions
Control Structures
7/41

Documenting Types
􏰀 Type specifications:
-spec Function(ArgType1, …, ArgTypeN)->ReturnType.
or
-spec Function(ArgName1 :: Type1, …, ArgNameN :: TypeN)->RT
􏰀 Type specifiers are used for:
􏰀 Documentation of intended usage 􏰀 Automatic detection of type errors
􏰀 The compiler does not check type but there are tools for doing this
8/41

Type Declarations – Examples
1 2 3 4 5 6 7 8 9
10 11 12
-spec drivers_license(integer()) -> atom().
drivers_license(Age) when Age < 16 -> forbidden ;
drivers_license(Age) when Age == 16 -> ’learners permit’ ;
drivers_license(Age) when Age == 17 -> ’probationary license’ ;
drivers_license(Age) when Age >= 65 ->
’vision test recommended but not required’ ;
drivers_license(_) -> ’full license’.
9/41

Dialyzer
􏰀 Checks that given specifications agree with call patterns 􏰀 Also detects exceptions and dead code
􏰀 It does so loosely using so called “Success Typings” http://www.it.uu.se/research/group/hipe/papers/ succ_types.pdf
􏰀 Assume that all is good in terms of typing (start from most general possible type) and then refining this view as the code analysis progresses
10/41

Dialyzer
1
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20
􏰀 Before using this tool you must initialize its internal tables (Persistent Lookup Tables)
􏰀 This process can take 5 minutes or more
$ dialyzer –build_plt –apps erts kernel stdlib crypto mnesia sasl common_test eunit
Creating PLT /Users/ebonelli/.dialyzer_plt … Unknown functions:
compile:file/2 compile:forms/2 compile:noenv_forms/2 compile:output_generated/1 cover:analyse/2 cover:analyse_to_file/2 cover:analyse_to_file/3 cover:compile_beam/1 cover:export/1 cover:get_main_node/0 cover:import/1 cover:imported_modules/0 cover:start/0 cover:start/1
cover:stop/0 cover:stop/1 cover:which_nodes/0
11/41
dbg:p/2

Checking Type Declarations
1 2 3 4 5 6 7 8 9
10 11 12
1 2
3 4
-spec drivers_license(integer()) -> atom().
drivers_license(Age) when Age < 16 -> forbidden ;
drivers_license(Age) when Age == 16 -> ’learners permit’ ;
drivers_license(Age) when Age == 17 -> ’probationary license’ ;
drivers_license(Age) when Age >= 65 ->
’vision test recommended but not required’ ;
drivers_license(_) -> ’full license’.
We check our code with dialyzer
$ dialyzer c1.erl
Checking whether the PLT /Users/ebonelli/.dialyzer_plt is
up-to-date… yes
Proceeding with analysis… done in 0m1.03s
done (passed successfully)
12/41

Checking Type Declarations
1 2 3 4 5
1 2
3 4
-spec drivers_license(integer()) -> string().
drivers_license(Age) when Age < 16 -> forbidden ;
%…other clauses here…
We check our code with dialyzer
$ dialyzer c1.erl
Checking whether the PLT /Users/ebonelli/.dialyzer_plt is
up-to-date… yes Proceeding with analysis …
c1.erl:5: Invalid type specification for function c1: drivers_license/1. The success typing is (_) -> ’ forbidden’ | ’full license’ | ’learners permit’ | ’ probationary license’ | ’vision test recommended but not
required’
done in 0m1.09s
done (warnings were emitted)
5 6
13/41

Checking Type Declarations
1 2 3 4 5 6 7 8 9
10 11 12
1 2
3 4
-spec drivers_license(integer()) -> string().
drivers_license(Age) when Age < 16 -> forbidden ;
drivers_license(Age) when Age == 16 -> ’learners permit’ ;
drivers_license(Age) when Age == 17 -> “probationary license” ;
drivers_license(Age) when Age >= 65 ->
’vision test recommended but not required’ ;
drivers_license(_) -> ’full license’.
We check our code with dialyzer
$ dialyzer c1.erl
Checking whether the PLT /Users/ebonelli/.dialyzer_plt is
up-to-date… yes
Proceeding with analysis… done in 0m0.99s
done (passed successfully)
14/41

Type Declarations – More Examples
􏰀 Type variables can be used in specifications to specify relations for the input and output arguments of a function
􏰀 For example, the following specification defines the type of a polymorphic identity function:
-spec id(X) -> X.
􏰀 Notice that the above specification does not restrict the input and output type in any way
15/41

Type Declarations – More Examples
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16
􏰀 Type variables can be constrained using a when clause
􏰀 The :: constraint should be read as “is a subtype of”
%% sum(L) returns the sum of the elements in L
-spec sum(List) -> number() when List :: [number()].
%% min(L) -> returns the minimum element of the list L -spec min(List) -> Min when
List :: [T,…], Min :: T,
T :: term().
%% append(X, Y) appends lists X and Y
-spec
append(List1, List2) -> List3 when List1 :: [T],
List2 :: [T],
List3 :: [T],
T :: term().
16/41

Type Expressions 1/3
􏰀 Singletons can be either integers or atoms: 􏰀 1,2or42
􏰀 ’foo’, ’bar’ or ’atom’ 􏰀 foo, 42
􏰀 Unions of singletons, what we normally refer to as “types”: 􏰀 integer(): any integer value
􏰀 float(): any floating point value 􏰀 atom(): any atom
􏰀 pid(): a process identifier
􏰀 ref(): a reference
􏰀 fun(): a function 􏰀 … and many more
17/41

Type Expressions 2/3
􏰀 Types for compound data structures: 􏰀 tuple(): a tuple of any form
􏰀 list(): a proper list of any length
􏰀 Union type constructor 􏰀 type | type
1 -spec f(’a’ | 1) -> ’b’ | 1. 2 f(1) ->
3 1;
4 f(a) ->
5 b.
18/41

Type Expressions 3/3
Some built-in types and how they are defined1:
term()
boolean()
byte()
char()
nil()
number()
list()
nonempty list() string()
nonempty string() function() module()
no return()
any()
’false’ — ’true’ 0..255
0..16#10ffff
[]
integer() — float() [any()]
nonempty list(any()) [char()]
[char(),…]
fun()
atom()
none()
1 http://erlang.org/doc/reference_manual/typespec.html
19/41

Defining Types – An Example
􏰀 Use of type directive
1 %%% {empty} — Empty tree
2 %%% {node,Data, LeftTree, RightTree} — Non empty tree
3
4 -type btree() :: {empty} | {node,term(),btree(),btree()}. 5
6 -spec sizeT(btree()) -> number().
7
8 sizeT({empty}) ->
9 0;
10 sizeT({node,_D,LT,RT}) ->
11 1 + sizeT(LT) + sizeT(RT).
20/41

Defining Types – Another Example
We would like to define our own type that specifies what a card
looks like.
1 -type value() :: 1..13.
2 -type suit() :: spade | heart | diamond | clubs. 3 -type card() :: {card, suit(), value()}.
4 -spec suit(card()) -> suit().
Define the type of a deck of cards.
1 -type deck() :: list(card())
21/41

An Example
1 -module(cards).
2 -export([kind/1, main/0]).
3
4 -type suit() :: spades | clubs | hearts | diamonds.
5 -type value() :: 1..10 | j | q | k.
6 -type card() :: {suit(), value()}.
7
8 kind({_, A}) when A >=
9 kind(_) -> face.
10
11 main() ->
12 number =
13 face =
14 number =
15 face =
kind({spades , kind({hearts , kind({rubies , kind({clubs ,
7}), k}), 4}),
q}).
1 1> c1:main().
2 face
Somewhat unexpected…
1, A =< 10 -> number;
22/41

An Example
1 2
3 4 5
$ dialyzer c1.erl
Checking whether the PLT /Users/ebonelli/.dialyzer_plt is
up-to-date… yes Proceeding with analysis …
done in 0m1.33s
done (warnings were emitted)
According to Dialyzer, everything is ok.
23/41

An Example
1 -module(cards).
2 -export([kind/1, main/0]).
3
4 -type suit() :: spades | clubs | hearts | diamonds.
5 -type value() :: 1..10 | j | q | k.
6 -type card() :: {suit(), value()}.
7
8 -spec kind(card()) -> face | number.
9 kind({_, A}) when A >=
10 kind(_) -> face.
11
12 main() ->
1, A =< 10 -> number;
7}), k}), 4}),
q}).
13 number =
14 face =
15 number =
16 face =
kind({spades , kind({hearts , kind({rubies , kind({clubs ,
24/41

An Example
1 2
3 4 5
6 7
$ dialyzer c1.erl
Checking whether the PLT /Users/ebonelli/.dialyzer_plt is
up-to-date… yes Proceeding with analysis …
c1.erl:34: Function main/0 has no local return c1.erl:37: The call c1:kind({’rubies’,4}) breaks the
contract (card()) -> ’face’ | ’number’ done in 0m1.02s
done (warnings were emitted)
25/41

(Lack of) Types
Documenting Types using spec Tail Recursion
Exceptions
Control Structures
26/41

List Examples
1 > c(list_examples).
2 {ok,list_examples}
3 > list_examples:sum([1,2,3,4]).
4 10
5 > list_examples:len([0,1,0,1]).
64
7 > list_examples:append([5,4],[1,2,3]). 8 [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])
27/41

Tail Recursion
􏰀 Programming pattern to increase performance 􏰀 It helps compilers when optimizing code
􏰀 Inefficient recursive definition
1 len([_|XS]) -> 1 + len(XS) ; 2 len([]) -> 0.
Observe the evaluation of len([1,2,3])
1 len([1,2,3]) == 1 + len([2,3])
2 len([1,2,3]) == 1 + (1 + len([3]))
3 len([1,2,3]) == 1 + (1 + (1 + len([]))) %% 4 len([1,2,3])==1+(1+(1+0))
5 len([1,2,3]) == 1 + (1 + 1)
6 len([1,2,3]) == 1 + 2
7 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!
28/41

Tail Recursion
􏰀 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
29/41

Tail Recursion
􏰀 We define len_a, the tail recursive version of len
􏰀 Function len_a has an extra parameters capturing the partial result of the function, i.e., how many elements len_a has seen so far
1 len_a([_|XS], Acc) -> len_a(XS, Acc+1); 2 len_a([], Acc) -> Acc.
We define len based on len_a as follows 1 len(XS) -> len_a(XS, 0).
What about the tail recursive version of sum and append?
30/41

(Lack of) Types
Documenting Types using spec Tail Recursion
Exceptions
Control Structures
31/41

Exceptions
Three kinds:
􏰀 errors: run-time errors such as 1+a; can be emulated with
error(Reason)
􏰀 exits: generated error; generated by a process using exit/1
􏰀 Studied next class
􏰀 throws: generated error; generated by a process using throw/1 􏰀 Brief overview next
32/41

Throw Exceptions
􏰀 Used for cases that the programmer can be expected to handle
􏰀 In comparison with exits and errors, they don’t really carry any ’crash that process!’ intent behind them, but rather control flow
􏰀 Good idea to document their use within a module using them
1 1> throw(permission_denied).
2 ** exception throw: permission_denied
33/41

Try…Catch
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6
-module(exceptions). -compile(export_all).
throws(F) -> try F() of
_ -> ok catch
Throw -> {throw , caught , Throw} end.
1> c(exceptions).
{ok,exceptions}
2> exceptions:throws(fun() -> throw(thrown) end). {throw ,caught ,thrown}
3> exceptions:throws(fun() -> erlang:error(pang) end). ** exception error: pang
34/41

Try..Catch
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
talk() -> “blah blah”.
sword(1) -> throw(slice);
sword(2) -> erlang:error(cut_arm); sword(3) -> exit(cut_leg); sword(4) -> throw(punch);
sword(5) -> exit(cross_bridge).
black_knight(Attack) when is_function(Attack , 0) -> try Attack () of
_ -> “None shall pass.” catch
throw:slice -> “It is but a scratch.”; error:cut_arm -> “I’ve had worse.”; exit:cut_leg -> “Come on you pansy!”; _:_ -> “Just a flesh wound.”
end.
35/41

Try–Catch
1 7> c(exceptions).
2 {ok,exceptions}
3 8> exceptions:talk().
4 “blah blah”
5 9> exceptions:black_knight(fun exceptions:talk/0). 6 “None shall pass.”
7 10> 8 “It
9 11>
exceptions:black_knight(fun() -> exceptions:sword(1) end ).
is but a scratch.”
exceptions:black_knight(fun() -> exceptions:sword(2) end ).
10 “I’ve had worse.”
11 12> exceptions:black_knight(fun() -> exceptions:sword(3) end
).
12 “Come on you pansy!”
13 13> exceptions:black_knight(fun() -> exceptions:sword(4) end
).
14 “Just a flesh wound.”
15 14> exceptions:black_knight(fun() -> exceptions:sword(5) end
).
16 “Just a flesh wound.”
36/41

Additional Constructs
1 2 3 4 5 6 7
try Expr of
Pattern -> Expr1
catch
Type:Exception -> Expr2
after % this always gets executed Expr3
end
􏰀 Expr3 is always run, be there an exception or not
37/41

Additional Constructs
1 1> catch throw(whoa).
2 whoa
3 2> catch exit(die).
4 {’EXIT’,die}
5 3> catch 1/0.
6 {’EXIT’,{badarith ,[{erlang ,’/’,[1,0]},
7 {erl_eval ,do_apply ,5},
8 {erl_eval ,expr ,5},
9 {shell ,exprs ,6},
10 {shell ,eval_exprs ,6},
11 {shell ,eval_loop ,3}]}}
12 4> catch 2+2.
13 4
38/41

(Lack of) Types
Documenting Types using spec Tail Recursion
Exceptions
Control Structures
39/41

Control Structures
1 2 3 4 5 6 7
is_greater_than(X, Y) -> if
X>Y -> true;
true -> % works as an ’else’ branch false
end
40/41

Control Structures
1 2 3 4 5 6 7 8 9
is_valid_signal(Signal) -> case Signal of
{signal , true;
{signal , true;
_Else -> false
end.
_What , _What ,
_From , _To} -> _To} ->
41/41