The public SWISH instance has been updated to support (SWISH) user defined attributed variables. I have updated the dict tutorial to demonstrate how dicts can be used to implement feature terms efficiently.
2 Likes
Hey Jan - while this looks nifty, I’m not getting the explanation of feature terms. It’s not clear to me why this needs to involve attributed variables and not just unifying dicts? Can you clarify please?
1 Like
You can’t unify dicts with different sets of keys. I’d, #{x:1} = #{y:2} simply fails. When using the feature set semantics you want X = #{x:1}, Y = #{y:2} to succeed, giving the unified variable the feature set #{x:1, y:2}. In other words, you want the two sets to get the united set of features but fail if they have a conflicting value for some feature.
The traditional way to deal with this is to examine the complete set of features used anywhere in the program and assign each feature a positional argument in a compound. So, for the above we would get fs(X,Y) and then the code X = fs(1,_), Y = fs(_,2), X = Y. This works great. Only, at least some applications have huge feature sets, while each such term only has a tiny fraction of the features filled.
For example, In the Alpino parser of Dutch, these terms have many thousands of arguments. Porting Alpino to SWI-Prolog (long time ago) required removing several limits on the number of variables in several parts of the system, just for this reason. Using dicts as above would be far more efficient, both in terms of space as time because we only consider the filled features and as dicts are sorted by keys, these operations finish in O(n), where n is the size of the dict. Compound term unification is also O(n), but needs to unify all “free” (unbound) features. Note that this is a unification of two variables and thus adds a trail entry.
As a nice bonus, you no longer need to examine the program to assign positions for each feature and you get nice readable dicts rather than a huge term with most variables.
1 Like
Ah!
Certainly dicts have needed some “try to unify” for a long time. What I wasn’t getting was why this needed to involve attributes. I’m reading this as the short answer is “for efficiency”.
No. The problem is that for extending a dict it needs to be mutable. Dicts are in the end just compound terms that follow the usual Prolog semantics. You cannot unify two different (ground) terms. If you add them as an attribute to a variable, you can. The attr_unify_hook/2 may accept or reject the unification and if it accepts it can decide on the new attribute values based on the attribute values of the two involved variables.
In other words, attributed variables allow you to extend unification and that is precisely what we need here. It also preserves the normal Prolog semantics: ground terms do not change. By using an attributed variable it is no longer a ground term and (thus) may change. That is also why people tend to add a variable to mutable terms (terms subject to setarg/3).
1 Like