We've seen how to extend our meta-interpreter to interpret built-ins like is/2. The technique is the same for other simple built-ins like is/2 and >/2.
The cut, however, is one built-in that isn't as easy to simulate.
In this example we'll see how it can be approximated fairly well using the mechanism of throwing and catching exceptions.
% Example 19 - Meta-Interpreter For The Cut
fruit(apple).
fruit(orange) :- !.
fruit(banana).
% meta-interpreter that handles the cut
prove(true) :- !.
prove(!) :- !, ( true ; throw(cut_exception) ).
prove((A,B)):- !, prove(A), prove(B).
prove(H) :-
catch((clause(H,B), prove(B)), cut_exception, fail),
write(H), write(" ← "), writeln(B).
Our example uses the same program we used to introduce the cut.
Incorrectly Interpreting The Cut
Let's look again at how we implemented unification =/2 in our meta-interpreter.
prove(A=B) :- !, A=B.
When the meta-interpreter finds a goal of the form A=B, this rule executes A=B, thus achieving the effect of attempting to unify A=B, which can either succeed or fail. The cut here prevents the more general prove(H) being matched if this rule prove(A=B) has matched.
Let's look at an example of implementing another built-in, the arithmetic assignment is/2.
prove(A is B) :- !, A is B.
Again, this rule will match goals of the form A is B, and execute A is B, which has the desired effect of attempting to assign the arithmetic evaluation of B to A.
Now let's examine a naive attempt at simulating the cut, following the same pattern.
prove(!) :- !, !.
Imagine our meta-interpreter is interpreting a rule H which has a cut as one of its goals. The meta-interpreter rule prove(!) will match that goal. This rule will succeed because cuts always succeed. This achieves the first effect of a cut. The second effect of a cut is to prevent backtracking. This doesn't work as we'd like because the cuts in prove(!):-!,! only prevent backtracking in the rule prove(!), and not in the rule H.
This is the reason we need a different approach to implementing the cut. We need a way to send a message from prove(!) back to the meta-interpreting of the parent rule H.
Throwing & Catching Exceptions
Like many languages, prolog supports the throwing and catching of exceptions.
If you're not familiar with this idea, think about prolog stopping when a problem occurs, for example running out of memory due to an endless search. When prolog runs out of memory it throws an exception related to the problem. That exception can be thought of as a special signal, sent with a higher priority than the program itself, which causes the program to be paused. Such signals, or exceptions, are intended to be caught, and handled appropriately. By default, an out of memory exception is caught by prolog itself, handled by printing out an error message and aborting the program.
Let's look at an example. The following defines bad(X), intentionally designed to cause an endless search that runs out of memory.
% bad/1 will cause a resource error
bad(X) :- bad(bad(X)).
If we issue a query bad(X), after a short while, the program will crash and an error message will be printed out.
?- bad(X).
Stack limit (0.2Gb) exceeded
Stack sizes: local: 2Kb, global: 0.2Gb, trail: 0Kb
Stack depth: 13,390,437, last-call: 100%, Choice points: 12
...
What we see is prolog's exception handler for this resource error printing out an explanation of what went wrong.
We can catch and handle exceptions by declaring an interest in a specific one, or asking to catch all exceptions. To do this we use catch(Goal, Exception, Handler), where Goal is the goal from which we expect an exception, Exception is the type of exception, and Handler is another goal which will run in response to an exception being caught.
The following asks prolog to catch any exception raised from the goal bad(X), and write out a representation of that exception. Because E is a variable, it will match any exception.
?- catch(bad(X), E, write(E)).
error(resource_error(stack),
stack_overflow{choicepoints:13,
depth:13390419, environments:19,
globalused:209227, localused:3,
stack:
...
Let's have a look at throwing our own custom exception.
% numerology(X) throws an exception if X=13
numerology(X):- \+ X=13.
numerology(X):- X=13, throw(unlucky).
% testnumber handles that exception
testnumber(X) :- catch(numerology(X), unlucky, writeln("unlucky number")).
The property numerology(X) succeeds if X cannot be unified with 13. If however X=13, then it throws a custom exception, which we've named unlucky.
The property testnumber(X) uses catch/3 to call numerology(X), watch for exceptions of the type unlucky, and handle them by printing “unlucky number”. Let's test it with 12 and 13.
?- testnumber(12).
true
?- testnumber(13).
unlucky number
true
We can see an exception was raised and caught in the case X=13. Notice how the prolog program did not abort after the exception was handled. It continued until it completed, reporting true. Exceptions don't abort a program unless the handler explicitly tells prolog to.
Meta-Interpreting The Cut
Having seen how to throw, catch and handle custom exceptions, we can now explore how to meta-interpret the cut.
The following is a new definition for prove(!).
prove(!) :- true.
prove(!) := !, throw(cut_exception).
When the meta-interpreter finds a cut, it wants to execute prove(!). The first rule matches and succeeds with a true. Although it may appear redundant, this success is what allows solutions in the interpreted cut's parent clause to be confirmed.
The second rule also matches and throws a custom exception, which we've called cut_exception. The lack of a cut in the body of the first rule allows this second one to execute.
The following uses prolog's semicolon ; to write the two rules as one. The semicolon means disjunction “or”, just like the comma means conjunction “and”.
prove(!) := !, (true; throw(cut_exception)).
We've already talked about why the handling of this exception needs to relate back to the entire rule in whose body the cut was found. Let's see how this is achieved.
prove(H) :-
catch((clause(H,B), prove(B)), cut_exception, fail),
write(H), write(" ← "), writeln(B).
The catch/3 here asks to register an interest in the cut_exception from the grouped goals (clause(H,B),prove(B)), not just prove(B), even though the exception can only come from prove(B). We'll see why soon. The handling of the exception is simply to fail.
Let's walk through how this works, step by step.
- If the rule for
Hhas a cut!in its bodyB, then it will eventually be matched byprove(!). prove(!)will succeed with atrueand confirm any solutions found up to that point.- On backtracking
prove(!)will also throw a custom exception given the namecut_exception. - The
cut_exceptionwill be caught in the context of calling the grouped goals(clause(H,B),prove(B)). - The handling of this
cut_exceptionis simply tofail. That means the full(clause(H,B),prove(B))is failed.
At this point, any goals in the body B before the cut have already been meta-interpreted and executed, with any solutions found remaining valid. This mirrors how the cut works in prolog itself.
When the cut is reached, the entire (clause(H,B),prove(B) is failed. Because clause(H,B) is failed, no further attempts are made to find additional rules which also have a head H. The effect of this is to prevent further backtracking for the rule H. This also mirrors how the cut works in prolog.
Phew! This is probably the most complicated prolog we'll encounter on this particular journey, so feel free to work through it several times.
Testing
Let's remind ourselves of the expected behaviour of the program we want to meta-interpret.
?- fruit(X).
X = apple
X = orange
The solution X=banana is excluded by the cut in fruit(orange):-!.
Let's test our enhanced meta-interpreter.
?- prove(fruit(X)).
fruit(apple) ← true
X = apple
fruit(orange) ← !
X = orange
Success! Our meta-interpreter has correctly simulated the cut. The printed explanations also give a visual clue as to why no more solutions were found after X=orange.
Limitations
This approach to meta-interpreting the cut is relatively simple, given the non-trivial effect the cut actually has on the execution of prolog. This simplicity brings with it some limitations.
First, this approach is computationally heavy, because throwing and handling exceptions is expensive. Exceptions are meant to be thrown, well, by exception, and not used in the normal execution of programs.
Second, in the unlikely case the program to be meta-interpreted throws an exception of the type cut_exception, this approach will collapse.
Key Points
- Because the cut effects the execution of its parent clause, it cannot be meta-interpreted in the same way as simple built-ins like
=/2. - The cut's behaviour can be approximated by throwing an exception when the cut is meta-interpreted, with the handler scoped to fail the group
(clause(H,B), prove(B)). This results in no further searches for rules that match the parent goalH. - This method has limitations. Throwing and catching exceptions is computationally expensive. The method will also fail if the program to be interpreted throws exceptions of the same type.