Attribute Variables

The Jekejeke Minlog extension finally provides attribute variables. These variables provide the glue between the forward chaining engine and the native Prolog unification. Access is possible in both directions.The forward chaining engine is based on the Jekejeke Minlog toolbox which provides trailed database updates. For the attribute variables we had to build a second toolbox. The second toolbox provides all the ingredients that are needed to make attribute variables work and to connect them with the forward chaining engine.

Attribute variables are found in various Prolog system implementations. There is currently no standard concerning attribute variables in terms of a fixed programming interface. Nevertheless there is a common understanding what functionally attribute variables should provide. In our design attribute variables have been conceived as a sub-class of ordinary variables. All our Prolog code that deals with variables went unchanged, since both classes implement the same interface. Nevertheless there are differences in the implementation.

The main difference is how attribute variables react during unification compared to ordinary variables. Ordinary variables do not have some preference during variable aliasing. We just instantiate the variables based on the way the unification problem was posed to the interpreter. For better performance we choose a unification argument order during clause invocation, so that head variables are bound to goal variables. This reduces the length of instantiation chains. But when using the =/2 predicate the end-user has full control on how instantiation chains are built:

Call:
W = V

Result:
W -> V
Call:
V = W

Result:
V -> W

When aliasing with attribute variables the unification problem is solved such that attribute variables are instantiated at the least moment and the instantiation of ordinary variables is preferred over the instantiation of attribute variables. An instantiation of an attribute variable is only necessary during aliasing if the other variable is also an attribute variable. If an attribute variable instantiation attempted is made, be it by another attribute variable or a Prolog term, the hooks of the attribute variables are first called to check for a veto:

Call:
A = V

Result:
V -> A
Call:
V = A

Result:
V -> A
Call:
A = B

Result:
A.hooks(B), A -> B

Further ingredients of the attribute variable toolbox are operations to associate and de-associate hooks from an attribute variable. An attribute variable can have zero, one or many hooks, the operations allow a trailed modification. A hook is a closure for two arguments and contrary to clauses the variables of the closure are shared. Hooks are only called once and they may veto the instantiation of a variable with a term. Hooks are also allowed to have side effects. This is exemplified by the subject to occurs check example found in the tutorial section of the Jekejeke Minlog language reference.


Picture 5: Rule Interaction

The subject to occurs check example does not show how to connect attribute variables with the forward chaining engine. In the appendix there are additional versions of the little solver extension from the previous chapter. These versions show how the connection works. The connection is based on a kind of Gödel coding of attribute variables. With the help of the reference data type of Jekejeke Prolog we can find a code ⟨v⟩ for each attribute variable v. The code behaves like an atom and does not change from assert to retrieval. It is therefore well suited to be used inside forward chaining facts.

The new versions of the “Little Solver” with attribute variables still have the bound/2 and refer/2 events, but only for internal purposes. These two events are generated from native Prolog unification. As soon as a variable has been used in a constraint it will be turned into an attribute variable and a hook will be associated with the attribute variable. This hook is responsible for the translation of native Prolog unification into corresponding internal events of the constraint solver. The hook will have access to the original attribute variables v and encode them as ⟨v⟩ in the generated internal event. 

Now there are situations where the old constraint solver generated new bound/2 and refer/2 events. For the new constraint solver these events should also be reflected by native Prolog unification. The idea is here that the constraint solver does generate these events indirectly by performing a call-out to native Prolog unification. The call-out is realized by advising the post/1 system predicate. The advising code will recognize internal events similar to bound/2 and refer/2 and have access to the code ⟨v⟩ of the attribute variables. It will perform according native Prolog unifications on the decoded attribute variables v.

In implementing constraint solvers, it might be necessary that the logic uses lexical comparison. For example when representing a polynomial it comes handy ordering the coefficients according to the variables of the polynomial. Implementing such algorithms is no problem when constraint variables are represented as atoms. We modified the Jekejeke Prolog runtime so that a lexical comparison is also possible when constraint variable are represented as coded attribute variables. For this purpose we have provided the possibility that the reference data type can be ordered so as to allow an ordering of the codes.

The CLP(FD) implementation that is bundled with Jekejeke Minlog gives again proof of concept that our attribute variables can be used to implement complex constraint solvers. The newest version of our CLP(FD) implementation shows a similar behavior versus variables as typical CLP(FD) implementations from other Prolog systems show. Concerning the implementation of constraint solvers, we have further experience from other applications in natural language processing and expert systems. Not all of these applications demand the introduction of attribute variables. Sometimes it is handier to have atoms as constraints variables, for example when variables names are assembled from smaller elements.

In Jekejeke Minlog the end-user has the choice to use attribute variables for his constraint solver or not. There is not automatism that compiles some attribute variable behavior into the forward chaining rules. Before we have introduced attribute variables we also experimented with what we called shared variables. Shared variables would be variables from clauses that are not universally quantified and that can thus communicate with other variables from other clauses. The experiments we conducted were based on the trailed database update toolbox from Jekejeke Minlog, so that the shared variables were temporal. The experiments were successful in that we could replicate some experiments from lambda Prolog.

But we quickly figured out that shared variables cannot be directly used for the realization of constraint solvers, since they don’t share the atomic property of for example coded attribute variables. Forward chaining rules over shared variables would lead to unwanted aliasing. Nevertheless shared variables are still on our agenda, together with the concept of existentially quantified variables in clauses, which we have not yet explored much. What concerns shared variables we already figured out that the coding of attribute variables can also be used to implement these. The other concept is still open, although we expect that attribute variables will also play a role here.

The experiments we have conducted so far with shared variables were mainly based on backward chaining. Backward chaining practically goes unchanged in the presence of shared variables. Only the invocation of a clause will lead to additional unifications with the shared variables. On the other hand shared variables pose interesting challenges to the forward chaining engine. It seems that they might introduce some non-determinism into the execution of forward chaining rules. We have not yet figured out the details, but we speculate that the deterministic findall/3 used in the firing of forward chaining rules needs to be replaced by the non-deterministic bagof/3. This lead is important since some logical operators are only implementable via forward chaining and not via backward chaining [11].

Comments