Something went wrong. Try again.
forked from gbury/dolmen
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732
(* This file is free software, part of dolmen. See file "LICENSE" for more information. *)
type location = Loc.t
type builtin = | Wildcard | Ttype | Unit | Void | Prop | Bool | True | False | Eq | Distinct (* Should all args be pairwise distinct or equal ? *)
| Ite (* Condional *) | Sequent (* Is the given sequent provable ? *)
| Int (* Arithmetic type for integers *) | Real (* Arithmetic type for reals *) | Minus (* arithmetic unary minus *) | Add | Sub | Mult (* arithmetic operators *) | Div | Mod (* arithmetic division *) | Int_pow | Real_pow (* arithmetic power (it's over 9000!) *) | Lt | Leq (* arithmetic comparisons *) | Gt | Geq (* arithmetic comparisons *)
| Subtype (* Function type constructor and subtyping relation *) | Product | Union (* Product and union of types (not set theory) *)
| Pi | Sigma (* Higher-order constant to encode forall and exists quantifiers *)
| Not (* Propositional negation *) | And | Or (* Conjunction and disjunction *) | Nand | Xor | Nor (* Advanced propositional connectives *) | Imply | Implied (* Implication and left implication *) | Equiv (* Equivalence *)
| Bitv of int (* Bitvector type (with given length) *) | Bitv_extract of int * int (* Bitvector extraction *) | Bitv_concat (* Bitvector concatenation *)
| Array_get | Array_set (* array operations *)
| Adt_check | Adt_project (* adt operations *)
| Record | Record_with | Record_access (* record operations *)
| Multi_trigger (* multi-triggers *) | Maps_to | In_interval of bool * bool | Check | Cut (* alt-ergo builtins *)
| Sexpr (* smtlib builtin for s-exprs *)
| Map_lambda (* smtlib2.7 builtin for function encoding into first order *) | Implicit_type_var (* The "type"/sort of an implicit type variable. *)
| As (* A builtin for the SMT-LIB's `as` """type annotation""", that affects type-checking so much it needs its own builtin *) | Fake_apply (* Workaround for languages who "function application" syntax does not actually have the semantics of function application. For instance, smtlib2.7 has extremely weird and unobvious rules for how applications are typechecked due to mixing it with their encoding of Higher-order. *)
type binder = | All | Ex | Pi | Arrow | Let_seq (* sequential let-binding *) | Let_par (* parrallel let-binding *) | Fun (* function parameter binding *) | Choice (* Indefinite description, or epsilon terms *) | Description (* Definite description *)
type descr = | Symbol of Id.t | Builtin of builtin | Colon of t * t | App of t * t list | Binder of binder * t list * t | Match of t * (t * t) list
and t = { term : descr; attr : t list; loc : location;}
(* Printing info *)
let infix_builtin = function | Add | Sub | Lt | Leq | Gt | Geq | Eq | And | Or | Nand | Xor | Nor | Imply | Implied | Equiv | Product | Union | Sequent | Subtype | Adt_check | Adt_project | Record_access -> true | Distinct -> true | _ -> false
let builtin_to_string = function | Wildcard -> "_" | Ttype -> "Ttype" | Unit -> "unit" | Void -> "()" | Prop -> "Prop" | Bool -> "Bool" | True -> "⊤" | False -> "⊥" | Eq -> "==" | Distinct -> "!=" | Ite -> "ite" | Sequent -> "⊢" | Int -> "ℤ" | Real -> "ℝ" | Minus -> "-" | Add -> "+" | Sub -> "-" | Mult -> "×" | Div -> "÷" | Mod -> "mod" | Int_pow -> "**" | Real_pow -> "**." | Lt -> "<" | Leq -> "≤" | Gt -> ">" | Geq -> "≥" | Subtype -> "⊂" | Product -> "*" | Union -> "∪" | Pi -> "Π" | Sigma -> "Σ" | Not -> "¬" | And -> "∧" | Or -> "∨" | Nand -> "⊼" | Xor -> "⊻" | Nor -> "V" | Imply -> "⇒" | Implied -> "⇐" | Equiv -> "⇔" | Bitv i -> Printf.sprintf "bitv(%d)" i | Bitv_extract (i, j) -> Printf.sprintf "bitv_extract(%d;%d)" i j | Bitv_concat -> "bitv_concat" | Array_get -> "get" | Array_set -> "set" | Adt_check -> "?" | Adt_project -> "#" | Record -> "record" | Record_with -> "record_with" | Record_access -> "." | Multi_trigger -> "multi" | Maps_to -> "↦" | In_interval (b, b') -> let bracket = function true -> "]" | false -> "[" in Printf.sprintf "in_interval%s%s" (bracket b) (bracket (not b')) | Check -> "check" | Cut -> "cut" | Sexpr -> "sexpr" | Map_lambda -> "map-lambda" | Implicit_type_var -> "TypeVar" | As -> "as" | Fake_apply -> "&"
let binder_to_string = function | All -> "∀" | Ex -> "∃" | Pi -> "Π" | Arrow -> "" | Let_seq | Let_par -> "let" | Fun -> "λ" | Choice -> "ε" | Description -> "@"
let binder_sep_string = function | All | Ex | Pi | Let_seq | Fun | Choice | Description -> "" | Let_par -> " and" | Arrow -> " →"
let binder_end_string = function | All | Ex | Pi | Choice | Description -> "." | Fun -> "=>" | Let_seq | Let_par -> "in" | Arrow -> "→"
(*(* Debug printing *)
let pp_builtin b builtin = Printf.bprintf b "%s" (builtin_to_string builtin)
let pp_binder b binder = Printf.bprintf b "%s" (binder_to_string binder)
let rec pp_descr b = function | Symbol id -> Id.pp b id | Builtin s -> pp_builtin b s | Colon (u, v) -> Printf.bprintf b "%a : %a" pp u pp v | App ({ term = Builtin sep ; _ }, l) when infix_builtin sep -> Misc.pp_list ~pp_sep:pp_builtin ~sep ~pp b l | App (f, l) -> Printf.bprintf b "%a(%a)" pp f (Misc.pp_list ~pp_sep:Buffer.add_string ~sep:"," ~pp) l | Binder (q, l, e) -> let sep = binder_sep_string q ^ " " in Printf.bprintf b "%a %a %s %a" pp_binder q (Misc.pp_list ~pp_sep:Buffer.add_string ~sep ~pp) l (binder_end_string q) pp e | Match (t, l) -> Printf.bprintf b "match %a with %a" pp t (Misc.pp_list ~pp_sep:Buffer.add_string ~sep:" | " ~pp:pp_match_case) l
and pp_match_case b (pattern, branch) = Printf.bprintf b "%a => %a" pp pattern pp branch
and pp b = function | { term = (Symbol _) as d; _ } | { term = (Builtin _) as d; _ } -> pp_descr b d | e -> Printf.bprintf b "(%a)" pp_descr e.term*)
(* Pretty-printing *)
let print_locs = false
let print_loc fmt loc = if print_locs then Format.fprintf fmt "[%a]" Loc.print_compact loc
let print_builtin fmt builtin = Format.fprintf fmt "%s" (builtin_to_string builtin)
let print_binder fmt binder = Format.fprintf fmt "%s" (binder_to_string binder)
let rec print_descr fmt = function | Symbol id -> Id.print fmt id | Builtin s -> print_builtin fmt s | Colon (u, v) -> Format.fprintf fmt "%a :@ %a" print u print v | App ({ term = Builtin b ; _ }, l) when infix_builtin b -> let pp_sep fmt () = Format.fprintf fmt " %a@ " print_builtin b in Format.pp_print_list ~pp_sep print fmt l | App (f, []) -> Format.fprintf fmt "%a" print f | App (f, l) -> let pp_sep = Format.pp_print_space in Format.fprintf fmt "%a@ %a" print f (Format.pp_print_list ~pp_sep print) l | Binder (q, l, e) -> let pp_sep fmt () = Format.fprintf fmt "%s@ " (binder_sep_string q) in Format.fprintf fmt "%a@ %a@ %s@ %a" print_binder q (Format.pp_print_list ~pp_sep print) l (binder_end_string q) print e | Match (t, l) -> let pp_sep fmt () = Format.fprintf fmt " | " in Format.fprintf fmt "match %a with %a" print t (Format.pp_print_list ~pp_sep print_match_case) l
and print_match_case fmt (pattern, branch) = Format.fprintf fmt "%a => %a" print pattern print branch
and print_attr fmt = function | [] -> () | a :: r -> Format.fprintf fmt "{%a}@,%a" print a print_attr r
and print fmt = function | { term = (Symbol _) as d ; attr; loc; } | { term = (Builtin _) as d ; attr; loc; } -> Format.fprintf fmt "@[<hov 2>%a@,%a@,%a@]" print_descr d print_loc loc print_attr attr | e -> Format.fprintf fmt "@[<hov 2>(%a)@,%a@,%a@]" print_descr e.term print_loc e.loc print_attr e.attr
(* Comparison *)let _descr = function | Symbol _ -> 1 | Builtin _ -> 2 | Colon _ -> 3 | App _ -> 4 | Binder _ -> 5 | Match _ -> 6
let rec compare_list cmp l l' = match l, l' with | [], [] -> 0 | _ :: _, [] -> 1 | [], _ :: _ -> -1 | t :: r, t' :: r' -> begin match cmp t t' with | 0 -> compare_list cmp r r' | x -> x end
let rec compare t t' = match t.term, t'.term with | Symbol s, Symbol s' -> Id.compare s s' | Builtin b, Builtin b' -> Stdlib.compare b b' | Colon (t1, t2), Colon (t1', t2') -> compare_list compare [t1; t2] [t1'; t2'] | App (f, l), App(f', l') -> compare_list compare (f :: l) (f' :: l') | Binder (b, vars, t), Binder (b', vars', t') -> begin match Stdlib.compare b b' with | 0 -> begin match compare_list compare vars vars' with | 0 -> compare t t' | x -> x end | x -> x end | Match (t, l), Match (t', l') -> begin match compare t t' with | 0 -> compare_list compare_pair l l' | x -> x end | u, v -> (_descr u) - (_descr v)
and compare_pair (a, b) (c, d) = match compare a c with | 0 -> compare b d | x -> x
let equal t t' = compare t t' = 0
(* Add an attribute *)let[@inline always] add_attr a t = { t with attr = a :: t.attr }
let[@inline always] add_attrs l t = { t with attr = l @ t.attr }
let[@inline always] set_attrs l t = assert (t.attr = []); { t with attr = l }
(* Make a term from its description *)let[@inline always] make ?(loc=Loc.no_loc) ?(attr=[]) term = { term; attr; loc; }
let[@inline always] builtin b ?loc () = make ?loc (Builtin b)
(* Internal shortcut to make a formula with bound variables. *)let[@inline always] mk_bind binder ?loc vars t = make ?loc (Binder (binder, vars, t))
(* Attach an attribute list to a term *)let annot ?(loc=Loc.no_loc) t l = { t with attr = t.attr @ l; loc }
(* Create a constant and/or variable, that is a leaf of the term AST. *)let[@inline always] const ?loc id = make ?loc (Symbol id)
(* Apply a term to a list of terms. *)let[@inline always] apply ?loc f args = make ?loc (App (f, args))
let[@inline always] match_ ?loc t l = make ?loc (Match (t, l))
(* Juxtapose two terms, usually a term and its type. Used mainly for typed variables, or type annotations. *)let[@inline always] colon ?loc t t' = make ?loc (Colon (t, t'))
let eq_t = builtin Eqlet neq_t = builtin Distinctlet not_t = builtin Notlet or_t = builtin Orlet and_t = builtin Andlet xor_t = builtin Xorlet nor_t = builtin Norlet nand_t = builtin Nandlet equiv_t = builtin Equivlet implies_t = builtin Implylet implied_t = builtin Implied
let pi_t = builtin Pilet sigma_t = builtin Sigma
let void = builtin Voidlet true_ = builtin Truelet false_ = builtin Falselet wildcard = builtin Wildcard
let ite_t = builtin Itelet sequent_t = builtin Sequent
let union_t = builtin Unionlet product_t = builtin Productlet subtype_t = builtin Subtype
let tType = builtin Ttypelet prop = builtin Proplet bool = builtin Boollet data_t ?loc () = const ?loc Id.(mk Attr "$data")
let ty_unit = builtin Unitlet ty_int = builtin Intlet ty_real = builtin Reallet uminus_t = builtin Minuslet add_t = builtin Addlet sub_t = builtin Sublet mult_t = builtin Multlet div_t = builtin Divlet mod_t = builtin Modlet int_pow_t = builtin Int_powlet real_pow_t = builtin Real_powlet lt_t = builtin Ltlet leq_t = builtin Leqlet gt_t = builtin Gtlet geq_t = builtin Geq
let array_get_t = builtin Array_getlet array_set_t = builtin Array_set
let bitv_t i = builtin (Bitv i)let bitv_concat_t = builtin Bitv_concatlet bitv_extract_t i j = builtin (Bitv_extract (i, j))
let adt_check_t = builtin Adt_checklet adt_project_t = builtin Adt_project
let record_t = builtin Recordlet record_with_t = builtin Record_withlet record_access_t = builtin Record_access
let sexpr_t = builtin Sexprlet map_lambda_t = builtin Map_lambdalet implicit_type_var_t = builtin Implicit_type_varlet as_t = builtin Aslet fake_apply_t = builtin Fake_apply
let nary t = (fun ?loc l -> apply ?loc (t ?loc ()) l)let unary t = (fun ?loc x -> apply ?loc (t ?loc ()) [x])let binary t = (fun ?loc x y -> apply ?loc (t ?loc ()) [x; y])let tertiary t = (fun ?loc x y z -> apply ?loc (t ?loc ()) [x; y; z])
(* {2 Usual functions} *)
let eq = binary eq_tlet neq = nary neq_t
(* {2 Logical connectives} *)
let not_ = unary not_tlet or_ = nary or_tlet and_ = nary and_tlet xor = binary xor_tlet imply = binary implies_tlet equiv = binary equiv_t
(** {2 Arithmetic} *)
let uminus = unary uminus_tlet add = binary add_tlet sub = binary sub_tlet mult = binary mult_tlet div = binary div_tlet mod_ = binary mod_tlet int_pow = binary int_pow_tlet real_pow = binary real_pow_tlet lt = binary lt_tlet leq = binary leq_tlet gt = binary gt_tlet geq = binary geq_t
(* {2 Arrays} *)
let array_get = binary array_get_tlet array_set = tertiary array_set_t
(* {2 Bitvectors} *)
let ty_bitv ?loc i = apply ?loc (bitv_t i ?loc ()) []
let bitv_extract ?loc t i j = apply ?loc (bitv_extract_t i j ?loc ()) [t]
let bitv_concat = binary bitv_concat_t
(* {2 ADTs} *)
let adt_check ?loc t id = let x = const ?loc id in apply ?loc (adt_check_t ?loc ()) [t; x]
let adt_project ?loc t id = let x = const ?loc id in apply ?loc (adt_project_t ?loc ()) [t; x]
(** {2 Records} *)
let record = nary record_t
let record_with ?loc t l = nary record_with_t ?loc (t :: l)
let record_access ?loc t id = let x = const ?loc id in binary record_access_t ?loc t x
(* {2 Binders} *)
let pi = mk_bind Pilet letin = mk_bind Let_seqlet letand = mk_bind Let_parlet exists = mk_bind Exlet forall = mk_bind Alllet lambda = mk_bind Funlet choice = mk_bind Choicelet description = mk_bind Description
let fun_ty = mk_bind Arrowlet arrow ?loc arg ret = fun_ty ?loc [arg] ret
(* {2 Free variables} *)
module S = Set.Make(Id)
let rec free_ids ~test acc t = match t.term with | Builtin _ -> acc | Colon (t, t') -> free_ids ~test (free_ids ~test acc t) t' | Symbol id -> if test id then S.add id acc else acc | App (t, l) -> List.fold_left (free_ids ~test) (free_ids ~test acc t) l | Binder (Arrow, l, t) -> List.fold_left (free_ids ~test) (free_ids ~test acc t) l | Binder (_, l, t) -> let s = free_ids ~test S.empty t in let bound, free = List.fold_left (free_ids_bound ~test) (S.empty, S.empty) l in let s' = S.filter (fun x -> not (S.mem x bound)) s in S.union acc (S.union s' free) | Match (t, l) -> let acc = List.fold_left (fun acc (pattern, branch) -> let s = free_ids ~test S.empty branch in let bound = free_ids ~test S.empty pattern in let s' = S.filter (fun x -> not (S.mem x bound)) s in S.union s' acc ) acc l in free_ids ~test acc t
and free_ids_bound ~test (bound, free) t = match t.term with | Colon (v, ty) -> free_ids ~test bound v, free_ids ~test free ty | _ -> free_ids ~test bound t, free
let fv t = let test id = id.Id.ns = Namespace.Var in S.elements (free_ids ~test S.empty t)
(* {2 Wrappers for alt-ergo} *)
let bitv ?loc s = const ?loc Id.(mk (Value Bitvector) s)
let cut = unary (builtin Cut)let check = unary (builtin Check)
let trigger ?loc l = apply ?loc (builtin ?loc Multi_trigger ()) l
let triggers_t = Id.(mk Attr "triggers")let triggers ?loc t = function | [] -> t | l -> let a = apply ?loc (const ?loc triggers_t) l in annot ?loc t [a]
let filters_t = Id.(mk Attr "filters")let filters ?loc t = function | [] -> t | l -> let a = apply ?loc (const ?loc filters_t) l in annot ?loc t [a]
let tracked ?loc id t = let a = const ?loc id in annot ?loc t [a]
let maps_to ?loc id t = let a = const ?loc id in binary (builtin Maps_to) ?loc a t
let in_interval ?loc t (lb, ls) (rb, rs) = tertiary (builtin (In_interval (ls, rs))) ?loc t lb rb
(* {2 Wrappers for dimacs} *)
let atom ?loc i = let s = Printf.sprintf "#%d" (abs i) in if i >= 0 then const ?loc Id.(mk Term s) else not_ ?loc (const ?loc Id.(mk Term s))
(* {2 Wrappers for smtlib} *)
let as_ ?loc ty f args = nary as_t ?loc (ty :: f :: args)
let str ?loc s = const ?loc Id.(mk (Value String) s)let int ?loc s = const ?loc Id.(mk (Value Integer) s)let real ?loc s = const ?loc Id.(mk (Value Real) s)let hexa ?loc s = const ?loc Id.(mk (Value Hexadecimal) s)let binary ?loc s = const ?loc Id.(mk (Value Binary) s)
let sexpr ?loc l = apply ?loc (sexpr_t ?loc ()) l
let par ?loc vars t = let vars = List.map (fun v -> colon ?loc v (tType ?loc ())) vars in forall ?loc vars t
let map_lambda ?loc vars t = nary map_lambda_t ?loc (vars @ [t])let fake_apply ?loc f args = nary fake_apply_t ?loc (f :: args)
(* {2 Wrappers for tptp} *)
let rat ?loc s = const ?loc Id.(mk (Value Rational) s)let distinct = const
let var ?loc id = const ?loc { id with Id.ns = Var }
let ite ?loc a b c = apply ?loc (ite_t ?loc ()) [a; b; c]
let sequent ?loc hyps goals = let hyps_t = apply ?loc (or_t ?loc ()) hyps in let goals_t = apply ?loc (and_t ?loc ()) goals in apply ?loc (sequent_t ?loc ()) [hyps_t; goals_t]
let union ?loc a b = apply ?loc (union_t ?loc ()) [a; b]let product ?loc a b = apply ?loc (product_t ?loc ()) [a; b]let subtype ?loc a b = apply ?loc (subtype_t ?loc ()) [a; b]
(* {2 Wrappers for Zf} *)
let quoted ?loc name = const ?loc (Id.mk Attr name)
(* {2 Term traversal} *)
type 'a mapper = { symbol : 'a mapper -> attr:t list -> loc:location -> Id.t -> 'a; builtin : 'a mapper -> attr:t list -> loc:location -> builtin -> 'a; colon : 'a mapper -> attr:t list -> loc:location -> t -> t -> 'a; app : 'a mapper -> attr:t list -> loc:location -> t -> t list -> 'a; binder : 'a mapper -> attr:t list -> loc:location -> binder -> t list -> t -> 'a; pmatch : 'a mapper -> attr:t list -> loc:location -> t -> (t * t) list -> 'a;}
let map mapper t = let wrap f = f mapper ~attr:t.attr ~loc:t.loc in match t.term with | Symbol id -> wrap mapper.symbol id | Builtin b -> wrap mapper.builtin b | Colon (u, v) -> wrap mapper.colon u v | App (f, args) -> wrap mapper.app f args | Binder (b, vars, body) -> wrap mapper.binder b vars body | Match (e, l) -> wrap mapper.pmatch e l
let id_mapper = { symbol = (fun m ~attr ~loc id -> set_attrs (List.map (map m) attr) @@ const ~loc id); builtin = (fun m ~attr ~loc b -> set_attrs (List.map (map m) attr) @@ builtin ~loc b ()); colon = (fun m ~attr ~loc u v -> set_attrs (List.map (map m) attr) @@ colon ~loc (map m u) (map m v)); app = (fun m ~attr ~loc f args -> set_attrs (List.map (map m) attr) @@ apply ~loc (map m f) (List.map (map m) args)); binder = (fun m ~attr ~loc b vars body -> set_attrs (List.map (map m) attr) @@ mk_bind ~loc b (List.map (map m) vars) (map m body)); pmatch = (fun m ~attr ~loc e l -> set_attrs (List.map (map m) attr) @@ match_ ~loc (map m e) (List.map (fun (pat, body) -> (map m pat, map m body)) l));}
let unit_mapper = { symbol = (fun m ~attr ~loc:_ _ -> List.iter (map m) attr); builtin = (fun m ~attr ~loc:_ _ -> List.iter (map m) attr); colon = (fun m ~attr ~loc:_ u v -> List.iter (map m) attr; map m u; map m v); app = (fun m ~attr ~loc:_ f args -> List.iter (map m) attr; map m f; List.iter (map m) args); binder = (fun m ~attr ~loc:_ _ vars body -> List.iter (map m) attr; List.iter (map m) vars; map m body); pmatch = (fun m ~attr ~loc:_ e l -> List.iter (map m) attr; map m e; List.iter (fun (pat, body) -> map m pat; map m body) l);}
module View = struct
module Sexpr = struct
type id = Id.t type nonrec t = t
exception Not_an_sexpr of t
let view t = match t.term with | Symbol id -> Dolmen_intf.View.Sexpr.Symbol id | App ( { term = Builtin Sexpr; _ }, l ) -> Dolmen_intf.View.Sexpr.App l | App (f, l) -> Dolmen_intf.View.Sexpr.App (f :: l) | _ -> raise (Not_an_sexpr t)
end
end