core.unify

Between clojure 1.6 and clojure 1.7, unification of maps stopped working correctly

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • 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}

Activity

Hide
Jason Felice added a comment -

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"?

Show
Jason Felice added a comment - 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"?

People

Vote (1)
Watch (0)

Dates

  • Created:
    Updated: