Prolog Goal Expansion
Jan Burse, created Oct 13. 2011
Before we started the new series 0.9.x of Jekejeke Prolog release we introduced goal expansion. We felt that without goal expansion the system would be incomplete although goal expansion is not mandated by the ISO core standard. The goal expansion can be switched off and on via the Prolog flag clause_expand. It is now by default switched on. The expansion mechanism itself is written in Prolog. If goal expansion is on the file consult routine will first call expand_term/2 and thus subsequently expand_goal/2 before it will assert a fact or rule.
If you are new to Prolog you might think of goal expansion as the C #define for Prolog. But there is a little difference. The Prolog goal expansion mechanism is syntax aware. The consult routine will do its expansion attempt not based on a string but based on the already parsed term. The Prolog goal expansion shares some properties of the C pre-processing. To define a goal expansion the end-user has to plug-in some goal_expand/2 facts or rules. By patterns or body conditions the end-user can provide conditional expansion. If a goal_expand/2 fact or rule fails the goal term is left unchanged. This can cover some of the C #ifdefine functionality albeit in a more dynamic fashion.
We might further compare the goal expansion mechanism with Lisp macros. Lisp macros are also syntax aware in that they work on S-expressions. But problems of variable scoping have led to a number of proposals for so called hygienic macros. The Prolog goal expansion mechanism on the other hand is not so much subject to variable scoping problems. Since goal_expand/2 facts or rules will provide new apart variables upon invocation establishing local variables in a rewrite comes for free. Further since predicates and modules cannot be locally introduced in a clause there is rarely confusion about predicate names.
To illustrate the working of goal expansion we have provided a little example. This example will list a few numbers and their squares. It will so in right adjust formatting the numbers. For convenience we have defined our own forthem/2 predicate. The predicate will allow us to perform the looping without any variable binding trace. A further convenience we have defined is the predicate printf/2. It is a very simple version that detects a single standing per cent sign (%) as a position for an expression that should evaluate to a number. We can run our little example by invoking the predicate squares/0 which has been defined as follows:
forthem(between(1,10,X),printf(' % * % = %\n',[X,X,X*X])).
We went then on to replace the definitions of forthem/2 and printf/2 by expansion rules. The expansion rule for forthem/2 is straight forward. No special measures for hygiene are necessary. The expansion can directly deal with goal arguments:
goal_expansion(forthem(C,A), \+ (C, \+ A)).
The expansion for printf/2 distinguishes two cases. We assume that the predicate is called with a second argument that is instantiated to a list. The first case is effective when the argument list is empty. In the generated code we will find a write statement for the formatting string:
The second case is effective when the argument list is non-empty. The rule will then dissect the given formatting string and consume an argument. In the generated code we will find a new local variable to hold the result of evaluating the argument. The rule will delegate the expansion of the rest of the arguments to the goal expansion mechanism by including a new printf/1 call in the expanded goal. This delegation is possible since the goal expansion mechanism repeats the expansion as long as changes are seen:
goal_expansion(printf(S,[E|T]), (write(P), H is E,
radjust(H), printf(Q,T))) :-
When we consult the Prolog text that makes use of goal expansion and when we perform a listing(squares/0) we will see the result of the goal expansion:
squares :- \+ (between(1, 10, X), \+ (write(' '), _B is X,
radjust(_B), write(' * '), _C is X, radjust(_C),
write(' = '), _D is X * X, radjust(_D), write('\n'))).
In practice one would not remove the definitions for forthem/2 and printf/2. They could be useful as a fall back when dynamically building goals that would contain these predicates. One can then also safely omit expansion when the second argument of printf/2 is a variable since code that would make use of such a call pattern can now fall back to the corresponding definitions.
The approach we took so far suggests a particular view on goal expansion. We can view it as a means for compile time partial evaluation of predicates. The goal_expansion/2 facts and rules basically define a partial evaluation strategy for the predicate at hand. And developing the goal_expansion/2 facts and rules can be done systematically. If a goal_expansion/2 clause has a body, then we find in the body the goals that are evaluated at compile time. In the return argument we find the goals that are supposed to be evaluated at runtime. The goal_expansions/2 facts and rules just defined the divide between compile time and runtime.
The aforementioned systematic development of goal_expansion/2 facts and rules can be shown correct as long as pure Prolog is involved. But in practice we often make use of impure Prolog predicates such as var/1 for term checking or \+/1 for the negation as failure. Impure Prolog predicates destroy the general validity of the systematic approach. Reasons for this deficiency can be found in a difference in the spill of variable bindings from the goal expansion to its context during compile time and under normal conditions at runtime. Examples are readily found, so for example the following two Prolog programs concerning var/1 do not work the same:
q(X) :- var(X), p(X). q(1) :- var(1).
Nevertheless goal expansion is a very attractive technique found in many Prolog systems. It has various application areas. Partially evaluated predicates run faster since a certain effort is done at compile time. This might be not so important for the squares example we have given here, but expanding predicates in hot spots can give additional speed. There are now quite a number of language features found in various Prolog systems which become only attractive through the speed gain of goal expansion. For example Jekejeke Prolog uses goal expansion for the implementation of DCGs. We will give more details and continue this topic in a subsequent blog entry.