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