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