8000 derived new facts from applying a rule · Z80coder/datalog-cpp@064808f · GitHub
[go: up one dir, main page]
Skip to content

Commit 064808f

Browse files
author
wright
committed
derived new facts from applying a rule
1 parent 89cb8d1 commit 064808f

File tree

3 files changed

+61
-69
lines changed

3 files changed

+61
-69
lines changed

‎Makefile‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,8 +6,8 @@ SRCS := ${SRCS} $(wildcard tests/*.cpp)
66
TARGETS := $(TARGETS) $(SRCS:.cpp=)
77

88
# set the build configuration set
9-
BUILD := release
10-
#BUILD := debug
9+
#BUILD := release
10+
BUILD := debug
1111
BIT := 64
1212
#BIT := 32
1313

‎src/Datalog.h‎

Lines changed: 56 additions & 65 deletions
E18F
Original file line numberDiff line numberDiff line change
@@ -20,8 +20,6 @@ using namespace std;
2020
template <typename T>
2121
struct Symbol : optional<T>
2222
{
23-
//typedef shared_ptr<Symbol> Type;
24-
2523
void bind(const T &value)
2624
{
2725
this->emplace(value);
@@ -148,7 +146,7 @@ static void unbind(const tuple<SymbolOrValue<Ts>...> &tuple)
148146
}
149147

150148
// bind 1 SymbolOrValue with 1 Value
151-
template <unsigned int I, typename VALUE_TYPE>
149+
template <typename VALUE_TYPE>
152150
bool bind(SymbolOrValue<VALUE_TYPE> &s, const VALUE_TYPE &v)
153151
{
154152
if (s.isSym())
@@ -171,7 +169,7 @@ bool bind(SymbolOrValue<VALUE_TYPE> &s, const VALUE_TYPE &v)
171169
template <typename ATOM_TYPE, typename GROUND_TYPE, size_t... Is>
172170
static bool bind(ATOM_TYPE &atom, const GROUND_TYPE &fact, index_sequence<Is...>)
173171
{
174-
bool success = ((bind<Is>(get<Is>(atom), get<Is>(fact))) and ...);
172+
bool success = ((bind(get<Is>(atom), get<Is>(fact))) and ...);
175173
if (success)
176174
{
177175
{
@@ -234,6 +232,7 @@ template <typename HEAD_RELATION, typename... BODY_RELATIONs>
234232
struct Rule
235233
{
236234
typedef Rule Define;
235+
typedef HEAD_RELATION HeadRelationType;
237236
typedef typename HEAD_RELATION::Atom HeadType;
238237
HeadType head;
239238
typedef tuple<BODY_RELATIONs...> BodyRelations;
@@ -417,24 +416,28 @@ static bool bind(typename RELATION_TYPE::Atom &atom,
417416
#endif
418417

419418
template <size_t I, typename RULE_TYPE, typename... RELATIONs>
420-
static void bind(typename RULE_TYPE::BodyType &atoms, // typedef tuple<typename BODY_RELATIONs::Atom...> BodyType;
419+
static bool bind(typename RULE_TYPE::BodyType &atoms, // typedef tuple<typename BODY_RELATIONs::Atom...> BodyType;
421420
const tuple<RELATIONs const *...> &slice)
422421
{
423422
// get the fact in the slice that can potentially bind
424423
typedef typename tuple_element<I, typename RULE_TYPE::BodyRelations>::type BodyRelationI;
425424
auto factPtr = get<BodyRelationI const *>(slice);
426-
const BodyRelationI& fact = *factPtr;
427-
// get the atom
428-
typename BodyRelationI::Atom &atom = get<I>(atoms);
429-
// try to bind the atom with the fact
430-
bind(atom, fact);
425+
bool success = false;
426+
if (factPtr) {
427+
const BodyRelationI& fact = *factPtr;
428+
// get the atom
429+
typename BodyRelationI::Atom &atom = get<I>(atoms);
430+
// try to bind the atom with the fact
431+
success = bind(atom, fact);
432+
}
433+
return success;
431434
}
432435

433436
template <typename RULE_TYPE, typename... RELATIONs, size_t... Is>
434-
static void bind(typename RULE_TYPE::BodyType &atoms,
437+
static bool bind(typename RULE_TYPE::BodyType &atoms,
435438
const tuple<RELATIONs const *...> &slice, index_sequence<Is...>)
436439
{
437-
((bind<Is, RULE_TYPE, RELATIONs...>(atoms, slice)), ...);
440+
return ((bind<Is, RULE_TYPE, RELATIONs...>(atoms, slice)) and ...);
438441
}
439442

440443
// bind n atoms (of multiple relation types) with 1 slice (of multiple relation types)
@@ -445,73 +448,61 @@ static bool bind(typename RULE_TYPE::BodyType &atoms,
445448
// unbind all the symbols
446449
unbind<RULE_TYPE>(atoms);
447450
// for each atom, bind with corresponding relation type in slice
448-
bind<RULE_TYPE, RELATIONs...>(atoms, slice,
451+
return bind<RULE_TYPE, RELATIONs...>(atoms, slice,
449452
make_index_sequence<tuple_size<typename RULE_TYPE::BodyType>::value>{});
450-
return false;
451453
}
452454

453-
// apply a rule to state
454-
template <typename RULE_TYPE, typename... RELATIONs>
455-
static void apply(RULE_TYPE &rule, const State<RELATIONs...> &state)
455+
template <typename VALUE_TYPE>
456+
void ground(const SymbolOrValue<VALUE_TYPE> &s, VALUE_TYPE &v)
456457
{
457-
auto it = state.iterator();
458-
while (it.hasNext())
458+
if (s.isSym())
459459
{
460-
auto slice = it.next();
461-
// slice is type typedef tuple<typename RELATIONs::GroundType const* ...> SliceType;
462-
/*bool success = */ bind<RULE_TYPE, RELATIONs...>(rule.body, slice);
460+
Symbol<VALUE_TYPE> &symbol = *s.getSym();
461+
assert(symbol.isBound());
462+
v = symbol.value();
463+
} else {
464+
v = s.getVal();
463465
}
464466
}
465467

466-
#if 0
467-
template<typename RELATION_TYPE>
468-
static bool apply(
469-
const typename RELATION_TYPE::AtomicType& atom,
470-
const RELATION_TYPE& relation)
471-
{
472-
// we have the atom, and some corresponding facts, now bind them
473-
// but we don't want the ground atoms
474-
// we want the bound atoms
475-
476-
// to avoid copying symbols we should try and find a complete binding across all relations,
477-
// and then move to next complete binding etc.
478-
479-
// so basically we want to stream all the combinations of facts, where each combination
480-
// consists of selecting 1 fact from each relation in the state
481-
return true;
468+
template <typename RELATION_TYPE, size_t... Is>
469+
static void ground(const typename RELATION_TYPE::Atom& atom, RELATION_TYPE& groundAtom, index_sequence<Is...>) {
470+
((ground(get<Is>(atom), get<Is>(groundAtom))), ...);
482471
}
483472

484-
template<typename RULE_TYPE, typename ... RELATIONs, size_t ... Is>
485-
static void apply(
486-
const typename RULE_TYPE::BodyType& body,
487-
const typename State<RELATIONs...>::RelationsType& relations,
488-
index_sequence<Is...>
489-
)
490-
{
491-
/*
492-
* Bind n atoms (of different relation types, such as the body of a rule)
493-
* with state consisting of
494-
* n_{i} facts (of different relation types i = 1 ... m)
495-
*/
496-
// for each atom in body find and bind with corresponding relation
497-
bool success = ((
498-
apply<typename tuple_element<Is, typename State<RELATIONs...>::RelationsType>::type>(
499-
get<Is>(body),
500-
get<typename tuple_element<Is, typename State<RELATIONs...>::RelationsType>::type>(relations)
501-
)) and ...);
473+
template <typename RELATION_TYPE>
474+
static RELATION_TYPE ground(const typename RELATION_TYPE::Atom& atom) {
475+
RELATION_TYPE groundAtom;
476+
ground<RELATION_TYPE>(atom, groundAtom, make_index_sequence<tuple_size<typename RELATION_TYPE::Atom>::value>{});
477+
return groundAtom;
502478
}
503479

504-
// bind a rule body to a tuple of relations
505-
template<typename RULE_TYPE, typename ... RELATIONs>
506-
static void apply(
507-
const typename RULE_TYPE::BodyType& body,
508-
const typename State<RELATIONs...>::RelationsType& relations
509-
)
480+
// apply a rule to state
481+
template <typename RULE_TYPE, typename... RELATIONs>
482+
static typename RULE_TYPE::HeadRelationType::Set apply(RULE_TYPE &rule, const State<RELATIONs...> &state)
510483
{
511-
apply<RULE_TYPE, RELATIONs...>(body, relations, make_index_sequence<tuple_size<typename RULE_TYPE::BodyType>::value>
512-
{});
484+
typedef typename RULE_TYPE::HeadRelationType HeadRelationType;
485+
typename HeadRelationType::Set derivedFacts;
486+
auto it = state.iterator();
487+
while (it.hasNext())
488+
{
489+
auto slice = it.next();
490+
if (bind<RULE_TYPE, RELATIONs...>(rule.body, slice)) {
491+
// successful bind, therefore add (grounded) head atom to new state
492+
cout << "successful bind of body" << endl;
493+
auto derivedFact = ground<HeadRelationType>(rule.head);
494+
{
495+
cout << "adding: ";
496+
datalog::print<typename HeadRelationType::TupleType>(cout, derivedFact); // TODO: avoid need for type
497+
cout << endl;
498+
}
499+
derivedFacts.insert(derivedFact);
500+
} else {
501+
cout << "failed to bind body" << endl;
502+
}
503+
}
504+
return derivedFacts;
513505
}
514-
#endif
515506

516507
#if 0
517508
template<typename RELATION_TYPE>

‎tests/types_test.cpp‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -125,7 +125,7 @@ int main()
125125
{
126126
cout << "successful bind" << endl;
127127
}
128-
else
128+
else
129129
{
130130
cout << "failed bind" << endl;
131131
}
@@ -153,6 +153,7 @@ int main()
153153
it2.next();
154154
}
155155

156-
apply<Rule2Type>(rule2, state1);
156+
auto derivedFacts1 = apply<Rule2Type>(rule2, state1);
157+
auto derivedFacts2 = apply<decltype(rule1)>(rule1, state1);
157158
}
158159
}

0 commit comments

Comments
 (0)
0