_Comment made by: eraserhd_
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(n) (relying on iteration over map keys being O(n) 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"?
