Path: utzoo!utgpu!attcan!uunet!mcvax!tuvie!brock From: brock@tuvie (Inst.f.Prakt.Info 1802) Newsgroups: comp.lang.prolog Subject: Re: Higher Order Extensions Message-ID: <685@tuvie> Date: 21 Apr 89 14:32:11 GMT References: <11500013@hpldola.HP.COM> <1790@etive.ed.ac.uk> Reply-To: ulrich@vip.UUCP (Ulrich Neumerkel) Organization: Technical University of Vienna, EDP-Center Lines: 144 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)