Recent Changes - Search:

PmWiki

pmwiki.org

edit SideBar

AttributedVariables

Attributed Variables

 ECLiPSeSICStushPrologSWI
Availabilitylanguagelibrary(atts)languagelanguage
Module-sensitiveyesyesyesyes
Attribute nameatom (=module by convention)1module+namemodule2module2
Attribute name spaceglobal (=module by convention)module+local=module=module
Declaration0..N per module (0..1 recommended)0..1 per modulenonenone
Handler namesdeclaredfixed hook namesfixed hook namesfixed hook names
handlersper attributeper moduleper module=attributeper module=attribute
post-unify handleryesnoyesyes
pre-unify handlerlibraryyesno 

Notes:

  1. . Attribute names do not have to be module names, but recommended to avoid naming conflicts in the global name space. Probably a mis-feature.
  2. . A non-module attribute can be added, but on unification the name is used for module-qualifying the unify handler.

Pre-unify handler

Behaviour in SICStus (and ECLiPSe compatibility library):

    Let Xs be the set of all attributed variables bound since last handler invocation (or failure).
    Undo the bindings of all Xs.
    For each X in Xs
        Invoke verify_attributes(X,V,Gs) where V is the value X was to be bound to.
        Re-do the binding X=V.
        Invoke the list of goals Gs. 

The characteristics of this scheme are

  • variable bindings are "serialized", i.e. bindings look as if done one by one.
  • the support for calling goals after all attribute handlers have been applied to the variable
  • no direct support for triggering goals after the whole batch of unifications

Note however

  • other modifications to variables (e.g. bounds, domain) are not serialized by this mechanism

Attributes and Goals

A constraint network is a graph made up of constraints and variables. In logic programming terminology this corresponds to predicates (goals) over variables.

  • a goal (constraint) can involve many variables
  • a variable can be involved in many goals (constraints)

Only in ECLiPSe does the Prolog engine have a concept of suspended goals/constraints.

In the other systems, delayed goals/constraints are implicit in data structures attached to variables via attributes. As a result, goals can get lost. In SWI they can even get lost when attached to variables:

% SWI + clpfd
p :- X#>Y, Y#>X.

?- p.
true.

while in ECLiPSe

?- p.

Delayed goals:
	-(_185{-1.0Inf .. 1.0Inf}) + _201{-1.0Inf .. 1.0Inf} #> 0
	_185{-1.0Inf .. 1.0Inf} - _201{-1.0Inf .. 1.0Inf} #> 0
Yes (0.00s cpu)

SWI does in fact offer a way to get at the lost constraint network:

?- call_residue_vars(p,V).
V = [_G1133, _G1136],
_G1133#=<_G1136+ -1,
_G1136#=<_G1133+ -1.

Another probably related hack is the SWI predicate attvars/2, which does a deep (recursively into attributes) traversal of its argument. Semantically, attributes are meta-level information, so any predicates ignoring this boundary are extremely dubious.

Even when a program makes sure that no goals attached to variables are lost, the prerequisite is that there is always a reference from a variable to *all* delayed goals it is involved in. This is not necessary in ECLiPSe.

Projection

project_attributes(+QueryVars, +AttrVars).

This is poorly documented (and understood?). Strangely it is explained via references to "the toplevel", which isn't a good way to give language semantics.

SICStus: "If the attributes on AttrVars can be interpreted as constraints, this predicate will typically “project” those constraints onto the relevant QueryVars. Ideally, the residual constraints will be expressed entirely in terms of the QueryVars, treating all other variables as existentially quantified. Operationally, project_attributes/2 must remove all attributes from AttrVars, and add transformed attributes representing the projected constraints to some of the QueryVars."

SWI manual advocates "If possible, project_attributes/2 should change the attributes so that all constraints are expressed as residual goals that refer only to QueryVars, while other variables are existentially quantified.", i.e. that project_attributes should have a side effect.

Notes regarding discussion about SICStus-style verify_attributes

General situation: we have an object-level with variables, and a meta-level that reasons about variables as data.

There is a claim floating around that variable bindings should be serialized. Not clear why, as long as the notifications are serialized.

AC3 propagators should not care, they recompute everything from the current state.

AC4 style propagators need a sequence of notifications, but

  • they should operate on a meta-representation of variables
  • bindings are only one kind of notification (others are bound update, etc)
  • they should update their meta-representation using the information in the notification
  • they should not be influenced by the object level otherwise (so bindings there should not matter)
  • they can update the object level eventually, producing further notifications
  • update steps must be sequenced
Edit - History - Print - Recent Changes - Search
Page last modified on November 14, 2024, at 01:11 PM