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

Shallow Backtracking

Gentle
Applications
Concepts
Examples
Handbook
Support
Download

Using shallow backtracking, a predicate invocation is elaborated as follows. The rules are tested in the given order. If a rule fails, the next rule is considered. If a rule succeeds, the predicate succeeds and the result is determined. If all rules fail, the predicate fails.

This implies that, when one considers a certain rule, one can be sure that preceding rules were not applicable.

For example, a predicate max computing the maximum of two integers (using the built-in predicates ge and lt for the relations greater-or-equal and less-than) that is defined by


   'rule' max(X, Y -> X): ge(X, Y)
   'rule' max(X, Y -> Y): lt(X, Y)

could also have been written as


   'rule' max(X, Y -> X): ge(X, Y)
   'rule' max(X, Y -> Y)

because the second rule is only used when X is less than Y. The disadvantage is that now the rule cannot be understood in isolation.

This style is often used for abbreviation. For example, a predicate kind that maps the set of letters a, b, c, ... , z onto the constants vowl or consonant can be written is this way:


   'rule'  kind(a -> vowl)
   'rule'  kind(e -> vowl)
   'rule'  kind(i -> vowl)
   'rule'  kind(o -> vowl)
   'rule'  kind(u -> vowl)

   'rule'  kind(Other -> consonant)

where the last rule replaces 21 rules dealing with consonants. Since none of the first five rules was applicable, we know that Other is a consonant.

[NEXT] [PREV]