1. 11 Sep, 2014 1 commit
  2. 10 Sep, 2014 2 commits
  3. 09 Sep, 2014 2 commits
  4. 08 Sep, 2014 2 commits
  5. 07 Sep, 2014 1 commit
  6. 22 Aug, 2014 1 commit
  7. 19 Aug, 2014 1 commit
  8. 07 Apr, 2014 1 commit
  9. 14 Mar, 2014 1 commit
  10. 29 Oct, 2013 1 commit
    • Andrei Paskevich's avatar
      Term: do not store t_vars in terms · 7abeba05
      Andrei Paskevich authored
      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.
      7abeba05
  11. 22 Apr, 2013 1 commit
    • Andrei Paskevich's avatar
      whyml: ensure the absence of alias in function types · 3cd56b05
      Andrei Paskevich authored
      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.
      3cd56b05
  12. 17 Apr, 2013 1 commit
  13. 07 Apr, 2013 3 commits
  14. 06 Apr, 2013 1 commit
    • Andrei Paskevich's avatar
      whyml: keep track of pvsymbols and psymbols in expressions · dce120fa
      Andrei Paskevich authored
      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".
      dce120fa
  15. 27 Mar, 2013 1 commit
  16. 26 Mar, 2013 2 commits
  17. 22 Mar, 2013 1 commit
    • Jean-Christophe Filliâtre's avatar
      lemma functions · 3a716828
      Jean-Christophe Filliâtre authored
      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
      3a716828
  18. 06 Mar, 2013 1 commit
  19. 03 Mar, 2013 1 commit
    • Andrei Paskevich's avatar
      track dangerous applications of equality · bb6734a1
      Andrei Paskevich authored
      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.]
      bb6734a1
  20. 07 Feb, 2013 1 commit
  21. 04 Feb, 2013 1 commit
  22. 03 Feb, 2013 4 commits
  23. 21 Jan, 2013 1 commit
  24. 19 Dec, 2012 2 commits
  25. 13 Nov, 2012 2 commits
  26. 21 Oct, 2012 4 commits