From HiLog to Prolog

From the discussion about the syntax of HiLog terms, it is clear that the HiLog syntax allows the incorporation of some higher-order constructs in a declarative way within logic programs. As we will show in this section, HiLog does so while retaining a clean first-order declarative semantics. The semantics of HiLog is first-order, because every HiLog term (and formula) is automatically encoded (converted) in predicate calculus in the way explained below.

Before we briefly explain the encoding of HiLog terms, let us note that the HiLog syntax is a simple (but notationally very convenient) encoding for Prolog terms, of some special form. In the same way that in Prolog:

1 + 2

is just an (external) shorthand for the term:

+(1, 2)

in the presence of an infix operator declaration for + (see section 4.3), so:

X(a, b)

is just an (external) shorthand for the Prolog compound term:

apply(X, a, b)

Also, in the presence of a hilog declaration (see section 3.8.4) for h, the HiLog term whose external representation is:

h(a, h, b)

is a notational shorthand for the term:

apply(h, a, h, b)

Notice that even though the two occurrences of h refer to the same symbol, only the one where h appears in a functor position is encoded with the special functor apply/$n, n \geq 1$.

The encoding of HiLog terms is performed based upon the existing declarations of hilog symbols. These declarations (see section 3.8.4), determine whether an atom that appears in a functor position of an external representation of a HiLog term, denotes a functor or the first argument of a set of special functors apply. The actual encoding is as follows:

• The encoding of any variable or parameter symbol (atom or number) that does not appear in a functor position is the variable or the symbol itself.
• The encoding of any compound term t where the functor f is an atom that is not one of the hilog symbols (as a result of a previous hilog declaration), is the compound term that has f as functor and has as arguments the encoding of the arguments of term t. Note that the arity of the compound term that results from the encoding of t is the same as that of t.
• The encoding of any compound term t where the functor f is either not an atom, or is an atom that is a hilog symbol, is a compound term that has apply as functor, has first argument the encoding of f and the rest of its arguments are obtained by encoding of the arguments of term t. Note that in this case the arity of the compound term that results from the encoding of t is one more than the arity of t.

Note that the encoding of HiLog terms described above, implies that even though the HiLog terms:

	p(a, b)
	h(a, b)

externally appear to have the same form, in the presence of a hilog declaration for h but not for p, they are completely different. This is because these terms are shorthands for the terms whose internal representation is:

	    p(a, b)
	apply(h, a, b)

respectively. Furthermore, only h(a,b) is unifiable with the HiLog term whose external representation is X(a, b).

We end this short discussion on the encoding of HiLog terms with a small example that illustrates the way the encoding described above is being done. Assuming that the following declarations of parameter symbols have taken place,

 :- hilog h.
 :- hilog (hilog).

before the compound terms of page  were read by XSB, the encoding of these terms in predicate calculus using the described transformation is as follows:

      foo(bar)                    prolog(a,X) 
   apply(hilog,X)             apply(123,john,500)
apply(X,kostis,sofia)       apply(X,Y,Z,apply(Y,W))
  f(a,apply(b(c),d))       apply(map(double),[],[])  
        apply(apply(h,apply(map(P),A,B)),C)