ok@cs.mu.oz.au (Richard O'Keefe) (11/06/89)
In article <5500@ubc-cs.UUCP>, kean@faculty.cs.ubc.ca (Alex Kean) writes: > 1) solve(true). > 2) solve((A,B)) :- solve(A), solve(B). > 3) solve(X) :- clause(X,Y), solve(Y). That's a pretty awful interpreter. (Yes, I know it's common.) > I guess I was surprised when the above program would not run in Quintus > Prolog upon any backtracking. You haven't got a copy of my tutorial notes, then! > 1) As I understand, the dynamic/static property is useful for compiler > optimization. If the default is static, then the compiler can optimize > without fear since the predicate cannot be altered. Am I correct? No. A static predicate cannot be *altered* (by assert or retract) but it can be *replaced* (by abolishing it and then adding a new predicate, or by compiling a file which redefines the predicate). The point of predicates being static by default is to ensure that you don't change anything *accidentally*. (Also, a :- dynamic declaration is used to tell the system "it is ok for this predicate to have no clauses.") One of the things which commonly went wrong in DEC-10 Prolog programs was that you would do p :- q. % these two lines r, % were switched s. and this would quietly be taken as a definition of (r,s) and that definition would be as quietly forgotten. (It was even worse in a Prolog interpreter I used once which would take it as a definition of (r,s) and redefine (',')/2...) This is just one of the reasons why any attempt to treat a built-in predicate inappropriately is reported. In this case, there is a built-in predicate called (',')/2. As it happens, there *IS* a clause for that predicate in the system, and you *really* do not want to get a copy of it. > 2) Is there an obvious solution to my problem that I am missing ? Yes. /*1*/ solve(true) :- !. /*2*/ solve((A,B)) :- !, solve(A), solve(B). /*3*/ solve(X) :- predicate_property(X, built_in), !, call(X). /*4*/ solve(X) :- clause(X, Y), solve(Y). I've added clause /*3*/ so that your interpreter can do arithmetic and such. The point is, once your clause 1) or clause 2) has been selected, there really is no point at all in ever considering any of the other clauses, so a cut is appropriate. Even if it was not needed to prevent calling solve(true) or solve((_,_)), you would still want it for efficiency. > 3) As I am not a Prolog expert, I am speaking from a user point of > view. I use high level programming languages because I want fast > prototyping capability to test out my theorems and lemmata. > In this situation, I find myself *not* testing my result but rather > combating with different systems specific capabilities and drawbacks. > Is my experience unwarranted? Yes. You *were* testing your code, which was broken to start with. What you wrote does NOT mean what you thought it meant, and some Prolog systems report that and some don't. Just to re-emphasize that the code was broken: one of the Prologs around here has a clause true. in it, which would show up in clause/2 as ?- clause(true, true). if the call clause(true, Y) were not blocked somehow. Then 'true' would have infinitely many proofs, which is not a very good idea. Quintus Prolog and NU Prolog both have clauses for (',')/2 as well. (There is much more to say about this, but I've got to leave something for the book.)
cdsm@sappho.doc.ic.ac.uk (Chris Moss) (11/09/89)
In article <5500@ubc-cs.UUCP> kean@faculty.cs.ubc.ca (Alex Kean) writes: > I proceed the experiment by using the meta-interpreter >defined by Sterling and Shapiro in their book (The Art of Prolog): > > 1) solve(true). > 2) solve((A,B)) :- solve(A), solve(B). > 3) solve(X) :- clause(X,Y), solve(Y). > >I guess I was surprise when the above program would not run in Quintus >prolog upon any backtracking. After understanding the debugging >behavior, I realized that upon backtracking, the term (A,B) in clause >(2) is unifiable with X in clause (3) and when the call of > > clause((A,B),Y) in clause(3), > >Quintus prolog reply with "attempting to use clause/2 on static predicate.." > 2) Is there an obvious solution to my problem that I am missing ? 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). 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. Instead of the negated bit above he prefers the 3rd clause as: solve(X) :- predicate_property(X, interpreted), clause(X,Y), solve(Y). and you then have to provide the appropriate definition, which by now should be child's play! 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. > > 3) As I am not a Prolog expert, I am speaking from a user point of > view. I use high level programming languages because I want fast > prototyping capability to test out my theorems and lemma. > In this situation, I find myself *not* testing my result but rather > combating with different systems specific capabilities and drawbacks. > Is my experience unwarranted ? This of course is precisely the argument in fovour of standardization. The problem with that was that everyone wanted to standardize on the way THEY did it. The set of comparison operators is a good example of the trouble this causes. In sequential Prolog one really needs 3 sets: arithmetic, term ordering and unification (equality and inequality). So that comes to a fair packet (at least 14). If you support a coroutining implementation of Prolog then you argue that \= should be delayed until it sufficiently ground. If you support constraints, then you want to allow arithmetic inequalities to be partially instantiated. Some people then argue that having @< for term less than and \== for term inequal is inconsistent and hard to remember. And so on. Now read on on the discussion of standards... Chris Moss.
ok@cs.mu.oz.au (Richard O'Keefe) (11/10/89)
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).