Next: wang: On-the-Fly Construction Up: The Logic/Functional Style Previous: The Logic/Functional Style

serialise: Inplace Updates of Non-Ground Structures

After the density database, the second practical PROLOG example given in [WPP77] is the relational serialise program. Its task is to transform a list of items into a corresponding list of their alphabetic serial numbers; e.g., [p,r,o,l,o,g] should become [4,5,3,2,3,1].

The subrelations of serialise demonstrate the use of the ``logical'' variable: first pairlists binds a request variable to a non-ground list of free variables (the prospective answer list), e.g. [Y1,Y2,Y3,Y4,Y5,Y6], and another request variable to a corresponding list of non-ground structures, e.g. [pair[p,Y1],pair[r,Y2],pair[o,Y3],pair[l,Y4], pair[o,Y5],pair[g,Y6]], thus generating two variable-coupled ``incomplete data structures''; then arrange (quick)sorts the list of pairs into a binary tree, calling a partition relation that uses the items in the first pair arguments for (string) comparison (unifiable non-ground terms are considered as duplicates to be identified by the first partition clause, e.g. joining pair[o,Y3] and pair[o,Y5] via Y5 = Y3); now numbered can count the ascending items, left to right, at the fringe of the tree and note the resulting serial numbers by ``inplace updates'' in the second pair arguments, which by logical-variable equality instantiate pairlists' prospective answer list to the final, ground result.

Although this binary serialise relation can be called like serialise([p,r,o,l,o,g], [4,5,3,2,3,1]), to check the relationship, and like serialise([p,r,o,l,o,g], S), to generate the list of serial numbers, it cannot be called like serialise(I, [4,5,3,2,3,1]), to generate all item lists mapping to given serial numbers (the comparison relation, e.g. the string< builtin below, expects constant items): the main serialise algorithm just employs a relational syntax to express a non-invertible function from item lists to serial-number lists, while it does make an essential, ``two-results'' use of the subrelation partition and of intermediate non-ground terms.

Therefore it appears natural to reformulate serialise in RELFUN's non-ground functional style, keeping the partition relation and intermediate non-ground returned values. Relationship-checking calls will then look like [4,5,3,2,3,1] is serialise([p,r,o,l,o,g]), an is-call containing a ground function call for serial-number generation as its rhs. The above explanation for the relational version can be transferred to this functional one by noting that the ``principal result'' is now always returned as a value instead of being bound to a request variable: the pairlists non-ground function only binds its prospective-answer result for use as serialise's foot premise R, but directly returns the list of pairs to the arrange function, which again returns its non-ground tree to the first argument of the self-nested numbered function.


serialise(L) :- numbered(arrange(pairlists(L,R)),1) & R.

pairlists([X|L],[Y|R]) :-& tup(pair[X,Y]|pairlists(L,R)).
pairlists([],[]) :-& [].

arrange([X|L]) :-
    partition(L,X,L1,L2),
    T1 is arrange(L1),
    T2 is arrange(L2) &
    tree[T1,X,T2].
arrange([]) :-& void.

partition([X|L],X,L1,L2) :- partition(L,X,L1,L2).
partition([X|L],Y,[X|L1],L2) :-
    before(X,Y), partition(L,Y,L1,L2).
partition([X|L],Y,L1,[X|L2]) :-
    before(Y,X), partition(L,Y,L1,L2).
partition([],Y,[],[]).

before(pair[X1,Y1],pair[X2,Y2]) :- string<(X1,X2).

numbered(tree[T1,pair[X,N1],T2],N0) :-&
    numbered(T2,1+(N1 is numbered(T1,N0))).
numbered(void,N) :-& N.
Note that the body of the first arrange clause can be simplified to partition(L,X,L1,L2) &tree(arrange(L1),X,arrange(L2)) if tree is defined as a self-passivating function or, similarly, if 3-tups are used instead of labeled binary trees (cf. subsection 3.2). Also notice that numbered `updates' the pair structures at the roots of the tree structures by is-binding the unavoidable logical variable N1 to the recursion result obtained from traversing the left subtree T1, a value which is incremented by 1+ for use in traversing the right subtree T2. This works since RELFUN's is-builtin both binds and returns the value of its rhs.

Finally, we can extract a reusable, parameterized sorting specification from the serialise program, thus simplifying the remaining specification. For this, the quicksort function qsort on lists is made generic wrt list-element types through an element-comparison relation Cr used as parameter. Applied to a non-empty list, arrange returns the value of a labeled binary tree constructor/function call, while qsort returns the value of our functional list concatenator appfun (incidentally, the argument order of partition and some clause orders are changed):


qsort[Cr]([]) :-& [].
qsort[Cr]([X|Y]) :- partition[Cr](X,Y,Sm,Gr) &
   appfun(qsort[Cr](Sm),tup(X|qsort[Cr](Gr))).

partition[Cr](X,[],[],[]).
partition[Cr](X,[X|Z],L1,L2) :- partition[Cr](X,Z,L1,L2).
partition[Cr](X,[Y|Z],[Y|Sm],Gr) :-
           Cr(Y,X),  partition[Cr](X,Z,Sm,Gr).
partition[Cr](X,[Y|Z],Sm,[Y|Gr]) :-
           Cr(X,Y),  partition[Cr](X,Z,Sm,Gr).
With qsort ``modularized out'' in this higher-order manner (Cr = before), serialise becomes a very concise function:

serialise(L) :-
  numbered(qsort[before](pairlists(L,R)),1) &
  R.

pairlists([],[]) :-& [].
pairlists([X|L],[Y|R]) :-& tup([X,Y]|pairlists(L,R)).

before([X1,Y1],[X2,Y2]) :- string<(X1,X2).

numbered([],N).
numbered([[X,N]|R],N) :- numbered(R,1+(N)).
It is now most easily observed that a ground call such as serialise([d,a,l,l,a,s]) via the non-ground call (with numbered operating here on qsort's list-of-lists value) numbered([[a,Y2],[d,Y1],[l,Y3],[s,Y6]],1) &[Y1,Y2,Y3,Y3,Y2,Y6] returns the ground value [2,1,3,3,1,4].



Next: wang: On-the-Fly Construction Up: The Logic/Functional Style Previous: The Logic/Functional Style


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