Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!munnari.oz.au!cs.mu.oz.au!ok From: ok@cs.mu.oz.au (Richard O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: Dynamic Properties Message-ID: <2672@munnari.oz.au> Date: 10 Nov 89 09:55:49 GMT References: <5500@ubc-cs.UUCP> <1350@gould.doc.ic.ac.uk> Sender: news@cs.mu.oz.au Distribution: comp.lang.prolog Lines: 228 In article <1350@gould.doc.ic.ac.uk>, cdsm@sappho.doc.ic.ac.uk (Chris Moss) writes: > In Quintus what you need is: > 1) solve(true). > 2) solve((A,B)) :- solve(A), solve(B). > 3) solve(X) :- \+(X=true;X=(_,_)), clause(X,Y), solve(Y). That's a rather inefficient way to do it compared with the method I showed. > Yes, it's a bit odd isn't it, and though Richard has argued against the > Sterling/Shapiro version I don't think he has a very good case. What stronger case can there be than "it doesn't work"? It is a _mistake_ to call clause(Head, Body) when Head is 'true' or (_,_); There _is_ a clause for (_,_) in several Prologs, and you definitely do not want to use it in this interpreter. (While it is the code found in Sterling and Shapiro, they did not invent it; it's not _their_ mistake. The code in the SICStus manual is correct.) > Instead of the negated bit above he prefers the 3rd clause as: > > solve(X) :- predicate_property(X, interpreted), > clause(X,Y), solve(Y). for the simple reason that that says precisely when it makes sense to try to look for a clause. In a previous posting in this thread I gave a still more efficient version, and I'm about to give it again. > There's another hidden problem: the obvious way to write my 3rd clause would > be X\=true, X\=(_,_) but Quintus, unlike Clocksin & Mellish, C-Prolog > etc. does NOT provide \=. I've never understood why. There are several reasons: (a) Quintus Prolog does not have \= as a built in predicate because it was originally designed to be compatible with DEC-10 Prolog, and DEC-10 Prolog does not have \= as a built in predicate. It was felt that most uses of \= were better done by other means, such as \== or =\=, or by if->then;else, and so on. While solve(true) :- !. solve((A,B)) :- !, solve(A), solve(B). solve(Head) :- clause(Head, Body), solve(Body). is not a brilliant method of writing a Prolog interpreter in Prolog, it is not *appallingly* inefficient, which solve(true). solve((A,B)) :- solve(A), solve(B). solve(Head) :- Head \= true, Head \= (_,_), clause(Head, Body), solve(Body) is. At this late date I _really_ should not have to explain why this code is inefficient. The Stony Brook Prolog compiler is one of the few that are smart enough to do something about it, but as I read the (2.5) manual you would have to code this as solve(Head) :- Head ?= true, Head = true. solve(Head) :- Head ?= (_,_), Head = (A, B), solve(A), solve(B). solve(Head) :- Head \= true, Head \= (_,_), clause(Head, Body), solve(Body). in order for it to spot the opportunity to put the cuts in. (This may be a misreading of the manual.) (b) It was felt that having not-always-sound negation was bad enough without adding not-always-sound-inequality. If you want the effect of \= and are willing to take responsibility for its soundness, you can write \+(X = Y) which is not as compact as X \= Y but is it really such a terrible thing? \= is after all vanishingly rare in good code. (c) Quintus the company *DOES* provide \=, just the same way that DEC-10 Prolog does, in a library package. It's even in the manual. library(not) provides: X \= Y identical to \+(X = Y), not always sound X ~= Y sound(*) inequality not(G) sound(*) negation (*) Sound in the sense that they report an error when it would be unsound to continue (that's precisely when the NU Prolog "sound" predicates would delay). > This of course is precisely the argument in favour of standardisation. Exactly. While I am of the opinion that anyone who writes X \= Y in his code rather than X ~= Y is asking for the trouble he is likely to get, (\=)/2 is now so widespread that it HAS to be in any credible standard. To give WG17 their due, it _is_ in WG17 Prolog. > The problem with that was that everyone wanted to standardise on the way > THEY did it. Not me. Never me. (Heck, if I had a BIM or ZYX manual, you'd find me beating WG17 over the collective head with _that_ as well.) > If you support a coroutining implementation of Prolog then > you argue that \= should be delayed until it is sufficiently ground. No you don't. You argue that _\=_ is an unsound inequality which happens to be provided in a number of Prologs (including NU Prolog and the Quintus library) but that a sound inequality should also be provided and should be spelled ~= (tilde equal) as it is in NU Prolog and the Quintus library. Just like NU Prolog provides two term comparison predicates: compare/3 acts exactly like DEC-10 Prolog and Quintus Prolog termCompare/3 is sound (NU Prolog does not provide infix forms of termCompare/3 other than = /2 and ~= /2; if you have the three-argument comparison that's almost always the one you want.) > Some people then argue that having @< for term less than > and \== for term inequality is inconsistent and hard to remember. Nobody has to stick with the built-in names: if you want to use $< for @< and $=\= for \== all you have to do is :- op(700, xfx, [$<, $=\=]). X $< Y :- compare(<, X, Y). X $=\= Y :- \+ compare(=, X, Y). and as long as the standard guarantees the existence and behaviour of compare/3 you are away laughing. The really interesting thing about the original question "how do I make all the predicates in a file of which it is known only that it is Prolog code dynamic" is that the person asking it didn't really want to make the predicates dynamic. The REAL question was "how do I put together a program which will let me _interpret_ the clauses in a file of which I know only that it is Prolog code?" Once you see it from that perspective, you realise that there is no need for the code to be loaded in the form of Prolog clauses at all, and we can use a coding which is better suited to interpretation. To get an idea of the difference that a better representation can make, I took the "triangle" example from Covington et al as I posted it last year (that's the peg jumping thing). The interpreter below was written using my knowledge of Quintus Prolog, but runs just fine in SICStus, and as SICStus Prolog's clause/2 and call/1 don't have to worry about a dynamic module system, I quote the SICStus times as likely to be more typical: Compiled Prolog: 1.14 seconds Interpreted with solve/1: 2.72 seconds (solve/1 compiled) Interpreted with interpret/1: 1.40 seconds (code below, compiled) That is, adopting a different representation for the clauses to be interpreted (and letting that representation be compiled) roughly doubled the speed for a small example (40-odd clauses). Having the program run about 23% slower when interpreted than when compiled isn't a bad trick. (As the heads of the clauses - and the code that builds the bodies - are compiled, this is not unlike a total-non-structure-sharing system.) As I recall it, turning h(X1,...,Xn) :- B into h(X1,...,Xn,B') was first described in this newsgroup by someone from BIM; sorry but I don't recall the name. translate_clause((Head :- Body), TableEntry) :- !, translate_head(Head, TableEntry, Body1), translate_body(Body, Body1). translate_clause(Head, TableEntry) :- translate_head(Head, TableEntry, true). translate_head(Head, TableEntry, Body) :- functor(Head, F, M), name(F, FName), name(G, [42 /* * */|FName]), N is M+1, functor(TableEntry, G, N), arg(N, TableEntry, Body), same_args(M, Head, TableEntry). same_args(N, Term1, Term2) :- ( N > 0 -> arg(N, Term1, Arg), arg(N, Term2, Arg), M is N-1, same_args(M, Term1, Term2) ; true ). translate_body(Var, call(Var)) :- var(Var), !. translate_body((A, B), and_then(A1,B1)) :- !, translate_body(A, A1), translate_body(B, B1). translate_body((A -> B ; C), if_then_else(A1,B1,C1)) :- !, translate_body(A, A1), translate_body(B, B1), translate_body(C, C1). translate_body((A ; B), or_else(A1,B1)) :- !, translate_body(A, A1), translate_body(B, B1). translate_body(\+(A), unprovable(A1)) :- !, translate_body(A, A1). translate_body(true, true) :- !. translate_body(G, system(G)) :- predicate_property(G, built_in), !. translate_body(Goal, user(TableEntry,Body)) :- translate_head(Goal, TableEntry, Body). slurp(File) :- asserta((term_expansion(X,Y) :- translate_clause(X,Y)), Ref), compile(File), erase(Ref). interpret(TopLevelGoal) :- translate_body(TopLevelGoal, Body), interpret_body(Body). interpret_body(call(X)) :- translate_body(X, Body), interpret_body(Body). interpret_body(and_then(A,B)) :- interpret_body(A), interpret_body(B). interpret_body(if_then_else(A,B,C)) :- ( interpret_body(A) -> interpret_body(B) ; interpret_body(C) ). interpret_body(or_else(A,B)) :- ( interpret_body(A) ; interpret_body(B) ). interpret_body(unprovable(A)) :- \+ interpret_body(A). interpret_body(true). interpret_body(system(G)) :- call(G). interpret_body(user(TableEntry,Body)) :- call(TableEntry), interpret_body(Body).