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

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

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

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

Fast Unification; `unifyFast True` is just equality

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

defuncEApp monomorphizes function applications.

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

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

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.

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?

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