程序代写代做代考 data structure Erlang database Advanced Programming – QuickCheck for Erlang

Advanced Programming – QuickCheck for Erlang

Advanced Programming
QuickCheck for Erlang

Ken Friis Larsen
kflarsen@diku.dk

Department of Computer Science
University of Copenhagen

October 23, 2018

1 / 25

Today’s Program

I Types in Erlang

I QuickCheck, with Erlang syntax

I Testing complex data-structures

2 / 25

Basicserver Behaviour

The basicserver behaviour:

-module(basicserver).
-export([…]).
-callback init() -> State :: term().
-callback handle(Arg :: term(), State :: term()) ->

{ ok, State :: term() } |
{ {error, Reason :: term()}, State :: term() }.

3 / 25

Basicserver Callback Module

-module(pb).
-export([…]).
-export([init/0, handle/2]).

-behaviour(basicserver).

init() -> …
handle(Arg, State) -> …

4 / 25

Some Flamingo Types

-type path() :: string().
-type request() :: {path(), [{string(), string()}]}.

-type action() ::
fun((request(), any(), State) -> {new_state, string(), State}

| {no_change, string()}).
-type route() :: #{ prefix := path(), group := integer() }.

-spec find_by_prefix(path(), [route()])
-> none | {found, route()}.

find_by_prefix(_Path, []) -> none;
find_by_prefix(Path, [#{ prefix := Pre} = Route | Rest]) ->

case lists:prefix(Pre, Path) of
true -> {found, Route};
false -> find_by_prefix(Path, Rest)

end.
5 / 25

Checking With dialyzer

I First build a Persistent Lookup Table (PLT) database for
dialyzer:

$ dialyzer –build_plt –apps erts kernel stdlib crypto

(wait a few minutes)

I Check your types with the command:

$ dialyzer –src flamingo.erl

I Fix your bugs

6 / 25

QuickCheck recap

I Testing is a cost-effective way to help us assess the correctness
of our code. However, writing test cases are boring (and
sometimes hard).

I We need to come up with good input data — instead, generate
random data (from a suitable distribution).

I Often we write many test for the same underlying idea —
instead, write down that underlying idea (property) and
generate test cases from that.

I QuickCheck motto: don’t write a unit test-suite – generate it.

7 / 25

Warm-up: Student Activity

I Lets’ write some tests for lists:delete

I Try to write a property relating lists:delete and
lists:member

8 / 25

Warm-up: Delete an element from a list

I When you delete an element from a list, it’s not there anymore:

prop_delete_0() ->
?FORALL({X, Xs}, {int(), list(int())},
not lists:member(X, lists:delete(X, Xs))).

I This succeeds when we check the property a hundred times

I . . . but not when we check it thousands of times

9 / 25

The Problem

I There is a problem with our specification, delete only removes
the first occurrence of the element

I How often do we even generate relevant test cases?

prop_member_probability() ->
?FORALL({X, Xs}, {int(), list(int())},
collect(lists:member(X, Xs), true)).

10 / 25

Collecting Statistics

Record the number of time X occurs in Xs. Running the property a
large number of times reveals that the probability that a random
value appears in a random list twice is around 0.5%.

occurs(X, Xs) ->
lists:foldl(fun(Y, Sum) ->

if X =:= Y -> Sum + 1;
X =/= Y -> Sum

end
end, 0, Xs).

prop_list_classification() ->
?FORALL({X, Xs}, {int(), list(int())},

collect(occurs(X, Xs), true)).

11 / 25

Use Implication to Generate more interesting

Test-cases

I Only look at cases where the value appears at least once in the
list.

prop_delete_1() ->
?FORALL({X, Xs}, {int(), list(int())},
?IMPLIES(lists:member(X, Xs),
not lists:member(X, lists:delete(X, Xs)))).

I Document that we expect the property to fail (within a hundred
attempts)

prop_delete_2() ->
fails(prop_delete_1()).

12 / 25

Getting The Specification Right

I What it the right specification for delete?
I delete only remove the first occurrence of an element

prop_delete_3() ->
?FORALL({Pre,X,Post}, {list(int()), int(), list(int())},
?IMPLIES(not lists:member(X, Pre),

equals(lists:delete(X, Pre ++ [X] ++ Post),
Pre ++ Post))).

13 / 25

Testing Data Structure Libraries

I dict: purely functional key-value store
I new()
I store(Key,Value,Dict)
I fetch(Key, Dict)
I . . .

I “No, stop! Don’t expose your dict”
I Complex representation
I Complex invariants
I We’ll just test the API

14 / 25

Keys Should Be Unique

I There should be no duplicate keys

no_duplicates(Lst) ->
length(Lst) =:= length(lists:usort(Lst)).

prop_unique_keys() ->
?FORALL(D,dict(),

no_duplicates(dict:fetch_keys(D))).

I We need a generator for dicts

15 / 25

Generating dicts

I Generate dicts using the API

dict_0() ->
?LAZY(

oneof([dict:new(),
?LET({K,V,D},{key(), value(), dict_0()},

dict:store(K,V,D))])
).

I Generate dicts symbolically

dict_1() ->
?LAZY(

oneof([{call,dict,new,[]},
?LET([D], dict_1(),
{call,dict,store,[key(),value(),D]})])

).

16 / 25

Properties for Symbolic Values

prop_unique_keys() ->
?FORALL(D,dict_1(),

no_duplicates(dict:fetch_keys(eval(D)))).

17 / 25

How good is our generator

I Let’s make a property for measuring the quality of our
generator

prop_measure() ->
?FORALL(D,dict(),
collect(length(dict:fetch_keys(eval(D))),true)).

I We can use frequency to generate more interesting dicts

dict_2() ->
?LAZY(

frequency(
[{1,{call,dict,new,[]}},
{4,?LET(D, dict_2(),

{call,dict,store,[key(),value(),D]})}]
)

).

18 / 25

I need a shrink now

dict_3() ->
?LAZY(
frequency([{1,{call,dict,new,[]}},

{4,?LETSHRINK([D],[dict_3()],
{call,dict,store,[key(),value(),D]})}])

).

19 / 25

Testing Aginst Models

I A dict should behave like a list of key-value pairs

I Thus, we implement a model of dicts

model(Dict) ->
dict:to_list(Dict).

model_store(K,V,L) ->
[{K,V}|L].

20 / 25

Commuting Diagrams

Dict

List

Dict+{K,V}

[{K,V}|List]

model(…)

dict:store(K,V,…)

model_store(K,V,…)

model(…)

21 / 25

Commuting Property

prop_store() ->
?FORALL({K,V,D},

{key(),value(),dict()},
begin

Dict = eval(D),
model(dict:store(K,V,Dict))
==
model_store(K,V,model(Dict)))

end).

22 / 25

Course Evaluation
(This morning 23 out of 144 had answered)

Please give feedback on:

I Pre-lecture Quizes (I know I’ve not made these for all my
lectures)

I Out of schema-group TA support (Robert in the canteen on
Sundays)

I OnlineTA for all assignments

I Extra focus on exam preparation

23 / 25

Summary

I Install Quviq Erlang QuickCheck.

I Use symbolic commands

I Test against models

I Be careful with your specification

I We can test complex data structures by generating sequences of
API calls

I Remember course evaluation

24 / 25

Exam

I One week take-home project (2/11–9/11)

I Hand in via Digital Exam

I Check with OnlineTA before submission

I Max group size is 1 (one)

I (Please remember that the University have zero-tolerance policy
regarding exam fraud)

25 / 25