Next: Varying-Arity Relationships Up: Relations Defined by Previous: PROLOG-like Structures and

Varying-Arity Structures

Lists can also be given a direct N-element interpretation because RELFUN permits varying-arity structures i.e., structures containing a vertical bar. Like cns was used as a binary list constructor we use tup as an N-ary list constructor (N 0). That is, [...] should be regarded as an abbreviation for tup[...]. This convention holds even if [...] contains a ``|''. So, the earlier lists really stand for tup[s[s[0]],tup[E,F],s[0]] and tup[X,Y|Z]. Such tup structures can again be viewed as nested cns structures as shown for lists above.

Varying arities are also permitted for all other RELFUN constructors. This can be used for reinterprating many `untyped' list representations as constructor-`tagged' structures. For instance, unbounded staples and dumps of elements can be written as varying-arity structures staple[...] and dump[...], whose constructors distinguish the two `types' of element collections. The unification of RELFUN structures containing a ``|'' generates a list value for a variable after the ``|'', as if the ``|'' would appear in a list context. Similarly, lists constitute the only structures to be spliced into other structures after the ``|''. Lists are thus the `neutral' data structure for transporting the ``|''-remainders of varying-arity structures.

For example, staple[book,folder,folder|Rest] represents a staple with a book followed by two folders on the top, and some unspecified remainder Rest. When unified with staple[book,Y,Y,paper,Z,paper], Y is bound to folder and Rest to the list [paper,Z,paper]. This list can again be spliced into, say, a dump beginning with a book, dump[book|Rest], resulting in dump[book,paper,Z,paper].

Unlike PROLOG we permit the vertical bar to follow directly after an opening square bracket, both in lists and in (other) structures. For any list X, the list [|X] is the same as X; additionally given a constructor c, the structure c[|X] exclusively uses the elements of the list X as its arguments. Thus with the Rest binding [paper,Z,paper], dump[|Rest] is equivalent to dump[paper,Z,paper].

It is now possible to define elementwise equality of staples and dumps using the facts


argumenteq(staple[|Args],dump[|Args]).
argumenteq(dump[|Args],staple[|Args]).
where the two Args occurrences of each fact will be bound to unifying lists of elements. Thus, while staple[book,X,X] and dump[Y,paper,paper] would not unify, the call argumenteq(staple[book,X,X],dump[Y,paper,paper]) succeeds.

Another use of varying-arity structures is the term representation of clauses themselves. In PROLOG ``:-'' can be regarded as a binary functor whose arguments are the clause head and a nesting of binary ``','''-conjunctions for the body; in RELFUN it is reinterpreted more concisely as an N-ary constructor (N 1) whose first argument is the head and whose remaining arguments make up the body conjuncts. The rule of the DATALOG example in subsection 2.1 thus becomes the PROLOG structure


:-(applicable(Tool,Field),
   ','(subfield(Field,Subfield),applicable(Tool,Subfield)))
and the RELFUN structure

:-[applicable[Tool,Field],subfield[Field,Subfield],
                          applicable[Tool,Subfield]]

The use of lists to treat ``|'' in all contexts suggests a technique for reducing varying-arity structures to fixed-arity ones. Each varying-arity c[x1,...,xN|X] could be replaced by the unary c[[x1,...,xN|X]], where the single argument is a list containing the original c arguments as elements. However, this naive method introduces unnecessary bracketing (which could be hidden to the user) and hinders intrastructure WAM indexing [Sin92] with respect to a structure's top-level arguments (which become `neutralized' to a tup or cns constructor). Instead of listifying all c arguments, a `semi-listifying' method might keep a fixed number, K N, of initial arguments and only listify the remaining ones, resulting in the (K+1)-ary c[x1,...,xK,[xK+1,...,xN|X]]. However, even if global static analysis is used to find the smallest K such that a vertical bar or a closing square bracket is used after the Kth argument of c (for K = 0 leading back to the naive method), an interactive user could employ c[a1,...,aI|R] with I < K. In certain queries such a structure could be pretranslated to c[a1,...,aI,R1,...,RJ,R*], with I+J = K, by `unrolling' the variable R used after the ``|'' i.e., generating new variables R1, ..., RJ and R*, and on success binding R to [R1,...,RJ|R*]. In general, it is hard to avoid making possible query patterns statically known to the global analyzer.



Next: Varying-Arity Relationships Up: Relations Defined by Previous: PROLOG-like Structures and


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