1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
<html>
<head><title>A_Sketch_of_How_the_Rewriter_Works.html -- ACL2 Version 3.1</title></head>
<body text=#000000 bgcolor="#FFFFFF">
<h2>A Sketch of How the Rewriter Works</h2>
<p>
Below we show the first target term, extracted from the
current conjecture. Below it we show the associativity rule.<p>
<img src=uaa-rewrite.gif><p>
The variables of the rewrite rule are <b>instantiated</B> so that the
<b>left-hand side</B> of the rule matches the target:<p>
<pre>
variable term from target
a x1
b x2
c (app x3 x4)
</pre>
<p>
Then the target is <b>replaced</B> by the instantiated <b>right-hand side</B>
of the rule.<p>
Sometimes rules have <b>hypotheses</B>. To make a long story short,
if the rule has hypotheses, then after matching the left-hand side,
the rewriter instantiates the hypotheses and rewrites them recursively.
This is called <b>backchaining</B>. If they all rewrite to true, then
the target is replaced as above.<p>
For more details on how the ACL2 rewriter works, see Boyer and Moore's
book <b>A Computational Logic</B>, Academic Press, 1979.
<br><br><br><a href="acl2-doc.html"><img src="llogo.gif"></a> <a href="acl2-doc-index.html"><img src="index.gif"></a>
</body>
</html>
|
