Dusa is datalog
Datalog-like languages use logical implication to express the sorts of problems that, in a language like SQL, you would solve with database joins. The simplest declarations in Dusa are just declaring facts, like who a character’s parent is.
parent "Arya" "Catelyn".parent "Arya" "Eddard".parent "Brandon" "Rickard".parent "Eddard" "Lyarra".parent "Eddard" "Rickard".parent "Rickard" "Edwyle".parent "Rickard" "Marna".parent "Sansa" "Catelyn".parent "Sansa" "Eddard".Logical implication
You can use these facts and logical implication to derive more facts, like “if X’s parent is Y, and Y’s parent is Z, then the grandparent of X is Z.” That looks like this:
grandparent X Z :- parent X Y, parent Y Z.The uppercase characters are variables. To conclude that Arya’s grandparent is
Lyarra, Dusa will use this rule with X assigned "Arya", Y assigned
"Eddard", and Z assigned "Lyarra".
It’s also easy to have inferences that build on themselves in a recursive fashion: an ancestor is either your parent or an ancestor of your parent. In Dusa, that looks like this:
ancestor X Y :- parent X Y.ancestor X Z :- parent X Y, ancestor Y Z.Using these rules, Dusa will calculate all of Arya’s ancestors: Catelyn, Eddard, Edwyle, Marna, and Rickard.
Relations and functions
The propositions in the previous section were all relations. Each of
parent, grandparent, and ancestor were relations between two characters.
In Dusa, it’s also possible to have propositions that are functions.
- Relations look like this:
prop t1 t2 ... tn-1 tn - Functions look like this:
prop t1 t2 ... tn-1 is tn(isis a keyword)
A function describes a unique key-value relationship. Familial relationships
don’t work like that: Arya has multiple parents and Eddard has multiple
children. But we could use weapon Char is W as a functional proposition to
describe a character’s favorite weapon, if each character can have at most one
favorite weapon.
weapon "Arya" is "smallsword".weapon "Eddard" is "greatsword".weapon "Sansa" is "bow".Functional propositions aren’t unique to Dusa, but they’re not too common in other Datalog-like languages. (One Datalog-like language that used functional propositions extensively was LogicBlox’s LogiQL language.)
Integrity constraints
Functional propositions create integrity constraints on the database of facts that Dusa maintains. If these constraints are violated by saying that multiple keys map to the same value, then the database is thrown out completely.
If we try to give Arya two favorite weapons, for instance, the database will be invalidated for violating an integrity constraint.
weapon "Arya" is "smallsword".weapon "Arya" is "greatsword".For a more subtle example, consider trying to make sibling a functional
proposition like this:
sibling A is B :- parent A P, parent B P, A != B.This will work initially, deriving that Arya and Sansa are siblings, as are Bran and Eddard. But if we then add a seemingly innocuous additional fact…
parent "Bran" "Eddard".…then Dusa will throw out the database in its entirety, reporting that there
are no solutions. By deriving both sibling "Arya" is "Sansa" and
sibling "Arya" is "Bran", the database fails an integrity constraint and is
completely invalidated.
The takeaway here is that we made a mistake: the sibling relationship should
be a relation, not a function.
Integrity constraints can also be added with the #forbid and #demand
directives. If we want to insist that no two characters have the same weapon,
we can write.
#forbid weapon Char1 is W, weapon Char2 is W, Char1 != Char2.Note that it’s necessary to say Char1 != Char2. If we left that out, Dusa
could match both Char1 and Char2 to "Arya" and therefore invalidate the
database for violating an integrity constraint.
A #demand predicate expresses something that must be true in order for the
database to be valid. This can be used like an assertion in programming,
invalidating the database if an expected fact doesn’t hold. If we want to make
sure we derive Marna as an ancestor of Arya, we can write this:
#demand ancestor "Arya" "Marna".