GitLab

we still keep bv_vars in the binders, so calculating the set
of free variables only has to descend to the topmost binders.
The difference on an example from BWare is quite striking:

/usr/bin/time why3-replayer : with t_vars

505.14user 15.58system 8:40.45elapsed 100%CPU (0avgtext+0avgdata 3140336maxresident)k

/usr/bin/time why3-replayer : without t_vars

242.96user 12.04system 4:16.31elapsed 99%CPU (0avgtext+0avgdata 2007184maxresident)k

Not only we take 2/3 of memory, but we also gain in speed (less work
for the GC, most probably).

This patch should be tested on big WhyML examples,
since src/whyml/mlw_*.ml are big users of t_vars.

Thanks to Guillaume for the suggestion.

This fixes invariant computation for a program symbol whose signature
contains a new tuple symbol. The early call of flush_tuples will miss
the tuple symbols inside specifications, but these do not participate
in invariant computation, and are not a worry. We still have to use
add_pdecl_with_tuples to catch them, though.

By popular demand, read effects are back. They serve to mark dependence
of a program function on external variables which are otherwise not
mentioned in the function's specification. Such annotation is necessary,
for example, to add the needed type invariants.

The "reads" clauses are comma-separated variables (contrary to write
effects, where one must point out the modified field).

If a user specifies a "reads" clause for a defined function, we check
that every listed variable occurs in the code and that every free
variable in the code occurs in the specification (which includes the
"reads" clause). Notice that this concers function arguments, too:

  val r : ref int
  let f (x : ref int) reads {r} = x := !r

would require x to be added to reads.

One exception to this rule is the the result type in a non-recursive
function may contain regions coming the function's arguments (though
not from the context). It is sometimes useful to write a function
around a constructor or a projection: see function [create] in
verifythis_fm2012_LRS.mlw. For recursive functions we impose
the full non-alias discipline.

Now that ghost writes are checked via e_syms.syms_pv,
there is no use for read effects anymore.

this commit changes the way of tracking occurrences of regions
and type variables for the purposes of generalization, effect
filtering, and effect checks. It restricts the previous
implementation in two aspects:

- a psymbol p can be monomorphic (= non-generalizable) in an effect
  only if p depends (= is defined via) a pvsymbol whose type contains
  the affected region. See bench/programs/bad-typing/recfun.mlw
  for an example. This restriction is required for soundness.

- an argument of a psymbol cannot contain a region shared with
  another argument or an external pvsymbol. However, we do not
  require (so far) that the argument's type doesn't contain the same
  region twice and we allow the result type to contain known regions.
  This restriction is not necessary for soundness, and is introduced
  only to avoid some unintentional user errors and reduce the gap
  between the types that can be implemented in a "let" and the types
  that can be declared in a "val".

This makes unnecessary all checks for ghost exceptions
escaping into the non-ghost code.

In this case, we break the encapsulation and prove the global
exception postcondition directly from the code under "abstract".

also, require to list all write/read effects whenever
at least one is listed

fix hashtbl_impl, mergesort_queue, and unraveling_a_card_trick

a lemma function is introduced with 'let lemma f' or 'let rec lemma f'
it is a ghost function
it must have return type unit and read-only effects
it introduces a goal (its WP), followed by an axiom
  forall args/reads, precondition => postcondition

We store in every lsymbol a new integer field ls_constr,
equal to zero if the lsymbol is not a constructor, and equal
to the number of constructors of the lsymbol's type otherwise.
It is allowed to declare or define an lsymbol with ls_constr > 0
as an ordinary function (otherwise algebraic type elimination
wouldn't work - though we might still check this in theories),
but it is forbidden to use a wrong ls_constr in algebraic type
definitions.

The ghostness of a match expression is now determined as follows:

If at least one branch expression is ghost,
  then the match is ghost;
else if there is only one branch,
  then the match is not ghost;
else if the matched expression is ghost,
  then the match is ghost;
else if at least one pattern matches a ghost field
        against a constructor with ls_constr > 1
  then the match is ghost;
else
  the match is not ghost.

We do just enough to recognize obvious non-ghost cases, and
make no attempt to handle redundant matches or to detect
exhaustive or-patterns in subpatterns.

In programs, but also in pure theories, it is not safe to compare
arbitrary types. For example, if we have a record with ghost fields,
a comparison may produce different results before and after ghost
code elimination. Even for pure types like 'map' or 'set', it is
unlikely that the result of logical equality will be the same as
the result of OCaml structural equality on the implemented type.

This commit makes the first step towards fixing this issue.
We proceed in the following way:

1. Every lsymbol (pure function or predicate symbol) carries
   a subset of type variables of its signature, called "opaque
   type variables". By marking a type variable 'a opaque in an
   lsymbol's signature, the user guarantees that this lsymbol
   can be implemented without ever comparing values of type 'a.
   In other words, this is a promise not to break into a type
   variable.

   The corresponding syntax is: "predicate safe (x y : ~'a)".

   All type variables in undefined symbols are non-opaque,
   unless annotated otherwise. Non-opaque is the default
   to keep the change conservative.

   Opacity of type variables in defined symbols is inferred
   from the definition. If the definition violates a given
   opacity annotation, an exception is raised. Notice that
   we only check definitions in _theory_ declarations. One
   can define an lsymbol in a _task_ in a way that violates
   opacity. We cannot forbid it, because various elimination
   transformations would replace safe operations (such as
   matching) with equalities. This is not a problem, since in
   the pure logical realm of provers opacity is not required
   One exception would be Coq, whose transformation chain must
   never perform such operations.

   All type variables in inductive predicates are non-opaque.
   Indeed, we can redefine equality via an inductive predicate.
   [TODO: find safe forms of inductive definitions and implement
   more reasonable restrictions.]

   All type variables in constructors and field symbols are opaque.

   It is forbidden to instantiate an opacity-preserving symbol
   with an opacity-breaking one in a clone substitution.

2. Similar type variable tracking is implemented for program symbols.
   Type variables in the signature of a "val" are non-opaque unless
   annotated otherwise. Opacity of type variables in defined symbols
   is inferred from the definition, and an exception is raised, if
   a given annotation is violated.

   The internal mechanism of tracking is different: the "eff_compar"
   field in effects contains the type variables that occur under
   equality or any other opacity-breaking operation. In this respect,
   our API is inconsistent between lsymbols and psymbols: the former
   asks for the opaque tvsymbols, the latter requires us to fill the
   spec with "comparison effects" for the non-opaque ones. [TODO:
   add the "~opaque" argument to create_psymbol and make the WhyML
   core fill the effect under the hood.]

   Every time an lsymbol or a psymbol is applied in a program,
   we check the substitution into its signature's type variables.
   If a non-opaque type variable is instantiated with a program type,
   an exception is raised. [TODO: be more precise and reject only
   types with ghost and model components - being mutable, private,
   or carrying an invariant doesn't conflict with equality.]

   Notice that we do not allow to compare program types even in
   the ghost code. This is not needed if we only consider the
   problems of the code extraction, but _might_ be necessary,
   if we also want to protect Coq realisations (see below).

This commit fixes the immediate problem of breaking the ghost
guarantees when equality or some other opacity-breaking lsymbol
is applied in a program to a type with ghost or "model" parts.

This leaves the problem of code extraction for programs that
compare complex types such as maps or sets (Coq driver is
affected by this, too, I guess). The next step is to provide
annotations for problematic type constructors. A declaration
"type ~map 'a 'b" would mean "logical equality on this type
is likely to be different from the structural equality on any
implementation of this type - therefore do not apply equality
to it: neither in programs (because this can't be implemented),
nor in pure functions (because they are extracted, too, and
because this can't be realized with Leibniz equality in Coq)."
[TODO: discuss and implement.]

[TODO: mb choose better term for "opaque" and notation for ~'a.]

Also, ghost fields in algerbraic types are now accepted in programs.

As of now, "function", "predicate", "inductive", "val", "let", "fun",
and constructors in algebraic type declarations all accept the same
syntax for parameters. In "function", "predicate", "inductive", "val",
and constructors in algebraic type declarations, binders without
colons are treated as type expressions:

    function f int (list bool) (int,real) (ghost bool)

is syntactic sugar for

    function f (_: int) (_: list bool) (_: (int,real)) (ghost _: bool)

In "let" and "fun", single unqualified idents are treated as parameter
names whose types are to be inferred, other binders without colons are
treated as type expressions:

    let f int (list bool) (int,real) (ghost bool)

is syntactic sugar for

    let f (int: ?) (_: list bool) (_: (int,real)) (ghost bool: ?)

Anonymous binders ("_") are accepted only if their type is specified.

In a chain "e1 op1 e2 op2 e3 op3 e4", each relation symbol is either:

- an infix symbol "=" or "<>", or

- a binary symbol whose value type is Bool.bool or Prop (for lsymbols)
  and whose arguments' types are not Bool.bool.

In other words, we interpret a chain as a conjunction only if there
is no possibility(*) to interpret it as a superposition. The exception
is only made for "=" and "<>", which are _always_ considered as
chainable, even if they are redefined with some bogus type signatures.
Notice that redefining "<>" has no effect whatsoever, since "<>" is
always treated as negated "=".

As for the evaluation order, the chain above would be equivalent to:
    let x2 = e2 in
    (e1 op1 x2) &&
        let x3 = e3 in
        (x2 op2 x3) &&
            (x3 op3 e4)
This is due to the fact that lazy conjunctions are evaluated from
left to right, function arguments are evaluated from right to left,
and no expression should be evaluated twice.

[*] well, not really, since we consider symbols ('a -> 'b -> bool)
as chainable, even though such chains could be interpreted as
superpositions(**). We could treat such symbols as unchainable,
but that would make equality and disequality doubly special cases,
and I don't like it. We'll see if the current conditions are not
enough.

[**] what also bothers me is dynamic types of locally defined
infix symbols, which can be type variables or Bool.bool depending
on the order of operations in Mlw_typing. Currently, I can't come
up with any example of bad behaviour -- we are somewhat saved by
not being able to write "let (==) = ... in ...").

File "why3/modules/array.mlw", line 141, characters 2-26:
warning: cloned theory map.MapPermut does not contain any abstract symbol; it should be used instead

Note that warn_clone_not_abstract is not called from clone_export so that
the location of the declaration can be passed.

Now, there are three kinds of types used in WhyML API:
  ity -- the type of first-order values, "i" stands for "individual"
  aty -- the type of higher-order values, "a" stands for "arrow"
  vty -- the sum of the previous two, "v" stands for "value"

We should probably rename the VTvalue constructor, since it carries
an ity, and not a vty. And I would gladly rename ity to something
more appropriate, too.

Instead, we now store the ghostness boolean directly
in pvsymbols, pssymbols, ppatterns, and exprs. We thus
remove one level of indirection, and vty_value becomes
a one-field record which we remove in the next commit.

This simplifies semantics, makes a lot of checks unnecessary,
and makes us compatible with OCaml.

In this way, we can always distinguish them from local theories and
modules. Both 'use Bool' and 'use why3.Bool' are accepted. No support
for use/clone of built-in modules is done yet, but so far we don't
needed (the only built-in module is why3.Prelude which is used by
default).

As of now, one cannot put a file "why3.why" at the root of loadpath,
since it will be inaccessible. Paths like why3/toto.why are still
admitted, but we will probably ban them too and reserve the whole
"why3.xxx.yyy" hierarchy for the built-in theories and modules.