8000 better rule definition · Z80coder/datalog-cpp@5aa0b17 · GitHub
[go: up one dir, main page]
Skip to content

Commit 5aa0b17

Browse files
author
wright
committed
better rule definition
1 parent 9283e60 commit 5aa0b17

File tree

3 files changed

+76
-107
lines changed

3 files changed

+76
-107
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,2 @@
11
# mini-datalog
2-
naive implementation of datalog in C++
2+
implementation of datalog (without negation, and semi-naive bottom-up evaluation) in C++

‎src/Datalog.h

Lines changed: 45 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -128,11 +128,35 @@ static typename RELATION_TYPE::Ground ground(const tuple<Ts...> &atom)
128128
return groundAtom;
129129
}
130130

131+
template<typename RELATION_TYPE, typename ... Ts>
132+
struct AtomTypeSpecifier {
133+
typedef RELATION_TYPE RelationType;
134+
typedef tuple<Ts...> AtomType;
135+
AtomType atom;
136+
};
137+
131138
template <typename ... Ts>
132-
tuple<Ts...> atom(Ts&&... args) {
139+
static tuple<Ts...> atom(Ts&&... args) {
133140
return tuple<Ts...>{args...};
134141
}
135142

143+
template <typename RELATION_TYPE, typename ... Us>
144+
static AtomTypeSpecifier<RELATION_TYPE, Us...> atom(Us&&... args) {
145+
return AtomTypeSpecifier<RELATION_TYPE, Us...>{atom(args...)};
146+
}
147+
148+
#if 0
149+
template <typename RELATION_TYPE, typename ... Us>
150+
static AtomTypeSpecifier<RELATION_TYPE, Us...> head(Us&&... args) {
151+
return atom<RELATION_TYPE, Us...>(args...);
152+
}
153+
154+
template <typename RELATION_TYPE, typename ... Us>
155+
static AtomTypeSpecifier<RELATION_TYPE, Us...> clause(Us&&... args) {
156+
return atom<RELATION_TYPE, Us...>(args...);
157+
}
158+
#endif
159+
136160
template <typename... Ts>
137161
struct Relation
138162
{
@@ -150,16 +174,6 @@ struct Relation
150174

151175
typedef set<TrackedGround, compare> TrackedSet;
152176

153-
template <typename ... Us>
154-
static tuple<Us...> head(Us&&... args) {
155-
return atom(args...);
156-
}
157-
158-
template <typename ... Us>
159-
static tuple<Us...> clause(Us&&... args) {
160-
return atom(args...);
161-
}
162-
163177
};
164178

165179
template <typename HEAD_RELATION, typename... BODY_RELATIONs>
@@ -169,22 +183,28 @@ struct Rule
169183
typedef tuple<BODY_RELATIONs...> BodyRelations;
170184
typedef tuple<typename BODY_RELATIONs::TrackedSet::const_iterator...> BodyRelationsIteratorType;
171185
typedef tuple<const typename BODY_RELATIONs::TrackedGround *...> SliceType;
186+
};
172187

173-
template <typename HEAD_ATOM, typename... BODY_ATOMs>
174-
struct RuleInstance {
175-
typedef Rule<HEAD_RELATION, BODY_RELATIONs...> RuleType;
176-
typedef HEAD_ATOM HeadType;
177-
HeadType head;
178-
typedef tuple<BODY_ATOMs...> BodyType;
179-
BodyType body;
180-
};
181-
182-
template <typename HEAD_ATOM, typename... BODY_ATOMs>
183-
static RuleInstance<HEAD_ATOM, BODY_ATOMs...> rule(HEAD_ATOM&& head, BODY_ATOMs&&... body) {
184-
return RuleInstance<HEAD_ATOM, BODY_ATOMs...>{head, {body...}};
185-
}
188+
template <typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs>
189+
struct RuleInstance {
190+
typedef Rule<typename HEAD_ATOM_SPECIFIER::RelationType, typename BODY_ATOM_SPECIFIERs::RelationType...> RuleType;
191+
typedef typename HEAD_ATOM_SPECIFIER::AtomType HeadType;
192+
HeadType head;
193+
typedef tuple<typename BODY_ATOM_SPECIFIERs::AtomType...> BodyType;
194+
BodyType body;
186195
};
187196

197+
template <typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs>
198+
RuleInstance<HEAD_ATOM_SPECIFIER, BODY_ATOM_SPECIFIERs...> rule(
199+
const HEAD_ATOM_SPECIFIER& h,
200+
const BODY_ATOM_SPECIFIERs&... b
201+
) {
202+
typedef RuleInstance<HEAD_ATOM_SPECIFIER, BODY_ATOM_SPECIFIERs...> RuleInstanceType;
203+
typename RuleInstanceType::HeadType head{h.atom};
204+
typename RuleInstanceType::BodyType body{b.atom...};
205+
return RuleInstanceType{head, body};
206+
}
207+
188208
template <typename RELATION_TYPE>
189209
static ostream& operator<<(ostream& out, const typename RELATION_TYPE::Ground& t) {
190210
out << "[";
@@ -444,7 +464,6 @@ struct State
444464
return convert(tuple, make_index_sequence<tuple_size<TupleType>::value>{});
445465
}
446466

447-
448467
};
449468

450469
template <typename... RELATIONs>
@@ -473,6 +492,7 @@ static bool bindBodyAtomsToSlice(typename RULE_INSTANCE_TYPE::BodyType &atoms,
473492
// get the atom
474493
auto &atom = get<I>(atoms);
475494
// try to bind the atom with the fact
495+
//success = bind(fact.second, atom);
476496
success = bind(fact.second, atom);
477497
}
478498
return success;

‎tests/types_test.cpp

Lines changed: 30 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -34,10 +34,7 @@ bool test1()
3434

3535
// Rule
3636
auto x = var<Name>();
37-
auto rule1 = Rule<Mortal, Thing>::rule(
38-
Mortal::head(x),
39-
Thing::clause(x, person)
40-
);
37+
auto rule1 = rule(atom<Mortal>(x), atom<Thing>(x, person));
4138

4239
State<Thing, Mortal> state{things, {}};
4340

@@ -77,24 +74,16 @@ bool test2()
7774
{rod, alan},
7875
{robin, alan}};
7976

80-
auto x = var<Name>();
81-
auto y = var<Name>();
82-
auto z = var<Name>();
83-
84-
auto directAcademicAncestor = Rule<AcademicAncestor, Adviser>::rule(
85-
AcademicAncestor::head(x, y),
86-
Adviser::clause(x, y)
87-
);
88-
auto indirectAcademicAncestor = Rule<AcademicAncestor, Adviser, AcademicAncestor>::rule(
89-
AcademicAncestor::head(x, z),
90-
Adviser::clause(x, y),
91-
AcademicAncestor::clause(y, z)
92-
);
93-
auto query = Rule<QueryResult, AcademicAncestor, AcademicAncestor>::rule(
94-
QueryResult::head(x),
95-
AcademicAncestor::clause(robin, x),
96-
AcademicAncestor::clause(x, mistral)
97-
);
77+
auto x = new Variable<Name>();
78+
auto y = new Variable<Name>();
79+
auto z = new Variable<Name>();
80+
81+
// TODO
82+
//auto inDirectAcademicAncestor = atom<AcademicAncestor>(x, z) <= atom<Adviser>(x, y) && atom<AcademicAncestor>(y, z);
83+
84+
auto directAcademicAncestor = rule(atom<AcademicAncestor>(x, y), atom<Adviser>(x, y));
85+
auto indirectAcademicAncestor = rule(atom<AcademicAncestor>(x, z), atom<Adviser>(x, y), atom<AcademicAncestor>(y, z));
86+
auto query = rule(atom<QueryResult>(x), atom<AcademicAncestor>(robin, x), atom<AcademicAncestor>(x, mistral));
9887

9988
// Apply rules
10089
State<Adviser, AcademicAncestor, QueryResult> state{advisers, {}, {}};
@@ -138,84 +127,44 @@ bool po1()
138127
auto anon7 = var<Number>();
139128
auto anon8 = var<Number>();
140129

141-
typedef Rule<A, Check, In> P0RuleType;
142-
143130
// A(1,i) :- Check(_, b, c, d, e, f), In(_, b, c, d, e, f, i).
144-
auto rule1 = P0RuleType::rule(
145-
A::head(1u, i), Check::clause(anon1, b, c, d, e, f), In::clause(anon2, b, c, d, e, f, i)
146-
);
131+
auto rule1 = rule(atom<A>(1u, i), atom<Check>(anon1, b, c, d, e, f), atom<In>(anon2, b, c, d, e, f, i));
147132
// A(2,i) :- Check(a, _, c, d, e, f), In(a, _, c, d, e, f, i).
148-
auto rule2 = P0RuleType::rule(
149-
A::head(2u, i), Check::clause(a, anon1, c, d, e, f), In::clause(a, anon2, c, d, e, f, i)
150-
);
133+
auto rule2 = rule(atom<A>(2u, i), atom<Check>(a, anon1, c, d, e, f), atom<In>(a, anon2, c, d, e, f, i));
151134
// A(3,i) :- Check(a, b, _, d, e, f), In(a, b, _, d, e, f, i).
152-
auto rule3 = P0RuleType::rule(
153-
A::head(3u, i), Check::clause(a, b, anon1, d, e, f), In::clause(a, b, anon2, d, e, f, i)
154-
);
135+
auto rule3 = rule(atom<A>(3u, i), atom<Check>(a, b, anon1, d, e, f), atom<In>(a, b, anon2, d, e, f, i));
155136
// A(4,i) :- Check(a, b, c, _, e, f), In(a, b, c, _, e, f, i).
156-
auto rule4 = P0RuleType::rule(
157-
A::head(4u, i), Check::clause(a, b, c, anon1, e, f), In::clause(a, b, c, anon2, e, f, i)
158-
);
137+
auto rule4 = rule(atom<A>(4u, i), atom<Check>(a, b, c, anon1, e, f), atom<In>(a, b, c, anon2, e, f, i));
159138
// A(5,i) :- Check(a, b, c, d, _, f), In(a, b, c, d, _, f, i).
160-
auto rule5 = P0RuleType::rule(
161-
A::head(5u, i), Check::clause(a, b, c, d, anon1, f), In::clause(a, b, c, d, anon2, f, i)
162-
);
139+
auto rule5 = rule(atom<A>(5u, i), atom<Check>(a, b, c, d, anon1, f), atom<In>(a, b, c, d, anon2, f, i));
163140
// A(6,i) :- Check(a, b, c, d, e, _), In(a, b, c, d, e, _, i).
164-
auto rule6 = P0RuleType::rule(
165-
A::head(6u, i), Check::clause(a, b, c, d, e, anon1), In::clause(a, b, c, d, e, anon2, i)
166-
);
141+
auto rule6 = rule(atom<A>(6u, i), atom<Check>(a, b, c, d, e, anon1), atom<In>(a, b, c, d, e, anon2, i));
167142
// A(7, i) :- Check(_, _, c, d, e, f), In(_, _, c, d, e, f, i).
168-
auto rule7 = P0RuleType::rule(
169-
A::head(7u, i), Check::clause(anon1, anon2, c, d, e, f), In::clause(anon3, anon4, c, d, e, f, i)
170-
);
143+
auto rule7 = rule(atom<A>(7u, i), atom<Check>(anon1, anon2, c, d, e, f), atom<In>(anon3, anon4, c, d, e, f, i));
171144
// A(8, i) :- Check(a, _, _, d, e, f), In(a, _, _, d, e, f, i).
172-
auto rule8 = P0RuleType::rule(
173-
A::head(8u, i), Check::clause(a, anon1, anon2, d, e, f), In::clause(a, anon3, anon4, d, e, f, i)
174-
);
145+
auto rule8 = rule(atom<A>(8u, i), atom<Check>(a, anon1, anon2, d, e, f), atom<In>(a, anon3, anon4, d, e, f, i));
175146
// A(9, i) :- Check(a, b, _, _, e, f), In(a, b, _, _, e, f, i).
176-
auto rule9 = P0RuleType::rule(
177-
A::head(9u, i), Check::clause(a, b, anon1, anon2, e, f), In::clause(a, b, anon3, anon4, e, f, i)
178-
);
147+
auto rule9 = rule(atom<A>(9u, i), atom<Check>(a, b, anon1, anon2, e, f), atom<In>(a, b, anon3, anon4, e, f, i));
179148
// A(10, i) :- Check(a, b, c, _, _, f), In(a, b, c, _, _, f, i).
180-
auto rule10 = P0RuleType::rule(
181-
A::head(10u, i), Check::clause(a, b, c, anon1, anon2, f), In::clause(a, b, c, anon3, anon4, f, i)
182-
);
149+
auto rule10 = rule(atom<A>(10u, i), atom<Check>(a, b, c, anon1, anon2, f), atom<In>(a, b, c, anon3, anon4, f, i));
183150
// A(11, i) :- Check(a, b, c, d, _, _), In(a, b, c, d, _, _, i).
184-
auto rule11 = P0RuleType::rule(
185-
A::head(11u, i), Check::clause(a, b, c, d, anon1, anon2), In::clause(a, b, c, d, anon3, anon4, i)
186-
);
151+
auto rule11 = rule(atom<A>(11u, i), atom<Check>(a, b, c, d, anon1, anon2), atom<In>(a, b, c, d, anon3, anon4, i));
187152
// A(12, i) :- Check(_, _, _, d, e, f), In(_, _, _, d, e, f, i).
188-
auto rule12 = P0RuleType::rule(
189-
A::head(12u, i), Check::clause(anon1, anon2, anon3, d, e, f), In::clause(anon4, anon5, anon6, d, e, f, i)
190-
);
153+
auto rule12 = rule(atom<A>(12u, i), atom<Check>(anon1, anon2, anon3, d, e, f), atom<In>(anon4, anon5, anon6, d, e, f, i));
191154
// A(13, i) :- Check(a, _, _, _, e, f), In(a, _, _, _, e, f, i).
192-
auto rule13 = P0RuleType::rule(
193-
A::head(13u, i), Check::clause(a, anon1, anon2, anon3, e, f), In::clause(a, anon4, anon5, anon6, e, f, i)
194-
);
155+
auto rule13 = rule(atom<A>(13u, i), atom<Check>(a, anon1, anon2, anon3, e, f), atom<In>(a, anon4, anon5, anon6, e, f, i));
195156
// A(14, i) :- Check(a, b, _, _, _, f), In(a, b, _, _, _, f, i).
196-
auto rule14 = P0RuleType::rule(
197-
A::head(14u, i), Check::clause(a, b, anon1, anon2, anon3, f), In::clause(a, b, anon4, anon5, anon6, f, i)
198-
);
157+
auto rule14 = rule(atom<A>(14u, i), atom<Check>(a, b, anon1, anon2, anon3, f), atom<In>(a, b, anon4, anon5, anon6, f, i));
199158
// A(15, i) :- Check(a, b, c, _, _, _), In(a, b, c, _, _, _, i).
200-
auto rule15 = P0RuleType::rule(
201-
A::head(15u, i), Check::clause(a, b, c, anon1, anon2, anon3), In::clause(a, b, c, anon4, anon5, anon6, i)
202-
);
159+
auto rule15 = rule(atom<A>(15u, i), atom<Check>(a, b, c, anon1, anon2, anon3), atom<In>(a, b, c, anon4, anon5, anon6, i));
203160
// A(16, i) :- Check(_, _, _, _, e, f), In(_, _, _, _, e, f, i).
204-
auto rule16 = P0RuleType::rule(
205-
A::head(16u, i), Check::clause(anon1, anon2, anon3, anon4, e, f), In::clause(anon5, anon6, anon7, anon8, e, f, i)
206-
);
161+
auto rule16 = rule(atom<A>(16u, i), atom<Check>(anon1, anon2, anon3, anon4, e, f), atom<In>(anon5, anon6, anon7, anon8, e, f, i));
207162
// A(17, i) :- Check(a, _, _, _, _, f), In(a, _, _, _, _, f, i).
208-
auto rule17 = P0RuleType::rule(
209-
A::head(17u, i), Check::clause(a, anon1, anon2, anon3, anon4, f), In::clause(a, anon5, anon6, anon7, anon8, f, i)
210-
);
163+
auto rule17 = rule(atom<A>(17u, i), atom<Check>(a, anon1, anon2, anon3, anon4, f), atom<In>(a, anon5, anon6, anon7, anon8, f, i));
211164
// A(18, i) :- Check(a, b, _, _, _, _), In(a, b, _, _, _, _, i).
212-
auto rule18 = P0RuleType::rule(
213-
A::head(18u, i), Check::clause(a, b, anon1, anon2, anon3, anon4), In::clause(a, b, anon5, anon6, anon7, anon8, i)
214-
);
165+
auto rule18 = rule(atom<A>(18u, i), atom<Check>(a, b, anon1, anon2, anon3, anon4), atom<In>(a, b, anon5, anon6, anon7, anon8, i));
215166
// A(19, i) :- Check(a, b, c, d, e, f), In(a, b, c, d, e, f, i).
216-
auto rule19 = P0RuleType::rule(
217-
A::head(19u, i), Check::clause(a, b, c, d, e, f), In::clause(a, b, c, d, e, f, i)
218-
);
167+
auto rule19 = rule(atom<A>(19u, i), atom<Check>(a, b, c, d, e, f), atom<In>(a, b, c, d, e, f, i));
219168

220169
RuleSet<decltype(rule1), decltype(rule2), decltype(rule3), decltype(rule4), decltype(rule5), decltype(rule6), decltype(rule7), decltype(rule8), decltype(rule9), decltype(rule10), decltype(rule11), decltype(rule12), decltype(rule13), decltype(rule14), decltype(rule15), decltype(rule16), decltype(rule17), decltype(rule18), decltype(rule19)>
221170
rules{

0 commit comments

Comments
 (0)
0