Next: Functions Defined by Up: Relations Defined by Previous: Varying-Arity Relationships

Higher-Order Constructors and Relations

While PROLOG restricts constructors and relations to constants, RELFUN also permits them to be variables or structures. This enables a restricted kind of higher-order operators, syntactically reducible to first-order operators, but more expressive and cleaner than PROLOG's use of extralogical builtins like functor, ``=..'', and metacall as higher-order substitutes. Higher-order unification of the kind studied with Prolog [NM90], however, is orthogonal to the extensions in RELFUN, which for simplicity and efficiency lives without -expressions (thus avoiding problems with -variables [Bac78]) and `semantic' extensions of Robinson unification.

Constructor variables can be used to abstract from, or force equality of, the `type' of structures, as encoded by their constructor. For example, the unification of staple[book,X,X] and F[Y,paper,paper] succeeds, binding F to the constructor staple. Also, the argumenteq definition of subsection 2.3 can be generalized to arbitrary constructors, using a single fact:


argumenteq(F[|Args],G[|Args]).
A converse definition, of constructoreq,

constructoreq(F[|Args1],F[|Args2]).
may be used to check equality of only the `types' of two structures, as in the successful constructoreq(staple[paper,book],staple[book,folder,X]). For PROLOG's structures constructoreq could be simulated by two calls of the functor builtin.

Constructor structures embody parameterized constructors such as stack[integer], which are themselves applicable to arguments as in stack[integer][3,1,2]. The above constructoreq fact can thus be refined to a conspareq definition, succeeding for equally parameterized constructor applications such as a stack and a heap of integers:


conspareq(F[Argtype][|Args1],G[Argtype][|Args2]).
The variables F and G stand here for constructors, e.g. stack and heap, of constructor structures, whose single Argtype parameters must be equal.

Relation variables in queries enable to find all relationships between given arguments. In the DATALOG knowledge base (cf. subsection 2.1) the query R(X,bridgebuilding) needs only fact retrieval for binding R to the relation subfield and X to the object architecture or, R to applicable and X to computerscience; the query R(computerscience,architecture) requires rule deduction for binding R to applicable. Later, using footed clauses (section 3), relations found in this way will become returnable values, as in R(X,X) &self[R][X], returning self[applicable][computerscience], where the R-value is part of a constructor structure. Note that the R's employed here are `relation-request' variables, free at the time of invoking the queries. More usual (mainly in LISP-based PROLOGs) is to permit variables in relation position only if they are always bound at the time of the call, as in the example of the next paragraph.

Relation variables in clauses permit the use of higher-order facts (recognized as such by the context) like virtue(supports), virtue(protects), etc. to abstract rules like


honorable(X) :- supports(X,Y).
honorable(X) :- protects(X,Y).
etc. to the single rule (``Honorable is who has a virtuous relationship to someone'')

honorable(X) :- virtue(R), R(X,Y).
Here we apply virtue as a unary second-order relation over binary relations, but more general higher-order relations can be useful.

Relation structures can be employed for defining operations on relations. For example, the relational product can be defined using the structure relproduct[R,S] as a relation, which permits relational square to be defined with just a fact that uses a relproduct structure as its second argument:


relproduct[R,S](X,Z) :- S(X,Y), R(Y,Z).
relsquare(R,relproduct[R,R]).
While the structure relproduct[...] can be (higher-order-)called directly, as in relproduct[fathrel,mothrel](john,W), the constant relsquare is (first-order-)called to bind a variable, which is then used as a structure-valued relation variable, as in relsquare(fathrel,T), T(john,W).

As discussed in [Bol90], higher-order relations of this form are not easily compiled into the WAM, which collects all clauses with the same constant relation name and arity into a procedure. However, relation variables and structures can be eliminated by simply introducing an apply relation constant as in [War82], which we shorten to ap: hor(...) is replaced by ap(hor,...) in all heads and bodies, moving the higher-order relation hor to the first argument position. The last example thus becomes


ap(relproduct[R,S],X,Z) :- ap(S,X,Y), ap(R,Y,Z).
ap(relsquare,R,relproduct[R,R]).
and can be queried by, e.g., ap(relsquare,father,T), ap(T,john,W). Note that the relsquare clause and goal would not have needed the ap dummy because the relsquare relation is a constant. However, even if all calls to a relation in a program can be found to be first-order by static analysis, the user could still issue relation-variable queries like P(R,relproduct[R,R]). In the WAM these would only work in the form ap(P,R,relproduct[R,R]), and presuppose that the relsquare clauses are ap-transformed, like all other ones. Consider the effect of having all clauses collected into ap/i procedures, whose first arguments always are the former relation names (hence, i > 0). The discriminating effect of calling differently named procedures is lost, but is simulated by the usual first-argument indexing, loosing of course the refined discrimination of non-ap first-argument indexing. Fortunately, in our WAM we can index on all arguments (to the left of ``|''), thus regaining full discriminative power for ap-reduced clauses.

For constructor variables and structures an analogous first-order reduction is possible using a dummy constructor, which should again be ap in order to permit metacalls for reduced clauses. As for earlier reductions this will affect WAM indexing: (top-level) structure's constructors are all mapped to the same dummy constant, loosing the constructors' indexing power, which could be regained by also indexing on their first arguments.



Next: Functions Defined by Up: Relations Defined by Previous: Varying-Arity Relationships


Harold Boley & Michael Sintek (sintek@dfki.uni-kl.de)