DeAL TutorialTop-Down Execution

Top-Down Execution of Programs (.deal | .fac)

In a bottom-up execution the goals of a rule rj are computed before the head of rj, and the results just obtained in the head are then used to compute the goals of other rules. A top-down execution occurs when values of some of the variables in the head are computed first, and their values are used in the computation of the goals. For instance:

%A DB of flat parts described by their geometric shape and weight.
%Different geometric shapes require a different number of
%parameters. Also actualkg is the actual weight of the
%part, but unitkg is the specific weight where the actual
%weight can be easily derived from the area of the part

query part_weight(No, Kilos).

r1: part_weight(No, Kilos) <- part(No, _ , actualkg(Kilos)).
r2: part_weight(No, Kilos) <- part(No, Shape, unitkg(K)), area(Shape, A), Kilos= K * A.

r3: area(circle(Dmtr), A1) <- A = Dmtr * Dmtr * 3.14/4.
r4: area(rectangle(Base, Height), A1) <- A1 = Base * Height.

%%   part#   shape   , weight
f1: part(22, circle(11), actualkg(34)).
f2: part(121, rectangle(10, 20), unitkg(2.1)).

The computation of this query can begin in a bottom-up fashion since fact f1 satisfies the goal in rule r1, and thus we obtain part_weight(22, 34). Now, f2 satisfies the first goal in r2, binding the variable Shape rectangle(10,20). Now, the second goal in r2, passes down the current value of Shape to the head of r4. The result is that Base and Height are now bound to 10 and 20, respectively and the goal in the body can now be safely computed yielding A1=200. This value is then returned to A in rule r2 and used in the computation of the last goal of the rule. Therefore, the area rules operate as a procedure that is called from the area goals in the rule. This top-down passing of parameters from goals to rule heads is often required for effective computation. The procedure calling analog is often applicable to top-down computation. For instance if have a set of facts similar to this describing the colors in which a given item comes:

part(socks, [red, black, blue]).

From these facts we might ask a query such as, find how many colors a given part comes in:

query part-color($Myitem, Color).

part-color(Item, Color) <- part(Item, ColorList), member(C, ColorList).

member(C, [C|_]).
member(C, [_| Crest]) <- member(C, Crest).

Here the value of $Myitem is passed down to the first argument in part-color and Item. This is very similar to procedure calls where the actual parameters are passed down to the formal parameters in the procedure head. Consider now the body of the part-color rules, where the goals are executed from left to right. The goal part(Item, ColorList) is first execute with the first arguent bound to Item = $Myitem, binding ColorList. For instance, if Myitems = socks then ColorList = [red, black, blue] = [red | [black | [blue] ]]. Then this list is passed to the second argument of member using unification, to yield C = red and Crest = [black|[blue]]. The recursive calls to member then proceed, always returning the head of the list until the tail is the empty list []. Observe that in the execution of the rule above, the actual work is performed during the actual recursive call when the second argument in the body is extracted from the second argument in the head, as per the equivalent formulation of the previous recursive rule as:

member(C, L) <- L = [_| Crest],  member(C, Crest).

In Datalog, this is called right-linear recursion, which is largely equivalent to tail-recursion in Lisp. Right-linear recursive rules (and symmetrically, left-recursive rules where the whole computation is performed after the recursive call) rules are supported efficiently in DeAL, using a single fixpoint computation. We might have linear rules where computation must be performed before and after the recursive call. Consider, for instance, the following rules that count length of the list:

length([H|T], C1) <- length(T, C), C1 = C+1.
length([], 0).

For these recursive rules, some computation takes place before the recursive call and some computation after. Thus they will be supported using the supplementary magic set method that requires two fixpoint computations. However, the length of a list can also be computed as follows:

length(L, Ll) <- clen(L, 0, Ll).  
clen([H|T], C, Ll) <- C1 = C + 1, clen(T, C1, Ll).
clen([], C, C).

This program uses a right-linear rule, where the computation is performed before the recursive call. In general, while the left/right-linear formulation of programs should be attempted whenever possible, many computations (e.g., list-append) cannot be expressed in this form and will be implemented using the supplementary magic method.


Last Updated 2014