Next: Higher-Order Constructors and Up: Functions Defined by Previous: Non-DeterminismDATALOG Relationalizing,

Full RELFUN Exemplified by ``Self''-Functions

When enriching DATAFUN with structures and lists we arrive at full RELFUN (we will immediately transfer the relational varying-arity extensions). Returning to successor structures for natural numbers, one should first note that it is illegal to nest active calls into passive structures like this: s[+(M,N)]. The usual equational definition of binary addition could still be transcribed by employing an is-call for +'s recursion:


+(0,N) :-& N.
+(s[M],N) :- A is +(M,N) & s[A].      (or   +(s[M],N) :-& +(M,s[N]).)

However, we prefer another method, relying on functions defined to simply return ``their own call as a structure''. Since the same functor can be a constructor and a defined function, we can define, e.g., s and tup as the following self-passivating functions:


s(M) :-& s[M].
tup(|Z) :-& tup[|Z].      (or   tup(|Z) :-& [|Z].   or   tup(|Z) :-& Z.)
Now, s and tup may also be called as active functions, evaluating their arguments in the usual call-by-value manner and returning passive structures that use the evaluated arguments as their arguments and the respective function names as their constructors.

For example, the call tup(subfield(engineering),s(s(0))) non-deterministically returns the lists [mechanics,s[s[0]]] or [architecture,s[s[0]]]; the LISP-cons-like tup-``|''-use tup(s(0)|[0]) returns [s[0],0]; the COMMON LISP-list*-like tup-``|''-use tup(a,b,c|[d,e]) returns [a,b,c,d,e]. Moreover, the s definition enables a direct analogue to equational addition:


+(0,N) :-& N.
+(s[M],N) :-& s(+(M,N)).

It should also be noted here that RELFUN definitions obey the ``constructor discipline'' [O'D85], which with our notation amounts to saying simply that ``clause heads must not have embedded parenthesized expressions''. This would be violated by the eq-nested signum calls shown in the introduction.

The earlier relation-to-function transcriptions (e.g., for the subfield operator) decreased the arity by one because one relation argument was distinguished as the function value. Alternatively, relations can often be refined to functions of the same arity returning an additional useful value. One class of functions generated in this way is filter functions i.e., functions acting as the identity for certain arguments or argument combinations, and failing for other ones. For instance, the sorted relation on lists of subsection 2.2 can be refined to the following filter function, whose recursive call is nested after the ``|'' into a cons-like tup call:


sorted([]) :-& [].
sorted([X]) :-& [X].
sorted([X,Y|Z]) :- lesseq(X,Y) & tup(X|sorted([Y|Z])).
This sorted function returns sorted lists unchanged (for non-ground ones like [s[0],E,s[s[0]]] enumerating their correct instantiations, here [s[0],s[0],s[s[0]]] and [s[0],s[s[0]],s[s[0]]]), and fails for unsorted lists (such as the non-ground [s[s[0]],E,s[0]]).

Below, a sample sorted call is given, which occurs in an (internally non-ground and non-deterministic) functional version of the well-known relational slow-sort program [Llo87]. This sort definition also exemplifies an essential use of non-ground function calls: since such calls both bind request variables and return a value, they can be used to split results into bindings, for the calls occurring somewhere above or after them, and a value, for the caller nested directly above them.


sort(X) :-& sorted(perm(X)).

perm([]) :-& [].
perm([X|Y]) :-& tup(U|perm(delete(U,[X|Y]))).

delete(X,[X|Y]) :-& Y.
delete(X,[Y|Z]) :-& tup(Y|delete(X,Z)).
Let us consider this bottom-up. The auxiliary function delete non-deterministically removes occurrences of its first argument from the list in its second argument. The permutation function can then use a non-ground delete call for result splitting: it non-deterministically binds U to arbitrary list elements, for the cons-like tup call, and returns U-less lists, for the recursive perm call. Finally, the sort main function calls the above sorted filter on the non-deterministic permutations of its argument. Note that this functional sort version specifies a computationally preferable (nesting) sequence by calling perm before sorted. In the relational sort specification commutativity of conjunction appears to permit calling sorted before perm, which, however, would not run in normal PROLOGs, as discussed in [Llo87]. A related benefit of the functional formulation is that the computationally less meaningful sort use for `unsorting' a given sorted list is syntactically marked by an is-call over a free sort call, whereas the relational version employs symmetrically-looking non-ground sort calls for both use modes, that would suggest ``equality of rights''.

A variant of filters is self-testing functions, which can also be viewed as self-passivating functions that yield unknown for an argument (sequence) considered ``ill-formed''. For example, the varying-arity sorted relation of subsection 2.4 can be refined to a self-testing function that fails for unsorted argument sequences:


sorted() :-& sorted[].
sorted(X) :-& sorted[X].
sorted(X,Y|Z) :- lesseq(X,Y), sorted[|W] is sorted(Y|Z) & sorted[X|W].
Now, the non-ground call sorted(s(0),E,s(s[0])) returns the correct instantiations of sorted[s[0],E,s[s[0]]], while sorted(s(s[0]),E,s(0)) yields unknown.

Concluding the series of ``self''-functions, let us proceed to self-normalizing functions, a variant of self-testing functions performing argument normalization. For instance, the previous list sort function can be used to define bag as a varying-arity function that returns a bag structure of the sorted arguments i.e., a normalized multiset:


bag(|X) :- W is sort(X) & bag[|W].
Now, the call bag(s[s[0]],0,s(s[0]),s(0)) returns bag[0,s[0],s[s[0]],s[s[0]]]. Recalling the discussion in subsection 2.2, it should be clear that even for a defined function (e.g., bag) no evaluation (e.g., normalization) will happen if it is applied with square brackets: tup(bag(s[0],0),bag[s[0],0]) returns [bag[0,s[0]],bag[s[0],0]].

The flattening, extra-arguments, and relationalize transformations from DATAFUN to DATALOG in subsection 3.1.3 are easily generalized to corresponding RELFUN-to-PROLOG transformations. For example, the above varying-arity bag function becomes a relation which must bind normal forms to a request variable (the extra first argument) instead of just returning them: bag(bag[|W]|X) :- sort(W,X). However, self-normalizing functions constitute a paradigmatic class of operators for which a relational reformulation seems not practically useful: a concise functional nesting like set(bag(s[0],0),bag[0,s[0]]) would become the relational conjunction bag(B,s[0],0), set(S,B,bag[0,s[0]]), treating the active and passive bags completely differently, even though they both evaluate to (equal) structures for the set. Again recalling subsection 3.1.3, the X1-reuse for value returning in the WAM also supports full RELFUN because X1 can point to structured return values on the heap just as it points to structured variable values.



Next: Higher-Order Constructors and Up: Functions Defined by Previous: Non-DeterminismDATALOG Relationalizing,


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