[comp.lang.prolog] cut for meta-interpreter

raf@bu-cs.UUCP (04/17/87)

Does anybody know how to implement PROLOG meta-circular interpreter
with cut without using ancestor cut? Is there a clean way to implement
(both at PROLOG level and at meta-interpreter level) ancestor cut?

-Rafail Ostrovsky, raf@bostonu.CSNET
-- 
:- try,!.

kam@druhi.UUCP (MorrisseyKA) (04/20/87)

In article <6681@bu-cs.BU.EDU>, raf@bu-cs.UUCP writes:
> Does anybody know how to implement PROLOG meta-circular interpreter
> with cut without using ancestor cut? Is there a clean way to implement
> (both at PROLOG level and at meta-interpreter level) ancestor cut?

One solution is:

	execute(true) :- !.
	execute((P,Q)) :- !, execute(P), execute(Q).
	execute(P) :- clause((P:-Q)), execute(Q).
	execute(P) :- P.

It is attributed to Pereira (don't know which one) and can be found on
page 157 of:

	HOW TO SOLVE IT WITH PROLOG
	4th edition
	by H. Coelho, J. Cotta, and L. Pereira
	Lisbon, 1985

Karen A. Morrissey

raf@bu-cs.UUCP (04/23/87)

In response to my question  for meta-circular interpreter
which includes cut (without the use of ancesstor cut 
in the implementation!) Karen A. Morrissey proposes 
the "solution" which is just a regular meta-interpeter,
but DOES NOT incorporate cut!

Here is a possible solution which does incorporate cut and
is based on the assumption (which is true for C-prolog)
that cut cuts the goal choice-point rather then the 
disjunctive choice-point:

%-------------------------------------------------------
%  /* meta-circular interpreter with cut  */
%-------------------------------------------------------
%  Author: Rafail Ostrovsky                4/20/1987
%-------------------------------------------------------
%
solve(G) :- solve(G,_).
solve(!,X) :- var(X);X=cut.
solve((A,B),C) :- solve(A,C),solve(B,C).
solve(A,C) 
    :-  C==cut;
        (system_pred(A),!,A);
        (clause(A,B),solve(B,C1),(var(C1);C1==cut,!,fail)).
%-------------------------------------------------------

I do not know how to implement ancesstor cut (see Shapiro and
Sterling book) without the use of ancesstor cut at the meta-level,
and how to implement meta-circular interpreter with cut 
without the use of the above assumption. 
/raf

raf@bu-cs.UUCP (04/24/87)

> Does anybody know how to implement PROLOG meta-circular interpreter
> with cut without using ancestor cut? Is there a clean way to implement
> (both at PROLOG level and at meta-interpreter level) ancestor cut?
> 

% I have solved the question I have posed, so never mind.
% Here is the meta-circular PROLOG interpreter which includes 
% both "cut" and "ancestor cut". (For explanation of what
% "ancestor cut" is see Sterling and Shapiro book
% "the art of prolog"). A proof of correctness is going
% to appear elsewhere.

%----------------------------------------------------------
% meta-circular interpreter which includes 
% "cut", "ancestor cut", "or" and "not" at the meta-level. 
%----------------------------------------------------------
% Author: Rafail Ostrovsky                    4/23/1987
%----------------------------------------------------------
%
solve(G) :- solve(G,_).
solve(!,X) :- var(X);X=cut.
solve(ancestor_cut(Pred),X) :- var(X);X=Pred.
solve(not(A),C) :- not solve(A,C).
solve((A,B),C) :- solve(A,C),solve(B,C).
solve((A;B),C) :- solve(A,C);solve(B,C).
solve(A,C) 
  :-  nonvar(C);
      (system_pred(A),!,A);
      (  clause(A,B),
         solve(B,C1),
         (  var(C1); 
            (nonvar(C1),functor(A,C1,_),!,fail); 
            (C1==cut,!,fail); 
            (nonvar(C1),C=C1))).

system_pred(clause(_,_)).
system_pred(true).
system_pred(solve).
%----------------------------------------------------------
Example:

test(X) :- p(X),q(X).
test(X) :- q(X).

p(1).
p(2).
p(3) :- ancestor_cut(test).
p(4).

q(1).
q(2).
q(3).
q(4).

?- solve(test(X)) will succeed with X = {1,2,3}.

/raf

nabiel@erix.UUCP (Nabiel Elshiewy) (04/25/87)

I think you better take a look into the record of 1985 IEEE Symp. on 
Logic programming. You'll find the interpreter you need and a bit more
in an article there written by R. O'Keefe "On the treatment of cuts in 
prolog source-level tools", pp 68-72.