GitLab

Type declarations for records (incuding the private records) can
now be followed by a "witness": a set of values for the record
fields that must satisfy the type invariant (if any). The fields
must be initialized with pure terminating program expressions.
The current syntax, proposed by Martin, is

    type t 'a = { f: ty1; g: ty2 }
      invariant { J[f,g] }
      by { f = e1; g = e2 }

The generated proof obligation is the VC for

    let g = e2 in let f = e1 in assert { J[f,g] }

In absence of an explicit witness, an existential proof obligation
"exists f,g. J[f,g]" is produced.

Without an argument, break and continue refer to the innermost loop.
A label put over an expression sequence starting with a loop, can be
used as an optional argument for break and continue:

  label L in
  [ghost] ["tag"] [M.begin]
    while true do
      ...
      break L
      ...
    done;
    [...]
  [end] [: unit]

In the square brackets are listed the constructions allowed between
the label declaration and the loop expression.

eval_match should not destruct user-written quantifiers.
For this purpose it preserves all quantifiers inside annotations.
For the same purpose it now also preserves all quantifiers appearing
inside terms in let-bindings (in particular, inside lambdas).

This commit also contains a fix for a curious exploit of our type
system which was made possible by a combination of local exceptions
and a special treatment of abstract blocks and whiteboxes.

Local exceptions allow us to exploit the type inference mechanism
and to force the same regions onto unrelated expressions. This is due
to the fact that local exceptions are region-monomorphic (this may be
relaxed in future). Of course, this was always possible via the API,
and the false aliases do not threaten the soundness of the system,
thanks to the following critical invariant:

  An allocation of a new mutable value always has an associated reset
  effect which invalidates the existing variables of the same type.

So, if two variables share a region, then exactly one of three
conditions must hold:

1. They are actually aliased, and modification of one must change
   the other in the VC.

2. They are not aliased, but the newer one invalidates the other:
   this is a case of false alias made benign by the reset effect.

3. The shared region is not actually reachable from the newer one:
        let x = if true then None else Some r
   this is another false alias, without an associated reset effect,
   yet still benign since the shared region is not reachable from x.

However, the type system and the VC generator must have the exact
same view on who's who's alias. If the VCgen encounters in the
same control flow two variables with a shared region in the type,
then the type system must have ensured one of the three conditions
above. Prior to this commit, there were two cases which violated
this:

- An exception raised in an abstract block that does not have
  an exceptional postcondition for it, escapes into the main
  control flow.

- A whitebox, by its nature, is fully handled inside the main
  control flow.

The violation came from the fact that abstract blocks and whiteboxes
are stored as cexps and so their effect is filtered by Ity.create_cty
in order to hide effects on variables allocated and collected inside
the block. This is a useful and necessary feature, except when the
VC of the block escapes into the main control flow and the forced
false aliases -- unchecked by the type system -- are seen by VCgen.
The implemented fix resolves the issue by restoring the hidden
effects for abstract blocks and whiteboxes.

Check bench/programs/bad-typing/false_alias*.mlw for two concrete
examples.

Just as abstract blocks, "white-box blocks" are program expressions
with an additional contract attached to their execution place.
Contrary to abstract blocks, whiteboxes do not hide their contents
from the outer computation. In most cases, you would not need
whiteboxes at all, as the same effect can be achieved by adding
assertions. Their utility comes from their syntax: the added
contract clauses bind to the expression and do not require
additional semicolons, begin-end's, let-in's or try-with's.

Compare:

    let x = <expr> in assert { P x }; x
to  <expr> ensures { P result }
or  <expr> returns { x -> P x }

    if ... then begin let x = <expr> in assert { P x }; x end; ...
to  if ... then <expr> ensures { P result }; ...

    try <expr> with E x -> assert { P x }; raise E x; end
to  <expr> raises { E x -> P x }

Internally, whiteboxes are just abstract blocks (zero-argument
anonymous functions executed in-place) with the label "vc:white_box"
on top. The user never needs to write this label explicitly though.

There is no reason why an abstract block cannot return an alias
with some external variable or exception.

This may produce false positives in cases like

  let x, ghost y = true, 3 + 42 (* (+) is logical here *)

The use of curly braces will suppress the warning (TODO).
Otherwise, this behaves reasonably well: there were only
two warnings inside examples/, both valid.

A symbol is now considered overloadable if it satisfies
the following conditions:
  - it has at least one parameter
  - it is non-ghost and has fully visible result
  - all of its parameters are non-ghost and have the same type
  - its result is either of the same type as its parameters
    or it is a monomorphic immutable type.

An overloadable symbol can be combined with other symbols of the
same arity and overloading kind. Otherwise, the new symbol shadows
the previously defined ones.

This generalisation allows us to overload symbols such as "size"
or "length", and also symbols of arbitraty non-zero arity.

I am reluctant to generalize this any further, because then we
won't have reasonable destructible signatures for type inference.

- requires a lot more testing
- support in extraction missing (exception raised)
- interaction with "syntax literal" remains to investigate

x.{f} is allowed and can be used for unary applications
M.{f} is not allowed, use {M.f} instead

It is confusing to use the keyword "label" to define an exception.
Also, the "label L in ..." binds too far and the break point is
not clearly defined.

We do need some syntactic sugar for
  exception X t in try <expr> with X r -> r
(at the very least "break" and "continue"), but labels are not it.

In the surface language, the loop index is always int in
the loop invariant and all annotations and pure terms inside
the loop. If you want to access the original range-typed index,
use "let copy_i = i in" in the program code before your assertion.
Of course, you cannot do that for the loop invariant, which is
what we want.

This allows to import an existing scope to the current namespace.
Not sure if we need this in the surface language, though.

In this way, someone who puts a part of his function
in an abstract block will not have broken "return"s.

Useful to break out of the loops:

  label Break in
  while ... do
    label Continue in
    ... raise Break ...
    ... raise Continue ...
  done

When a label is put over a non-unit expression,
raise acts as return:

  label Return in
  if ... then raise Return 42; 0

Also, "return <expr>" returns from the innermost function.
This includes abstract blocks, too, so if you want to return
across an abstract block, you should rather use a label at
the top of the main function. TODO/FIXME: maybe we should
let "return" pass across abstract blocks by default, to
avoid surprises?

One shortcoming of the labels-as-exceptions is that they cannot
be used to transmit tuples with ghost elements, nor return ghost
values from non-ghost expressions. A local exception with an
explicit mask should be used instead. Similarly, to return
a partially ghost value from a function, it must have have
its mask explicitly written (which is a good practice anyway).
We cannot know the mask of an expr before we construct it,
but in order to construct it, we need to create the local
exceptions first.

Another caveat is that while it is possible to catch an exception
generated by a label, you should avoid to do so. We only declare
the local exception if the expression under the label _raises_
the exception, and thus the following code will not typecheck:

  label X in (try raise X with X -> () end)

Indeed, the expression in the parentheses does not raise X,
and so we do not declare a local exception X for this label,
and so the program contains an undeclared exception symbol.

current syntax is

    exception Return (int, ghost bool) in
    ...
    try
      ...
      raise Return (5, false)
      ...
    with
      Return (i, b) -> ...
    ...

These exceptions can carry mutable and non-monomorphic values.
They can be raised from local functions defined in the scope
of the exception declaration.

Since local exceptions can carry results with type variables
and regions, we need to freeze them in the function signatures.

This is a prototype version that requires no additional annotation.
In addition to the existing rules of scoping:

  - it is forbidden to declare two symbols with the same name
    in the same scope ("everything can be unambiguously named"),

  - it is allowed to shadow an earlier declaration with a newer one,
    if they belong to different scopes (e.g., via import),

we define one new rule:

  - when an rsymbol rs_new would normally shadow an rsymbol rs_old,
    but (1) both of them are either
      - binary relations: t -> t -> bool,
      - binary operators: t -> t -> t, or
      - unary operators:  t -> t
    and (2) their argument types are not the same,
    then rs_old remains visible in the current scope.
    Both symbols should take non-ghost arguments and
    return non-ghost results, but effects are allowed.
    The name itself is not taken into account, hence
    it is possible to overload "div", "mod", or "fact".

Clause (1) allows us to perform type inference for a family of rsymbols,
using an appropriate generalized signature.

Clause (2) removes guaranteed ambiguities: we treat this case as
the user's intention to redefine the symbol for a given type.

Type inference failures are still possible: either due to
polymorphism (['a -> 'a] combines with [int -> int] and
will fail with the "ambiguous notation" error), or due
to inability to infer the precise types of arguments.
Explicit type annotations and/or use of qualified names
for disambiguation should always allow to bypass the errors.

Binary operations on Booleans are treated as relations, not as
operators. Thus, (+) on bool will not combine with (+) on int.

This overloading only concerns programs: in logic, the added rule
does not apply, and the old symbols get shadowed by the new ones.

In this setting, modules never export families of overloaded symbols:
it is impossible to "use import" a single module, and have access to
several rsymbols for (=) or (+).

The new "overloading" rule prefers to silently discard the previous
binding when it cannot be combined with the new one. This allows us
to be mostly backward compatible with existing programs (except for
the cases where type inference fails, as discussed above).

This rule should be enough to have several equalities for different
program types or overloaded arithmetic operations for bounded integers.
These rsymbols should not be defined as let-functions: in fact, it is
forbidden now to redefine equality in logic, and the bounded integers
should be all coerced into mathematical integers anyway.

I would like to be able to overload mixfix operators too, but
there is no reasonable generalized signature for them: compare
"([]) : map 'a 'b -> 'a -> 'b" with "([]) : array 'a -> int -> 'a"
with "([]) : monomap -> key -> elt". If we restrict the overloading
to symbols with specific names, we might go with "'a -> 'b -> 'c" for
type inference (and even "'a -> 'b" for some prefix operators, such
as "!" or "?"). To discuss.

As we have to implement the "HERE" and "PARENT" qualifiers anyway,
allowing this shadowing lets us accept more programs without
compromising the "everything is unambigously nameable" invariant.