File size: 9,801 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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
-- SPDX-License-Identifier: AGPL-3.0-or-later

-- | Refinement types over the lambda calculus, checked by Hcalc.
--
-- A refinement type @{v : Int | p}@ is the integers satisfying @p@, a formula
-- of linear arithmetic over @v@ and the integer variables in scope. Checking
-- is bidirectional, as in Liquid Haskell but without inference: lambdas and
-- top-level definitions carry their types. Each subtyping step
-- @G |- {v | p} <: {v | q}@ becomes the verification condition
-- @[G] /\ p ==> q@, which Hcalc decides.
--
-- Hcalc's answers are not trusted: a VC is accepted only when its
-- unsatisfiability certificate checks ('checkUnsat'), and a rejection
-- reports Hcalc's counter-model, which the tests check falsifies the VC.
--
-- Hcalc decides over the rationals. A VC valid over the rationals is valid
-- over the integers, so acceptance is sound for integer programs; the
-- converse fails, so some correct integer programs are rejected. The tests
-- include one.
module MP.Lambda.Refine
  ( RType (..)
  , Cmp (..)
  , Expr (..)
  , RefineError (..)
  , checkProgram
  , checkTop
  , Value (..)
  , run
  , satisfiesType
  ) where

import qualified Data.Map.Strict as Map
import MP.Hcalc.Smt

-- | @RInt v p@ is @{v : Int | p}@; @RFun x a b@ is @(x : a) -> b@, where @b@
-- may mention @x@.
data RType = RInt String Formula | RFun String RType RType
  deriving (Eq, Show)

data Cmp = CLe Expr Expr | CLt Expr Expr | CEq Expr Expr
  deriving (Eq, Show)

-- | Applications take a variable (A-normal form): name an argument with a
-- let first. That keeps every substitution into a refinement a variable for
-- a variable.
data Expr
  = EVar String
  | ENum Integer
  | EAdd Expr Expr
  | ESub Expr Expr
  | EMul Integer Expr
  | EIf Cmp Expr Expr
  | ELet String Expr Expr
  | ELam String RType Expr
  | EApp Expr String
  | EAnn Expr RType
  deriving (Eq, Show)

data RefineError
  = -- | The VC, and a model of its negation: a counterexample.
    NotSubtype Formula Model
  | -- | Hcalc said valid, but its certificate did not check.
    BadCertificate Formula
  | IllFormed String
  deriving (Eq, Show)

data Env = Env {bindings :: [(String, RType)], guards :: [Formula]}

------------------------------------------------------------------------------
-- Formulas

substTerm :: String -> Term -> Term -> Term
substTerm x s t = case t of
  TVar y -> if y == x then s else t
  TConst _ -> t
  TAdd a b -> TAdd (substTerm x s a) (substTerm x s b)
  TSub a b -> TSub (substTerm x s a) (substTerm x s b)
  TScale k a -> TScale k (substTerm x s a)

substF :: String -> Term -> Formula -> Formula
substF x s f = case f of
  FLe a b -> FLe (sub a) (sub b)
  FLt a b -> FLt (sub a) (sub b)
  FEq a b -> FEq (sub a) (sub b)
  FNot g -> FNot (substF x s g)
  FAnd gs -> FAnd (map (substF x s) gs)
  FOr gs -> FOr (map (substF x s) gs)
  FImp a b -> FImp (substF x s a) (substF x s b)
  _ -> f
  where
    sub = substTerm x s

-- | @substType x y t@ replaces the variable @x@ by the variable @y@ in @t@,
-- capture-avoiding: a binder named @y@ is renamed first, so that the
-- substituted @y@ is not captured by it.
substType :: String -> String -> RType -> RType
substType x y t = case t of
  RInt v p
    | v == x -> t
    | v == y -> let v' = freshFrom v t in RInt v' (substF x (TVar y) (substF v (TVar v') p))
    | otherwise -> RInt v (substF x (TVar y) p)
  RFun z a b
    | z == x -> RFun z (substType x y a) b
    | z == y -> let z' = freshFrom z t in RFun z' (substType x y a) (substType x y (substType z z' b))
    | otherwise -> RFun z (substType x y a) (substType x y b)
  where
    -- A name not occurring anywhere in the type, nor equal to x or y.
    freshFrom base ty =
      case [n | k <- [1 :: Int ..], let n = base <> replicate k '\'', n /= x, n /= y, not (occurs n ty)] of
        (n : _) -> n
        [] -> base

occurs :: String -> RType -> Bool
occurs n t = case t of
  RInt v p -> v == n || n `elem` formulaVars p
  RFun z a b -> z == n || occurs n a || occurs n b

formulaVars :: Formula -> [String]
formulaVars f = case f of
  FLe a b -> termVars a ++ termVars b
  FLt a b -> termVars a ++ termVars b
  FEq a b -> termVars a ++ termVars b
  FNot g -> formulaVars g
  FAnd gs -> concatMap formulaVars gs
  FOr gs -> concatMap formulaVars gs
  FImp a b -> formulaVars a ++ formulaVars b
  _ -> []
  where
    termVars t = case t of
      TVar v -> [v]
      TConst _ -> []
      TAdd a b -> termVars a ++ termVars b
      TSub a b -> termVars a ++ termVars b
      TScale _ a -> termVars a

-- | The facts the environment contributes to a VC: each integer binder's
-- refinement, about that binder, and every branch condition taken.
embed :: Env -> [Formula]
embed env = [substF v (TVar x) p | (x, RInt v p) <- bindings env] ++ guards env

-- | Reserved for the value a refinement talks about; user names cannot
-- start with an underscore.
nu :: String
nu = "_v"

------------------------------------------------------------------------------
-- Checking

valid' :: Formula -> Either RefineError ()
valid' vc = case valid vc of
  Unsat cert
    | checkUnsat (FNot vc) cert -> Right ()
    | otherwise -> Left (BadCertificate vc)
  Sat m -> Left (NotSubtype vc m)

subtype :: Env -> RType -> RType -> Either RefineError ()
subtype env (RInt v p) (RInt w q) =
  valid' (FImp (FAnd (embed env ++ [substF v (TVar nu) p])) (substF w (TVar nu) q))
subtype env (RFun x a1 b1) (RFun y a2 b2) = do
  subtype env a2 a1
  subtype env {bindings = (x, a2) : bindings env} b1 (substType y x b2)
subtype _ a b = Left (IllFormed ("shapes differ: " <> show a <> " and " <> show b))

pureTerm :: Env -> Expr -> Either RefineError Term
pureTerm env e = case e of
  EVar x -> case lookup x (bindings env) of
    Just (RInt _ _) -> Right (TVar x)
    _ -> Left (IllFormed (x <> " is not an integer in scope"))
  ENum n -> Right (TConst (fromInteger n))
  EAdd a b -> TAdd <$> pureTerm env a <*> pureTerm env b
  ESub a b -> TSub <$> pureTerm env a <*> pureTerm env b
  EMul k a -> TScale (fromInteger k) <$> pureTerm env a
  _ -> Left (IllFormed ("not a linear integer expression: " <> show e))

condition :: Env -> Cmp -> Either RefineError Formula
condition env c = case c of
  CLe a b -> FLe <$> pureTerm env a <*> pureTerm env b
  CLt a b -> FLt <$> pureTerm env a <*> pureTerm env b
  CEq a b -> FEq <$> pureTerm env a <*> pureTerm env b

synth :: Env -> Expr -> Either RefineError RType
synth env e = case e of
  EVar x -> case lookup x (bindings env) of
    Just (RInt _ _) -> Right (RInt nu (FEq (TVar nu) (TVar x)))
    Just t -> Right t
    Nothing -> Left (IllFormed (x <> " is not in scope"))
  EApp f x -> do
    tf <- synth env f
    case tf of
      RFun y a b -> do
        tx <- synth env (EVar x)
        subtype env tx a
        Right (substType y x b)
      _ -> Left (IllFormed ("applying a non-function: " <> show f))
  EAnn body t -> check env body t >> Right t
  _ -> (\t -> RInt nu (FEq (TVar nu) t)) <$> pureTerm env e

check :: Env -> Expr -> RType -> Either RefineError ()
check env e t = case (e, t) of
  (ELam x a body, RFun y a' b) -> do
    fresh x
    subtype env a' a
    check env {bindings = (x, a) : bindings env} body (substType y x b)
  (EIf c a b, _) -> do
    g <- condition env c
    check env {guards = g : guards env} a t
    check env {guards = FNot g : guards env} b t
  (ELet x e1 e2, _) -> do
    fresh x
    t1 <- synth env e1
    check env {bindings = (x, t1) : bindings env} e2 t
  _ -> synth env e >>= \t' -> subtype env t' t
  where
    fresh x
      | take 1 x == "_" = Left (IllFormed ("names may not start with _: " <> x))
      | x `elem` map fst (bindings env) = Left (IllFormed ("shadowing " <> x))
      | otherwise = Right ()

-- | Check one definition against its type, given earlier definitions.
checkTop :: [(String, RType)] -> Expr -> RType -> Either RefineError ()
checkTop defs = check (Env defs [])

-- | Check definitions in order; each may use the ones before it.
checkProgram :: [(String, RType, Expr)] -> Either (String, RefineError) ()
checkProgram = go []
  where
    go _ [] = Right ()
    go defs ((name, t, body) : rest) = case checkTop defs body t of
      Left err -> Left (name, err)
      Right () -> go ((name, t) : defs) rest

------------------------------------------------------------------------------
-- Running programs, to test what checking promises

data Value = VInt Integer | VFun (Value -> Maybe Value)

-- | Evaluate under an environment of values; 'Nothing' on a type error.
run :: Map.Map String Value -> Expr -> Maybe Value
run env e = case e of
  EVar x -> Map.lookup x env
  ENum n -> Just (VInt n)
  EAdd a b -> arith (+) a b
  ESub a b -> arith (-) a b
  EMul k a -> run env a >>= \v -> case v of
    VInt n -> Just (VInt (k * n))
    _ -> Nothing
  EIf c a b -> do
    holds <- cmp c
    run env (if holds then a else b)
  ELet x e1 e2 -> run env e1 >>= \v -> run (Map.insert x v env) e2
  ELam x _ body -> Just (VFun (\v -> run (Map.insert x v env) body))
  EApp f x -> do
    fv <- run env f
    xv <- Map.lookup x env
    case fv of
      VFun g -> g xv
      _ -> Nothing
  EAnn body _ -> run env body
  where
    ints a b = do
      va <- run env a
      vb <- run env b
      case (va, vb) of
        (VInt m, VInt n) -> Just (m, n)
        _ -> Nothing
    arith op a b = (\(m, n) -> VInt (op m n)) <$> ints a b
    cmp c = case c of
      CLe a b -> uncurry (<=) <$> ints a b
      CLt a b -> uncurry (<) <$> ints a b
      CEq a b -> uncurry (==) <$> ints a b

-- | Whether an integer satisfies @{v | p}@, given values for the other
-- integer variables @p@ mentions.
satisfiesType :: Map.Map String Integer -> Integer -> RType -> Bool
satisfiesType ints n t = case t of
  RInt v p -> evalFormula (Model Map.empty (Map.map fromInteger (Map.insert v n ints))) p
  RFun {} -> False