Attributed variables: library interfaces / impleme

问题:

When I was skimming some prolog related questions recently, I stumbled upon this answer by @mat to question How to represent directed cyclic graph in Prolog with direct access to neighbour verticies .

So far, my personal experience with attributed variables in Prolog has been very limited. But the use-case given by @mat sparked my interest. So I tried using it for answering another question, ordering lists with constraint logic programming.

First, the good news: My first use of attributed variables worked out like I wanted it to.

Then, the not so good news: When I had posted by answer, I realized there were several API's and implementations for attributed variables in Prolog.

I feel I'm over my head here... In particular I want to know the following:

• What API's are in wide-spread use? Up to now, I found two: SICStus and SWI.
• Which features do the different attributed variable implementations offer? The same ones? Or does one subsume the other?
• Are there differences in semantics?
• What about the actual implementation? Are some more efficient than others?
• Can be (or is) using attributed variables a portability issue?

Lots of question marks, here... Please share your experience / stance? Thank you in advance!

---

Edit 2015-04-22

Here's a code snippet of the answer mentioned above:

init_att_var(X,Z) :-
    put_attr(Z,value,X).

get_att_value(Var,Value) :-
    get_attr(Var,value,Value).

So far I "only" use put_attr/3 and get_attr/3, but---according to the SICStus Prolog documentation on attributed variables---SICStus offers put_attr/2 and get_attr/2.

So even this very shallow use-case requires some emulation layer (one way or the other).

回答1:

I would like to focus on one important general point I noticed when working with different interfaces for attributes variables: When designing an interface for attributed variables, an implementor should also keep in mind the following:

• Is it possible to take attributes into account when reasoning about simultaneous unifications, as in [X,Y] = [0,1]?

This is possible for example in SICStus Prolog, because such bindings are undone before verify_attributes/3 is called. In the interface provided by hProlog (attr_unify_hook/2, called after the unification and with all bindings already in place) it is hard to take into account the (previous) attributes of Y when reasoning about the unification of X in attr_unify_hook/2, because Y is no longer a variable at this point! This may be sufficient for solvers that can make decisions based on ground values alone, but it is a serious limitation for solvers that need additional data, typically stored in attributes, to see whether a unification should succeed, and which are then no longer easily available. One obvious example: Boolean unification with decision diagrams.

As of 2016, the verify-attributes branch of SWI-Prolog also supports verify_attributes/3, thanks to great implementation work by Douglas Miles. The branch is ready for testing and intended to be merged into master as soon as it works correctly and efficiently. For compatibility with hProlog, the branch also supports attr_unify_hook/2: It does so by rewriting such definitions to the more general verify_attributes/3 at compilation time.

Performance-wise, it is clear that there may be a downside to verify_attributes/3, because making several variables ground at the same time may let you sooner see (in attr_unify_hook/2) that a unification cannot succeed. However, I will gladly and any time exchange this typically negligible advantage for the improved reliability, ease of use, and increased functionality that the more general interface gives you, and which is in any case already the standard behaviour in SICStus Prolog which is on top of its generality also one of the faster Prolog systems around.

SICStus Prolog also features an important predicate called project_attributes/2: It is used by the toplevel to project constraints to query variables. SWI-Prolog also supports this in recent versions.

There is also one huge advantage of the SWI interface: The residual goals that attribute_goals//1 and hence copy_term/3 give you are always a list. This helps users to avoid defaultyness in their code, and encourages a more declarative interface, because a list of pure constraint goals cannot contain control structures.

Interestingly, neither interface lets you interpret unifications other than syntactically. Personally, I think there are cases where you may want to interpret unifications differently than syntactically, however, there may also be good arguments against that.

The other interface predicates for attributed variables are mostly easily interchangable with simple wrapper predicates for different systems.

回答2:

Jekejeke Minlog has state-less or thin attribute variables. Well not exactly, an attribute variable can have zero, one or many hooks, which are allowed to be closures, and hence can carry a little state.

But typically an implementation manages the state elsewere. For this purpose Jekejeke Minlog allows creating reference types from variables, so that they can be used as indexes into tables.

The full potential is unleashed if this combined with trailing and/or forward chaining. As an example we have implemented CLP(FD). There is also a little solver tutorial.

The primitive ingredients in our case are:

1) State-less Attribute Variables
2) Trailing and Variable Keys
3) Continuation Queue

The attribute variables hooks might have binding effects upto extending the continuation queue but are only executed once. Goals from the continuation queue can be non-deterministic.

There are some additional layers before realizing applications, that are mostly aggregations of the primitives to make changes temporarily.

The main applications so far are open source here and here:

a) Finite Domain Constraint Solver
b) Herbrand Constraints
c) Goal Suspension

Bye

回答3:

You can find one of the oldest and most elaborate implementations of attributed variables in ECLiPSe, where it forms part of the wider infrastructure for implementing constraint solvers.

The main characteristics of this design are:

• attributes must be declared, and in return the compiler supports efficient access
• a syntax for attributed variables, so that they can be read and written
• a more complete set of handlers for attribute operations, so that attributes are not only taken into account for unification, but also for other generic operations such as term copying and subsumption tests
• a clear separation between the concepts of variable attribute and suspended goals
• used in over a dozen of ECLiPSe's libraries

This paper (section 4) and the ECLiPSe documentation have more details.

回答4:

An additional perspective on attributed variable libraries is how many attributes can be defined per module. In the case of SWI-Prolog/YAP and citing SWI documentation:

Each attribute is associated to a module, and the hook (attr_unify_hook/2) is executed in this module.

This is a severe limitation for implementers of libraries such as CLP(FD) as it forces using additional modules for the sole purpose of having multiple attributes instead of being able to define as many attributes as required in the module implementing their library. This limitation doesn't exist on the SICStus Prolog interface, which provides a directive attribute/1 that allows the declaration of an arbitrary number of attributes per module.