# DeAL TutorialTop-Down Execution

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

In a bottom-up execution the goals of a rule r_{j} are computed before the head of r_{j}, 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.