python-pyke 1.1.1-5 / usr / lib / python2.7 / dist-packages / pyke / contexts.py

# $Id: contexts.py 081917d30609 2010-03-05 mtnyogi $
# coding=utf-8
# 
# Copyright © 2007-2008 Bruce Frederiksen
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

"""
    A context is used to store all of a rule's pattern variable bindings for a
    specific rule invocation during inferencing (both forward-chaining and
    backward-chaining rules).

        >>> from pyke import pattern
        >>> c = simple_context()
        >>> var = variable('foo')
        >>> var
        $foo
        >>> var.name
        'foo'
        >>> c.bind(var.name, c, 123)
        True
        >>> c.lookup(var)
        (123, None)
        >>> c.lookup_data(var.name)
        123
    
    This is a shallow binding scheme which must "unbind" variables when a
    rule is done.  Each time a rule is invoked, a new context object is
    created to store the bindings for the variables in that rule.  When the
    rule is done, this context is abandoned; so the variables bound there
    do not need to be individually unbound.  But bindings done to
    variables in other contexts _do_ need to be individually unbound.
    These bindings happen when a variable in the calling rule, which must
    be bound in that rule's context, is matched to a non-variable pattern (i.e.,
    pattern_literal or pattern_tuple) in the called rule's context.

    For example, a caller, rule A, has its own context:

        >>> A_context = simple_context()

    and a pattern of $foo within a subgoal in its 'when' clause:

        >>> A_pattern = variable('foo')

    In proving this subgoal, rule B is being tried.  A new context is
    created for rule B:

        >>> B_context = simple_context()

    Rule B has a literal 123 in its 'proven' clause:

        >>> B_pattern = pattern.pattern_literal(123)

    Now B's 'proven' clause is pattern matched to A's subgoal, which
    results in:

        >>> B_pattern.match_pattern(B_context, B_context, A_pattern, A_context)
        True

    The pattern matches!  But the $foo variable belongs to A, so it must be
    bound in A's context, not B's.

        >>> A_context.lookup(A_pattern)
        (123, None)
        >>> B_context.lookup(A_pattern)
        Traceback (most recent call last):
            ...
        KeyError: '$foo not bound'

    This is done by using the current rule's context as a controlling context
    for all the bindings that occur within that rule.  If the binding is for
    a variable in another context, the controlling context remembers the
    binding in its undo_list.  When the rule is finished, it executes a 'done'
    method on its context which undoes all of the bindings in its undo_list.

        >>> B_context.done()
        >>> A_context.lookup(A_pattern)
        Traceback (most recent call last):
            ...
        KeyError: '$foo not bound'

    Thus, in binding a variable to a value, there are three contexts
    involved:

        controlling_context.bind(variable, variable_context,
                                 value [, value_context])

    The value_context must be omitted if value is any python data, and
    must be included if value is a pattern (including another variable).

    Variables are bound to as just strings so that they can be accessed
    easily from python code without needing the variable objects.

        >>> A_context.bind('foo', A_context, 123)
        True
        >>> A_context.lookup_data('foo')
        123
    
    But to differentiate variables from string literals in the patterns,
    variables are special objects.  When a variable is bound as data (to
    another variable), it is bound as a variable object (again, to
    differentiate it from plain python strings).

        >>> a_var = variable('a_var')
        >>> a_var
        $a_var
        >>> b_var = variable('b_var')
        >>> b_var
        $b_var
        >>> B_context.bind(b_var.name, B_context, a_var, A_context)
        True
        >>> B_context.lookup(b_var)
        Traceback (most recent call last):
            ...
        KeyError: '$a_var not bound'
        >>> ans = B_context.lookup(b_var, True)
        >>> ans                                 # doctest: +ELLIPSIS
        ($a_var, <pyke.contexts.simple_context object at ...>)
        >>> ans[1] is A_context
        True
    
    But to differentiate variables from string literals in the patterns,
    variables are special objects.  When a variable is bound as data (to
    another variable), it is bound as a variable object (again, to
    differentiate it from plain python strings).

        >>> type(ans[0])
        <class 'pyke.contexts.variable'>

    The anonymous variables have names starting with '_'.  Binding
    requests on anonymous variables are silently ignored.

        >>> anonymous('_ignored')
        $_ignored
        >>> A_context.bind('_bogus', A_context, 567)
        False
        >>> A_context.lookup_data('_bogus')
        Traceback (most recent call last):
            ...
        KeyError: '$_bogus not bound'
        >>> A_context.lookup_data('_bogus', True)
        '$_bogus'
"""

import sys

from pyke import pattern, unique

_Not_found = unique.unique('Not_found')

# Set to a sequence (or frozenset) of variable names to trace their bindings:
debug = ()

class simple_context(object):
    def __init__(self):
        self.bindings = {}
        self.undo_list = []
        self.save_all_undo_count = 0

    def dump(self):
        for var_name in sorted(self.bindings.iterkeys()):
            print "%s: %s" % (var_name, repr(self.lookup_data(var_name, True)))

    def bind(self, var_name, var_context, val, val_context = None):
        """ val_context must be None iff val is not a pattern.
            Returns True if a new binding was created.
        """
        assert not isinstance(val, pattern.pattern) \
                   if val_context is None \
                   else isinstance(val, pattern.pattern)
        if var_name[0] == '_': return False
        if var_context is self:
            assert var_name not in self.bindings
            if val_context is not None:
                val, val_context = val_context.lookup(val, True)
            if val_context == var_context and isinstance(val, variable) and \
               val.name == var_name:
                # binding $x to $x; no binding necessary!
                return False
            if var_name in debug:
                if val_context:
                    sys.stderr.write("binding %s in %s to %s in %s\n" %
                        (var_name, var_context, val, val_context))
                else:
                    sys.stderr.write("binding %s in %s to %s\n" %
                        (var_name, var_context, val))
            self.bindings[var_name] = (val, val_context)
            if self.save_all_undo_count:
                self.undo_list.append((var_name, self))
            return True
        ans = var_context.bind(var_name, var_context, val, val_context)
        if ans: self.undo_list.append((var_name, var_context))
        return ans

    def is_bound(self, var):
        val, where = var, self
        while where is not None and isinstance(val, variable):
            ans = where.bindings.get(val.name)
            if ans is None: return False
            val, where = ans
        # where is None or not isinstance(val, variable)
        return where is None or val.is_data(where)

    def lookup_data(self, var_name, allow_vars = False, final = None):
        """ Converts the answer into data only (without any patterns in it).
            If there are unbound variables anywhere in the data, a KeyError is
            generated.
        """
        if final is not None:
            val = final.get((var_name, self), _Not_found)
            if val is not _Not_found: return val
        binding = self.bindings.get(var_name)
        if binding is None:
            if allow_vars: return "$" + var_name
            raise KeyError("$%s not bound" % var_name)
        val, context = binding
        if context is not None:
            val = val.as_data(context, allow_vars, final)
        if isinstance(val, bc_context): val = val.create_plan(final)
        if final is not None: final[var_name, self] = val
        return val

    def lookup(self, var, allow_variable_in_ans = False):
        """ Returns value, val_context.
            Returns (var, self) if not bound and allow_variable_in_ans, else
            raises KeyError.
        """
        val, where = var, self
        while where is not None and isinstance(val, variable):
            ans = where.bindings.get(val.name)
            if ans is None: break
            val, where = ans
        else:
            # where is None or not isinstance(val, variable)
            return val, where
        # where is not None and isinstance(val, variable)
        if allow_variable_in_ans: return val, where
        raise KeyError("%s not bound" % str(val))

    def mark(self, save_all_undo = False):
        if save_all_undo: self.save_all_undo_count += 1
        return len(self.undo_list)

    def end_save_all_undo(self):
        assert self.save_all_undo_count > 0
        self.save_all_undo_count -= 1

    def undo_to_mark(self, mark, *var_names_to_undo):
        for var_name, var_context in self.undo_list[mark:]:
            var_context._unbind(var_name)
        del self.undo_list[mark:]
        for var_name in var_names_to_undo:
            self._unbind(var_name)

    def done(self):
        """ Unbinds all variables bound through 'self's 'bind' method.
            The assumption here is that 'self' is being abandoned, so we don't
            need to worry about self.bindings.
        """
        for var_name, var_context in self.undo_list:
            var_context._unbind(var_name)

    def _unbind(self, var_name):
        del self.bindings[var_name]

class bc_context(simple_context):
    def __init__(self, rule):
        super(bc_context, self).__init__()
        self.rule = rule

    def name(self): return self.rule.name

    def __repr__(self):
        return "<bc_context for %s at 0x%x>" % (self.name(), id(self))

    def create_plan(self, final = None):
        if final is None: final = {}
        return self.rule.make_plan(self, final)

class variable(pattern.pattern):
    """ The code to force variables of the same name to be the same object is
        probably not needed anymore...
    """
    Variables = {}

    def __new__(cls, name):
        var = cls.Variables.get(name)
        if var is None:
            var = super(variable, cls).__new__(cls)
            cls.Variables[name] = var
        return var

    def __init__(self, name):
        self.name = name

    def __repr__(self): return '$' + self.name

    def lookup(self, my_context, allow_variable_in_ans = False):
        return my_context.lookup(self, allow_variable_in_ans)

    def match_data(self, bindings, my_context, data):
        if self.name in debug:
            sys.stderr.write("%s.match_data(%s, %s, %s)\n" %
                (self, bindings, my_context, data))
        var, var_context = my_context.lookup(self, True)
        if isinstance(var, variable):
            bindings.bind(var.name, var_context, data)
            return True
        if self.name in debug:
            sys.stderr.write("%s.match_data: lookup got %s in %s\n" %
                (self, var, var_context))
        if var_context is None: return var == data
        return var.match_data(bindings, var_context, data)

    def simple_match_pattern(self, bindings, my_context, pattern_b, b_context):
        var, var_context = my_context.lookup(self, True)
        if isinstance(var, variable):
            bindings.bind(var.name, var_context, pattern_b, b_context)
            return True
        if var_context is None:
            return pattern_b.match_data(bindings, b_context, var)
        return var.simple_match_pattern(bindings, var_context,
                                        pattern_b, b_context)

    def match_pattern(self, bindings, my_context, pattern_b, b_context):
        var, var_context = my_context.lookup(self, True)
        if isinstance(var, variable):
            bindings.bind(var.name, var_context, pattern_b, b_context)
            return True
        if var_context is None:
            return pattern_b.match_data(bindings, b_context, var)
        return var.match_pattern(bindings, var_context, pattern_b, b_context)

    def as_data(self, my_context, allow_vars = False, final = None):
        return my_context.lookup_data(self.name, allow_vars, final)

    def is_data(self, my_context):
        return my_context.is_bound(self)

class anonymous(variable):
    def __init__(self, name):
        assert name[0] == '_', \
               "anonymous variables must start with '_', not %s" % name
        super(anonymous, self).__init__(name)

    def lookup(self, my_context, allow_variable_in_ans = False):
        if allow_variable_in_ans: return self, my_context
        raise KeyError("$%s not bound" % self.name)

    def match_data(self, bindings, my_context, data):
        return True

    def match_pattern(self, bindings, my_context, pattern_b, b_context):
        return True

    def as_data(self, my_context, allow_vars = False, final = None):
        if allow_vars: return "$%s" % self.name
        raise KeyError("$%s not bound" % self.name)

    def is_data(self, my_context):
        return False