How To Invent A Meta-interpreter For The Ancestor Cut

Appeared in Volume 7/4, November 1994

Keywords: meta-level, cut.

The designing of meta-interpreters for certain extensions of Prolog can be a difficult programming task. We illustrate a method which simplifies this task by applying one extension of Prolog to describe another one. Then partial evaluation is used to obtain the final meta-interpreter written directly in Prolog.

We assume an ancestor cut as a mechanism difficult to define by writing a meta-interpreter. In the first step, we introduce an exception handling mechanism to Prolog, increasing its expressiveness. Then we apply it to define the meta-interpreter for Prolog with the ancestor cut. Finally, using partial evaluation, we eliminate the exception handling extension. In such a way we obtain the desired meta-interpreter for the ancestor cut as a program written directly in ordinary Prolog.

Our exception handling mechanism is similar to the one discussed in [Meie89] and [Demo89]. The meta-interpreter supporting it is shown in the figure 1.

solve_except(true,noball).
solve_except((G,R),B):-
  solve_except(G,B1),
  ( B1 = ball(_),
    B=B1
  ; solve_except(R,B) ).
solve_except(exit_block(B),ball(B)).
solve_except(block(G,C,R),B):-
  copy_term(G,Copy),
  solve_except(Copy,B1),
  ( B1=ball(C),
    !,
    solve_except(R,B)
  ; G=Copy,
    B=B1 ).
solve_except(G,noball):-
  system(G),
  G.
solve_except(G,B):-
  clause(G,C),
  solve_except(C,B).

Fig. 1 The meta-interpreter for exception handling.

We assume that a block is abandoned deterministically if an exception signal arises inside it. Otherwise, the block is interpreted with no restrictions of backtracking. This allows to write the meta-interpreter for the ancestor cut as shown in figure 2.

solve_cut(true). 
solve_cut(!(_)). 
solve_cut(!(A)):-
  exit_block(A). 
solve_cut((G,R)):-
  solve_cut(G),
  solve_cut(R). 
solve_cut(G):-
  block((clause(G,B),solve_cut(B)),
         A,
         goto_ancestor(A,G)).

goto_ancestor(N,_):-
  number(N),
  N > 0,
  N1 is N - 1,
  exit_block(N1). 
goto_ancestor(A,G):-
  A=.._,
  A \= G,
  exit_block(A).

Fig. 2 The meta-interpreter for the ancestor cut written in Prolog with exception handling.

The ancestor cut is defined according to the description in [StSh86]. A result of using such a cut is similar to using the standard cut in the ancestor's clause (pointed by the parameter of the ancestor cut).

To apply the meta-interpreter solve_cut/1 to a goal G, we use the following query:

?-solve_except(solve_cut(G),B).

Now, we perform the specialization of the meta-interpreter solve_except/2 w.r.t. the meta-interpreter solve_cut/1 by partial evaluation. We obtain the procedure shown in the figure 3 as the result. This is the meta-interpreter for the ancestor cut written in ordinary Prolog.

solve_cut(true,noball).
solve_cut(!(_),noball).
solve_cut(!(A),ball(A)).
solve_cut((G,R),B):-
  solve_cut(G,B1),
  ( B1 = ball(_)
    B = B1
  ; solve_cut(R,B) ).
solve_cut(G,B):-
  clause(G,C),
  solve_cut(C,B1),
  ( B1 = ball(A),
    !,
    goto_ancestor(A,G,B)
  ; B = B1 ).

goto_ancestor(N,_,B):-
  number(N),
  N > 0,
  N1 is N - 1,
  B = ball(N1).
goto_ancestor(A,G,B) :-
  A =.._,
  A \= G,
  B = ball(A).

Fig. 3 The meta-interpreter for the ancestor cut compiled to ordinary Prolog.

The applied specialization algorithm uses unfolding and the "pushing down of meta-arguments".

During the partial evaluation, we heuristically eliminated calls to copy_term/2. In the meta-interpreter in figure 2 the exception signal is handled by the procedure goto_ancestor/2. This procedure sends the proper exception signal to one of its parents or causes failure, which makes the variables free in the interpreted goal. So, removing the call of copy_term/2 doesn't affect the procedural equivalence between solve_except/2 and its version specialized w.r.t. solve_cut/1.

The example illustrates how to collapse the meta-interpreter tower by means of partial evaluation. It seems that this method may be applied to other mechanisms. Also, this method is not restricted to Prolog and its extensions.

References

[BeLl90] K.Benkerimi, J.W.Lloyd: A Partial Evaluation Procedure for Logic Programs, in: Logic Programming, Proceedings of the North American Conference, MIT Press, 1990, pp.343-358.

[BuRu89] M.Bugliesi, F.Russo: Partial Evaluation in Prolog: Some Improvements about Cut, in: Logic Programming Proceedings of the North American Conference, MIT Press, 1989, pp.645-660.

[Demo89] B.Demoen: The Implementation of Catch and Throw in WAM: Optimizations and Alternatives, Report CW 99, Department of Computer Science K.U.Leuven, 1989.

[LaSt88] A.Lakhotia, L.Sterling: How to Control Unfolding when Specializing Intepreters, Case Western Reserve University, CES-TR-88-08, 1988.

[LaSt90] A.Lakhotia, L.Sterling: ProMiX: a Prolog Partial Evaluation System, in: L.Sterling (ed.) Th Practice of Prolog, MIT Press, 1990, pp.137-179.

[Meie89] M.Meier: Event Handling in Prolog, in: Logic Programming, Proceedings of the North American Conference, MIT Press, 1989, pp.871-887.

[Owen88] S.Owen: Issues in the Partial Evaluation of Meta-interpreters, in: H.D.Abramson, M.H.Rogers (eds.), Meta-Programming in Logic Programming, MIT Press, 1989, pp. 319-339.

[Sahl90] D.Sahlin: The Mixtus Approach to Automatic Partial Evaluation of Full Prolog, in: Logic Programming Proceedings of the North American Conference, MIT Press, 1990, pp.377-398.

[StSh86] L.Sterling, E.Shapiro: The Art of Prolog, MIT Press, 1986.

[VeDe88] R.Venken, B.Demoen: A Partial Evaluation System for Prolog: some Practical Considerations, in: New Generation Computing , 6, 1988, pp.279-290.

Jacek Martinek, Pawel Pietrzak
Technical University of Poznan
pl.Sklodowskiej-Curie 5
60-965 Poznan, Poland
Email: pawelp@ruby.poz.edu.pl