DeAL TutorialRecursion

Recursion Defined

Recursion is a form of predicate definition, using the predicate itself in the rule body.

Example: Derive all even numbers less than 98.

even(0).
even(Y) <- even(X), Y = X + 2,  Y < 98.

export even(X).

query even(X).
even(0)
even(2)
...
even(96)

Recursion: Bottom-Up Evaluation

even(0).
even(Y) <- even(X), Y = X + 2,  Y > 0.
export even(X).

would pass the safety test of the compiler, but it will start printing all integers in an infinite loop.

export even($X).

will also run in the same loop, although it might not print out anything.

Transitive Closure (.deal | .fac)

We have a database relation called parents:

parent(joe, jack).
parent(joe, jill).
parent(sam, jack).
parent(jack, mary).
parent(mary, lucy).

Example: Y is an ancestor of X if Y is a parent of X or if there exists a Z such that Z is a parent of X and Y is an ancestor of Z

ancestor(X, Y) <- parent(X, Y).
ancestor(X, Y) <- parent(X, Z), ancestor(Z, Y).

export ancestor(X, Y).
query ancestor(X, Y).
Recursion: Transitive Closure Evaluation

Step1: Start with the rule whose body is the base relation.

S1 = {ancestor(joe, jack), ancestor(joe, jill), ancestor(sam, jack), ancestor(jack, mary), ancestor(mary, lucy)}

Result = S1

Step2: Result is joined with parent. New tuples are pairs of nodes that can be reached along some path in 2 steps.

S2 = {ancestor(joe, mary), ancestor(sam, mary), ancestor(jack,lucy)}

Result = S1 ∪ S2

Step3: Result is joined again withparent. New tuples are pairs that are reachable along a path in 3 steps.

S3 = {ancestor(joe, jucy), ancestor(sam, lucy)}

Result = S1 ∪ S2 ∪ S3

No pairs can be reached along paths of more than 3 steps, and the computation terminates. We say that the computation has reached fixpoint.

Switching the rule order and the order of the goals within the rules will not change the result of this transitive closure.

Example: Bill of Materials (.deal | .fac)

Bill of materials (BOM) problems are related to assemblies containing superparts composed of subparts that are eventually composed of elementary parts. The assembly(Part, Subpart, Qty) predicate in the parts database contains parts, their immediate subpart, and the quantity with which they are used in the part. part_cost(BasicPart, Supplier, Cost, Time) contains the basic parts.

The following rule serves as a constraint and should be part of the specifications.

violation <- part_cost(BasicPart, _, _, _), assembly(BasicPart, _ , _).

That is, a part cannot be both a basic part and a superpart within this database.

For each part find all the subparts---not just the immediate subparts 
all_subparts(Part, Sub) <- assembly(Part, Sub, _).
all_subparts(Part, Sub2) <- all_subparts(Part, Sub1), assembly(Sub1, Sub2).
Safe query forms for this rule: 
export all_subparts($X, Y).
export all_subparts(X, $Y).
export all_subparts($X, $Y).
For each part, basic or otherwise, find all of the basic subparts, only

Let us think bottom-up for this.

% A basic part is a subpart of itself.

basic_sub_parts(BasicPart, BasicPart) <- part_cost(BasicPart, _ , _).
basic_sub_parts(Part1, Sub) <-
                   basic_sub_parts(Part, Sub), 
                   assembly(Part1, Part).
For each part, basic or otherwise, find all of the basic subparts, only

Let us think bottom-up for this.

% A basic part is a subpart of itself.

basic_sub_parts(BasicPart, BasicPart) <- part_cost(BasicPart, _ , _).
basic_sub_parts(Part1, Sub) <- basic_sub_parts(Part, Sub), assembly(Part1, Part).
Last Updated 2014