Transcript Principle of structural induction for fp

COSC 4P41 – Functional Programming
Testing vs Proving
• Testing
– uses a set of “typical” examples,
– symbolic testing,
– may find errors, but cannot show absents of errors,
– “easy” to do.
• Proving correctness
– establishes properties of programs by a mathematical proof,
• failure  error in the program
• success  program is correct
– difficult enterprise.
Testing and proving should both be part of the development process of
reliable software.
© M. Winter
10.1
COSC 4P41 – Functional Programming
Properties of programs
• Definedness and termination
Evaluating an expression can have one of two outcomes:
– the evaluation can halt, or terminate, to give a result, or
– the evaluation can go on forever.
The proofs we consider state a property that holds for all defined
values (partial correctness).
• Finiteness
In a lazy language we have two kinds of special elements:
– infinite objects, e.g., infinite lists,
– partially defined objects.
• Programs as formulas
A definition
square :: Int -> Int
square x = x*x
leads to the following formula
 x::Int (square x = x*x)
© M. Winter
10.2
COSC 4P41 – Functional Programming
Verification
• Principle of extensionality:
Two functions f and g are equal if they have the same value at every
argument.
• Principle of induction for natural numbers:
In order to prove that a logical property P(n) holds for all natural
numbers n we have to do two things:
– Base case: Prove P(0).
– Induction step: Prove P(n+1) on the assumption that P(n) holds.
• Principle of structural induction for lists:
In order to prove that a logical property P(xs) holds for all finite lists
xs we have to do two things:
– Base case: Prove P([]).
– Induction step: Prove P(x:xs) on the assumption that P(xs)
holds.
© M. Winter
10.3
COSC 4P41 – Functional Programming
Reasoning about algebraic types
Verification for algebraic types follows the example of lists.
• Principle of structural induction for algebraic types:
In order to prove that a logical property P(x) holds for all finite
elements of an algebraic type T:
– Base case: Prove P(C) for all non-recursive constructors C of T.
– Induction step: Prove P(Cr y1 … yn) for all recursive
constructors Cr of T on the assumption that P(y1) and … and
P(yn) holds.
Example:
data Tree a = Empty | Node a (Tree a) (Tree a)
– Base case: Prove P(Empty)
– Induction step: Prove P(Node x t1 t2) for all x of type a on the
assumption that P(t1) and … and P(t2) holds.
© M. Winter
10.4
COSC 4P41 – Functional Programming
List induction revisited
To prove a property for all finite or partial lists (fp-lists) we can use the
following principle:
• Principle of structural induction for fp-lists:
In order to prove that a logical property P(xs) holds for all fp-lists xs
we have to do three things:
– Base case: Prove P([]) and P(undef).
– Induction step: Prove P(x:xs) on the assumption that P(xs)
holds.
• fp-lists as an approximation of infinite lists:
[a1,a2,a3,…] is approximated by the collection
undef, a1:undef, a1:a2:undef, a1:a2:a3:undef, …
For some properties (admissible or continuous predicates) it is enough
to show the property for all approximations to know that it will be
valid for all infinite lists as well. In particular, this is true for all
equations.
© M. Winter
10.5
COSC 4P41 – Functional Programming
Case study
Consider again the following data type for expressions:
data Expr = Lit Int
| IVar Var
| Let Var Expr Expr
| Expr :+: Expr
| Expr :-: Expr
| Expr :*: Expr
| Expr :\: Expr
deriving Show
The meaning (value) of such an expression is evaluated using a Store.
Store is an abstract data type providing several functions.
© M. Winter
10.6
COSC 4P41 – Functional Programming
Case study (cont’d)
USER
initial :: Store
value
:: Store -> Var -> Int
update
:: Store -> Var -> Int -> Store
IMPLEMENTOR
eval
eval
eval
eval
eval
eval
eval
eval
:: Expr -> Store ->
(Lit n)
store
(IVar v)
store
(Let v e1 e2) store
(e1 :+: e2)
store
(e1 :-: e2)
store
(e1 :*: e2)
store
(e1 :\: e2)
store
© M. Winter
Int
= n
= value store v
= eval e2 (update store v (eval e1 store))
= eval e1 store + eval e2 store
= eval e1 store - eval e2 store
= eval e1 store * eval e2 store
= eval e1 store `div` eval e2 store
10.7
COSC 4P41 – Functional Programming
Case study (cont’d)
Several questions arise:
1. What are the natural properties which should be fulfilled by Expr and
the eval function?
2. What are natural properties of the functions provided by the ADT
Store?
3. Are those properties sufficient to show the properties of eval?
© M. Winter
10.8
COSC 4P41 – Functional Programming
Case study (cont’d)
1. Consider the following function:
subst
subst
subst
subst
subst
subst
subst
subst
:: Expr -> Expr
(Lit n)
_
(IVar v)
e
(Let v e1 e2) e
(e1
(e1
(e1
(e1
:+:
:-:
:*:
:\:
e2)
e2)
e2)
e2)
e
e
e
e
-> Var -> Expr
_ = Lit n
w = if v==w then
w = Let v (subst
(if v==w
w = subst e1 e w
w = subst e1 e w
w = subst e1 e w
w = subst e1 e w
e else (IVar
e1 e w)
then e2 else
:+: subst e2
:-: subst e2
:*: subst e2
:\: subst e2
v)
subst e2 e w)
e w
e w
e w
e w
A natural property would be
eval (subst e1 e2 v) store
= eval e1 (update store v (eval e2 store))
© M. Winter
10.9
COSC 4P41 – Functional Programming
Case study (cont’d)
2. Consider the following properties:
value initial v = 0
value (update store v n) v = n
v /= w  value (update store v n) w = value store w
Notice, every element of Store can be generated using initial and
update. These functions are “abstract” constructor functions for the
ADT Store. For all other functions (the function value) axioms in
terms of the constructor functions are provided. This will give a
sufficient set of axioms.
3. Yes!!! (see derivation in class).
© M. Winter
10.10
COSC 4P41 – Functional Programming
Proving in Isabelle
© M. Winter
10.11
COSC 4P41 – Functional Programming
© M. Winter
10.12
COSC 4P41 – Functional Programming
© M. Winter
10.13