Next: Higher-Order Constructors and Up: Relations Defined by Previous: Varying-Arity Structures

Varying-Arity Relationships

Proceeding from constructor terms to atomic formulas, we come to the LISP-inspired PROLOG extension of varying-arity relation applications i.e., clause heads and bodies directly containing a ``|''. Thus, both structures and applications can be ended by a vertical bar followed by an ordinary variable; equivalently, they could be ended by a ``sequence variable'' as used in KIF [GF91]. Varying-arity applications give argument sequences the flavor of an implicit list data structure. For instance, the N-ary version (N 0) of the sorted relation

sorted(X,Y|Z) :- lesseq(X,Y), sorted(Y|Z).
permits calls like sorted(0,W,s[s[0]],s[s[s[0]]]), binding W to 0, s[0], or s[s[0]].

As in LISP, the N-ary flexibility gained can be used, among other things, to flatten nestings of binary associative operators like + and append. Their output cannot go to the (usual) last argument position because of the asymmetry of ``|''-list-splicing; the only uniformly usable output argument is the first one.

For example, while ordinary PROLOGs' ternary append relation is already quite flexible, LM-PROLOG [CK85] defines a natural N-ary extension (N > 0), which in RELFUN is rewritten as

append(Total,[]|Back) :- append(Total|Back).
append([First|Total],[First|Front]|Back) :- append(Total,Front|Back).
It `contains' LISP's unary null predicate, a list-typed PROLOG-like binary ``='' relation, and a permuted, list-typed version of PROLOG's ternary append relation (append(1,[],1) won't succeed), but is actually a varying-arity relation, which can be used in surprisingly diverse ways. Two samples are append([a,b,c],L1,...,Lm), splitting a given list into arbitrarily many lists, and append([a,b,a,b,a,b],Leftcontext,[a,b,a],Rightcontext), unifying symmetric list segments.

Of course, a simple transformer can put the varying number of arguments of such relations into a single list. For sorted the additional brackets would lead back to the original definition; for append, with its distinguished first argument, however, they would become a syntactic burden. Also, the transformation can result in serious problems for even the standard WAM-indexing scheme because the first (and only) relation argument becomes of type list indiscriminately. This could be remedied by a version of the semi-listifying arity-fixing technique sketched for structures in subsection 2.3 (e.g., listifying only the N-1 input lists of append).

Next: Higher-Order Constructors and Up: Relations Defined by Previous: Varying-Arity Structures

Harold Boley & Michael Sintek (