A Clojure library for combining directed acyclic graphs (DAGs) via unification. Unification is similar to merge (http://clojure.github.io/clojure/clojure.core-api.html#clojure.core/merge), except that if arguments have the same keys, the arguments' values for those keys will be recursively combined via unification to yield the value for the key in the combined map.
% git clone git@github.com:ekoontz/dag-unify.git
% cd dag-unify
% lein repl
nREPL server started on port 56364 on host 127.0.0.1 - nrepl://127.0.0.1:56364
REPL-y 0.3.7, nREPL 0.2.12
Clojure 1.8.0
Java HotSpot(TM) 64-Bit Server VM 1.8.0_121-b13
Docs: (doc function-name-here)
(find-doc "part-of-name-here")
Source: (source function-name-here)
Javadoc: (javadoc java-object-or-class-here)
Exit: Control+D or (exit) or (quit)
Results: Stored in vars *1, *2, *3, an exception in *e
user=> (require '[dag_unify.core :as dag])
nil
First, let's create a directed acyclic graph by using a Clojure atom:
user=> (def foo (let [shared-value (atom :top)]
#_=> {:a {:b shared-value}
#_=> :c shared-value}))
#'user/foo
user=> (dag/pprint foo)
{:a {:b [[1] :top]}, :c [1]}
Note in the above that in the directed acyclic graph foo
, the value for the
path [:a :b]
is set to the same value as the path [:c]
.
Now, let's unify this with a specific value at the path: [:c]
, namely 42
.
user=> (dag/pprint (dag/unify foo {:c 42}))
{:c [[1] 42], :a {:b [1]}}
user=>
Using dag-unify's built-in get-in
, we get the same value for the
paths [:a :b]
and [:c]
:
user=> (def foo2 (dag/unify foo {:c 42}))
#'user/foo2
user=> (dag/pprint foo2)
{:c [[1] 42], :a {:b [1]}}
user=> (dag/get-in foo2 [:a :b])
42
user=> (dag/get-in foo2 [:c])
42
Consider the behavior of Clojure's merge
:
user> (merge {:a {:b 42}}
{:a {:c 43}})
{:a {:c 43}}
Note that the the first argument's {:b 42}
is lost from the return
value - it was overwritten by the second argument's value for :a
-
{:c 43
}.
With unify
, however, we preserve both arguments' values for :a
and
combine them as follows:
user> (unify {:a {:b 42}}
{:a {:c 43}})
{:a {:b 42, :c 43}}
We can use Atoms with a map to represent a DAG:
user> (def foo (let [shared-value (atom :top)]
{:a {:b shared-value}
:c shared-value}))
#'user/foo
user> foo
{:a {:b #atom[:top 0x57212d5f]}, :c #atom[:top 0x57212d5f]}
And then unify
that DAG with another map to cause the atom's value
to be modified:
user> (unify foo {:c 42})
{:c #atom[42 0x57212d5f], :a {:b #atom[42 0x57212d5f]}}
user> foo
{:a {:b #atom[42 0x57212d5f]}, :c #atom[42 0x57212d5f]}
user>
The function dag_unify.pprint
can be used to display such DAGs more legibly:
user> (dag/pprint (dag/unify foo {:c 42}))
{:a {:b [[1] :top]}, :c [1]}
If one or more arguments to unify
is a map with a key whose value is
an atom, then the value of that key will still be that same atom, but its
value will be modified to be the unification of the arguments. For example:
(let [shared-value (atom {:b 42})
foo {:a shared-value}
bar {:a {:c 43}}]
(dag/unify foo bar))
=> {:a #<Atom@344dc027: {:c 43, :b 42}>}
Above, foo
's value for :a
is a reference to the value {:b 42}
. foo
's value for :a
is unified with bar
's value for :a
({:c 43}
), and the result {:b 42, c 43}
is the new value of the
reference, and this reference is the value :a
for the unification of
foo
and bar
.
:top
For the special keyword :top
, the following is true for all X
:
(unify X :top) => X
In other words, :top
is the identity
element of
unification. It is the most unspecific, most general value possible.
Atoms work with :top
as in the following example:
(let [shared-value (atom :top)
foo {:a shared-value
:b shared-value}
bar {:a 42}]
(unify foo bar))
=> {:b #<Atom@51670b57: 42>, :a #<Atom@51670b57: 42>}
In the immediately above case, foo
has an unspecified :top
value
that is shared by foo
's :a
and :b
key. bar
had a more specific
value (i.e. 42) for :a
, but no :b
key. The result of unification
of foo
and bar
is a map with :a
and :b
both sharing the same
value 42
.
:fail
For the special keyword :fail
, the following is true for all X
:
(unify X :fail) => :fail
In any map, if any key's value is equal to :fail
, the entire map is
equal to :fail
. For example, the following map, despite its
complicated structure:
{:a 42
:b {:c {:d :fail
:e {:f 43}
:g 44}}
:h {:i "hello"}}
is no different from :fail
as far as unification is concerned.
:fail
is used to represent a failed attempt of trying to unify
values which are not equal (if atomic values) or have some part that
is not equal. For example:
(let [shared-value (atom :top)
foo {:a shared-value
:b shared-value}
bar {:a 42
:b 43}]
(unify foo bar))
=> :fail
Above, the :a
value and :b
values of bar
should be identical
because :foo
has a shared value which :a
and :b
both point to.
However, these two atomic values (42 and 43) are not equal
to one another. The result is that the unification of foo
and bar
is :fail
.
For unification of simple values (numbers, strings, keywords), they
are compared by equality. If the values to be unified are not equal,
then :fail
is returned:
(unify 1 1)
=> 1
(unify 1 2)
=> :fail
unify!
versus unify
unify!
is destructive: it will modify its arguments if they contain
references, whereas unify
copies its arguments before performing
unification, so that the input arguments are never modified.
Copyright © 2015 Eugene Koontz
Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.
"Feature Structures & Unification" http://www.nltk.org/howto/featstruct.html A similar library written in Python for the the Natural Language Toolkit (NLTK).
Can you improve this documentation?Edit on GitHub
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close