SNAPKITTYWEST's picture
montrepol: exact mathematics in Haskell, with proofs and a certifying solver
5316c4e verified
Raw History Blame Contribute Delete
4.37 kB
-- SPDX-License-Identifier: AGPL-3.0-or-later
-- | The simply typed lambda calculus with integers and booleans, in de Bruijn
-- form: a type checker and a call-by-value small-step semantics.
--
-- The metatheory (progress, preservation, the substitution lemma, and that
-- evaluation terminates) is tested on random well-typed terms in @test/@. It
-- is evidence, not proof; the proofs of these facts are classical.
--
-- The @{-\@ ... \@-}@ comments are Liquid Haskell refinements. GHC ignores
-- them; the separate build in @liquid/@ compiles this very file with the
-- Liquid Haskell plugin and Z3, and checks them, together with termination of
-- every function here and totality of every pattern match.
module MP.Lambda.Simple
( Ty (..)
, Term (..)
, typeOf
, isValue
, shift
, subst
, step
, evaluate
, size
) where
infixr 5 `TArr`
data Ty = TInt | TBool | TArr Ty Ty
deriving (Eq, Show)
-- | @Var 0@ is the innermost binder.
data Term
= Var Int
| Lam Ty Term
| App Term Term
| Lit Integer
| BoolLit Bool
| Add Term Term
| Leq Term Term
| If Term Term Term
deriving (Eq, Show)
-- | The type of a term in a context, if it has one. Terminates because every
-- recursive call is on a strictly smaller term.
{-@ typeOf :: [Ty] -> t:Term -> Maybe Ty / [size t] @-}
typeOf :: [Ty] -> Term -> Maybe Ty
typeOf ctx t = case t of
Var i -> case drop i ctx of
(ty : _) | i >= 0 -> Just ty
_ -> Nothing
Lam a body -> TArr a <$> typeOf (a : ctx) body
App f x -> do
tf <- typeOf ctx f
tx <- typeOf ctx x
case tf of
TArr a b | a == tx -> Just b
_ -> Nothing
Lit _ -> Just TInt
BoolLit _ -> Just TBool
Add a b -> do
ta <- typeOf ctx a
tb <- typeOf ctx b
if ta == TInt && tb == TInt then Just TInt else Nothing
Leq a b -> do
ta <- typeOf ctx a
tb <- typeOf ctx b
if ta == TInt && tb == TInt then Just TBool else Nothing
If c a b -> do
tc <- typeOf ctx c
ta <- typeOf ctx a
tb <- typeOf ctx b
if tc == TBool && ta == tb then Just ta else Nothing
isValue :: Term -> Bool
isValue t = case t of
Lam _ _ -> True
Lit _ -> True
BoolLit _ -> True
_ -> False
-- | @shift d c t@ adds @d@ to every variable of @t@ at or above the cutoff @c@.
shift :: Int -> Int -> Term -> Term
shift d c t = case t of
Var i -> Var (if i >= c then i + d else i)
Lam a body -> Lam a (shift d (c + 1) body)
App f x -> App (shift d c f) (shift d c x)
Add a b -> Add (shift d c a) (shift d c b)
Leq a b -> Leq (shift d c a) (shift d c b)
If x a b -> If (shift d c x) (shift d c a) (shift d c b)
_ -> t
-- | @subst j s t@ is @t[j := s]@.
subst :: Int -> Term -> Term -> Term
subst j s t = case t of
Var i -> if i == j then s else Var i
Lam a body -> Lam a (subst (j + 1) (shift 1 0 s) body)
App f x -> App (subst j s f) (subst j s x)
Add a b -> Add (subst j s a) (subst j s b)
Leq a b -> Leq (subst j s a) (subst j s b)
If x a b -> If (subst j s x) (subst j s a) (subst j s b)
_ -> t
-- | One call-by-value step, or 'Nothing' for a value or a stuck term.
step :: Term -> Maybe Term
step t = case t of
App (Lam _ body) v | isValue v -> Just (shift (-1) 0 (subst 0 (shift 1 0 v) body))
App f x
| not (isValue f) -> (`App` x) <$> step f
| otherwise -> App f <$> step x
Add (Lit a) (Lit b) -> Just (Lit (a + b))
Add a b
| not (isValue a) -> (`Add` b) <$> step a
| otherwise -> Add a <$> step b
Leq (Lit a) (Lit b) -> Just (BoolLit (a <= b))
Leq a b
| not (isValue a) -> (`Leq` b) <$> step a
| otherwise -> Leq a <$> step b
If (BoolLit c) a b -> Just (if c then a else b)
If c a b -> (\c' -> If c' a b) <$> step c
_ -> Nothing
-- | Step until a value, a stuck term, or the fuel runs out ('Nothing').
-- Terminates because the fuel decreases and is checked before each step.
{-@ evaluate :: fuel:Int -> Term -> Maybe Term / [fuel] @-}
evaluate :: Int -> Term -> Maybe Term
evaluate fuel t
| isValue t = Just t
| fuel <= 0 = Nothing
| otherwise = case step t of
Just t' -> evaluate (fuel - 1) t'
Nothing -> Just t
{-@ measure size @-}
{-@ size :: Term -> {v:Int | v >= 1} @-}
size :: Term -> Int
size t = case t of
Lam _ b -> 1 + size b
App a b -> 1 + size a + size b
Add a b -> 1 + size a + size b
Leq a b -> 1 + size a + size b
If c a b -> 1 + size c + size a + size b
_ -> 1