RELFUN from a PROLOG point of view                (22-Oct-97)

Harold Boley

RELFUN has much in common with PROLOG, but differs in several important respects. The following list introduces some of the most notable RELFUN characteristics from a PROLOG point of view.
  1. There are functions such as square, which can be called like relations (i.e. as a prefix to parenthesized arguments) such as in square(3), and which return values. Thus, function calls can be nested, call-by-value, into other operator (function or relation) calls as illustrated by <(square(3),+(2,3,5)).  Even built-in RELFUN operators such as the polyadic + and < are written in prefix notation.  Relations can be defined by Horn clauses, much like in PROLOG.  Functions can be defined by directed equations, either unconditionally as in square(X) :& *(X,X). or conditionally as in square(X) :- numberp(X) & *(X,X). Conditional equations thus are like PROLOG clauses with an ampersand--instead of a comma--preceding the value to be returned. RELFUN functions may--like PROLOG relations--bind free actual arguments.
  2. Since (round) parentheses are used--as in mathematics and most programming languages--to denote active function and relation calls, [square] brackets are used to denote passive structures (i.e. constructor applications), such as in address[dfki,kl,de].  Even when there are no function calls, the use of brackets for structures --as for lists--is clearer than PROLOG's use of parentheses for both relation calls and structures: it sets apart calls like works(ludwig,address[dfki,kl,de]) from nested structures like room[wittgenstein,address[dfki,kl,de]].
  3. Higher-order notations are permitted for functions, relations, and constructors by allowing them to be, e.g., structures as in twice[square](3), partition[<](2,[3,2,1],Sm,Gr),  and address[office][dfki,kl,de]. Free variables are also allowed in operator positions as in R(john,mary), querying for arbitrary relationships between fixed individuals.
  4. PROLOG's cut operator in RELFUN is viewed as a determinism specifier not only for relations but also for functions, which is natural since RELFUN functions may--again like PROLOG relations--non-deterministically enumerate several solutions. For instance,  these are (cutless) definitions of a non-deterministic membrn relation and membfn function:
  5. membrn(X,[X|R]). membfn(X,[X|R]) :& [X|R].
    membrn(X,[Y|R]) :- membrn(X,R). membfn(X,[Y|R]) :& membfn(X,R).

    E.g., membfn(fone,[email,fone,web,fone]) enumerates the values [fone,web,fone] and [fone].  But the following (neck-cut) definitions specify a membrd relation and membfd function deterministically, thus confining themselves to the first of the above solutions:

    membrd(X,[X|R])!. membfd(X,[X|R]) !& [X|R].
    membrd(X,[Y|R]) :- membrd(X,R). membfd(X,[Y|R]) :& membfd(X,R).

  6. For pure DATALOG, the syntax of RELFUN does not differ from the one of PROLOG. However, as indicated in 2., PROLOG structures like address(dfki,Site,de) in RELFUN become address[dfki,Site,de], while PROLOG's parenthesized notation in RELFUN would try to call address as an active operator. PROLOG's vertical bar for rest lists in RELFUN is generalized to arbitrary polyadic structures and calls, and may occur immediately after an opening bracket or parenthesis. PROLOG's  is-primitive in RELFUN becomes .=, which permits arbitrary user-defined right-hand-side functions, rather than just arithmetic built-ins. PROLOG's clauses are generalized for value returning by replacing the right-most conjunctive comma by an ampersand (conditional equations), where :- & may be joined to :& (unconditional equations). The cut is regarded as part of the clause syntax (replacing a comma), not as a kind of argumentless built-in call (between commas); for neck cuts, it may be joined with :- or :& to !- or !&. Unlike in PROLOG, top-level calls are not terminated by a period, since this is again considered as part of the clause syntax.
  7. PROLOG's bagof is replaced by RELFUN's tupof primitive, which returns its list of solutions as--cf. 4.--in tupof(membfn([fone,Nr],[[email,_],[fone,311],[web,_],[fone,312]])), returning [[[fone,311],[web,_],[fone,312]],[[fone,312]]].  PROLOG's negation as failure or \+ in RELFUN is naf; the once primitives are the same. RELFUN's arithmetic and list built-ins, however, where mostly inspired by LISP. The command builtins shows built-in functions, relations, and extra-logicals; help shows further commands, of which more or m replaces PROLOG's semicolon for obtaining further solutions. There is a prelude containing--among many other definitions--a LISP-list-like function tup(|Elems) :& [|Elems]. for listifying a variable-length sequence of call-by-value evaluated elements.
  8. Functions can be transformed into PROLOG-like relations by RELFUN's relationalize and rf2pro commands; deterministic relations can be transformed into LISP-like functions by its FLIP package. Still, the direct availability of all the RELFUN operator kinds has turned out to provide a natural functional-logic integration idiom for various applications. The semantic formalization of pure RELFUN parallels SLD resolution and Herbrand models for pure PROLOG. Full RELFUN is available as an interpreter written in LISP; for efficiency, the RELFUN compiler expands on PROLOG's WAM technology, using an emulator rewritten in C.