🚀 go-pugleaf

In article <11500013@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes:
>There are certain extensions to pure Prolog which are commonly regarded
>as necessary for `real world' programming, namely:
>    o  set expressions (findall, etc.)
>    o  negation as failure
>Are these extensions really necessary, and why?
>They surely are not necessary for the purpose of computation, since pure
>Prolog is equivalent to the most powerful known model of computation.
                      ^^^^^^^^^^^^^ yes you _should_ use it
And in article <1790@etive.ed.ac.uk> jah@lfcs.ed.ac.uk (James Harland)
notes:
>[nearly everything omitted] I know that findall etc are
>strictly second-order, and that pure Prolog is strictly first-order, and so
>there is a mis-match.
There is not always a real mismatch!

          In some cases, such as the one You (Pat) have
     mentioned <<['3','+','7']>>, it is possible to
     have a much more convenient way to reason about
     "all solutions" in Prolog - more clearly: to rea-
     son about Prolog's nondeterminism. It is not
     applicable in general but it is useful and con-
     venient. With this programming methodology you can
     have to a limited degree a kind of data abstrac-
     tion. You can apply it when the set as an object
     of its own is not your primiary interest but when
     you want to state something about this set.

One of the first tasks when writing predicates is to  choose
appropriate  datastructures; and usually lists are chosen...
They are mostly (because of lack of time) never changed,  as
one  would  have  to rewrite a very large part of his predi-
cates. If one looks to OOPL's but also CLU one  gets  really
jealous   about   their  possibility  to  change  the  rep(-
resentation) of something so easily. A very boring thing  to
program  in  Prolog is similar to (don't flame me about that
comparison) iterators - say in CLU. This is  the  case  when
you make some treewalks on datastructures. You want to state
something about all elements -- more general all  solutions.
Universal  quantification  in deductive databases is to some
extend similar to it etc.etc.  I never saw it used as in the
following  - but maybe I'm wrong about that - every program-
mer does it unconsciously - indeed.
 
This method can only be applied  when  you  have  enumerable
sets  of  solutions,  when you can transform the predicate P
which describes the set of solutions to the following  form.
Please forgive me the misleading names.

        normalform(In,Out) :-
                compute(In,Intermediate),
                (show(Intermediate,Out); normalform(Intermediate,Out)).

The idea is that all nondeterministic parts which will  con-
tribute  to  the  set  of solutions are expressed by the ;/2
only. compute/2 should be thus deterministic.

Example: list/1 + member/2

    list([]).
    list([_|Xs]) :- list(Xs).

    member(X,[X|Ys]).
    member(Y,[X|Ys]) :- member(Y,Ys).
    <==>
    member(X,Xs) :- Xs = [X|_]; Xs = [_|Ys], member(X,Ys).
    <==>
    member(X,Xs) ;- Xs = [Y|Ys], (X = Y; member(X,Ys)).
    <==>

Final result:
    member(X,Xs) :- normalform([_|Xs],X).
    compute([_|Xs],Xs).
    show([X|_],X).

Example: tree/1 + member_tree/2

    tree(empty).
    tree(node(_,R,L)) :- tree(R), tree(L).

    member_tree(node(X,R,L),Y) :-
            X = Y; member_tree(R,Y); member_tree(L,Y)
    <==>
    member_tree(node(X,R,L),Y) :-
            X = Y; member(Z,[R,L]), member_tree(Z,Y).
    <==>
    member_tree(node(X,R,L),Y) :- X = Y; member_member_tree([A,B],Y).
            member_member_tree([X|Xs],Y) :-
                   member_tree(X,Y); member_member_tree(Xs,Y).
            <==>
            member_member_tree([node(X,R,L)|Xs],Y) :-
                   X = Y; member_member_tree([R,L],Y); member_member_tree(Xs,Y).
            member_member_tree([empty|Xs],Y) :-
                   member_member_tree(Xs,Y).
            <==>
            member_member_tree([node(X,A,B)|Xs],Y) :-
                   X = Y; member_member_tree([A,B|Xs],Y).
            member_member_tree([empty|Xs],Y) :-
                   member_member_tree(Xs,Y).
    <==>

Final result:
    member_tree(Y,X) :- normalform([node(_,X,empty)],Y).
    compute([node(_,R,L)|Xs],[R,L|Xs]).
    compute([empty|R],R).
    show([node(X,_,_)|_],X).

After this step the predicate stating p about all  solutions
is:
    forallnormalform(X) :-
            not compute(X,_).
    forallnormalform(X) :-
            compute(X,Y),
            show(Y,Z), 
            p(Z),
            forallnormalform(Y).

Instead of the declarative "not  compute(X,_)"  you'll  find
for tree/1 respectively list/1 empty and [].

Program transformation is funny  but  not  simple.  Most  so
called  program  transformations are done by hand and so are
the mine. (There might be some typos in it,  but  I  believe
the  <==> is right.) To take just the applications mentioned
having no completely general way to  do  this  is  no  great
disadvantage.   When  you  are  capable  to design some term
structures you'll also be  capable  to  define  the  related
"iterator".  The  advantage is just that it is not necessary
to rewrite your programs. You can play around with  the  rep
similar to OOPLs. After these steps you'll unfold show/2 and
compute/2 to get the predicate you  would  have  written  by
hand.

This programming style is in some  way  a  more  declarative
alternative  to  the  ad  hoc  map*  features  of functional
languages because the patterns of recursion are explained by
logical  quantification.  In  Hope  for example you could do
this too, however list/1 and tree/1 would be a type _defini-
tion_  only.  How the related iterators depend on these type
definitions, how they can be generated,  remains  mysterious
in Hope.


Ulrich (ulrich@vip.at ~ UUCP: ...!mcvax!tuvie!vip!ulrich)