LARA

Types Expressing Program Properties

Suppose that we wish to define types such as

type upto[n] = {x:Int | 0 <= x & x < n}
type posArr = {f:Array[Int] | forall i:upto[f.length]. 0 <= f(i)}
var w : upto[v]
var a : posArr = new Array[10]
var i : upto[10] 
var p : upto[MAXINT]
a[i] = 4 // must prove: 0 <= i < 10, 0 <= 4
p = a[0] // must prove: 0 <= 0 < 10, 0 <= a[0] < 10

The types can then refer to values. These are dependent types. Scala has a special form of these (path-dependent types).

In general, dependent types require some form of automated theorem proving to check the implications of underlying constraints.