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 meta`call` 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:

A converse definition, ofargumenteq(F[|Args],G[|Args]).

may be used to check equality of only the `types' of two structures, as in the successfulconstructoreq(F[|Args1],F[|Args2]).

*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 `integer`s:

The variablesconspareq(F[Argtype][|Args1],G[Argtype][|Args2]).

*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

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

Here we applyhonorable(X) :- virtue(R), R(X,Y).

*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:

While the structurerelproduct[R,S](X,Z) :- S(X,Y), R(Y,Z). relsquare(R,relproduct[R,R]).

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

and can be queried by, e.g.,ap(relproduct[R,S],X,Z) :- ap(S,X,Y), ap(R,Y,Z). ap(relsquare,R,relproduct[R,R]).

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.