liquid-fixpoint-0.8.10.1: Predicate Abstraction-based Horn-Clause/Implication Constraint Solver

Safe HaskellNone
LanguageHaskell98

Language.Fixpoint.SortCheck

Contents

Description

This module has the functions that perform sort-checking, and related operations on Fixpoint expressions and predicates.

Synopsis

Sort Substitutions

data TVSubst Source #

API for manipulating Sort Substitutions -----------------------------------

Checking Well-Formedness

checkSorted :: Checkable a => SrcSpan -> SEnv Sort -> a -> Maybe Doc Source #

checkSortedReft :: SEnv SortedReft -> [Symbol] -> SortedReft -> Maybe Doc Source #

Checking Refinements ------------------------------------------------------

checkSortFull :: Checkable a => SrcSpan -> SEnv SortedReft -> Sort -> a -> Maybe Doc Source #

Sort inference

sortExpr :: SrcSpan -> SEnv Sort -> Expr -> Sort Source #

Sort Inference ------------------------------------------------------------

exprSort :: String -> Expr -> Sort Source #

Expressions sort ---------------------------------------------------------

Unify

unifyFast :: Bool -> Env -> Sort -> Sort -> Maybe TVSubst Source #

Fast Unification; `unifyFast True` is just equality

unifys :: Env -> Maybe Expr -> [Sort] -> [Sort] -> CheckM TVSubst Source #

Apply Substitution

apply :: TVSubst -> Sort -> Sort Source #

Applying a Type Substitution ----------------------------------------------

defuncEApp :: SymEnv -> Expr -> [(Expr, Sort)] -> Expr Source #

defuncEApp monomorphizes function applications.

Exported Sorts

boolSort :: Sort Source #

Exported Basic Sorts -----------------------------------------------

strSort :: Sort Source #

Exported Basic Sorts -----------------------------------------------

Sort-Directed Transformations

class Elaborate a where Source #

Elaborate: make polymorphic instantiation explicit via casts, make applications monomorphic for SMTLIB. This deals with polymorphism by elaborate-ing all refinements except for KVars. THIS IS NOW MANDATORY as sort-variables can be instantiated to int and bool.

Methods

elaborate :: Located String -> SymEnv -> a -> a Source #

Instances
Elaborate Sort Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Elaborate SortedReft Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Elaborate Expr Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Elaborate BindEnv Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Elaborate Rewrite Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Elaborate Equation Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Elaborate AxiomEnv Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Elaborate a => Elaborate [a] Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Methods

elaborate :: Located String -> SymEnv -> [a] -> [a] Source #

Elaborate a => Elaborate (Maybe a) Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Methods

elaborate :: Located String -> SymEnv -> Maybe a -> Maybe a Source #

Elaborate e => Elaborate (Triggered e) Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Loc a => Elaborate (SInfo a) Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Methods

elaborate :: Located String -> SymEnv -> SInfo a -> SInfo a Source #

Loc a => Elaborate (SimpC a) Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

Methods

elaborate :: Located String -> SymEnv -> SimpC a -> SimpC a Source #

Elaborate (Symbol, Sort) Source # 
Instance details

Defined in Language.Fixpoint.SortCheck

applySorts :: Visitable t => t -> [Sort] Source #

NOTE:apply-monomorphization

Because SMTLIB does not support higher-order functions, all _non-theory_ function applications

EApp e1 e2

are represented, in SMTLIB, as

(Eapp (EApp apply e1) e2)

where apply is 'ECst (EVar "apply") t' and t is 'FFunc a b' a,b are the sorts of e2 and 'e1 e2' respectively.

Note that *all polymorphism* goes through this machinery.

Just before sending to the SMT solver, we use the cast t to generate a special apply_at_t symbol.

To let us do the above, we populate SymEnv with the _set_ of all sorts at which apply is used, computed by applySorts.

NOTE:coerce-apply
-- related to [NOTE:apply-monomorphism]

Haskell's GADTs cause a peculiar problem illustrated below:

```haskell data Field a where FInt :: Field Int FBool :: Field Bool

proj :: Field a -> a -> a proj fld x = case fld of FInt -> 1 + x FBool -> not b ```

## The Problem

The problem is you cannot encode the body of proj as a well-sorted refinement:

```haskell if is$FInt fld then (1 + (coerce (a ~ Int) x)) else (not (coerce (a ~ Bool) x)) ```

The catch is that x is being used BOTH as Int and as Bool which is not supported in SMTLIB.

## Approach: Uninterpreted Functions

We encode coerce as an explicit **uninterpreted function**:

```haskell if is$FInt fld then (1 + (coerce(a -> int) x)) else (not (coerce(a -> bool) x)) ```

where we define, extra constants in the style of apply

```haskell constant coerce(a -> int ) :: a -> int constant coerce(a -> bool) :: a -> int ```

However, it would not let us verify:

```haskell

unwrap :: Field a -> a -> a unwrap fld x = proj fld x

test = unwrap FInt 4 == 5 && unwrap FBool True == False ```

because we'd get

```haskell unwrap FInt 4 :: { if is$FInt FInt then (1 + coerce_int_int 4) else ... } ```

and the UIF nature of coerce_int_int renders the VC invalid.

## Solution: Eliminate Trivial Coercions

HOWEVER, the solution here, may simply be to use UIFs when the coercion is non-trivial (e.g. `a ~ int`) but to eschew them when they are trivial. That is we would encode:

| Expr | SMTLIB | |:-----------------------|:-------------------| | `coerce (a ~ int) x` | `coerce_a_int x` | | `coerce (int ~ int) x` | x |

which, I imagine is what happens _somewhere_ inside GHC too?

unElab :: Visitable t => t -> t Source #

Predicates on Sorts

isMono :: Sort -> Bool Source #

Predicates on Sorts -------------------------------------------------------

runCM0 :: SrcSpan -> CheckM a -> Either ChError a Source #