Demo:
\end{code} nats = 0 `C` 1 `C` 3 `C` N {-@ nats :: L Nat @-} \begin{code}
*Every element* in `nats` is non-negative:
\end{code} data L a = N | C a (L a) \begin{code}
\end{code} infixr `C` \begin{code}
-------------- Example: Lists ================================ Types Yield Universal Invariants (Notoriously hard with *pure* SMT) ---------------------------- Types = Universal Invariants ======================= {#universalinvariants} \end{code} zero' = zero {-@ zero' :: Nat @-} \begin{code}
Via SMT, LiquidHaskell infers `EqZero <: Nat`, hence:
\end{code} type Nat = {v : Int | 0 <= v} \begin{code} . ------------------------ Example: Natural Numbers -------- --- --------------------------------------------------- **So** : `{v:Int | v=0} <: {v:Int | 0<=v}` **As** : `v=0` *implies* `0<=v` ... via SMT -------- --- ---------------------------------------------------
------------------------ Subtyping is Implication -------- --- ---------------------------- **Then** : `{v : t | p} <: {v : t | q}` **If** : `p => q` -------- --- ----------------------------
------------------------ Subtyping is Implication
-------- --- --------------------------------------------- **Then** : `S` is a *subtype* of `T` **If** : Refinement of `S` *implies* refinement of `T` -------- --- ---------------------------------------------
------------------------ Subtyping is Implication [Predicate Subtyping](http://pvs.csl.sri.com/papers/subtypes98/tse98.pdf) ------------------------ Subtyping is Implication ========================== Refinements Are Predicates -------------------------- Refinements Are Predicates ============================ {#refinementsArePredicates}
Lets take a look.
Demo
Refinement types via special comments `{-@ ... @-}`
\end{code} zero = 0 {-@ zero :: EqZero @-} \begin{code}
Integers equal to `0` ------- Example \end{code} {-@ type EqZero = {v:Int | v = 0} @-} \begin{code}
Integers equal to `0` ------- Example ------------------ Types + Predicates ======================= Simple Refinement Types
\end{code} range :: Int -> Int -> L Int odds :: L Int evens :: L Int nats :: L Int abs :: Int -> Int safeDiv :: Int -> Int -> Int zero' :: Int zero :: Int -- boring haskell type sigs import Prelude hiding (abs, max) import Language.Haskell.Liquid.Prelude module SimpleRefinements where {-@ LIQUID "--no-termination" @-} \begin{code}
----------------------- Simple Refinement Types ======================= {#simplerefinements} ad 6 z q d < 1 * ) $ # c K @ ? : 9 " !
x
i
h
c
b
7
h g N 5 4 u t s b Q P
{
z
u
t
g
7
~ w v u Y = < . f e ` _ # | { z y
Need way to [measure](#measures) *length of a list* ...
-
**A:** Precondition: `i` between `0` and list **length**. -
**Q:** How to ensure safety?
(Mouseover to view type of `liquidError`)
\end{code} _ ! _ = liquidError "Oops!" (C _ xs) ! i = xs ! (i - 1) (C x _) ! 0 = x (!) :: L a -> Int -> a \begin{code} --------------------------- Example: Indexing Into List
**Question:** What is the type of `go` ?
\end{code} | otherwise = N | n < j = n `C` go (n + 1) go n where range i j = go i {-@ range :: i:Int -> j:Int -> L (Btwn i j) @-} \begin{code}
`(range i j)` returns `Int`s between `i` and `j` ---------------- Example: `range` \end{code} {-@ type Btwn I J = {v:_|(I <= v && v < J)} @-} \begin{code}
`(range i j)` returns `Int`s between `i` and `j` ---------------- Example: `range` `(range i j)` returns `Int`s between `i` and `j` ---------------- Example: `range` ======================== Dependent Function Types + *Relational* invariants + Outputs *refer to* inputs ------------------------ Dependent Function Types ====================== {#dependentfunctions} \end{code} | otherwise = 0 - x | 0 <= x = x abs x {-@ abs :: x:Int -> Nat @-} \begin{code}
+ **Output type** specifies *post-condition* + **Postcondition** result is non-negative
-------------- Example: `abs`
What if precondition does not hold?
Demo:
\end{code} safeDiv x y = x `div` y {-@ safeDiv :: Int -> NonZero -> Int @-} \begin{code}
+ **Input type** specifies *pre-condition* + **Pre-condition** divisor is *non-zero*.
------------------ Example: `safeDiv`
\end{code} {-@ type NonZero = {v:Int | v /= 0} @-} \begin{code}
**Precondition** divisor is *non-zero*.
------------------ Example: `safeDiv` ========================= ad
& v k j e d M L ? ' -
Contracts: Function Types -------------------------- Contracts = Function Types ================= {#functiontypes}
What if `evens` contained `1`?
Demo:
\end{code} odds = 1 `C` 3 `C` 5 `C` N {-@ odds :: L Odd @-} evens = 0 `C` 2 `C` 4 `C` N {-@ evens :: L Even @-} \begin{code}
\end{code} type Odd = {v:Int | v mod 2 /= 0} type Even = {v:Int | v mod 2 = 0} \begin{code}
----------------------- Example: Even/Odd Lists