unify(feature1,
feature2,
bindings1=None,
bindings2=None,
fail=None)
| source code
|
In general, the 'unify' procedure takes two values, and either returns
a value that provides the information provided by both values, or fails
if that is impossible.
These values can have any type, but fall into a few general cases:
-
Values that respond to
has_key represent feature
structures. The unify procedure will recurse into them
and unify their inner values.
-
Variables represent an unknown value, and are
handled specially. The values assigned to variables are tracked using
bindings.
-
None represents the absence of information.
-
Any other value is considered a base value. Base values are compared to each
other with the == operation.
The value 'None' represents the absence of any information. It
specifies no properties and acts as the identity in unification.
>>> unify(3, None) 3
>>> unify(None, 'fish')
'fish'
A base value unifies with itself, but not much else. >>>
unify(True, True) True
>>> unify([1], [1])
[1]
>>> unify('a', 'b')
Traceback (most recent call last):
...
UnificationFailure
When two mappings (representing feature structures, and usually
implemented as dictionaries) are unified, any chain of keys that accesses
a value in either mapping will access an equivalent or more specific
value in the unified mapping. If this is not possible, UnificationFailure
is raised.
>>> f1 = dict(A=dict(B='b'))
>>> f2 = dict(A=dict(C='c'))
>>> unify(f1, f2) == dict(A=dict(B='b', C='c'))
True
The empty dictionary specifies no features. It unifies with any
mapping. >>> unify({}, dict(foo='bar')) {'foo': 'bar'}
>>> unify({}, True)
Traceback (most recent call last):
...
UnificationFailure
Representing dictionaries in YAML form is useful for making feature
structures readable:
>>> f1 = yaml.load("number: singular")
>>> f2 = yaml.load("person: 3")
>>> print show(unify(f1, f2))
number: singular
person: 3
>>> f1 = yaml.load('''
... A:
... B: b
... D: d
... ''')
>>> f2 = yaml.load('''
... A:
... C: c
... D: d
... ''')
>>> print show(unify(f1, f2))
A:
B: b
C: c
D: d
Variables are names for unknown values. Variables are assigned values
that will make unification succeed. The values of variables can be reused
in later unifications if you provide a dictionary of _bindings_ from
variables to their values. >>> bindings = {} >>> print
unify(Variable('x'), 5, bindings) 5
>>> print bindings
{'x': 5}
>>> print unify({'a': Variable('x')}, {}, bindings)
{'a': 5}
The same variable name can be reused in different binding dictionaries
without collision. In some cases, you may want to provide two separate
binding dictionaries to unify -- one for each feature
structure, so their variables do not collide.
In the following examples, two different feature structures use the
variable ?x to require that two values are equal. The values assigned to
?x are consistent within each structure, but would be inconsistent if
every ?x had to have the same value.
>>> f1 = yaml.load('''
... a: 1
... b: 1
... c: ?x
... d: ?x
... ''')
>>> f2 = yaml.load('''
... a: ?x
... b: ?x
... c: 2
... d: 2
... ''')
>>> bindings1 = {}
>>> bindings2 = {}
>>> print show(unify(f1, f2, bindings1, bindings2))
a: 1
b: 1
c: 2
d: 2
>>> print bindings1
{'x': 2}
>>> print bindings2
{'x': 1}
Feature structures can involve _reentrant_ values, where multiple
feature paths lead to the same value. This is represented by the features
having the same Python object as a value. (This kind of identity can be
tested using the is operator.)
Unification preserves the properties of reentrance. So if a reentrant
value is changed by unification, it is changed everywhere it occurs, and
it is still reentrant. Reentrant features can even form cycles; these
cycles can now be printed through the current YAML library.
>>> f1 = yaml.load('''
... A: &1 # &1 defines a reference in YAML...
... B: b
... E:
... F: *1 # and *1 uses the previously defined reference.
... ''')
>>> f1['E']['F']['B']
'b'
>>> f1['A'] is f1['E']['F']
True
>>> f2 = yaml.load('''
... A:
... C: c
... E:
... F:
... D: d
... ''')
>>> f3 = unify(f1, f2)
>>> print show(f3)
A: &id001
B: b
C: c
D: d
E:
F: *id001
>>> f3['A'] is f3['E']['F']
True
This unification creates a cycle: >>> f1 = yaml.load(''' ...
F: &1 {} ... G: *1 ... ''') >>> f2 = yaml.load(''' ... F:
... H: &2 {} ... G: *2 ... ''') >>> f3 = unify(f1, f2)
>>> print f3 {'G': {'H': {...}}, 'F': {'H': {...}}} >>>
print f3['F'] is f3['G'] True >>> print f3['F'] is f3['G']['H']
True >>> print f3['F'] is f3['G']['H']['H'] True
A cycle can also be created using variables instead of reentrance.
Here we supply a single set of bindings, so that it is used on both sides
of the unification, making ?x mean the same thing in both feature
structures.
>>> f1 = yaml.load('''
... F:
... H: ?x
... ''')
>>> f2 = yaml.load('''
... F: ?x
... ''')
>>> f3 = unify(f1, f2, {})
>>> print f3
{'F': {'H': {...}}}
>>> print f3['F'] is f3['F']['H']
True
>>> print f3['F'] is f3['F']['H']['H']
True
Two sets of bindings can be provided because the variable names on
each side of the unification may be unrelated. An example involves
unifying the following two structures, which each require that two values
are equivalent, and happen to both use ?x to express that
requirement.
>>> f1 = yaml.load('''
... a: 1
... b: 1
... c: ?x
... d: ?x
... ''')
>>> f2 = yaml.load('''
... a: ?x
... b: ?x
... c: 2
... d: 2
... ''')
>>> bindings1 = {}
>>> bindings2 = {}
>>>
>>>
>>>
>>> print show(unify(f1, f2, bindings1, bindings2))
a: 1
b: 1
c: 2
d: 2
>>> print bindings1
{'x': 2}
>>> print bindings2
{'x': 1}
If a variable is unified with another variable, the two variables are
_aliased_ to each other; they share the same value, similarly to
reentrant feature structures. This is represented in a set of bindings as
one variable having the other as its value. >>> f1 =
yaml.load(''' ... a: ?x ... b: ?x ... ''') >>> f2 =
yaml.load(''' ... b: ?y ... c: ?y ... ''') >>> bindings = {}
>>> print show(unify(f1, f2, bindings)) a: &id001 ?y b:
*id001 c: *id001 >>> print bindings {'x': ?y}
Reusing the same variable bindings ensures that appropriate bindings
are made after the fact: >>> bindings = {} >>> f1 =
{'a': Variable('x')} >>> f2 = unify(f1, {'a': {}}, bindings)
>>> f3 = unify(f2, {'b': Variable('x')}, bindings) >>>
print show(f3) a: &id001 {} b: *id001 >>> print bindings
{'x': {}}
- Parameters:
feature1 (object (probably a mapping)) - The first object to be unified.
feature2 (object (probably a mapping)) - The second object to be unified.
bindings1 (dict or None) - The variable bindings associated with the first object.
bindings2 (dict or None) - The variable bindings associated with the second object, if these
are distinct from bindings1 .
- Returns:
object (probably a mapping)
- The result of unifying the two objects.
|