Constraints

[mikeday]

At some point we're going to encounter constraints that aren't part of the type of any individual value, like this example:

x: U16BE,
y: U16BE,
where x + y < 100

In some cases these can be reformulated into individual types, but this can make their expression less straightforward and is not always possible.

Nevertheless, we should probably avoid diving headlong into constraint solvers until we have some very compelling motivating examples.

[markbrown]

Here's a realistic example that generates some non-trivial constraints. For the following I'll assume that + and - take and return values of type {..}. We could try some more accurate signatures, but for now I'll leave things mostly up to constraint solving so we can see what happens.

I also need some array comprehension syntax. I'm not sure whether that has been discussed before, but I mean something like:

[ e | i < n ] : Array n t

where i is a new variable, and e of type t is evaluated for each value of i. Type rules for arrays would be:

Γ ⊢ n : {0..}     Γ,i:{0..n-1} ⊢ e : t
--------------------------------------  (COMP)
    Γ ⊢ [ e | i < n ] : Array n t


Γ ⊢ e1 : Array n t      Γ ⊢ e2 : {0..n-1}
-----------------------------------------  (INDEX)
              Γ ⊢ e1.e2 : t

Constraints are generated by a bounds-check rule:

        Γ ⊧ m <= e        Γ ⊧ e <= n
Γ ⊢ e : {..}    Γ ⊢ m : {..}    Γ ⊢ n : {..}
--------------------------------------------  (BOUND)
               Γ ⊢ e : {m..n}

This rule generates two constraints. I've used the "models" turnstile rather than "proves" for such constraints; this is meant to indicate that we aren't proving the claims within this proof system, but we still expect them to be true (and we will later check that with constraint solving or checking).

Here's the code, which constructs an array from an existing one, with the elements in reverse order.

def reverse (t:*) (n:{0..}) (a:Array n t) : Array n t := [ a.((n-1)-i) | i < n ].

A proof of type correctness is as follows. Let Γ = t:*, n:{0..}, a:Array n t.

• Γ ⊢ [ a.((n-1)-i) | i < n ] : Array n t (COMP)
  • Γ ⊢ n : {0..} (VAR)
  • Γ,i:{0..n-1} ⊢ a.((n-1)-i) : t (INDEX)
    • Γ,i:{0..n-1} ⊢ a : Array n t (VAR)
    • Γ,i:{0..n-1} ⊢ (n-1)-i : {0..n-1} (BOUND)
      • Γ,i:{0..n-1} ⊧ 0 <= (n-1)-i (*)
      • Γ,i:{0..n-1} ⊧ (n-1)-i <= n-1 (*)
      • Γ,i:{0..n-1} ⊢ (n-1)-i : {..} (APP)
        • Γ,i:{0..n-1} ⊢ (-) (n-1) : {..} -> {..} (APP)
          • Γ,i:{0..n-1} ⊢ (-) : {..} -> {..} -> {..} (MINUS-INT)
          • Γ,i:{0..n-1} ⊢ n-1 : {..} (APP)
            • Γ,i:{0..n-1} ⊢ (-) n : {..} -> {..} (APP)
              • Γ,i:{0..n-1} ⊢ (-) : {..} -> {..} -> {..} (MINUS-INT)
              • Γ,i:{0..n-1} ⊢ n : {..} (SUB)
                • Γ,i:{0..n-1} ⊢ {0..} ≼ {..} (RANGE-LB1)
                  • Γ,i:{0..n-1} ⊢ 0 : {..} (LIT-INT)
                • Γ,i:{0..n-1} ⊢ n : {0..} (VAR)
            • Γ,i:{0..n-1} ⊢ 1 : {..} (LIT-INT)
        • Γ,i:{0..n-1} ⊢ i : {..} (SUB)
          • Γ,i:{0..n-1} ⊢ {0..n-1} ≼ {..} (TRANS)
            • Γ,i:{0..n-1} ⊢ {0..n-1} ≼ {0..} (RANGE-UB2)
              • Γ,i:{0..n-1} ⊢ n-1 : {..} (as above)
            • Γ,i:{0..n-1} ⊢ {0..} ≼ {..} (as above)
          • Γ,i:{0..n-1} ⊢ i : {0..n-1} (VAR)
      • Γ,i:{0..n-1} ⊢ 0 : {..} (LIT-INT)
      • Γ,i:{0..n-1} ⊢ n-1 : {..} (as above)

The use of the BOUND rule generates two constraints, marked with (*). It's fairly easy to see that both are true, given that i and n are non-negative, and i is no greater than n-1.

After that is a fairly typical use of the APP rule. The MINUS-INT rule is just the axiom giving the signature of (-). The SUB and RANGE-* rules are more interesting, because we have that n:{0..} but we need n:{..}. SUB invokes the subtype relation, and RANGE-LB1 lets us essentially remove a lower bound that we don't need. Similarly, we can also remove an upper bound we don't need (leaving the other bound in place) using RANGE-UB2 and connecting the two subtyping steps with TRANS.

This example also shows that there is no real chicken-and-egg problem with the use of {..} as an argument to its own bounds. The problem is in trying to describe .. as a single type function, when there are really four distinct types:

• {..}
• {m..}
• {..n}
• {m..n}

[markbrown]

As regards the solving of these constraints, we could try using a third party solver of some sort or try to find some way ourselves. Unfortunately, bounds propagation where variables may appear in the bounds doesn't work well in the case that a variable is multiplied by something whose sign is indeterminate. The reason for this is that we can't tell whether the upper and lower bounds should swap places or not due to the multiplication, and we can't find out by comparing things immediately because we are dealing with variables not numbers.

In the case of linear formulas, or formulas involving non-negative integers, we can apply the bounds propagation method. That is the case above, where we generated the following constraints:

Γ,i:{0..n-1} ⊧ 0 <= (n-1)-i
Γ,i:{0..n-1} ⊧ (n-1)-i <= n-1

Since i depends on n but not the other way around (i.e., n occurs in the bounds of i), we can start by eliminating i by replacing it with its range. Then it can be evaluated according to the rules of bounds inference, treating every other expression as a singleton range. The first constraint thus turns into

0 <= (n-1)-{0..n-1}

which in turn becomes

0 <= {(n-1)-(n-1) .. (n-1)-0}

which simplifies to

0 <= {0..n-1}

which is true because 0 <= 0. Similarly, the steps for the second constraint are:

(n-1)-{0..n-1} <= n-1
{(n-1)-(n-1) .. (n-1)-0} <= n-1
{0..n-1} <= n-1

the final step of which is true because n-1 <= n-1 by reflexivity.

[markbrown]

As another example we can look at append. I'll define another new construct for this, similar to an if-then-else:

  Γ ⊢ m : {..}         Γ ⊢ n : {..}
Γ,m < n ⊢ e1 : t     Γ,m >= n ⊢ e2 : t
--------------------------------------  (IFLT)
   Γ ⊢ iflt m n then e1 else e2 : t

The new construct, iflt, compares the first two arguments and takes the then branch if the first is less than the second, and the else branch otherwise. The difference with plain if-then-else is that, in each branch, the corresponding fact is added to the type checking environment. So we add m < n in the then branch and m >= n in the else branch.

We can then define:

def append (t:*) (m:{0..}) (a:Array m t) (n:{0..}) (b:Array n t) : Array (m+n) t :=
    [ iflt i m then a.i else b.(i-m) | i < m+n ].

The constraints we would generate when type checking the array accesses are:

Γ, i:{0..m+n-1}, i < m  ⊧  0 <= i
Γ, i:{0..m+n-1}, i < m  ⊧  i <= m-1
Γ, i:{0..m+n-1}, i >= m  ⊧  0 <= i-m
Γ, i:{0..m+n-1}, i >= m  ⊧  i-m <= n-1

We can solve these using the method above, after adjusting the range of i to account for the additional constraint in the environment.

[markbrown]

A more detailed example of solving. This function returns a segment of an array starting at a given position and with a given length. The dependent argument types allow us to ensure this function is total.

def segment (t:*) (n:{0..}) (a:Array n t)
            (start:{0..n}) (len:{0..n-start}) : Array len t :=
    [ a.(start + i) | i < len ].

This time we get the constraint

Γ ⊧ 0 ≤ start + i ≤ n-1

where Γ includes n:{0..}, start:{0..n}, len:{0..n-start}, and i:{0..len-1}.

This one is interesting to solve because we need to eliminate more than one variable. We do this in dependency order - first i then len then start. (Note that I've formulated this slightly differently to above; I've combined two constraints into one for the sake of brevity. Hope that's not made it unclear.)

We first eliminate i by replacing it with its range:

Γ ⊧ 0 ≤ start + {0..len-1} ≤ n-1
Γ ⊧ 0 ≤ {start..start+len-1} ≤ n-1
Γ ⊧ 0 ≤ start, start+len-1 ≤ n-1

Then we do the same for len:

Γ ⊧ 0 ≤ start, start+{0..n-start}-1 ≤ n-1
Γ ⊧ 0 ≤ start, {start-1..n-1} ≤ n-1

The second part of this turns into n-1 ≤ n-1, which is true by reflection. We eliminate start on the remaining part of the constraint:

Γ ⊧ 0 ≤ {0..n}
Γ ⊧ 0 ≤ 0

So this constraint is also true.