Qi Prolog

Prolog

Qi Prolog is a version of Prolog that provides the object code for the sequent calculus rules of Qi. Unlike commercial stand-alone Prologs, Qi Prolog is not inspired by the Warren Abstract Machine (WAM), but instead by the AUM (Abstract Unification Machine) that is biased towards producing efficient functional programming object code. Under SBCL, Qi Prolog delivers about 300 KLIPS. Qi Prolog comes in two flavours - M Prolog based on Edinburgh syntax and S Prolog based on Qi list expressions.

M Prolog

Qi Prolog M syntax is largely Edinburgh syntax for reasons of familiarity with the standard Prolog conventions. Since Qi uses a different reader to consult a Prolog file from that used to load a Qi file, if you wish to mix Edinburgh syntax (M-syntax) Prolog code with Qi code in one file then the M-syntax Prolog has to be placed in a sanitary string.

(m-prolog
"member(X,[X | _]).
member(X,[_ | Y]) :- member(X,Y).")

Qi Prolog generates a function called member from the previous definition. The function prolog? receives any number of Prolog goals and returns true or false.

(12-) (prolog? (member 1 [1]) (member 2 [X]))
true

Extralogical Predicates

Qi Prolog contains 8 extralogical predicates.

is; which is a binary predicate that corresponds to the Edinburgh Prolog is. It can be written either in prefix or infix form. So 'X is 1' and 'is(X,1)' are legal. The second expression is an evaluable Qi expression. Thus 'X is (+ 3 4)' will bind X to 7.
bind which works as a prefix is; bind is faster however since the variables in the second expression are not dereferenced.
when; which is a unary predicate that receives an evaluable Qi expression e of type boolean. If e is true then the call succeeds. If e is false then it fails. If e is not a boolean then an error is returned.
fwhen; which works as when; fwhen is faster since the variables in the second expression are not dereferenced.
return; is a unary predicate which receives an evaluable Qi expression e. The Prolog computation is stopped and e is returned as a result.
!; is a zero place predicate that performs the Prolog cut.
call; is a unary predicate which receives a literal as a list and applies the predicate of the literal to its terms.
findall; which enables multiple solutions to be found.

Here is len (length) defined in Qi Prolog.

(m-prolog
"len([ ], 0).
len([X | Y], N) :- len(Y,M), N is (+ M 1).")

Here return is used to coerce prolog? into returning a non-boolean value.

(14-) (prolog? (len [a b c] N) (return N))
3

when and call can be used to implement negation as failure (written here as ~). We then enquire if a and b are not unifiable

(15-) (m-prolog
"~(P) :- call(P), !, fail. ~(P).
fail :- when(false).")
[~ fail]

(16-) (prolog? (~ [= a b]))
true

And here when is used to define a predicate that compares numbers.

(m-prolog "greater(X,Y) :- when((> X Y)).")

Unification and Equality

As in Edinburgh Prolog, = performs unification between terms. =! performs unification with an occurs-check. == compares two terms for strict equality.

(16-) (prolog? (= X 1))
true

(17-) (prolog? (= X [f X]))
true

(18-) (prolog? (=! X [f X]))
false

(19-) (prolog? (== X 1))
false

unify, unify! and identical are legitimate substitutions for these predicates.

Note that repeated variables in Qi Prolog programs are interpreted using occurs-check unification (in most implementations of Prolog this is not true). Thus (m-prolog "f(X, X).") is compiled exactly as (m-prolog "f(X,Y) :- =!(X,Y)."). The function occurs-check will change this behaviour. (occurs-check -) disables automatic compilation with occurs-check unification. (occurs-check +) restores the default. This declaration also extends to the compilation of data types and rule closures which compile into Qi Prolog.

Multiple Solutions in Qi Prolog

findall is a tertiary predicate that receives an input pattern P, a literal L expressed as a list and an output variable V. The variable V is bound to all those instances of P for which the literal L is provable. This is a generalisation of the usual Prolog findall predicate. An example.

(20-) (m-prolog
"app([], X, X).
app([X | Y], W, [X | Z]) :- app(Y, W, Z).")
[app]

(21-) (prolog? (findall [X Y] [app X Y [1 2 3]] Z) (return Z))
[[[ ] [1 2 3]] [[1] [2 3]] [[1 2] [3]] [[1 2 3] [ ]]]

It is easy to integrate this feature into a Qi function.

(22-) (m-prolog
"friend(mary,john).
friend(mary, jim).")[friend]

(23-) (define friends
X -> (prolog? (findall Y [friend X Y] Z) (return Z)))
friends

(24-) (friends mary)
[john jim]

Mode Declarations

A mode declaration in Qi Prolog is used to suspend unification in favour of pattern-matching and is used only in the head of a clause. Generally mode declarations are used to speed up code and reduce the footprint of the generated Lisp code. (mode .. -) enables pattern-matching. Here is an example.

(22-) (m-prolog "f(a).")
[f]

(23-) (prolog? (f X))
true

(24-) (m-prolog "f((mode a -))")
[f]

(25-) (prolog? (f X))
false

(26-) (prolog? (f a))
true

The default mode is unification signalled by (mode … +). Mode declarations can be nested within each other as in (mode [f a (mode b +)] -). In this event the innermost declaration has priority. The above expression would thus perform pattern-matching with respect to [f a b] and all its elements save b which would receive unification.

Use of Applications in Qi Prolog

Qi Prolog allows function expressions to be embedded into the tails of Horn clauses. Thus

f(X) :- g((* 2 X)).

would create a Horn clause procedure that receives an input and doubles it, passing the result to g. The (…) notation can be used in the head of a Horn clause but its significance is different.

f((1,2,3)).

signifies a predicate that expects to receive a list structure [1 2 3]. The (…) construction is actually syntactic sugar for a list construction containing a complex series of mode declarations.

f((1,2,3)). is equivalent to f([1 | (mode [(mode 2 +) | [(mode 3 +) | [ ]]]] -)). The expression (1,2,3) is a complex term and the mode declarations effectively mean that (1,2,3) is either unified to a variable or unified element by element to the corresponding term. Hence a complex term cannot be broken up within unification in the way that a simple list can be.

Here is an illustration.

(1-) (m-prolog "try((f a b)).")
[try]

(2-) (prolog? (try X) (return X))
[f a b]

(3-) (prolog? (try [A B C]) (return A))
f

(4-) (prolog? (try [A | B]) (return A))
false

The final input fails because a complex term cannot be broken up as a list can. In general complex terms process faster than lists and take less code space because of their mode declarations. They are useful in automated reasoning applications where terms are to be treated as logical units rather than decomposable lists.

S Syntax Prolog

The S syntax version of Qi Prolog is more suitable than the M syntax version for the machine generation of Horn clauses. In the internals of the M Prolog compiler, M Prolog is converted first into S Prolog, before being compiled to Lisp. s-prolog receives a list of Horn clauses expressed in S syntax format and compiles them to code.

A Horn clause in S syntax has the form [Head :- Body] where Head is a literal and Body is a (possibly empty) list of literals. A literal is a list headed by a symbol (the predicate) and followed by a series of n (n ³ 0) terms which may themselves be lists. The easiest way to understand S syntax is to compare M syntax clauses with their S syntax equivalents.

M Prolog	S Prolog
(m-prolog "f(a).")	(s-prolog [[[f a] :- [ ]]])
(m-prolog "m(X,[X \| _]). m(X,[_ \| Y]) :- m(X,Y).")	(s-prolog [[[m X [X \| _]] :- [ ]] [[m X [_ \| Y]] :- [[m X Y]]]])
(m-prolog "len([],0). len([_ \| Y],N) :- len(Y,M), N is (+ M 1).")	(s-prolog [[[len [ ] 0] :- [ ]] [[len [_ \| Y] N] :- [[len Y M] [is N [+ M 1]]]])
(m-prolog "c(X,Y) :- ==(X,Y). d(X,Y) :- =(X,Y). e(X,Y) :- =!(X,Y).")	(s-prolog [[[c X Y] :- [[== X Y]]] [[d X Y] :- [[= X Y]]] [[e X Y] :- [[=! X Y]]]])

Mark