Attributed variables: High-level considerations

[triska]

I would like to contribute some of the experience I gained with attributed variables, usable at your discretion in later stages of this project. I am mentioning this now, at a rather high level, because adding these provisions later may turn out to be very complex. I will, at your request or initiative, gladly discuss any of these aspects in their own separate issues.

At the surface, adding attributes to variables does not seem hard. However, once you look a bit more into it, there are several tough issues involved. I start with what proved to be the toughest part in SWI-Prolog, and is still unresolved: There should be a predicate like verify_attributes/3. Please see SWI-Prolog/roadmap#14 for the justification. This deserves its own issue, and so I only bring it briefly to your attention here, for future consideration.

Next, please take a look at Precise Garbage Collection in Prolog by Neumerkel et al.. This paper is critical to understand how an efficient implementation of library(pio) is possible, reclaiming stack space as soon as possible and thus lazily parsing a file with low memory overhead.

Finally, a critical predicate when working with attributed variables is call_residue_vars/2. Briefly, it lets you reason about all variables whose attributes were modified during the execution of a goal. This facility is of critical importance when reasoning about constraint logic programs. I only briefly touch on this essential topic here by showing the following example:

inconsistent :-
        X #> Y,
        Y #< X.

With this sample program, we have:

?- inconsistent.
true.

This although declaratively, the goal cannot hold! To reason about these constraints, we can do:

?- call_residue_vars(inconsistent, Vs).
Vs = [_3162, _3168],
_3162#=<_3168+ -1,
_3168#=<_3162+ -1.

This exposes the variables that are still involved in constraints whose satisfiability is not yet determined.

Overall, once you implement setting/getting attributes and a hook like verify_attributes/3, the relevant constraints like dif/2 and also CLP(FD) can be implemented in Prolog itself.

[mthom]

Is there good source material on the implementation of attributed variables? Holzbaur doesn't appear to be what I'm looking for. I found a paper on the XSB system by Warren that contains some details, but its focus is removed from the basics.

[triska]

One standard reference is:

• Bart Demoen, Dynamic attributes, their hProlog implementation, and a first evaluation, October 2002

Please consider that as a useful starting point. Beware though! The following publication (Section 4.7) explains that this interface is insufficient in general:

• Markus Triska, The Boolean Constraint Solver of SWI-Prolog: System Description, FLOPS 2016

A good implementation of attributed variables must first and foremost enable the required generality of its interface predicates. This may require a completely different approach!

[mthom]

It's a start. Thanks Markus.

[mthom]

OK, I've read the papers, SICStus documentation, and most of the SWI Prolog issue thread. Nevertheless, I've concluded that implementing verify_attributes/3 is indeed not all that hard, so there are probably some subtleties I am missing. Would you mind walking me through them?

[triska]

It is also my impression that implementing verify_attributes/3 should not be very hard if you know what you are doing.

In SWI-Prolog, interest for constraint-related functionality is exceptionally low (for a Prolog system), so I think the reason this is not implemented is mostly that nobody has seriously looked into it. Also, there are only two or three people working on constraint-related features in SWI-Prolog that are even aware of the need for this feature.

In general, there should be no major stumbling blocks. Any existing binding must be undone, the hook must run, and then the scheduled goals must be invoked.

It may be useful to consider a concrete program that uses verify_attributes/3 in non-trivial ways. For example, here is a port of library(clpb) in such a way that it works with the SICStus interface:

https://www.metalevel.at/clpb/clpb.pl

Once you manage to run this program in your system, it will also give you a free CLP(B) system. Only a few libraries are needed to make this work.

Please let me know any time if you have any questions about this!

[mthom]

What does the :- initialization(...). directive in SICSTUS do? My guess is that it runs the contained code every time the module is loaded.

[triska]

Yes, exactly! initialization/1 is a standard directive:

7.4.2.6 initialization/1

A directive initialization(T) converts the term T to
a goal G and includes it in a set of goals which shall
be executed immediately after the Prolog text has been
prepared for execution. The order in which any such goals
will be executed shall be implementation defined.

Note that it does not matter where the directive is placed in the file! It is always loaded after the (entire) file "has been prepared for execution".

[triska]

Attributed variables work very well so far!

Thank you a lot, this is a very nice achievement!