Algebraic types correspond to RUL programs, in which predicates are
deterministic and only have a single argument. The stepwise enhancement
paradigm has no such restriction, hence nondeterministic skeletons such as
branch/1 (Program 2b) and connected/2 (Program 9)
can be used.
connected(A, A).
connected(A0, A) :-
edge(A0, A1),
connected(A1, A).
Program 9: Transitive closure of the edge/2 relation
As noted in (Naish, [Nai96]), higher order logic programs can also be
nondeterministic and nondeterministic analogues of foldr can be
constructed. A version of foldr for paths in a graph was
written (using considerable intellectual effort) based on the simple
transitive closure procedure connected/2, above.
The close relationship between ``shape'' and stepwise enhancement we have
uncovered can be used to generalise the transformation from algebraic
types (or RUL programs) to foldr functions. From an arbitrary skeleton
(not necessarily a RUL program), we can generate an appropriate version
of foldr as follows.
=1pc0
Definition
6.1.(foldr transformation)
A procedure with A arguments and C clauses leads to a
higher order procedure with C+A+1 arguments. It has C
``higher order'' arguments and one additional ``result'' argument. The
recursive calls in the clause bodies have the same higher order arguments
as the head and new variables for their results. Each clause also has an
additional call/N with the higher order argument for that
clause, the variables in the head which did not appear in any recursive body
calls, result arguments of the body calls and the result argument of the
head. If this call has only two arguments then call/2 is
replaced by =/2 (the higher order argument is simply a term
which is returned for the base case; the call to =/2 can then be
optimised away, as in Program 7).
Mutual recursion can be treated in the same way. Each procedure in a set of (mutually recursive) procedures is transformed as above, where C is the number of clauses in the set of procedures. In the description of the transformation above and other transformations in Section 8 we refer to ``recursive'' calls. This should be interpreted as including mutual recursion when transforming multiple procedures. Our implementation of the tools introduced in Section 7 has been made more flexible by using an even more liberal definition: a call to any procedure defined in the input to the tool is considered recursive and C is the number of clauses defined in procedures indirectly called by a specified procedure.
For list/1 and tree/1 the results are the
foldr/4 and foldrbt/4 definitions given in
Programs 7 and 8. For branch/1 and connected/2
the results are in Program 10. The foldrcon/5 procedure here is
actually more general than the manually constructed version (which had
a base case of V=FB instead of call/3) and
can be used in the applications described in (Naish, [Nai96]).
Section 6.1 gives an example where a call is needed in the
base case.
foldrb(FL, FR, FB, leaf(X), V) :-
call(FB, X, V).
foldrb(FL, FR, FB, t(L,R), V) :-
foldrb(FL, FR, FB, L, V1),
call(FL, R, V1, V).
foldrb(FL, FR, FB, t(L,R), V) :-
foldrb(FL, FR, FB, R, V2),
call(FR, L, V2, V).
foldrcon(FE, FB, A, A, V) :-
call(FB, A, V).
foldrcon(FE, FB, A0, A, V) :-
edge(A0, A1),
foldrcon(FE, FB, A1, A, V1),
call(FE, A0, V1, V).
Program 10: Nondeterministic foldr for branch and connected