Plang uses a continuation-based model for implementing p_context_execute_goal(). The mathematical foundations we adopted can be found in section 2 of the following paper:
Mathematically, a goal is a function that operates on three continuations: success, fail, and cut-fail. Evaluating the goal produces a new set of success, fail, and cut-fail continuations. In Plang, goals are represented as nodes in a graph, with the success and cut-fail continuations represented as outgoing links to other nodes. The fail continuation is a pointer to a node that is stored in the execution state with the pointer to the current node.
The execution state has two node pointers: the current node to execute, and the "fail point" node. A goal node operates on this state and outputs two new values for the current node and "fail point".
Some examples of goal execution:
Upon back-tracking, the current node is set to the "fail point", and the "fail point" is set to the "cut fail point" of the new current node. If "fail point" is NULL when back-tracking is requested, then a top-level goal failure has occurred.
Top-level goals are prepared for execution by creating a new current node for the goal G. The "success" and "cut fail point" links on the goal node are set to NULL. The "fail point" is also set to NULL.
A top-level goal succeeds once the current node becomes NULL (because a "success" link was encountered that was NULL). The top-level goal is re-executed by setting the current node to "fail point", and "fail point" to the "cut fail point" of the new current node. All solutions are exhausted once "fail point" becomes NULL on a top-level goal.
The paper above does not describe the handling of catch/3 and throw/1 in a Prolog environment. We extend the mechanism by adding a "catch point" continuation link to the execution state. When a catch/3 goal is executed, the "catch point" link is set to point at the catch/3 goal, with the previous "catch point" saved in the new catch point node.
When a throw/1 is executed, a backtrack is performed to the "cut fail point" of the catch node. Execution proceeds from the catch point with the recovery goal if the catch term matches. If the catch term does not match, the process repeats to find the next-outer "catch point" node. If the "catch point" is NULL, then the top-level goal has finished with a thrown error.
The current "catch point" is saved in fail nodes so that it can be restored upon backtracking. The "catch point" also needs to be restored when the body of the catch/3 succeeds. We handle this by inserting a special $$pop_catch goal as the success continuation for the body goal.
The standard semantics for predicate execution is to try each clause in turn until one succeeds. Upon backtracking, the next succeeding clause is chosen, until there are no more clauses. This can be very inefficient if there are lots of clauses associated with a predicate. For example, evaluating X == Y with the following predicate will involve trying a lot of irrelevant clauses first:
eval(A + B, Result) { ... } // clause 1
eval(A - B, Result) { ... } // clause 2
eval(A * B, Result) { ... } // clause 3
eval(A / B, Result) { ... } // clause 4
eval(-A, Result) { ... } // clause 5
eval(A && B, Result) { ... } // clause 6
eval(A || B, Result) { ... } // clause 7
eval(!A, Result) { ... } // clause 8
eval(A == B, Result) { ... } // clause 9
...
eval(A, Result) { ... } // clause N
The usual solution to this performance problem is indexing. One of the arguments is used to create an index that maps an incoming value to a list of clauses that are most likely to match that kind of value. In the case of (==)/2, the index will list clauses 9 and N (a variable matches any incoming value). Now only those two clauses need to be tried when we evaluate X == Y; we can safely assume that all other clauses will fail without trying them explicitly.
Plang indexes predicates with more than four clauses. When the fifth clause is added, Plang inspects the current clauses to determine the best argument for indexing. The best argument is that which changes the most from clause to clause; usually the first, but could be the second for class member predicates (the first argument to class member predicates is the Self variable).
After the index argument has been chosen all of the clauses are inserted into a red-black tree. The tree maps the top-level functor, atom, string, or number in the index argument to a list of clauses that matches that top-level type. Clauses without a top-level type (usually those that have a variable in the index argument) are added to a separate list.
When a predicate is called, the top-level type of the incoming argument value is used to look up the relevant clause list in the red-black tree. This list is merged with the separate variable clause list to produce the list of clauses to be tried in order. If the incoming argument value is a variable, then all clauses in the predicate are tried in order.
Plang compiles clauses into a modified form of the Warren Abstract Machine (or "WAM"). We will only skim over the details in this page. The best reference on the WAM is the following book:
The following modifications to the traditional WAM are noteworthy:
switch_on_term and switch_on_constant are not used. To illustrate the differences between static and dynamic compiled forms, consider the following example clause:
a(5, f(Y, b))
{
c(X);
d(X, Y);
}
The dynamic version of the clause is compiled into the following code, which performs get instructions on each of the arguments, and a put instruction for the clause body:
get_constant 5, X0 get_functor f/2, X1 unify_variable X2 unify_atom b put_functor ','/2, X3 set_functor c/1, X4 set_variable X5 reset_argument X3, 1 set_functor d/2, X4 set_value X5 set_value X2 return X3
Dynamic clauses are executed by p_term_unify_clause() and return the body as a callable term to be executed by the engine. Dynamic clauses complete deterministically with either success or failure. Non-determinism is provided by the caller when it executes the body term.
1.6.1