Relational-Functional Programming Languages

Languages integrating functional and logic (relational) programming concepts [\protect\citeauthoryearDeGroot and Lindstrom1986] are currently often called functional logic programming languages. However, we will employ the term relational-functional programming languages, where the term relational language is used as a superconcept for both purely logic languages and logic languages enhanced by (functionally appropriate but) extra-logical features such as the cut/commit operator.

The integration of different programming paradigms into a new programming language aims at a language inheriting the advantages of the original languages. In the case of the integration of relational and functional programming languages, their declarativeness and, in particular, their expressiveness, i.e. their suitability for partially disjoint problem classes, is inherited.

In general, there are two different ways of integrating functional and relational programming languages [\protect\citeauthoryearBoley1992]:

1. by tightly integrating both paradigms into unified ones [\protect\citeauthoryearLock1993][\protect\citeauthoryearHanus1991][\protect\citeauthoryearBoley1986]
2. by loose coupling, obtaining hybrid languages (for classic systems, see [\protect\citeauthoryearRobinson1985][\protect\citeauthoryearSloman and Hardy1983]) which are often parts of multi-language expert system shells

Both approaches have their advantages and disadvantages:

1. While tightly integrated languages maintain full declarativeness, they require existing software libraries to be re-implemented and cannot be easily augmented by additional programming paradigms. Furthermore, tightly integrated languages often lose some of the efficiency of the separate languages since techniques of their efficient execution can usually not be entirely transferred to the integrated language.
2. Hybrid languages have the disadvantage of not completely maintaining declarativeness: applications have to be split into parts specified in different paradigms and communicating via interface primitives. For large, modular applications this is often insignificant: complete modules can be specified either in the functional or the relational sublanguage, accessing each other only via well-defined interfaces.

The loose integration of relational languages and LISP in this work was inspired by RELFUN [\protect\citeauthoryearBoley1992], a tightly integrated relational-plus-functional programming language also building upon PROLOG and LISP (the original version [\protect\citeauthoryearBoley1986] not only used a LISP-like syntax for both relations and functions but also LISP-like dotted-pair patterns for unification).

In addition to functions being accessible on the right-hand side of the generalized is builtin, RELFUN also allows function calls in each premise, all of which can be nested for call-by-value evaluation. This requires a syntactical distinction between active function applications and passive structures: while round parentheses are reserved for applications, the square brackets used for PROLOG lists are generalized to be also used for structures (which can thus be viewed as labeled lists).

In RELFUN, the tight integration of functions into a relational language is performed via functional clauses, an extension of relational (Horn) clauses by a value-returning premise (the last premise, preceded by an ampersand, ``&''). This directly leads to the main difference between RELFUN and the loose integration described in this work: RELFUN functions inherit all properties of ordinary relations and are thus potentially non-deterministic, as the following example illustrates:

For relations and functions to be applied only deterministically, RELFUN extends PROLOG's cut use to its functional clauses:

memberp(X, [X | R], [X | R]) :- !.
memberp(X, [_ | R], Z) :- member(X, R, Z).

member(X, [X | R]) :- ! & [X | R].
member(X, [_ | R]) :-& member(X, R).

Now, member(1, [0,1,2,3,1,4,6]) succeeds only once (with the first solution).

A principal goal of this work will be to transform the deterministic memberp relation into the deterministic member function and both into the LISP-like LL-language for execution on the highly efficient stack machine LLAMA.

For providing some notation, as our highest-level relational (input) language we will use a sublanguage of RELFUN, here called REL, encompassing relations, the generalized is-primitive, as well as cut and once operators.

REL clauses will thus employ RELFUN's syntax, e.g. structures will be enclosed in square brackets, since this generalization is useful in the context of relational-functional languages (and can even enhance the readability of purely relational languages). Furthermore, RELFUN functions will be used as one of our intermediate representation languages in the transformation of REL into LL (section 4.2.3).