🚀 go-pugleaf

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).