39348
|
1 |
(* ========================================================================= *)
|
|
2 |
(* ORDERED REWRITING FOR FIRST ORDER TERMS *)
|
39502
|
3 |
(* Copyright (c) 2003 Joe Hurd, distributed under the BSD License *)
|
39348
|
4 |
(* ========================================================================= *)
|
|
5 |
|
|
6 |
signature Rewrite =
|
|
7 |
sig
|
|
8 |
|
|
9 |
(* ------------------------------------------------------------------------- *)
|
|
10 |
(* Orientations of equations. *)
|
|
11 |
(* ------------------------------------------------------------------------- *)
|
|
12 |
|
|
13 |
datatype orient = LeftToRight | RightToLeft
|
|
14 |
|
|
15 |
val toStringOrient : orient -> string
|
|
16 |
|
|
17 |
val ppOrient : orient Print.pp
|
|
18 |
|
|
19 |
val toStringOrientOption : orient option -> string
|
|
20 |
|
|
21 |
val ppOrientOption : orient option Print.pp
|
|
22 |
|
|
23 |
(* ------------------------------------------------------------------------- *)
|
|
24 |
(* A type of rewrite systems. *)
|
|
25 |
(* ------------------------------------------------------------------------- *)
|
|
26 |
|
|
27 |
type reductionOrder = Term.term * Term.term -> order option
|
|
28 |
|
|
29 |
type equationId = int
|
|
30 |
|
|
31 |
type equation = Rule.equation
|
|
32 |
|
|
33 |
type rewrite
|
|
34 |
|
|
35 |
(* ------------------------------------------------------------------------- *)
|
|
36 |
(* Basic operations. *)
|
|
37 |
(* ------------------------------------------------------------------------- *)
|
|
38 |
|
|
39 |
val new : reductionOrder -> rewrite
|
|
40 |
|
|
41 |
val peek : rewrite -> equationId -> (equation * orient option) option
|
|
42 |
|
|
43 |
val size : rewrite -> int
|
|
44 |
|
|
45 |
val equations : rewrite -> equation list
|
|
46 |
|
|
47 |
val toString : rewrite -> string
|
|
48 |
|
|
49 |
val pp : rewrite Print.pp
|
|
50 |
|
|
51 |
(* ------------------------------------------------------------------------- *)
|
|
52 |
(* Add equations into the system. *)
|
|
53 |
(* ------------------------------------------------------------------------- *)
|
|
54 |
|
|
55 |
val add : rewrite -> equationId * equation -> rewrite
|
|
56 |
|
|
57 |
val addList : rewrite -> (equationId * equation) list -> rewrite
|
|
58 |
|
|
59 |
(* ------------------------------------------------------------------------- *)
|
|
60 |
(* Rewriting (the order must be a refinement of the rewrite order). *)
|
|
61 |
(* ------------------------------------------------------------------------- *)
|
|
62 |
|
|
63 |
val rewrConv : rewrite -> reductionOrder -> Rule.conv
|
|
64 |
|
|
65 |
val rewriteConv : rewrite -> reductionOrder -> Rule.conv
|
|
66 |
|
|
67 |
val rewriteLiteralsRule :
|
|
68 |
rewrite -> reductionOrder -> LiteralSet.set -> Rule.rule
|
|
69 |
|
|
70 |
val rewriteRule : rewrite -> reductionOrder -> Rule.rule
|
|
71 |
|
|
72 |
val rewrIdConv : rewrite -> reductionOrder -> equationId -> Rule.conv
|
|
73 |
|
|
74 |
val rewriteIdConv : rewrite -> reductionOrder -> equationId -> Rule.conv
|
|
75 |
|
|
76 |
val rewriteIdLiteralsRule :
|
|
77 |
rewrite -> reductionOrder -> equationId -> LiteralSet.set -> Rule.rule
|
|
78 |
|
|
79 |
val rewriteIdRule : rewrite -> reductionOrder -> equationId -> Rule.rule
|
|
80 |
|
|
81 |
(* ------------------------------------------------------------------------- *)
|
|
82 |
(* Inter-reduce the equations in the system. *)
|
|
83 |
(* ------------------------------------------------------------------------- *)
|
|
84 |
|
|
85 |
val reduce' : rewrite -> rewrite * equationId list
|
|
86 |
|
|
87 |
val reduce : rewrite -> rewrite
|
|
88 |
|
|
89 |
val isReduced : rewrite -> bool
|
|
90 |
|
|
91 |
(* ------------------------------------------------------------------------- *)
|
|
92 |
(* Rewriting as a derived rule. *)
|
|
93 |
(* ------------------------------------------------------------------------- *)
|
|
94 |
|
|
95 |
val rewrite : equation list -> Thm.thm -> Thm.thm
|
|
96 |
|
|
97 |
val orderedRewrite : reductionOrder -> equation list -> Thm.thm -> Thm.thm
|
|
98 |
|
|
99 |
end
|