8000 simplify · Z80coder/datalog-cpp@be33591 · GitHub
[go: up one dir, main page]
Skip to content

Commit be33591

Browse files
author
wright
committed
simplify
1 parent 5bd7111 commit be33591

File tree

2 files changed

+242
-142
lines changed

2 files changed

+242
-142
lines changed

‎src/Datalog.h

Lines changed: 174 additions & 105 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,8 @@
66
#include <variant>
77
#include <vector>
88
#include <map>
9+
#include <memory>
10+
#include <optional>
911
#include <limits>
1012
#include <cassert>
1113
#include <iostream>
@@ -14,119 +16,195 @@ namespace datalog {
1416

1517
using namespace std;
1618

17-
struct Symbol {
18-
string name;
19-
};
20-
2119
template<typename T>
22-
struct SymbolOrValue {
20+
struct Symbol : optional<T> {
2321

24-
SymbolOrValue() :
25-
isSymbol(false), symbol(Symbol { "" }) {
22+
void bind(const T& value) {
23+
this->emplace(value);
2624
}
2725

28-
SymbolOrValue(const T& value) :
29-
isSymbol(false), symbol(Symbol { "" }), value(value) {
26+
void unbind() {
27+
this->reset();
3028
}
3129

32-
SymbolOrValue(const Symbol& symbol) :
33-
isSymbol(true), symbol(symbol), value() {
30+
bool isBound() const {
31+
return this->has_value();
3432
}
3533

36-
SymbolOrValue(const SymbolOrValue& other) :
37-
isSymbol(other.isSymbol), symbol(other.symbol), value(other.value) {
34+
const T& value() const {
35+
return this->optional<T>::value();
3836
}
37+
};
3938

40-
bool isSym() const {
41-
return this->isSymbol;
42-
}
39+
template<typename T>
40+
struct SymbolOrValue : public variant<T, shared_ptr<Symbol<T>>> {
4341

44-
const Symbol& getSym() const {
45-
return this->symbol;
46-
}
42+
typedef shared_ptr<Symbol<T>> SymbolType;
4743

48-
const T& getVal() const {
49-
assert(!isSymbol);
50-
return value;
51-
}
52-
53-
void bindVal(const T& value) {
54-
this->value = value;
44+
bool isSym() const {
45+
return holds_alternative<SymbolType>(*this);
5546
}
5647

57-
bool operator <(const SymbolOrValue &other) const {
58-
return value < other.value;
48+
const shared_ptr<Symbol<T>>& getSym() const {
49+
return get<SymbolType>(*this);
5950
}
6051

61-
SymbolOrValue& operator =(const SymbolOrValue &other) {
62-
this->isSymbol = other.isSymbol;
63-
this->symbol = other.symbol;
64-
this->value = other.value;
65-
return *this;
52+
const T& getVal() const {
53+
return get<T>(*this);
6654
}
67-
68-
private:
69-
bool isSymbol;
70-
Symbol symbol;
71-
T value;
7255
};
7356

7457
template<typename ... Ts>
75-
struct RelationType {
58+
struct Relation {
7659
typedef tuple<Ts...> GroundType;
7760
typedef tuple<SymbolOrValue<Ts> ...> AtomicType;
78-
};
79-
80-
template<typename RELATION_TYPE>
81-
struct Relation {
82-
typedef typename RELATION_TYPE::GroundType GroundType;
8361
Relation(const set<GroundType>& tuples) :
8462
tuples(tuples) {
8563
}
8664
const set<GroundType> tuples;
8765
};
8866

67+
template<typename HEAD_RELATION, typename ... BODY_RELATIONs>
68+
struct Rule {
69+
const typename HEAD_RELATION::AtomicType head;
70+
const tuple<typename BODY_RELATIONs::AtomicType...> body;
71+
};
72+
73+
template<typename RELATION_TYPE, size_t ... Is>
74+
static void unbind(const typename RELATION_TYPE::AtomicType& tuple, index_sequence<Is...>) {
75+
((get<Is>(tuple).getSym()->unbind()), ...);
76+
}
77+
8978
template<typename RELATION_TYPE>
90-
struct Atom {
91-
typedef typename RELATION_TYPE::AtomicType AtomicType;
92-
Atom(const AtomicType& tuple) :
93-
tuple { tuple } {
94-
#if 0
95-
unsigned int index = 0;
96-
apply([this, &index](auto&&... args) {
97-
((args.isSym() ? declareSym(args, index++, symIndexMap) : noOp(index++)), ...);}, tuple);
98-
#endif
79+
static void unbind(const typename RELATION_TYPE::AtomicType& tuple) {
80+
auto indexSequence = make_index_sequence<tuple_size<typename RELATION_TYPE::AtomicType>::value> { };
81+
unbind<RELATION_TYPE>(tuple, indexSequence);
82+
}
83+
84+
// bind 1 SymbolOrValue with 1 Value
85+
template<unsigned int I, typename VALUE_TYPE>
86+
bool bind(SymbolOrValue<VALUE_TYPE>& s, const VALUE_TYPE& v) {
87+
if (s.isSym()) {
88+
Symbol<VALUE_TYPE>& symbol = *s.getSym().get();
89+
// has the symbol already been bound?
90+
if (symbol.isBound()) {
91+
// is it a consistent binding?
92+
if (!(symbol.value() == v)) {
93+
return false;
94+
}
95+
}
96+
symbol.bind(v);
97+
cout << "bound " << s.getSym() << " to " << v << endl;
9998
}
100-
const AtomicType tuple;
99+
return true;
100+
}
101+
102+
template<typename RELATION_TYPE, size_t ... Is>
103+
static optional<typename RELATION_TYPE::AtomicType> bind(
104+
const typename RELATION_TYPE::AtomicType& atom,
105+
const typename RELATION_TYPE::GroundType& fact,
106+
index_sequence<Is...>
107+
) {
108+
typename RELATION_TYPE::AtomicType boundAtom { atom };
109+
unbind<RELATION_TYPE>(boundAtom);
110+
bool successfulBinding = ((bind<Is>(get<Is>(boundAtom), get<Is>(fact))) and ...);
111+
if (successfulBinding) {
112+
return boundAtom;
113+
}
114+
return nullopt;
115+
}
116+
117+
// bind 1 atom with 1 fact
118+
template<typename RELATION_TYPE>
119+
static optional<typename RELATION_TYPE::AtomicType> bind< 10000 /span>(
120+
const typename RELATION_TYPE::AtomicType& atom,
121+
const typename RELATION_TYPE::GroundType& fact
122+
) {
123+
auto indexSequence = make_index_sequence<tuple_size<typename RELATION_TYPE::GroundType>::value> { };
124+
return bind<RELATION_TYPE>(atom, fact, indexSequence);
125+
}
126+
127+
// bind 1 atom with a relation (n facts)
101128
#if 0
102-
typedef map<string, set<unsigned int>> SymIndexMapType;
103-
SymIndexMapType symIndexMap;
104-
private:
105-
template<typename T>
106-
static void declareSym(const T& t, unsigned int index, SymIndexMapType& symIndexMap) {
107-
auto symbolName = t.getSym().name;
108-
if (symIndexMap.count(symbolName) == 0) {
109-
symIndexMap.insert( { symbolName, { } });
129+
template<typename RELATION_TYPE>
130+
static Relation<RELATION_TYPE> bind(const Atom<RELATION_TYPE>& atom, const Relation<RELATION_TYPE>& relation) {
131+
set<typename Relation<RELATION_TYPE>::GroundType> outputTuples;
132+
for (const auto& fact : relation.tuples) {
133+
const auto& boundAtom = bind(atom, fact);
134+
if (boundAtom.has_value()) {
135+
// outputTuples.insert(boundAtom.value());
110136
}
111-
auto it = symIndexMap.find(symbolName);
112-
it->second.insert(index);
113137
}
114-
static void noOp(unsigned int index) {
138+
return Relation<RELATION_TYPE>{outputTuples};
139+
}
140+
#else
141+
142+
#if 0
143+
template<typename RELATION_TYPE>
144+
static Relation<RELATION_TYPE> bind(const typename RELATION_TYPE::AtomicType& atom, const Relation<RELATION_TYPE>& relation) {
145+
set<typename Relation<RELATION_TYPE>::GroundType> outputTuples;
146+
for (const auto& fact : relation.tuples) {
147+
// const auto& boundAtom = bind(atom, fact);
148+
// if (boundAtom.has_value()) {
149+
// outputTuples.insert(boundAtom.value());
150+
// }
115151
}
152+
return Relation<RELATION_TYPE>{outputTuples};
153+
}
116154
#endif
117-
};
118155

119-
template<typename ... ATOMs>
120-
struct Body {
121-
typedef variant<ATOMs...> AtomsType;
122-
const vector<AtomsType> atoms;
123-
};
156+
#endif
124157

125-
template<typename HEAD_RELATION, typename ... BODY_RELATIONs>
126-
struct Rule {
127-
const Atom<HEAD_RELATION> head;
128-
const Body<Atom<BODY_RELATIONs> ...> body;
129-
};
158+
template<typename RELATION_TYPE>
159+
static RELATION_TYPE merge(const RELATION_TYPE& r1, const RELATION_TYPE& r2) {
160+
set<typename RELATION_TYPE::GroundType> tuples { r1.tuples };
161+
tuples.insert(r2.tuples.begin(), r2.tuples.end());
162+
return RELATION_TYPE { tuples };
163+
}
164+
165+
}
166+
167+
#endif /* SRC_DATALOG_H_ */
168+
169+
#if 0
170+
// bind 1 SymbolOrValue with 1 Value
171+
template<unsigned int I, typename VALUE_TYPE, typename VARIANT_TYPE>
172+
bool bind(SymbolOrValue<VALUE_TYPE>& s, const VALUE_TYPE& v, map<string, VARIANT_TYPE>& bindings) {
173+
if (s.isSym()) {
174+
const auto& symbolName = s.getSym().name;
175+
// Has this symbol already been bound?
176+
if (bindings.count(symbolName) > 0) {
177+
// Is this a consistent binding?
178+
#if 0
179+
const auto& boundVariant = bindings.at(symbolName);
180+
const auto& boundVariantIndex = boundVariant.index();
181+
const auto& boundValue = get<boundVariantIndex>(boundVariant);
182+
if (!(boundValue == v)) {
183+
return false;
184+
}
185+
#endif
186+
}
187+
s.bindVal(v);
188+
VARIANT_TYPE vt(in_place_index_t<I> { }, v);
189+
cout << "Recording binding at index " << I << endl;
190+
bindings.insert( { symbolName, vt });
191+
cout << "Bound " << s.getSym().name << " to " << v << endl;
192+
}
193+
return true;
194+
}
195+
196+
// bind 1 atom with 1 fact
197+
template<typename RELATION_TYPE, size_t ... Is>
198+
static optional<Atom<RELATION_TYPE>> bind(const Atom<RELATION_TYPE>& atom, const typename RELATION_TYPE::GroundType& fact, index_sequence<Is...>) {
199+
typename RELATION_TYPE::AtomicType boundAtom { atom.tuple };
200+
map<string, typename RELATION_TYPE::VariantType> bindings;
201+
bool successfulBinding = ((bind<Is>(get<Is>(boundAtom), get<Is>(fact), bindings)) and ...);
202+
if (successfulBinding) {
203+
return Atom<RELATION_TYPE> { boundAtom };
204+
}
205+
return nullopt;
206+
}
207+
#endif
130208

131209
#if 0
132210
typedef map<string, set<unsigned int>> SymBindingsType;
@@ -140,27 +218,29 @@ static void noOp() {
140218
#endif
141219

142220
#if 0
143-
template<typename RELATION_TYPE>
144-
constexpr typename RELATION_TYPE::AtomicType bind(const typename RELATION_TYPE::AtomicType& atom, const typename RELATION_TYPE::GroundType& fact, size_t i) {
145-
typename RELATION_TYPE::AtomicType boundAtom{atom};
146-
if (get<i>(atom)) {
221+
unsigned int index = 0;
222+
apply([this, &index](auto&&... args) {
223+
((args.isSym() ? declareSym(args, index++, symIndexMap) : noOp(index++)), ...);}, tuple);
224+
#endif
147225

226+
#if 0
227+
typedef map<string, set<unsigned int>> SymIndexMapType;
228+
SymIndexMapType symIndexMap;
229+
private:
230+
template<typename T>
231+
static void declareSym(const T& t, unsigned int index, SymIndexMapType& symIndexMap) {
232+
auto symbolName = t.getSym().name;
233+
if (symIndexMap.count(symbolName) == 0) {
234+
symIndexMap.insert( { symbolName, { } });
235+
}
236+
auto it = symIndexMap.find(symbolName);
237+
it->second.insert(index);
148238
}
149-
return boundAtom;
150-
}
151-
152-
// bind 1 atom with 1 fact
153-
template<typename RELATION_TYPE, size_t ... Is>
154-
static Atom<RELATION_TYPE> bind(const Atom<RELATION_TYPE>& atom, const typename RELATION_TYPE::GroundType& fact, index_sequence<Is...>) {
155-
typename RELATION_TYPE::AtomicType boundAtom { atom.tuple };
156-
157-
((boundAtom = bind<RELATION_TYPE>(boundAtom, fact, Is)), ...);
158-
//((boundAtom = bind<RELATION_TYPE>(boundAtom, fact, Is)), ...);
159-
//apply([&boundAtom](auto&&... element) {
160-
// ((atomicElement.isSym() ? bind(atomicElement, symBindings) : noOp()), ...);}, fact);
239+
static void noOp(unsigned int index) {
240+
}
241+
#endif
161242

162-
return Atom<RELATION_TYPE> { boundAtom };
163-
}
243+
#if 0
164244

165245
template<typename RELATION_TYPE>
166246
static Relation<RELATION_TYPE> bind(const Atom<RELATION_TYPE>& atom, const Relation<RELATION_TYPE>& relation) {
@@ -173,14 +253,3 @@ static Relation<RELATION_TYPE> bind(const Atom<RELATION_TYPE>& atom, const Relat
173253
return boundAtoms;
174254
}
175255
#endif
176-
177-
template<typename RELATION_TYPE>
178-
static RELATION_TYPE merge(const RELATION_TYPE& r1, const RELATION_TYPE& r2) {
179-
set<typename RELATION_TYPE::GroundType> tuples { r1.tuples };
180-
tuples.insert(r2.tuples.begin(), r2.tuples.end());
181-
return RELATION_TYPE { tuples };
182-
}
183-
184-
}
185-
186-
#endif /* SRC_DATALOG_H_ */

0 commit comments

Comments
 (0)
0