Next: Relations Defined by Up: Extended Logic-plus-Functional Programming Previous: Abstract


Many approaches are possible for combining logic and functional programming, as illustrated by the collection [DL86]. These can be preclassified in two principal dimensions. (1) The combination may start with a model-theoretic semantics which is then refined (via proof theory) for practical programming or, it may start with an implemented operational semantics which is tuned in practice and then abstracted for model-theoretic foundation. (2) A quite separate distinction is whether one is interested in a loosly coupled hybrid system or, whether one strives for a tightly integrated logic/functional language.

With RELFUN we have been pursuing the latter alternatives of these dimensions: it was first operationally defined as a highly integrated language (cf. [Bol86]), which was later endowed with a model-theoretic semantics capturing the essence of the integration (cf. [Bol93]).

The language's operational side stems from its origin as a pure-LISP-based interpreter. Also the present version is both implemented in, and can access precoded functionality from (a subset of) COMMON LISP. Besides the definitional interpreter this implementation consists of a WAM compiler/emulator system. The RELFUN-in-LISP implementation runs all the examples to be presented here, where the speed is acceptable except, understandably, for the LISP-in-RELFUN example.

RELFUN's integrating concept is valued clauses, encompassing both PROLOG-style Horn clauses (for defining relations) and directed conditional equations (for defining functions). While the former start off from Horn logic, the idea for the latter is to regard a function definition like

not as clauses of a logic with equality (shown on the left) but as clauses that return the right-hand sides of the directed equations via a (``&''-marked) premise following after possible conditions (shown on the right):

eq(signum(X),-1) :- X < 0.                       signum(X) :- X < 0 & -1.
eq(signum(0),0).                                 signum(0) :- & 0.
eq(signum(X),1)  :- X > 0.                       signum(X) :- X > 0 & 1.
Hence, function calls need not be embedded into eq calls with auxiliary request variables, as in eq(signum(-2.7),SignumA), eq(signum(3.1),SignumB), SignumA < SignumB, but can be written directly, as in signum(-2.7) < signum(3.1). We then interpret value-returning premises (after the ampersand) as generalized Horn-rule premises: apart from being terms like -1 they may be calls like *(-1,X) or member(X,[-1,-3,-5]) and nestings like +(*(-1,X),3) or member(X,rest([-1,-3,-5])). Nestings are evaluated strictly call-by-value, as, classically, in FP [Bac78].

The RELFUN notions of relation and function are amalgamated to an abstract operator concept: functions are generalized to non-ground, non-deterministic operators, hence relations can be viewed as characteristic functions. Our notion of relations as true-valued functions is like in SLOG [Fri85], except that RELFUN's valued facts return true implicitly. Another amalgamating notion is akin to LISP's ``useful non-nil values'': relation-like operators may on success return a value more informative than true (e.g., we can let member return the list starting from the element found). All kinds of RELFUN operators can be applied in generalized Horn-rule premises, which are usable uniformly to the left as well as to the right of the ``&''-separator. Actually, such premises constitute a valued conjunction, also permitted as a top-level query (e.g., member(X,L) &member(X,M) non-deterministically returns rest lists of M whose first element also occurs in L). A special valued conjunction calling only relations to the left of ``&'' and having a single variable to its right (e.g., country(X), between(X,atlantic,pacific) &X) can be viewed as an indefinite description or -expression (e.g., ), also provided in other relational/functional amalgamations (see [PS91]).

Certain RELFUN functions can be inverted by calling them non-ground (by-value) on the right-hand side (rhs) of a generalized PROLOG is-primitive, mimicking relations (incl. the above eq predicate). RELFUN thus provides a version of innermost conditional narowing [Fri85]. Its operational semantics flattens functional nestings to relational conjunctions, thus inherits the search-space reduction of SLD-resolution [BGM88]. Hence, our WAM implementation of (first-order) RELFUN can approach the speed of PROLOG [Bol90].

Besides its attempt at integrating basic notions of PROLOG and LISP, many of RELFUN's extended concepts can also be transferred to relational and functional programming individually. In the following section (2) the extended relational component will be treated, including higher-order relations. The next section (3) will then augment this by the extended functional component and discuss its benefits. Finally, the section (4) before the conclusions will give three sample uses of the relational/functional style.

Next: Relations Defined by Up: Extended Logic-plus-Functional Programming Previous: Abstract

Harold Boley & Michael Sintek (