File size: 4,373 Bytes
5316c4e | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | -- 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
|