<< Back to previous view

[UNIFY-9] Between clojure 1.6 and clojure 1.7, unification of maps stopped working correctly Created: 28/Feb/17  Updated: 01/Mar/17

Status: Open
Project: core.unify
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Jason Felice Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None
Environment:

Failure duplicated on clojure 1.7, clojure 1.9.0-alpha14.
Does not fail on 1.5.1, 1.6.



 Description   

With 1.9.0-alpha14:

dev=> (clojure.core.unify/unify {:a '?x, :c :d} {:c :d, :a :b})
nil
dev=> (clojure.core.unify/unify {:a '?x, :c :d} {:a :b, :c :d})
{?x :b}


 Comments   
Comment by Jason Felice [ 01/Mar/17 10:47 AM ]

There's an indication in UNIFY-6 that we expected this to work, although the current algorithm never supported variables in keys. It did unify values of like keys, but it relied on two maps with the same key sets having the same iteration order. That's what broke.

An easy fix would be to restore the previous behavior–the previous behavior was O (relying on iteration over map keys being O for their current order), and the easy fix would make it something like O(n log_32 n) for maps.

A more interesting fix would be to add support for variables in keys. This is something I find valuable (and interesting). This changes the algorithm because the lack of order of a set makes multiple unifications possible, e.g. (unify {:a 1, :b 2} {?x _, ?y _}) has two unifications: {?x :a, ?y :b} and {?x :b, ?y :a}, and therefore backtracking (or something like it) becomes necessary.

This same mechanism could be used for sets, as reported in UNIFY-8.

Would the "interesting" fix be considered, or should I just go for "easy"?





[UNIFY-6] Create tests for k&v map unification Created: 25/May/12  Updated: 25/May/12

Status: Open
Project: core.unify
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Substitution in map keys or values should both work. I doubt there are tests around this.






[UNIFY-3] Enhance documentation Created: 03/Feb/12  Updated: 03/Feb/12

Status: Open
Project: core.unify
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Fogus Assignee: Fogus
Resolution: Unresolved Votes: 0
Labels: docs


 Description   

The current unify docs are spartan and "just the facts". It would be useful to have a set of docs that:

  • explain unification
  • explain the library use cases
  • show a simple example use





Generated at Sat Mar 25 01:17:21 CDT 2017 using JIRA 4.4#649-r158309.