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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
/********************* */
/*! \file theory_uf_rewriter.h
** \verbatim
** Original author: Dejan Jovanovic
** Major contributors: Morgan Deters
** Minor contributors (to current version): none
** This file is part of the CVC4 project.
** Copyright (c) 2009-2013 New York University and The University of Iowa
** See the file COPYING in the top-level source directory for licensing
** information.\endverbatim
**
** \brief [[ Add one-line brief description here ]]
**
** [[ Add lengthier description here ]]
** \todo document this file
**/
#include "cvc4_private.h"
#ifndef __CVC4__THEORY__UF__THEORY_UF_REWRITER_H
#define __CVC4__THEORY__UF__THEORY_UF_REWRITER_H
#include "theory/rewriter.h"
#include "theory/substitutions.h"
namespace CVC4 {
namespace theory {
namespace uf {
class TheoryUfRewriter {
public:
static RewriteResponse postRewrite(TNode node) {
if(node.getKind() == kind::EQUAL || node.getKind() == kind::IFF) {
if(node[0] == node[1]) {
return RewriteResponse(REWRITE_DONE, NodeManager::currentNM()->mkConst(true));
} else if(node[0].isConst() && node[1].isConst()) {
// uninterpreted constants are all distinct
return RewriteResponse(REWRITE_DONE, NodeManager::currentNM()->mkConst(false));
}
if (node[0] > node[1]) {
Node newNode = NodeManager::currentNM()->mkNode(node.getKind(), node[1], node[0]);
return RewriteResponse(REWRITE_DONE, newNode);
}
}
if(node.getKind() == kind::APPLY_UF && node.getOperator().getKind() == kind::LAMBDA) {
// resolve away the lambda
context::Context fakeContext;
theory::SubstitutionMap substitutions(&fakeContext);
TNode lambda = node.getOperator();
for(TNode::iterator formal = lambda[0].begin(), arg = node.begin(); formal != lambda[0].end(); ++formal, ++arg) {
// typechecking should ensure that the APPLY_UF is well-typed, correct arity, etc.
Assert(formal != node.end());
// This rewrite step is important: if we have (f (f 5)) for
// some lambda term f, we want to beta-reduce the inside (f 5)
// application first. Otherwise, we can end up in infinite
// recursion, because f's formal (say "x") gives the
// substitution "x |-> (f 5)". Fine, the body of the lambda
// gets (f 5) in place for x. But since the same lambda ("f")
// now occurs in the body, it's got the same bound var "x", so
// substitution continues and we replace that x by (f 5). And
// then again. :-(
//
// We need a better solution for distinguishing bound
// variables like this, but for now, handle it by going
// inside-out. (Quantifiers shouldn't ever have this problem,
// so long as the bound vars in different quantifiers are kept
// different.)
Node n = Rewriter::rewrite(*arg);
substitutions.addSubstitution(*formal, n);
}
return RewriteResponse(REWRITE_DONE, substitutions.apply(lambda[1]));
}
return RewriteResponse(REWRITE_DONE, node);
}
static RewriteResponse preRewrite(TNode node) {
if(node.getKind() == kind::EQUAL || node.getKind() == kind::IFF) {
if(node[0] == node[1]) {
return RewriteResponse(REWRITE_DONE, NodeManager::currentNM()->mkConst(true));
} else if(node[0].isConst() && node[1].isConst()) {
// uninterpreted constants are all distinct
return RewriteResponse(REWRITE_DONE, NodeManager::currentNM()->mkConst(false));
}
}
if(node.getKind() == kind::APPLY_UF && node.getOperator().getKind() == kind::LAMBDA) {
// resolve away the lambda
context::Context fakeContext;
theory::SubstitutionMap substitutions(&fakeContext);
TNode lambda = node.getOperator();
for(TNode::iterator formal = lambda[0].begin(), arg = node.begin(); formal != lambda[0].end(); ++formal, ++arg) {
// typechecking should ensure that the APPLY_UF is well-typed, correct arity, etc.
Assert(formal != node.end());
// This rewrite step is important: see note in postRewrite().
Node n = Rewriter::rewrite(*arg);
substitutions.addSubstitution(*formal, n);
}
return RewriteResponse(REWRITE_DONE, substitutions.apply(lambda[1]));
}
return RewriteResponse(REWRITE_DONE, node);
}
static inline void init() {}
static inline void shutdown() {}
};/* class TheoryUfRewriter */
}/* CVC4::theory::uf namespace */
}/* CVC4::theory namespace */
}/* CVC4 namespace */
#endif /* __CVC4__THEORY__UF__THEORY_UF_REWRITER_H */
|
