[NEXT] [PREV]    HANDBOOK / GENTLE PRIMER / Describing Computations /

Rule Bodies


So far we have discussed rules without bodies. A rule body is a sequence of statements, in most cases predicate invocations, that can be used to break down the computation of the particular rule into subtasks or to reduce a problem to another problem for which there is a solution.

For example, we could add a rule to the definition of predicate favorite stating that jack prefers the same color as jane:

   'rule' favorite(jack -> X): favorite(jane -> X)
Consider the invocation

   favorite(jack -> C)
The new rule is selected (because the expression jack matches the pattern jack), and its body is evaluated. This means that the invocation favorite(jane -> X) is elaborated. This succeeds and defines X as red. After processing the body the expressions constituting the output parameters of the rule head are evaluated. Here the expression is simply a variable, X, which has just been defined as red. Hence, red is the output value of the original invocation. So C is defined as red.

It is very common for the rules of a predicate to directly follow the type definition of its argument. There is a rule for each alternative of the type, and inside this rule the members of the body process the constituents of that alternative. The result is given by combining the results of the members.

Assume that, besides lists of colors, we have also defined lists of persons:

   'type' PersonList
      list(Person, PersonList)
(We can use the same functors in both list type definitions because it is clear from the context which type is meant.)

We now want to define a predicate favorites that takes a list of persons and returns a list of colors of the same length. An element of the color list is the favorite color of the person at the corresponding position in the person list. For example,

   list(julia, list(jane, nil))
is mapped to

   list(blue, list(red, nil))
We introduce two rules, each one handling an alternative of the above type definition:

   'rule' favorites(list(Head, Tail) -> list(ColorHead, ColorTail)):
      favorite(Head -> ColorHead)
      favorites(Tail -> ColorTail)

   'rule' favorites(nil -> nil)
The first rule decomposes its argument into Head and Tail and uses the suitable predicates to compute the favorite color of the Head and the favorite color list of the Tail. Given these values the resulting color list can be constructed.

The second rule simply has an empty body. For an empty person list we return an empty color list.

A rule body is evaluated by evaluating its members in the given order. If a member fails then the rule fails. If all members succeed, then the rule succeeds.

A rule

  • 'rule' A : B1 B2 ... Bn
can be understood as a logical statement
  • A if B1 and B2 and ... and Bn
For example, the rule

   'rule' grandfather(X -> Z): father(X -> Y) father(Y -> Z)
can be read as
  • the grandfather of X is Z if
    (there is a Y such that)
    the father of X is Y and
    the father of Y is Z.