Next: The Logic/Functional Style Up: Functions Defined by Previous: Full RELFUN Exemplified

Higher-Order Constructors and Functions

Our derivation of functional programming extensions now arrives at variables and structures used as constructors or functions, and at their combination with non-ground and non-deterministic calls.

Constructor variables and structures, introduced in a relational context (subsection 2.5), are also useful in a functional setting. For instance, a function genints enumerates the integers in the alternating order , , , ..., returned as the infinitely non-deterministic values 0 or s[0] or p[0] or s[s[0]] or p[p[0]] or ... Its definition employs a constructor variable, Sign, for building up a homogeneous, `absolute' nesting before binding the structure's ``neutral signs'' (equal in all levels!) to either the successor or predecessor constructor. Instead of using the constants s and p, we could also apply as constructors the defined functions 1+ and 1- or structures like inc[1] and inc[-1].


genints() :-& 0.
genints() :-& genints(Sign[0]).
genints(Sign[N]) :- Sign is s & Sign[N].
genints(Sign[N]) :- Sign is p & Sign[N].
genints(Sign[N]) :-& genints(Sign[Sign[N]]).
While the main nullary genints/0 generates all integers, the auxiliary unary genints/1 can also be called as genints(Sign[...Sign[0]...]) to generate the integers whose absolute value is not less than the `absolute' argument, as genints(s[0]) to generate the positive integers, as genints(p[0]) to generate the negative integers, and in other meaningful ways.

Function variables in queries can be utilized much like the corresponding relation variables (see subsection 2.5). For example, given the DATAFUN version of the density database (cf. subsection 3.1.2), the query F(china) asks for all unary properties of china, enumerating the attribute F = area with the returned value 3380, the attribute F = pop with its value, etc.

Function variables in clauses give us the abstraction power of functional arguments in the fashion of functional programming. Thus, revise is a ternary function applying any unary function F to the Nth element of a list (for N greater than the list length or N less than 1 it returns the list unchanged):


revise(F,N,[]) :-& [].
revise(F,1,[H|T]) :-& tup(F(H)|T).
revise(F,N,[H|T]) :-& tup(H|revise(F,1-(N),T)).
Similarly, the sort function could be parameterized by a Compare relation to be handed to the sorted filter, which would abstract from the specific lesseq relation (in particular, from the representation of naturals as s structures). Of course, this ``functional style'' of universally quantified operator variables, occurring on both sides of definitions, is also useful in purely relational examples. Conversely, the ``relational style'' of existentially quantified operator variables, occurring only on the rhs of definitions, would also be useful in purely functional examples. Thus, the earlier function-variable query about china could be further abstracted for use in the rhs of a rule returning attribute/value pairs of an object. The below attval function employs both the rhs-only variable Attribute and an lhs/rhs variable Valfilter (bound, e.g., to numfilter) for filtering the values returned by Attribute:

attval(Obj,Valfilter) :-& tup(Attribute,Valfilter(Attribute(Obj))).
numfilter(X) :- numberp(X) & X.
Note that the free variable Attribute in the first tup position becomes bound by its application in the second tup position before the tup actually returns the pair.

Function structures can be employed like ``function-forming operators'' in FP [Bac78]. Bringing the relational-product example in subsection 2.5 back to functional programming, functional composition can be defined by using the structure compose[F,G] as a function, which permits twice to be defined as a compose-structure-valued footed fact:


compose[F,G](X) :-& F(G(X)).
twice(F) :-& compose[F,F].
Again, while the structure compose[...] can be (higher-order-)called directly, as in compose[fathfun,mothfun](john), the constant twice is (first-order-)called in function position to return an applicable function structure, as in twice(fathfun)(john).

Let us now turn to the combination of higher-order operators with non-ground and non-deterministic calls.

For example, , the inversion of a unary function F, can be defined as a function structure inv[F] which calls F freely within an is-call only accepting F values that match the argument V of (for an N-ary F we just add a ``|''):


inv[F](V) :- V is F(X) & X.     (generally   inv[F](V) :- V is F(|X) & X.)
Thus, inv[area](1139) calls 1139 is area(X), hence returns india or other countries for which area returns 1139 (the general inv would also work, returning [india]).

Another example, a version of the -operator, additionally employs a result-splitting-like technique (used in the sort definition) to fork the entire result of a call into both the binding of a request variable and the returned value. First, we define a non-deterministic generator naturals, enumerating the naturals from an initialization given in the first argument, where the next natural is always both bound to the second argument and returned.


naturals(N,N) :-& N.
naturals(N,V) :-& naturals(1+(N),V).
For instance, naturals(3,V) binds V to 3 or 4 or ...; at the same time it returns each of these values. This then permits to concisely define a non-deterministic mu higher-order function taking unary functions over the naturals as its argument and returning their smallest argument for which they return 0, then their second-smallest argument, etc., diverging if there is none (left):

mu(F) :- 0 is F(naturals(0,V)) & V.

The ap reduction of higher-order relations in subsection 2.5 directly transfers to function variables and structures. For instance, the above rule could be reduced to


ap(mu,F) :- 0 is ap(F,ap(naturals,0,V)) & V.
changing F from a function variable into an argument variable. The effects on the WAM implementation are the same as discussed for higher-order relations.



Next: The Logic/Functional Style Up: Functions Defined by Previous: Full RELFUN Exemplified


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