Next: References Up: Extended Logic-plus-Functional Programming Previous: eval: Interpreting a


The RELFUN research attempts to combine and extend programming concepts and techniques that have accumulated in the relational (principally, PROLOG) and functional (prototypically, LISP) communities.

A comprehensive subset of PROLOG is kept as a sublanguage with little syntactic modification (structures written with square brackets instead of parentheses, cut used as a separator instead of a goal). This basis is then systematically extended by advanced relational notions, a rich set of functional notions, and a combination of both.

The functional sublanguage of RELFUN is much influenced by the implementation language LISP. But as in newer functional languages, like ML and MIRANDA, a function is defined by ``patternaction'' clauses instead of a conditional expression. Generalizing pattern matching to unification, RELFUN permits non-ground functions, as allowed in other logic/functional integrations [DL86]. This also leads to non-deterministic functions, enumerating finitly or infinitly many values via backtracking.

The relational/functional integration entails a continuing cross-fertilization of the two language styles. For instance, relational (logical) variables are reused for enabling the non-ground function arguments and values; also, the relational (extra-logical) once/``!'' is reused for making function calls/definitions deterministic. In RELFUN these constructs are employed in the same fashion for relations and functions. Conversely, varying-arity and certain higher-order operators are transferred from the functional to the relational world. Again, the cross-fertilization leads to a uniform use of such operators in both sublanguages.

In fact, some operators can play the role of both functions and relations. For example, the concise pair of clauses

disj[Op|Ops](|Args) :-& Op(|Args).
disj[Op|Ops](|Args) :-& disj[|Ops](|Args).
defines disj as a varying-arity, higher-order, non-ground, non-deterministic function structure that recursively applies its operator parameters op1, ... (one or more relations or functions) to zero or more (possibly non-ground) arguments arg1,..., enumerating the (possibly non-ground) values of op1(arg1,...), ... A disj call fails if none of these operator calls successfully returns a value, hence we have at the same time defined a disjunction relation of `success'/`failure' logic. (A cut ending the first clause would prevent functional value enumeration as well as relational truth multiplicity after the first success.)

Summarizing, RELFUN provides a tunable system of relational/functional language extensions, which can be used in isolation and in free combination. In particular, this holds for the orthogonal functional, varying-arity, higher-order, and cut extensions of the pure-PROLOG-like Horn language. Several other extensions of pure PROLOG/LISP, e.g. finite domains [Bol94] and sort lattices [Hal94], being quite independent from the ones in the RELational/FUNctional kernel, were added in a uniform fashion, e.g. leading to domain values as well as arguments. Further extensions, e.g. modules [Her95], may follow in a similar manner.

Besides the `dynamic' interplay between our language extensions, there are `static' reduction possibilities for several of them. Most notably, the functional sublanguage can be relationalized and the higher-order part can be reduced to the first-order part. While with these reductions RELFUN's semantics is indirectly founded on the usual Herbrand models for Horn clauses, there is also a more direct characterization of RELFUN's first-order hornish and footed clauses [Bol93], using functionally extended Herbrand models (instead of distinguishing an equality relation). The `horizontal' transformations of the full language into a sublanguage are also important in preparation for RELFUN's `vertical' WAM compilation. While the complete language is implemented as an interpreter, a slightly restricted version is also realized as a compiler/emulator [Sin94][Bol90]. The RELFUN sources are available in (a portable subset of) COMMON LISP along with programming examples, e.g. the ones from this paper.

In our hybrid expert-system shell, COLAB, RELFUN's backward rules were augmented by forward rules, taxonomies, and constraints [BHHMng]. Problems of realistic size have been solved by RELFUN [BBK94][Bol92] and RELFUN/COLAB [BHH+91] programs.


Next: References Up: Extended Logic-plus-Functional Programming Previous: eval: Interpreting a

Harold Boley & Michael Sintek (