B-Prolog - Matching Clauses

Matching Clauses

A matching clause is a form of a clause where the determinacy and input/output unifications are denoted explicitly. The compiler translates matching clauses into matching trees and generates indexes for all input arguments. The compilation of matching clauses is much simpler than that of normal Prolog clauses because no complex program analysis or specialization is necessary; and the generated code tends to be more compact and faster. The B-Prolog compiler and most of the library predicates are written in matching clauses.

A matching clause takes the following form:

H, G => B

where H is an atomic formula, G and B are two sequences of atomic formulas. H is called the head, G the guard, and B the body of the clause. No call in G can bind variables in H and all calls in G must be in-line tests. In other words, the guard must be flat. The following gives an example predicate in matching clauses that merges two sorted lists:

merge(,Ys,Zs) => Zs=Ys. merge(Xs,,Zs) => Zs=Xs. merge(,,Zs),X Zs=,merge(Xs,,ZsT). merge(Xs,,Zs) => Zs=,merge(Xs,Ys,ZsT).

The cons occurs in both the head and the body of the third clause. To avoid reconstructing the term, we can rewrite the clause into the following:

merge(,Ys,Zs),Ys=,X Zs=,merge(Xs,Ys,ZsT).

The call Ys= in the guard matches Ys against the pattern .