Coverage for nltk.sem.evaluate: 63%

100

101

102

103

# Natural Language Toolkit: Models for first-order languages with lambda

# Author: Ewan Klein <ewan@inf.ed.ac.uk>,

# URL: <http://nltk.sourceforge.net>

# For license information, see LICENSE.TXT

#TODO:

#- fix tracing

#- fix iterator-based approach to existentials

"""

This module provides data structures for representing first-order

models.

"""

from __future__ import print_function

from pprint import pformat

import inspect

import textwrap

from nltk.decorators import decorator # this used in code that is commented out

from nltk.sem.logic import (AbstractVariableExpression, AllExpression,

AndExpression, ApplicationExpression, EqualityExpression,

ExistsExpression, IffExpression, ImpExpression,

IndividualVariableExpression, LambdaExpression,

LogicParser, NegatedExpression, OrExpression,

Variable, is_indvar)

class Error(Exception): pass

class Undefined(Error): pass

def trace(f, *args, **kw):

argspec = inspect.getargspec(f)

d = dict(zip(argspec[0], args))

if d.pop('trace', None):

print()

for item in d.items():

print("%s => %s" % item)

return f(*args, **kw)

def is_rel(s):

"""

Check whether a set represents a relation (of any arity).

:param s: a set containing tuples of str elements

:type s: set

:rtype: bool

"""

# we have the empty relation, i.e. set()

if len(s) == 0:

return True

# all the elements are tuples of the same length

elif s == set([elem for elem in s if isinstance(elem, tuple)]) and\

len(max(s))==len(min(s)):

return True

else:

raise ValueError("Set %r contains sequences of different lengths" % s)

def set2rel(s):

"""

Convert a set containing individuals (strings or numbers) into a set of

unary tuples. Any tuples of strings already in the set are passed through

unchanged.

For example:

- set(['a', 'b']) => set([('a',), ('b',)])

- set([3, 27]) => set([('3',), ('27',)])

:type s: set

:rtype: set of tuple of str

"""

new = set()

for elem in s:

if isinstance(elem, str):

new.add((elem,))

elif isinstance(elem, int):

new.add((str(elem,)))

else:

new.add(elem)

return new

def arity(rel):

"""

Check the arity of a relation.

:type rel: set of tuples

:rtype: int of tuple of str

"""

if len(rel) == 0:

return 0

return len(list(rel)[0])

class Valuation(dict):

"""

A dictionary which represents a model-theoretic Valuation of non-logical constants.

Keys are strings representing the constants to be interpreted, and values correspond

to individuals (represented as strings) and n-ary relations (represented as sets of tuples

of strings).

An instance of ``Valuation`` will raise a KeyError exception (i.e.,

just behave like a standard dictionary) if indexed with an expression that

is not in its list of symbols.

"""

def __init__(self, iter):

"""

:param iter: a list of (symbol, value) pairs.

"""

dict.__init__(self)

for (sym, val) in iter:

if isinstance(val, str) or isinstance(val, bool):

self[sym] = val

elif isinstance(val, set):

self[sym] = set2rel(val)

else:

msg = textwrap.fill("Error in initializing Valuation. "

"Unrecognized value for symbol '%s':\n%s" % (sym, val), width=66)

raise ValueError(msg)

def __getitem__(self, key):

if key in self:

return dict.__getitem__(self, key)

else:

raise Undefined("Unknown expression: '%s'" % key)

def __str__(self):

return pformat(self)

@property

def domain(self):

"""Set-theoretic domain of the value-space of a Valuation."""

dom = []

for val in self.values():

if isinstance(val, str):

dom.append(val)

elif not isinstance(val, bool):

dom.extend([elem for tuple in val for elem in tuple if elem is not None])

return set(dom)

@property

def symbols(self):

"""The non-logical constants which the Valuation recognizes."""

return sorted(self.keys())

class Assignment(dict):

"""

A dictionary which represents an assignment of values to variables.

An assigment can only assign values from its domain.

If an unknown expression *a* is passed to a model *M*\ 's

interpretation function *i*, *i* will first check whether *M*\ 's

valuation assigns an interpretation to *a* as a constant, and if

this fails, *i* will delegate the interpretation of *a* to

*g*. *g* only assigns values to individual variables (i.e.,

members of the class ``IndividualVariableExpression`` in the ``logic``

module. If a variable is not assigned a value by *g*, it will raise

an ``Undefined`` exception.

A variable *Assignment* is a mapping from individual variables to

entities in the domain. Individual variables are usually indicated

with the letters ``'x'``, ``'y'``, ``'w'`` and ``'z'``, optionally

followed by an integer (e.g., ``'x0'``, ``'y332'``). Assignments are

created using the ``Assignment`` constructor, which also takes the

domain as a parameter.

>>> from nltk.sem.evaluate import Assignment

>>> dom = set(['u1', 'u2', 'u3', 'u4'])

>>> g3 = Assignment(dom, [('x', 'u1'), ('y', 'u2')])

>>> g3

{'y': 'u2', 'x': 'u1'}

There is also a ``print`` format for assignments which uses a notation

closer to that in logic textbooks:

>>> print(g3)

g[u2/y][u1/x]

It is also possible to update an assignment using the ``add`` method:

>>> dom = set(['u1', 'u2', 'u3', 'u4'])

>>> g4 = Assignment(dom)

>>> g4.add('x', 'u1')

{'x': 'u1'}

With no arguments, ``purge()`` is equivalent to ``clear()`` on a dictionary:

>>> g4.purge()

>>> g4

{}

:param domain: the domain of discourse

:type domain: set

:param assign: a list of (varname, value) associations

:type assign: list

"""

def __init__(self, domain, assign=None):

dict.__init__(self)

self.domain = domain

if assign:

for (var, val) in assign:

assert val in self.domain,\

"'%s' is not in the domain: %s" % (val, self.domain)

assert is_indvar(var),\

"Wrong format for an Individual Variable: '%s'" % var

self[var] = val

self._addvariant()

def __getitem__(self, key):

if key in self:

return dict.__getitem__(self, key)

else:

raise Undefined("Not recognized as a variable: '%s'" % key)

def copy(self):

new = Assignment(self.domain)

new.update(self)

return new

def purge(self, var=None):

"""

Remove one or all keys (i.e. logic variables) from an

assignment, and update ``self.variant``.

:param var: a Variable acting as a key for the assignment.

"""

if var:

val = self[var]

del self[var]

else:

self.clear()

self._addvariant()

return None

def __str__(self):

"""

Pretty printing for assignments. {'x', 'u'} appears as 'g[u/x]'

"""

gstring = "g"

for (val, var) in self.variant:

gstring += "[%s/%s]" % (val, var)

return gstring

def _addvariant(self):

"""

Create a more pretty-printable version of the assignment.

"""

list = []

for item in self.items():

pair = (item[1], item[0])

list.append(pair)

self.variant = list

return None

def add(self, var, val):

"""

Add a new variable-value pair to the assignment, and update

``self.variant``.

"""

assert val in self.domain,\

"%s is not in the domain %s" % (val, self.domain)

assert is_indvar(var),\

"Wrong format for an Individual Variable: '%s'" % var

self[var] = val

self._addvariant()

return self

class Model(object):

"""

A first order model is a domain *D* of discourse and a valuation *V*.

A domain *D* is a set, and a valuation *V* is a map that associates

expressions with values in the model.

The domain of *V* should be a subset of *D*.

Construct a new ``Model``.

:type domain: set

:param domain: A set of entities representing the domain of discourse of the model.

:type valuation: Valuation

:param valuation: the valuation of the model.

:param prop: If this is set, then we are building a propositional\

model and don't require the domain of *V* to be subset of *D*.

"""

def __init__(self, domain, valuation):

assert isinstance(domain, set)

self.domain = domain

self.valuation = valuation

if not domain.issuperset(valuation.domain):

raise Error("The valuation domain, %s, must be a subset of the model's domain, %s"\

% (valuation.domain, domain))

def __repr__(self):

return "(%r, %r)" % (self.domain, self.valuation)

def __str__(self):

return "Domain = %s,\nValuation = \n%s" % (self.domain, self.valuation)

def evaluate(self, expr, g, trace=None):

"""

Call the ``LogicParser`` to parse input expressions, and

provide a handler for ``satisfy``

that blocks further propagation of the ``Undefined`` error.

:param expr: An ``Expression`` of ``logic``.

:type g: Assignment

:param g: an assignment to individual variables.

:rtype: bool or 'Undefined'

"""

try:

lp = LogicParser()

parsed = lp.parse(expr)

value = self.satisfy(parsed, g, trace=trace)

if trace:

print()

print("'%s' evaluates to %s under M, %s" % (expr, value, g))

return value

except Undefined:

if trace:

print()

print("'%s' is undefined under M, %s" % (expr, g))

return 'Undefined'

def satisfy(self, parsed, g, trace=None):

"""

Recursive interpretation function for a formula of first-order logic.

Raises an ``Undefined`` error when ``parsed`` is an atomic string

but is not a symbol or an individual variable.

:return: Returns a truth value or ``Undefined`` if ``parsed`` is\

complex, and calls the interpretation function ``i`` if ``parsed``\

is atomic.

:param parsed: An expression of ``logic``.

:type g: Assignment

:param g: an assignment to individual variables.

"""

if isinstance(parsed, ApplicationExpression):

function, arguments = parsed.uncurry()

if isinstance(function, AbstractVariableExpression):

#It's a predicate expression ("P(x,y)"), so used uncurried arguments

funval = self.satisfy(function, g)

argvals = tuple([self.satisfy(arg, g) for arg in arguments])

return argvals in funval

else:

#It must be a lambda expression, so use curried form

funval = self.satisfy(parsed.function, g)

argval = self.satisfy(parsed.argument, g)

return funval[argval]

elif isinstance(parsed, NegatedExpression):

return not self.satisfy(parsed.term, g)

elif isinstance(parsed, AndExpression):

return self.satisfy(parsed.first, g) and \