Next: Varying-Arity Structures Up: Relations Defined by Previous: Open-World DATALOG

## PROLOG-like Structures and Lists

Let us now proceed to PROLOG with structures and its RELFUN extensions. PROLOG has only constructor symbols and no defined function symbols; arguments to PROLOG relations must always be (passive) structures and can never be (active) calls. RELFUN, on the other hand, does support both of these categories, hence has a notational need to distinguish between them.

First consider the more basic distinction of relations on the one hand, and constructors and defined functions on the other hand: while mathematical accounts of first-order logic express the distinction by disjoint sets of relation (predicate) and function symbols, PROLOG just distinguishes predicate (top-level) and functor (sublevel) uses of these symbols, and permits the same symbol to occur as a predicate and as a functor. This permits metalogical reinterpretations of certain structures as goals (via call).

In the same interactive-programming spirit RELFUN does not distinguish active and passive functor symbols but just active and passive functor uses. For this we note that all functor uses take the form of applications, which we write with round parentheses for `active' operator calls and with square brackets for `passive' structured terms. In the relational part of RELFUN this means that only top-level relation calls are written with parentheses, PROLOG-like structures are written with brackets. (In the functional part both top-level and nested function calls will be parenthesized, too.)

Consider the successor constructor s, often used together with 0 for specifying invertible operations on natural numbers. Thus, while in PROLOG the structure corresponding to 2 is s(s(0)), in RELFUN it is s[s[0]]. For instance, the RELFUN lesseq relation definition

```
lesseq(0,N).
lesseq(s[M],s[N]) :- lesseq(M,N).```
permits the call lesseq(X,s[s[0]]) to generate the X-values 0, s[0], or s[s[0]].

N-element RELFUN lists, as in LISP and PROLOG, can be regarded as a short-hand for nested binary structures (we use the distinguished constructor ``cns'' instead of the usual ``.''). For example, the (non-ground) list [s[s[0]],[E,F],s[0]] reduces to the nesting cns[s[s[0]],cns[cns[E,cns[F,nil]],cns[s[0],nil]]]. A vertical bar in lists causes their cns-reduction to end with the element after the ``|'' (usually a variable) rather than with the distinguished constant nil. Thus, [X,Y|Z] reduces to cns[X,cns[Y,Z]]. This ``lists-to-structures'' transformation is used both for WAM compilation and mathematical formalization. Note that the sorted relation definition in PROLOG/RELFUN

```
sorted([]).
sorted([X]).
sorted([X,Y|Z]) :- lesseq(X,Y), sorted([Y|Z]).```
and its cns-reduced form in RELFUN
```
sorted(nil).
sorted(cns[X,nil]).
sorted(cns[X,cns[Y,Z]]) :- lesseq(X,Y), sorted(cns[Y,Z]).```
consistently employ square brackets to indicate the `passiveness' of lists and structures, while in PROLOG the cns-reduced form would employ round parentheses.

Next: Varying-Arity Structures Up: Relations Defined by Previous: Open-World DATALOG

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