Feature Structures in Python (Part II)

[James Tauber]

This is part II. Note that it hasn't be changed to use clear() instead of
having the del_features() function yet.

Again, suggestions for improvement appreciated.

James

###
### FEATURE STRUCTURES IN PYTHON (Part II)
###
### James Tauber - http://jtauber.com/
### Updated: 2003-06-19
#
# This is the second part of a guide to implementing feature structures
# in Python.
#
# In the previous part, we saw how to use dictionaries for feature
# structures and how to implement reentrancy. In this part we'll look
# at subsumption.
#
# Previously, we defined the following:

class feature(str):
    pass

def del_features(feature_structure):
    for f in feature_structure.keys():
        del feature_structure[f]

##
## SUBSUMPTION
#
# We will define subsumption recursively, to cover nested feature
# structures. In particular, F1 will be said to subsume F2 iff, for
# every feature in F1, the same feature exists in F2 and the value of
# the feature in F1 subsumes the value in F2. Furthermore, an atomic
# value will only subsume another atomic if they are equal.
#
# NOTE: I'll postpone the question of whether None should subsume
# everything.
#
# Let's unpack the definition.
#
# The definition depends on whether the two objects being compared are
# dictionaries or not. Let's initially cover the non-dictionary case.

def _subsume_1(value1, value2):
    return value1 == value2

assert _subsume_1("np", "np")
assert not _subsume_1("np", "vp")

# 
# Now let's define the corresponding function for two
# feature-structures with atomic values:

def _subsume_2(structure1, structure2):
    for feat in structure1:  # iterate over features in first
        if feat in structure2 and \
               _subsume_1(structure1[feat], structure2[feat]):
            pass                 # if compatible, continue along
        else:
            return 0             # found an incompatibility
    return 1                 # got through with no problems

assert _subsume_2({}, {})

fs1 = {
    "NUMBER": "sg",
    "PERSON": 3
}

fs2 = {
    "NUMBER": "pl",
    "PERSON" : 3
}

fs3 = {
    "NUMBER" : "sg"
}

fs4 = {
    "PERSON": 3
}

assert not _subsume_2(fs1, fs2)
assert not _subsume_2(fs1, fs3)
assert not _subsume_2(fs1, fs4)
assert not _subsume_2(fs2, fs1)
assert not _subsume_2(fs2, fs3)
assert not _subsume_2(fs2, fs4)
assert _subsume_2(fs3, fs1)
assert not _subsume_2(fs3, fs2)
assert not _subsume_2(fs3, fs4)
assert _subsume_2(fs4, fs1)
assert _subsume_2(fs4, fs2)
assert not _subsume_2(fs4, fs3)

# 
# Now we are in a position to properly define our subsume function:

def subsume(object1, object2):
    if type(object1) == type(object2) == dict:
        for feat in object1:
            if feat in object2 and \
                   subsume(object1[feat], object2[feat]):
                pass
            else:
                return 0
        return 1
    else:
        return object1 == object2

# 
# Let's repeat the same tests with the next function.

assert subsume("np", "np")
assert not subsume("np", "vp")

assert subsume({}, {})

assert not subsume(fs1, fs2)
assert not subsume(fs1, fs3)
assert not subsume(fs1, fs4)
assert not subsume(fs2, fs1)
assert not subsume(fs2, fs3)
assert not subsume(fs2, fs4)
assert subsume(fs3, fs1)
assert not subsume(fs3, fs2)
assert not subsume(fs3, fs4)
assert subsume(fs4, fs1)
assert subsume(fs4, fs2)
assert not subsume(fs4, fs3)

# 
# And now some new ones:

assert not subsume(1, fs1)
assert not subsume(fs1, 1)

fs5 = {
    "NUMBER": "sg",
    "GENDER": "masc"
}

assert not subsume(fs1, fs5)
assert not subsume(fs5, fs1)

fs6 = {
    "CAT": "np",
    "AGR": {
        "NUMBER": "sg",
        "PERSON": 3
    }
}

fs7 = {
    "CAT": "np"
}

fs8 = {
    "AGR": {
        "NUMBER": "sg"
    }
}

fs9 = {
    "AGR": {
        "PERSON" : 3
    }
}

assert not subsume(fs6, fs7)
assert not subsume(fs6, fs8)
assert not subsume(fs6, fs9)
assert subsume(fs7, fs6)
assert not subsume(fs7, fs8)
assert not subsume(fs7, fs9)
assert subsume(fs8, fs6)
assert not subsume(fs8, fs7)
assert not subsume(fs8, fs9)
assert subsume(fs9, fs6)
assert not subsume(fs9, fs7)
assert not subsume(fs9, fs8)

fs10 = {
    "AGR": {
        "PERSON" : 1
    }
}

assert not subsume(fs9, fs10)
assert not subsume(fs10, fs9)
assert not subsume(fs10, fs6)

### CONTINUED IN Part III (unification)


-- 
  James Tauber
  http://jtauber.com/