Frama-C API - QED
module ADT = ADT
module Field = Field
module Fun = Fun
module Var : Qed.Logic.Variable
module Term : Qed.Logic.Symbol with type t = term
module Tset : Qed.Idxset.S with type elt = term
Non-structural, machine dependent, but fast comparison and efficient merges
module Tmap : Qed.Idxmap.S with type key = term
Non-structural, machine dependent, but fast comparison and efficient merges
Structuraly ordered, but less efficient access and non-linear merges
Structuraly ordered, but less efficient access and non-linear merges
Variables
type var = Var.t
type tau = (Field.t, ADT.t) Qed.Logic.datatype
module Tau : Qed.Logic.Data with type t = tau
module Vars : Qed.Idxset.S with type elt = var
module Vmap : Qed.Idxmap.S with type key = var
val sort_of_var : var -> Qed.Logic.sort
val base_of_var : var -> string
Terms
type repr = term expression
val decide : term -> bool
Return true
if and only the term is e_true
. Constant time.
val is_true : term -> Qed.Logic.maybe
Constant time.
val is_false : term -> Qed.Logic.maybe
Constant time.
val is_prop : term -> bool
Boolean or Property
val is_int : term -> bool
Integer sort
val is_real : term -> bool
Real sort
val is_arith : term -> bool
Integer or Real sort
val are_equal : term -> term -> Qed.Logic.maybe
Computes equality
val sort : term -> Qed.Logic.sort
Constant time
Path-positioning access
This part of the API is DEPRECATED
Basic constructors
val e_true : term
val e_false : term
val e_bool : bool -> term
val e_int : int -> term
val e_float : float -> term
val e_zint : Z.t -> term
val e_real : Q.t -> term
Quantifiers and Binding
val e_bind : Qed.Logic.binder -> var -> term -> term
Bind the given variable if it appears free in the term, or return the term unchanged.
Opens the top-most bound variable with a (fresh) variable. Can be only applied on top-most lc-term from `Bind(_,_,_)`, thanks to typing.
val e_open : pool:pool -> ?forall:bool -> ?exists:bool -> ?lambda:bool -> term -> (Qed.Logic.binder * var) list * term
Open all the specified binders (flags default to `true`, so all consecutive top most binders are opened by default). The pool must contain all free variables of the term.
val e_close : (Qed.Logic.binder * var) list -> term -> term
Closes all specified binders
Generalized Substitutions
module Subst : sig ... end
The environment sigma must be prepared with the desired substitution. Its pool of fresh variables must covers the entire domain and co-domain of the substitution, and the transformed values.
Locally Nameless Representation
These functions can be unsafe because they might expose terms that contains non-bound b-vars. Never use such terms to build substitutions (sigma).
val lc_vars : term -> Qed.Bvars.t
val lc_closed : term -> bool
All bound variables are under their binder
Similar to f_iter
but exposes non-closed sub-terms of `Bind` as regular term
values instead of lc_term
ones.
Iteration Scheme
val f_map : ?pool:pool -> ?forall:bool -> ?exists:bool -> ?lambda:bool -> (term -> term) -> term -> term
Pass and open binders, maps its direct sub-terms and then close then opened binders Raises Invalid_argument in case of a bind-term without pool. The optional pool must contain all free variables of the term.
val f_iter : ?pool:pool -> ?forall:bool -> ?exists:bool -> ?lambda:bool -> (term -> unit) -> term -> unit
Iterates over its direct sub-terms (pass and open binders) Raises Invalid_argument in case of a bind-term without pool. The optional pool must contain all free variables of the term.
Partial Typing
val typeof : ?field:(Field.t -> tau) -> ?record:(Field.t -> tau) -> ?call:(Fun.t -> tau option list -> tau) -> term -> tau
Try to extract a type of term. Parameterized by optional extractors for field and functions. Extractors may raise Not_found
; however, they are only used when the provided kinds for fields and functions are not precise enough.
Support for Builtins
Register a simplifier for function f
. The computation code may raise Not_found
, in which case the symbol is not interpreted.
If f
is an operator with algebraic rules (see type operator
), the children are normalized before builtin call.
Highest priority is 0
. Recursive calls must be performed on strictly smaller terms.
The force
parameters defaults to false
, when it is true
, if there exist another builtin, it is replaced with the new one. Use with care.
Register a builtin for rewriting f a1..an
into f b1..bm
.
This is short cut for set_builtin
, where the head application of f
avoids to run into an infinite loop.
The force
parameters defaults to false
, when it is true
, if there exist another builtin, it is replaced with the new one. Use with care.
set_builtin_get f rewrite
register a builtin for rewriting (f a1..an)[k1]..[km]
into rewrite (a1..an) (k1..km)
.
The force
parameters defaults to false
, when it is true
, if there exist another builtin, it is replaced with the new one. Use with care.
Register a builtin for simplifying (f e…).fd
expressions. Must only use recursive comparison for strictly smaller terms.
The force
parameters defaults to false
, when it is true
, if there exist another builtin, it is replaced with the new one. Use with care.
Register a builtin equality for comparing any term with head-symbol. Must only use recursive comparison for strictly smaller terms. The recognized term with head function symbol is passed first.
Highest priority is 0
. Recursive calls must be performed on strictly smaller terms.
The force
parameters defaults to false
, when it is true
, if there exist another builtin, it is replaced with the new one. Use with care.
Register a builtin for comparing any term with head-symbol. Must only use recursive comparison for strictly smaller terms. The recognized term with head function symbol can be on both sides. Strict comparison is automatically derived from the non-strict one.
Highest priority is 0
. Recursive calls must be performed on strictly smaller terms.
The force
parameters defaults to false
, when it is true
, if there exist another builtin, it is replaced with the new one. Use with care.
Specific Patterns
val affine : term -> term Qed.Logic.affine
Symbol
type t = term
val id : t -> int
unique identifier (stored in t)
val hash : t -> int
constant access (stored in t)
val pretty : Stdlib.Format.formatter -> t -> unit
val weigth : t -> int
Informal size
Utilities
val is_closed : t -> bool
No bound variables
val is_simple : t -> bool
Constants, variables, functions of arity 0
val is_atomic : t -> bool
Constants and variables
val is_primitive : t -> bool
Constants only
val size : t -> int
val basename : t -> string
val debug : Stdlib.Format.formatter -> t -> unit
val pp_id : Stdlib.Format.formatter -> t -> unit
internal id
val pp_rid : Stdlib.Format.formatter -> t -> unit
head symbol with children id's
val pp_repr : Stdlib.Format.formatter -> repr -> unit
head symbol with children id's
Shared sub-terms
Occurrence check. is_subterm a b
returns true
iff a
is a subterm of b
. Optimized wrt shared subterms, term size, and term variables.
Computes the sub-terms that appear several times. shared marked linked e
returns the shared subterms of e
.
The list of shared subterms is consistent with order of definition: each trailing terms only depend on heading ones.
The traversal is controlled by two optional arguments:
shared
those terms are not traversed (considered as atomic, default to none)shareable
those terms (is_simple
excepted) that can be shared (default to all)subterms
those sub-terms a term to be considered during traversal (lc_iter
by default)
Low-level shared primitives: shared
is actually a combination of building marks, marking terms, and extracting definitions:
let share ?... e =
let m = marks ?... () in
List.iter (mark m) es ;
defs m
Create a marking accumulator. Same defaults than shared
.
Mark a term to be explicitly shared