Default Rules

The problem of partially defined functions:

Computation failure when no rule is applicable.
Solution:

FP.- Exceptions
The failure can be treated => default value
```
default f(X) = value.
```
FLP.- Problem: Goal f(X)
The default value can be returned iff the normal rules determine that they cannot compute the call. => Constrained answers:
```
f(0):= 0.
f(1):= 1.
default f(X)= 2.
```
Goal f(X) => Result 2 if X ~= 0, X ~= 1

PROLOG predicates: Partially defined boolean functions.
CWA + Negation -> default rule with result false.

Expressivity of Default Rules

Problem: Substraction

Compute the substraction of natural numbers.

The partially defined version is completed with a default rule in order to return an integer. Integers are defined as signed numbers.

type int = + nat | - nat.

fun invert: int -> int.
    invert (+ Y) = - Y.
    invert (- Y) = + Y.

fun subs : nat * nat -> int.
    subs Y 0 = + Y.
    subs (succ Y) (succ X) = subs Y X.
    default subs Y X) = invert (subs X Y).

eval subs (succ 0) X.
> result: + (succ 0)      answer: X = 0
> result + 0              answer: X = (succ 0)
> result - X'             answer: X = (succ X'), X' ~= 0
> no (more) solutions.

Problem: Square roots

Compute the infinite list of integer square roots of the natural numbers. We accumulate the previous square root and it is increased when a perfect square is found. A natural number is a perfect square if it is the product of another natural number by itself. Otherwise the number is no perfect.

Try to solve it in your favourite language before you check the solution in a functional logic language

Explicit and Implicit Negation

By using default rules, PROLOG programs with negation are subsumed by functional logic languages. The negated part of a predicate is obtained by using a default rule with body false.

Problem: Disjoint Lists

Decide if a pair of lists are disjointed, i.e. they do not share elements.

fun member: A * list A -> bool.
    member X [Y|L] = X=Y => true # member X L.
    default member X L = false.

fun disjoint: list A * list A -> bool.
    disjoint L1 L2 = ~ ((member Y L1), (member Y L2)).

solve disjoint [Y | L]  [X, (succ 0)].
>     result: true    answer: L = [], X ~= Y, Y ~= s (0)
>     . . .

Remember that we had explicit negation, so the programmer can freely use explicit negation and negation as failure for a predicate. Kowalski pointed out the advantages of the distinction between explicit and implicit negation for knowledge representation.

Default Rules - Implementation -

Narrowing strategy: The modification of the narrowing rule to cope with default rules has been presented in Moreno 94 using the technique of constructive negation
Constructive negations: defined to handle negation in logic programming Chang 88, 89, Stuckey 91, Drabent 94
Translation to PROLOG: The only implementation of constructive negation is done in SEPIA, a PROLOG compiler developed at ECRC.
It seems that it could be possible to translate default rules into this PROLOG version the achieve an implementation.

Go to index

Default Rules

Default Rules

Expressivity of Default Rules

Problem: Substraction

Problem: Square roots

Explicit and Implicit Negation

Problem: Disjoint Lists

Default Rules - Implementation -

Narrowing strategy

Translation to PROLOG