Commits

Carl Friedrich Bolz committed f891d80

playing around...

  • Participants
  • Parent commits 8d7d90f
  • Branches continuation-based

Comments (0)

Files changed (11)

prolog/builtin/control.py

-import py
-from prolog.interpreter import engine, helper, term, error
+from prolog.interpreter import engine, helper, term, error, continuation
 from prolog.builtin.register import expose_builtin
 
 # ___________________________________________________________________
 def impl_cut(engine, heap, continuation):
     raise error.CutException(continuation)
 
-class AndContinuation(engine.Continuation):
-    def __init__(self, next_call, continuation):
-        self.next_call = next_call
-        self.continuation = continuation
-
-    def _call(self, engine):
-        next_call = self.next_call.dereference(engine.heap)
-        next_call = helper.ensure_callable(next_call)
-        return engine.call(next_call, self.continuation, choice_point=False)
-
 @expose_builtin(",", unwrap_spec=["callable", "raw"], handles_continuation=True)
-def impl_and(engine, heap, call1, call2, continuation):
+def impl_and(engine, heap, call1, call2, scont, fcont):
     if not isinstance(call2, term.Var) and not isinstance(call2, term.Callable):
         error.throw_type_error('callable', call2)
-    and_continuation = AndContinuation(call2, continuation)
-    return engine.call(call1, and_continuation, choice_point=False)
+    scont = continuation.BodyContinuation(engine, scont, call2)
+    return engine.call(call1, scont, fcont, heap)
 
+class OrContinuation(continuation.FailureContinuation):
+    def __init__(self, engine, nextcont, undoheap, orig_fcont, altcall):
+        continuation.Continuation.__init__(self, engine, nextcont)
+        self.altcall = altcall
+        self.undoheap = undoheap
+        self.orig_fcont = orig_fcont
+
+    def activate(self, fcont, heap):
+        assert self.undoheap is None
+        scont = continuation.BodyContinuation(self.engine, self.nextcont,
+                                              self.altcall)
+        return scont, fcont, heap
+
+    def fail(self, heap):
+        assert self.undoheap is not None
+        heap = heap.revert_upto(self.undoheap)
+        self.undoheap = None
+        return self, self.orig_fcont, heap
+
+            
 @expose_builtin(";", unwrap_spec=["callable", "callable"],
                 handles_continuation=True)
-def impl_or(engine, heap, call1, call2, continuation):
-    oldstate = heap.branch()
-    try:
-        return engine.call(call1, continuation, choice_point=True)
-    except error.UnificationFailed:
-        heap.revert_and_discard(oldstate)
-    return engine.call(call2, continuation, choice_point=False)
+def impl_or(engine, heap, call1, call2, scont, fcont):
+    newscont = continuation.BodyContinuation(engine, scont, call1)
+    fcont = OrContinuation(engine, scont, heap, fcont, call2)
+    return newscont, fcont, heap.branch()
 
-@expose_builtin(["not", "\\+"], unwrap_spec=["callable"])
-def impl_not(engine, heap, call):
+@expose_builtin(["not", "\\+"], unwrap_spec=["callable"],
+                handles_continuation=True)
+def impl_not(engine, heap, call, scont, fcont):
+    newscont = continuation.BodyContinuation(engine, XXX(scont), call1)
     try:
         try:
             engine.call(call)

prolog/builtin/register.py

         self.numargs = numargs
         self.signature = signature
 
-    def call(self, engine, query, continuation):
-        return self.function(engine, query, continuation)
+    def call(self, engine, query, scont, fcont, heap):
+        return self.function(engine, query, scont, fcont, heap)
         
     def _freeze_(self):
         return True
     if not name.isalnum():
         name = func.func_name
     funcname = "wrap_%s_%s" % (name, len(unwrap_spec))
-    code = ["def %s(engine, query, continuation):" % (funcname, )]
-    code.append("    heap = engine.heap")
+    code = ["def %s(engine, query, scont, fcont, heap):" % (funcname, )]
     if not translatable:
         code.append("    if we_are_translated():")
         code.append("        raise error.UncatchableError('%s does not work in translated version')" % (name, ))
         else:
             assert 0, "not implemented " + spec
     if handles_continuation:
-        subargs.append("continuation")
+        subargs.append("scont")
+        subargs.append("fcont")
     call = "    result = %s(%s)" % (func.func_name, ", ".join(subargs))
     code.append(call)
     if not handles_continuation:
-        code.append("    return continuation.call(engine, choice_point=False)")
+        code.append("    return scont, fcont, heap")
     else:
         code.append("    return result")
     miniglobals = globals().copy()

prolog/interpreter/continuation.py

+from pypy.rlib import jit
+from prolog.interpreter import error
+from prolog.interpreter.term import Term, Atom, Rule, Var
+from prolog.interpreter.function import Function
+
+def driver(scont, fcont, heap):
+    while scont is not None:
+        try:
+            scont, fcont, heap  = scont.activate(fcont, heap)
+        except error.UnificationFailed:
+            if fcont is None:
+                raise
+            scont, fcont, heap = fcont.fail(heap)
+            if scont is None:
+                raise
+
+class Engine(object):
+    def __init__(self):
+        self.heap = Heap()
+        self.signature2function = {}
+        self.parser = None
+        self.operations = None
+
+    # _____________________________________________________
+    # database functionality
+
+    def add_rule(self, rule, end=True):
+        from prolog import builtin
+        if isinstance(rule, Term):
+            if rule.name == ":-":
+                rule = Rule(rule.args[0], rule.args[1])
+            else:
+                rule = Rule(rule, None)
+        elif isinstance(rule, Atom):
+            rule = Rule(rule, None)
+        else:
+            error.throw_type_error("callable", rule)
+            assert 0, "unreachable" # make annotator happy
+        signature = rule.signature
+        if signature in builtin.builtins:
+            error.throw_permission_error(
+                "modify", "static_procedure", rule.head.get_prolog_signature())
+        function = self._lookup(signature)
+        function.add_rule(rule, end)
+
+    @jit.purefunction_promote
+    def get_builtin(self, signature):
+        from prolog.builtin import builtins
+        builtin = builtins.get(signature, None)
+        return builtin
+
+    @jit.purefunction
+    def _lookup(self, signature):
+        signature2function = self.signature2function
+        function = signature2function.get(signature, None)
+        if function is None:
+            signature2function[signature] = function = Function()
+        return function
+
+    # _____________________________________________________
+    # parsing-related functionality
+
+    def _build_and_run(self, tree):
+        from prolog.interpreter.parsing import TermBuilder
+        builder = TermBuilder()
+        term = builder.build_query(tree)
+        if isinstance(term, Term) and term.signature == ":-/1":
+            self.run(term.args[0])
+        else:
+            self.add_rule(term)
+        return self.parser
+
+    def runstring(self, s):
+        from prolog.interpreter.parsing import parse_file
+        trees = parse_file(s, self.parser, Engine._build_and_run, self)
+
+    def parse(self, s):
+        from prolog.interpreter.parsing import parse_file, TermBuilder
+        builder = TermBuilder()
+        trees = parse_file(s, self.parser)
+        terms = builder.build_many(trees)
+        return terms, builder.varname_to_var
+
+    def getoperations(self):
+        from prolog.interpreter.parsing import default_operations
+        if self.operations is None:
+            return default_operations
+        return self.operations
+
+    # _____________________________________________________
+    # Prolog execution
+
+    def run_query(self, query, continuation=None):
+        driver(*self.call(query, continuation, None, Heap()))
+    run = run_query
+
+    def call(self, query, scont, fcont, heap):
+        signature = query.signature
+        builtin = self.get_builtin(signature)
+        if builtin is not None:
+            return builtin.call(self, query, scont, fcont, heap)
+
+        # do a real call
+        function = self._lookup(signature)
+        startrulechain = function.rulechain
+        if startrulechain is None:
+            error.throw_existence_error(
+                "procedure", query.get_prolog_signature())
+        rulechain = startrulechain.find_applicable_rule(query)
+        scont = UserCallContinuation(self, scont, query,
+                                     rulechain)
+        return scont, fcont, heap
+
+# ___________________________________________________________________
+# Heap implementation
+
+class Heap(object):
+    def __init__(self, prev=None):
+        self.trail = []
+        self.prev = prev
+
+    # _____________________________________________________
+    # interface that term.py uses
+
+    def add_trail(self, var):
+        """ Remember the current state of a variable to be able to backtrack it
+        to that state. Usually called just before a variable changes. """
+        self.trail.append((var, var.binding))
+
+    def newvar(self):
+        """ Make a new variable. Should return a Var instance, possibly with
+        interesting attributes set that e.g. add_trail can inspect."""
+        result = Var()
+        return result
+
+    # _____________________________________________________
+
+    def branch(self):
+        """ Branch of a heap for a choice point. The return value is the new
+        heap that should be used from now on, self is the heap that can be
+        backtracked to."""
+        res = Heap(self)
+        return res
+
+    def revert_upto(self, heap):
+        """ Revert to the heap corresponding to a choice point. The return
+        value is the new heap that should be used."""
+        previous = None
+        while self is not heap:
+            self._revert()
+            previous = self
+            self = self.prev
+        return previous
+
+    def _revert(self):
+        for var, oldbinding in self.trail:
+            var.binding = oldbinding
+        self.trail = []
+
+# ___________________________________________________________________
+# Continuation classes
+
+class Continuation(object):
+    """ Represents a continuation of the Prolog computation. This can be seen
+    as an RPython-compatible way to express closures. """
+
+    def __init__(self, engine, nextcont):
+        self.engine = engine
+        self.nextcont = nextcont
+
+    def activate(self, fcont, heap):
+        """ Follow the continuation. heap is the heap that should be used while
+        doing so, fcont the failure continuation that should be activated in
+        case this continuation fails. This method can only be called once, i.e.
+        it can destruct this object. 
+        
+        The method should return a triple (next cont, failure cont, heap)"""
+        raise NotImplementedError("abstract base class")
+
+class FailureContinuation(Continuation):
+    """ A continuation that can represent failures. It has a .fail method that
+    is called to prepare it for being used as a failure continuation.
+    
+    NB: a Continuation can be used both as a failure continuation and as a
+    success continuation."""
+
+    def fail(self, heap):
+        """ Needs to be called to prepare the object as being used as a failure
+        continuation. Particularly useful for objects that are both a regular
+        and a failure continuation. """
+        # returns (next cont, failure cont, heap)
+        raise NotImplementedError("abstract base class")
+
+class BodyContinuation(Continuation):
+    """ Represents a bit of Prolog code that is still to be called. """
+    def __init__(self, engine, nextcont, body):
+        Continuation.__init__(self, engine, nextcont)
+        self.body = body
+
+    def activate(self, fcont, heap):
+        return self.engine.call(self.body, self.nextcont, fcont, heap)
+
+    def __repr__(self):
+        return "<BodyContinuation %r>" % (self.body, )
+
+class ChoiceContinuation(FailureContinuation):
+    """ An abstract base class for Continuations that represent a choice point,
+    i.e. a point to which the execution can backtrack to."""
+
+    def __init__(self, *args):
+        FailureContinuation.__init__(self, *args)
+        self.undoheap = None
+        self.orig_fcont = None
+
+    #def activate(self, fcont, heap):
+    #    this method needs to be structured as follows:
+    #    <some code>
+    #    if <has more solutions>:
+    #        fcont, heap = self.prepare_more_solutions(fcont, heap)
+    #    <construct cont> # must not raise UnificationFailed!
+    #    return cont, fcont, heap
+
+    def prepare_more_solutions(self, fcont, heap):
+        self.undoheap = heap
+        heap = heap.branch()
+        self.orig_fcont = fcont
+        fcont = self
+        return fcont, heap
+    
+    def fail(self, heap):
+        assert self.undoheap is not None
+        heap = heap.revert_upto(self.undoheap)
+        return self, self.orig_fcont, heap
+
+class UserCallContinuation(ChoiceContinuation):
+    def __init__(self, engine, nextcont, query, rulechain):
+        ChoiceContinuation.__init__(self, engine, nextcont)
+        self.query = query
+        signature = query.signature
+        self.rulechain = rulechain
+
+    def activate(self, fcont, heap):
+        rulechain = self.rulechain
+        query = self.query
+        restchain = rulechain.find_next_applicable_rule(query)
+        if restchain is not None:
+            fcont, heap = self.prepare_more_solutions(fcont, heap)
+            self.rulechain = restchain
+        cont = RuleContinuation(self.engine, self.nextcont, rulechain.rule, query)
+        return cont, fcont, heap
+
+    def __repr__(self):
+        return "<UserCallContinuation query=%r rule=%r>" % (
+                self.query, self.rulechain.rule, )
+
+class RuleContinuation(Continuation):
+    def __init__(self, engine, nextcont, rule, query):
+        Continuation.__init__(self, engine, nextcont)
+        self.rule = rule
+        self.query = query
+
+    def activate(self, fcont, heap):
+        nextcall = self.rule.clone_and_unify_head(heap, self.query)
+        if nextcall is not None:
+            cont = BodyContinuation(self.engine, self.nextcont, nextcall)
+        else:
+            cont = self.nextcont
+        return cont, fcont, heap

prolog/interpreter/engine.py

 
 
 
+from prolog.interpreter.continuation import Heap, Engine

prolog/interpreter/error.py

 
 class CutException(PrologError):
     def __init__(self, continuation):
+        assert 0, "shouldn't be used any more"
         self.continuation = continuation
 
 def throw_instantiation_error():

prolog/interpreter/term.py

 import math
-from prolog.interpreter.error import UnificationFailed, UncatchableError
+from prolog.interpreter.error import UnificationFailed
 from prolog.interpreter import error
 from pypy.rlib.objectmodel import we_are_translated, UnboxedValue
 from pypy.rlib.objectmodel import compute_unique_id
-from pypy.rlib.rarithmetic import intmask
 from pypy.rlib.objectmodel import specialize
 from pypy.rlib.debug import make_sure_not_resized
 from pypy.rlib import jit
     def contains_var(self, var, heap):
         return False
 
-    #def __eq__(self, other):
-    #    # for testing
-    #    return (self.__class__ == other.__class__ and
-    #            self.__dict__ == other.__dict__)
-
-    #def __ne__(self, other):
-    #    # for testing
-    #    return not (self == other)
-
     def eval_arithmetic(self, engine):
         error.throw_type_error("evaluable", self)
 
 class Var(PrologObject):
-    STANDARD_ORDER = 0
+    TYPE_STANDARD_ORDER = 0
 
     created_after_choice_point = None
 
     def __repr__(self):
         return "NumberedVar(%s)" % (self.num, )
 
+
 class NonVar(PrologObject):
     __slots__ = ()
 
 
 
 class Atom(Callable):
-    STANDARD_ORDER = 1
+    TYPE_STANDARD_ORDER = 1
 
     cache = {}
     _immutable_ = True
 
 
 class Number(NonVar): #, UnboxedValue):
-    STANDARD_ORDER = 2
+    TYPE_STANDARD_ORDER = 2
     _immutable_ = True
     __slots__ = ("num", )
 
 NUMBER_0 = Number(0)
 
 class Float(NonVar):
-    STANDARD_ORDER = 2
+    TYPE_STANDARD_ORDER = 2
     _immutable_ = True
     def __init__(self, floatval):
         self.floatval = floatval
 
 class BlackBox(NonVar):
     # meant to be subclassed
-    STANDARD_ORDER = 4
+    TYPE_STANDARD_ORDER = 4
     def __init__(self):
         pass
 
     obj.unify_and_standardize_apart(other.args[i], heap, memo)
 
 class Term(Callable):
-    STANDARD_ORDER = 3
+    TYPE_STANDARD_ORDER = 3
     _immutable_ = True
     _immutable_fields_ = ["args[*]"]
 
     return 1
 
 def cmp_standard_order(obj1, obj2, heap):
-    c = rcmp(obj1.STANDARD_ORDER, obj2.STANDARD_ORDER)
+    c = rcmp(obj1.TYPE_STANDARD_ORDER, obj2.TYPE_STANDARD_ORDER)
     if c != 0:
         return c
     if isinstance(obj1, Var):

prolog/interpreter/test/test_builtin.py

     heaps = collect_all(e, "f(!).")
     assert len(heaps) == 1
 
+def test_or_and_call_with_cut():
+    assert_false("(!, fail); true.")
+    assert_true("(call(!), fail); true.")
+
+
+def test_cut1():
+    e = get_engine("""
+        g(a).
+        g(b).
+        a(a).
+        b(b).
+        f(X) :- g(X),!,b(X).
+        f(x).
+        f(y).
+    """)
+    heaps = collect_all(e, "f(X).")
+    assert len(heaps) == 0
+    assert_true("!.")
+
+def test_cut2():
+    e = get_engine("""
+        g(a).
+        g(b).
+        h(a, x).
+        h(a, y).
+        f(X, Y) :- g(X), !, !, !, !, !, h(X, Y).
+    """)
+    heaps = collect_all(e, "f(X, Y).")
+    assert len(heaps) == 2
+
+def test_cut3():
+    e = get_engine("""
+        member(H, [H | _]).
+        member(H, [_ | T]) :- member(H, T).
+
+        s(a, L) :- !, fail.
+        s(b, L).
+        s(X, L) :-
+            member(Y, L),
+            L = [_| S],
+            s(Y, S).
+    """)
+    #    import pdb; pdb.set_trace()
+    assert_true("s(d, [a, b]).", e)
+
+def test_rule_with_cut_calling_rule_with_cut():
+    e = get_engine("""
+        f(b) :- !.
+        f(c).
+        g(X) :- f(X), !.
+        g(a).
+    """)
+    heaps = collect_all(e, "g(X).")
+    assert len(heaps) == 1
+
+def test_not_with_cut():
+    e = get_engine("""
+    p1 :- \\+ q1.
+    q1 :- fail.
+    q1 :- true.
+    
+    p2:- \\+ q2.
+    q2 :- !, fail.
+    q2 :- true.
+    """)
+    assert_false("p1.", e)
+    assert_true("p2.", e)
 
 def test_term_construction():
     assert_true("g(a, b, c) =.. [G, A, B, C].")

prolog/interpreter/test/test_continuation.py

+import py
+from prolog.interpreter.continuation import *
+
+def test_driver():
+    order = []
+    class FakeC(object):
+        def __init__(self, next, val):
+            self.next = next
+            self.val = val
+        
+        def activate(self, fcont, heap):
+            if self.val == -1:
+                raise error.UnificationFailed
+            order.append(self.val)
+            return self.next, fcont, heap
+
+        def fail(self, heap):
+            order.append("fail")
+            return self, None, heap
+
+
+    c5 = FakeC(FakeC(FakeC(FakeC(FakeC(None, 1), 2), 3), 4), 5)
+    driver(c5, None, None)
+    assert order == [5, 4, 3, 2, 1]
+
+    order = []
+    ca = FakeC(FakeC(FakeC(FakeC(FakeC(None, -1), 2), 3), 4), 5)
+    driver(ca, c5, None)
+    assert order == [5, 4, 3, 2, "fail", 5, 4, 3, 2, 1]
+
+def test_failure_continuation():
+    order = []
+    h = Heap()
+    class FakeC(object):
+        def __init__(self, next, val):
+            self.next = next
+            self.val = val
+        
+        def activate(self, fcont, heap):
+            if self.val == -1:
+                raise error.UnificationFailed
+            order.append(self.val)
+            return self.next, fcont, heap
+
+        def fail(self, heap):
+            order.append("fail")
+            return self, None, heap
+
+    class FakeF(ChoiceContinuation):
+        def __init__(self, next, count):
+            self.next = next
+            self.count = count
+
+        def activate(self, fcont, heap):
+            if self.count:
+                fcont, heap = self.prepare_more_solutions(fcont, heap)
+            res = self.count
+            order.append(res)
+            self.count -= 1
+            return self.next, fcont, heap
+
+    ca = FakeF(FakeC(FakeC(None, -1), 'c'), 10)
+    driver(ca, FakeC(None, "done"), h)
+    assert order == [10, 'c', 9, 'c', 8, 'c', 7, 'c', 6, 'c', 5, 'c', 4, 'c',
+                     3, 'c', 2, 'c', 1, 'c', 0, 'c', "fail", "done"]
+
+def test_heap():
+    h1 = Heap()
+    v1 = h1.newvar()
+    v2 = h1.newvar()
+    h1.add_trail(v1)
+    v1.binding = 1
+    h2 = h1.branch()
+    h2.add_trail(v1)
+    v1.binding = 2
+    h2.add_trail(v2)
+    v2.binding = 3
+
+    h3 = h2.revert_upto(h1)
+    assert v1.binding == 1
+    assert v2.binding is None
+    assert h3 is h2
+
+
+
+    
+def test_full():
+    from prolog.interpreter.term import Var, Atom, Term
+    all = []
+    class CollectContinuation(object):
+        def activate(self, fcont, heap):
+            all.append(query.getvalue(heap))
+            raise error.UnificationFailed
+    e = Engine()
+    e.add_rule(Term("f", [Atom.newatom("x")]), True)
+    e.add_rule(Term("f", [Atom.newatom("y")]), True)
+    e.add_rule(Term("g", [Atom.newatom("a")]), True)
+    e.add_rule(Term("g", [Atom.newatom("b")]), True)
+            
+    query = Term(",", [Term("f", [Var()]), Term("g", [Var()])])
+    py.test.raises(error.UnificationFailed,
+                   e.run_query, query, CollectContinuation())
+    assert all[0].args[0].args[0].name == "x"
+    assert all[0].args[1].args[0].name == "a"
+    assert all[1].args[0].args[0].name == "x"
+    assert all[1].args[1].args[0].name == "b"
+    assert all[2].args[0].args[0].name == "y"
+    assert all[2].args[1].args[0].name == "a"
+    assert all[3].args[0].args[0].name == "y"
+    assert all[3].args[1].args[0].name == "b"
+
+# ___________________________________________________________________
+# integration tests
+
+from prolog.interpreter.parsing import parse_query_term, get_engine
+from prolog.interpreter.parsing import get_query_and_vars
+from prolog.interpreter.error import UnificationFailed
+from prolog.interpreter.test.tool import collect_all, assert_true, assert_false
+
+def test_trivial():
+    e = get_engine("""
+        f(a).
+    """)
+    t, vars = get_query_and_vars("f(X).")
+    e.run(t)
+    assert vars['X'].dereference(e.heap).name == "a"
+
+def test_and():
+    e = get_engine("""
+        g(a, a).
+        g(a, b).
+        g(b, c).
+        f(X, Z) :- g(X, Y), g(Y, Z).
+    """)
+    e.run(parse_query_term("f(a, c)."))
+    t, vars = get_query_and_vars("f(X, c).")
+    e.run(t)
+    assert vars['X'].dereference(e.heap).name == "a"
+
+def test_and_long():
+    e = get_engine("""
+        f(x). f(y). f(z).
+        g(a). g(b). g(c).
+        h(d). h(e). h(f).
+        f(X, Y, Z) :- f(X), g(Y), h(Z).
+    """)
+    heaps = collect_all(e, "f(X, Y, Z).")
+    assert len(heaps) == 27  
+
+def test_numeral():
+    e = get_engine("""
+        num(0).
+        num(succ(X)) :- num(X).
+        add(X, 0, X).
+        add(X, succ(Y), Z) :- add(succ(X), Y, Z).
+        mul(X, 0, 0).
+        mul(X, succ(0), X).
+        mul(X, succ(Y), Z) :- mul(X, Y, A), add(A, X, Z).
+        factorial(0, succ(0)).
+        factorial(succ(X), Y) :- factorial(X, Z), mul(Z, succ(X), Y).
+    """)
+    def nstr(n):
+        if n == 0:
+            return "0"
+        return "succ(%s)" % nstr(n - 1)
+    e.run(parse_query_term("num(0)."))
+    e.run(parse_query_term("num(succ(0))."))
+    t, vars = get_query_and_vars("num(X).")
+    e.run(t)
+    assert vars['X'].dereference(e.heap).num == 0
+    e.run(parse_query_term("add(0, 0, 0)."))
+    py.test.raises(UnificationFailed, e.run, parse_query_term("""
+        add(0, 0, succ(0))."""))
+    e.run(parse_query_term("add(succ(0), succ(0), succ(succ(0)))."))
+    e.run(parse_query_term("mul(succ(0), 0, 0)."))
+    e.run(parse_query_term("mul(succ(succ(0)), succ(0), succ(succ(0)))."))
+    e.run(parse_query_term("mul(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0)))))."))
+    e.run(parse_query_term("factorial(0, succ(0))."))
+    e.run(parse_query_term("factorial(succ(0), succ(0))."))
+    e.run(parse_query_term("factorial(%s, %s)." % (nstr(5), nstr(120))))
+
+def test_or_backtrack():
+    e = get_engine("""
+        a(a).
+        b(b).
+        g(a, b).
+        g(a, a).
+        f(X, Y, Z) :- (g(X, Z); g(X, Z); g(Z, Y)), a(Z).
+        """)
+    t, vars = get_query_and_vars("f(a, b, Z).")
+    e.run(t)
+    assert vars['Z'].dereference(e.heap).name == "a"
+    f = collect_all(e, "X = 1; X = 2.")
+    assert len(f) == 2
+
+def test_backtrack_to_same_choice_point():
+    e = get_engine("""
+        a(a).
+        b(b).
+        start(Z) :- Z = X, f(X, b), X == b, Z == b.
+        f(X, Y) :- a(Y).
+        f(X, Y) :- X = a, a(Y).
+        f(X, Y) :- X = b, b(Y).
+    """)
+    assert_true("start(Z).", e)
+
+def test_collect_all():
+    e = get_engine("""
+        g(a).
+        g(b).
+        g(c).
+    """)
+    heaps = collect_all(e, "g(X).")
+    assert len(heaps) == 3
+    assert heaps[0]['X'].name == "a"
+    assert heaps[1]['X'].name == "b"
+    assert heaps[2]['X'].name == "c"
+
+def test_lists():
+    e = get_engine("""
+        nrev([],[]).
+        nrev([X|Y],Z) :- nrev(Y,Z1),
+                         append(Z1,[X],Z).
+
+        append([],L,L).
+        append([X|Y],L,[X|Z]) :- append(Y,L,Z).
+    """)
+    e.run(parse_query_term("append(%s, %s, X)." % (range(30), range(10))))
+    return
+    e.run(parse_query_term("nrev(%s, X)." % (range(15), )))
+    e.run(parse_query_term("nrev(%s, %s)." % (range(8), range(7, -1, -1))))
+
+def test_indexing():
+    # this test is quite a lot faster if indexing works properly. hrmrm
+    e = get_engine("g(a, b, c, d, e, f, g, h, i, j, k, l). " +
+            "".join(["f(%s, g(%s)) :- g(A, B, C, D, E, F, G, H, I ,J, K, l). "
+                      % (chr(i), chr(i + 1))
+                                for i in range(97, 122)]))
+    t = parse_query_term("f(x, g(y)).")
+    for i in range(200):
+        e.run(t)
+    t = parse_query_term("f(x, g(y, a)).")
+    for i in range(200):
+        py.test.raises(UnificationFailed, e.run, t)
+
+def test_indexing2():
+    e = get_engine("""
+        mother(o, j).
+        mother(o, m).
+        mother(o, b).
+
+        sibling(X, Y) :- mother(Z, X), mother(Z, Y).
+    """)
+    heaps = collect_all(e, "sibling(m, X).")
+    assert len(heaps) == 3
+
+def test_runstring():
+    e = get_engine("foo(a, c).")
+    e.runstring("""
+        :- op(450, xfy, foo).
+        a foo b.
+        b foo X :- a foo X.
+    """)
+    assert_true("foo(a, b).", e)
+
+def test_call_atom():
+    e = get_engine("""
+        test(a).
+        test :- test(_).
+    """)
+    assert_true("test.", e)
+
+
+def test_metainterp():
+    e = get_engine("""
+        run(X) :- solve([X]).
+        solve([]).
+        solve([A | T]) :-
+            my_pred(A, T, T1),
+            solve(T1).
+
+        my_pred(app([], X, X), T, T).
+        my_pred(app([H | T1], T2, [H | T3]), T, [app(T1, T2, T3) | T]).
+
+    """)
+    assert_true("run(app([1, 2, 3, 4], [5, 6], X)), X == [1, 2, 3, 4, 5, 6].", e)

prolog/interpreter/test/test_engine.py

 from prolog.interpreter.test.tool import prolog_raises
 from prolog.interpreter.engine import Heap, TrailHolder
 
-def test_trivial():
-    e = get_engine("""
-        f(a).
-    """)
-    t, vars = get_query_and_vars("f(X).")
-    e.run(t)
-    assert vars['X'].dereference(e.heap).name == "a"
-
-def test_and():
-    e = get_engine("""
-        g(a, a).
-        g(a, b).
-        g(b, c).
-        f(X, Z) :- g(X, Y), g(Y, Z).
-    """)
-    e.run(parse_query_term("f(a, c)."))
-    t, vars = get_query_and_vars("f(X, c).")
-    e.run(t)
-    assert vars['X'].dereference(e.heap).name == "a"
-
-def test_and_long():
-    e = get_engine("""
-        f(x). f(y). f(z).
-        g(a). g(b). g(c).
-        h(d). h(e). h(f).
-        f(X, Y, Z) :- f(X), g(Y), h(Z).
-    """)
-    heaps = collect_all(e, "f(X, Y, Z).")
-    assert len(heaps) == 27  
-
-def test_numeral():
-    e = get_engine("""
-        num(0).
-        num(succ(X)) :- num(X).
-        add(X, 0, X).
-        add(X, succ(Y), Z) :- add(succ(X), Y, Z).
-        mul(X, 0, 0).
-        mul(X, succ(0), X).
-        mul(X, succ(Y), Z) :- mul(X, Y, A), add(A, X, Z).
-        factorial(0, succ(0)).
-        factorial(succ(X), Y) :- factorial(X, Z), mul(Z, succ(X), Y).
-    """)
-    def nstr(n):
-        if n == 0:
-            return "0"
-        return "succ(%s)" % nstr(n - 1)
-    e.run(parse_query_term("num(0)."))
-    e.run(parse_query_term("num(succ(0))."))
-    t, vars = get_query_and_vars("num(X).")
-    e.run(t)
-    assert vars['X'].dereference(e.heap).num == 0
-    e.run(parse_query_term("add(0, 0, 0)."))
-    py.test.raises(UnificationFailed, e.run, parse_query_term("""
-        add(0, 0, succ(0))."""))
-    e.run(parse_query_term("add(succ(0), succ(0), succ(succ(0)))."))
-    e.run(parse_query_term("mul(succ(0), 0, 0)."))
-    e.run(parse_query_term("mul(succ(succ(0)), succ(0), succ(succ(0)))."))
-    e.run(parse_query_term("mul(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0)))))."))
-    e.run(parse_query_term("factorial(0, succ(0))."))
-    e.run(parse_query_term("factorial(succ(0), succ(0))."))
-    e.run(parse_query_term("factorial(%s, %s)." % (nstr(5), nstr(120))))
-
-def test_or():
-    e = get_engine("""
-        g(a, b).
-        g(b, a).
-        f(X, Y) :- g(X, b); g(a, Y).
-        """)
-    e.run(parse_query_term("f(a, c)."))
-    e.run(parse_query_term("f(d, b)."))
-    prolog_raises("ERROR", "foo(X); X = 1")
-
-
-def test_or_and_call_with_cut():
-    assert_false("(!, fail); true.")
-    assert_true("(call(!), fail); true.")
-
-def test_or_backtrack():
-    e = get_engine("""
-        a(a).
-        b(b).
-        g(a, b).
-        g(a, a).
-        f(X, Y, Z) :- (g(X, Z); g(X, Z); g(Z, Y)), a(Z).
-        """)
-    t, vars = get_query_and_vars("f(a, b, Z).")
-    e.run(t)
-    assert vars['Z'].dereference(e.heap).name == "a"
-    f = collect_all(e, "X = 1; X = 2.")
-    assert len(f) == 2
-
-def test_backtrack_to_same_choice_point():
-    e = get_engine("""
-        a(a).
-        b(b).
-        start(Z) :- Z = X, f(X, b), X == b, Z == b.
-        f(X, Y) :- a(Y).
-        f(X, Y) :- X = a, a(Y).
-        f(X, Y) :- X = b, b(Y).
-    """)
-    assert_true("start(Z).", e)
-
-def test_equivalent_with_quotes():
-    e = get_engine("""
-        g('a', X).
-        g('b', 'c').
-    """)
-    e.run(parse_query_term("g(a, b)."))
-    e.run(parse_query_term("g(b, c)."))
-
 def test_error_unknown_function():
     e = get_engine("""
         g(a).
     """)
     prolog_raises("existence_error(procedure, h/1)", "f(X)", e)
     
-def test_collect_all():
-    e = get_engine("""
-        g(a).
-        g(b).
-        g(c).
-    """)
-    heaps = collect_all(e, "g(X).")
-    assert len(heaps) == 3
-    assert heaps[0]['X'].name == "a"
-    assert heaps[1]['X'].name == "b"
-    assert heaps[2]['X'].name == "c"
-
-def test_cut():
-    e = get_engine("""
-        g(a).
-        g(b).
-        a(a).
-        b(b).
-        f(X) :- g(X),!,b(X).
-        f(x).
-        f(y).
-    """)
-    heaps = collect_all(e, "f(X).")
-    assert len(heaps) == 0
-    assert_true("!.")
-
-def test_cut2():
-    e = get_engine("""
-        g(a).
-        g(b).
-        h(a, x).
-        h(a, y).
-        f(X, Y) :- g(X), !, !, !, !, !, h(X, Y).
-    """)
-    heaps = collect_all(e, "f(X, Y).")
-    assert len(heaps) == 2
-
-def test_cut3():
-    e = get_engine("""
-        member(H, [H | _]).
-        member(H, [_ | T]) :- member(H, T).
-
-        s(a, L) :- !, fail.
-        s(b, L).
-        s(X, L) :-
-            member(Y, L),
-            L = [_| S],
-            s(Y, S).
-    """)
-    #    import pdb; pdb.set_trace()
-    assert_true("s(d, [a, b]).", e)
-
-def test_rule_with_cut_calling_rule_with_cut():
-    e = get_engine("""
-        f(b) :- !.
-        f(c).
-        g(X) :- f(X), !.
-        g(a).
-    """)
-    heaps = collect_all(e, "g(X).")
-    assert len(heaps) == 1
-
-def test_not_with_cut():
-    e = get_engine("""
-    p1 :- \\+ q1.
-    q1 :- fail.
-    q1 :- true.
-    
-    p2:- \\+ q2.
-    q2 :- !, fail.
-    q2 :- true.
-    """)
-    assert_false("p1.", e)
-    assert_true("p2.", e)
 
 def test_numbers():
     e = get_engine("""
     """)
     e.run(parse_query_term("g(2, 2)."))
 
-def test_lists():
-    e = get_engine("""
-        nrev([],[]).
-        nrev([X|Y],Z) :- nrev(Y,Z1),
-                         append(Z1,[X],Z).
-
-        append([],L,L).
-        append([X|Y],L,[X|Z]) :- append(Y,L,Z).
-    """)
-    e.run(parse_query_term("append(%s, %s, X)." % (range(30), range(10))))
-    return
-    e.run(parse_query_term("nrev(%s, X)." % (range(15), )))
-    e.run(parse_query_term("nrev(%s, %s)." % (range(8), range(7, -1, -1))))
-
-def test_indexing():
-    # this test is quite a lot faster if indexing works properly. hrmrm
-    e = get_engine("g(a, b, c, d, e, f, g, h, i, j, k, l). " +
-            "".join(["f(%s, g(%s)) :- g(A, B, C, D, E, F, G, H, I ,J, K, l). "
-                      % (chr(i), chr(i + 1))
-                                for i in range(97, 122)]))
-    t = parse_query_term("f(x, g(y)).")
-    for i in range(200):
-        e.run(t)
-    t = parse_query_term("f(x, g(y, a)).")
-    for i in range(200):
-        py.test.raises(UnificationFailed, e.run, t)
-
-def test_indexing2():
-    e = get_engine("""
-        mother(o, j).
-        mother(o, m).
-        mother(o, b).
-
-        sibling(X, Y) :- mother(Z, X), mother(Z, Y).
-    """)
-    heaps = collect_all(e, "sibling(m, X).")
-    assert len(heaps) == 3
-
-def test_runstring():
-    e = get_engine("foo(a, c).")
-    e.runstring("""
-        :- op(450, xfy, foo).
-        a foo b.
-        b foo X :- a foo X.
-    """)
-    assert_true("foo(a, b).", e)
-
 def test_handle_non_callable():
     py.test.raises(CatchableError, assert_true, "1.")
 
-def test_call_atom():
-    e = get_engine("""
-        test(a).
-        test :- test(_).
-    """)
-    assert_true("test.", e)
 
-
-def test_metainterp():
-    e = get_engine("""
-        run(X) :- solve([X]).
-        solve([]).
-        solve([A | T]) :-
-            my_pred(A, T, T1),
-            solve(T1).
-
-        my_pred(app([], X, X), T, T).
-        my_pred(app([H | T1], T2, [H | T3]), T, [app(T1, T2, T3) | T]).
-
-    """)
-    assert_true("run(app([1, 2, 3, 4], [5, 6], X)), X == [1, 2, 3, 4, 5, 6].", e)
-
-class TestHeap(object):
+class XTestHeap(object):
     def test_trail(self):
         h = Heap()
         t1 = h.newtrail()

prolog/interpreter/test/test_parsing.py

         g('ASa0%!!231@~!@#%', a, []). /* /* /* * * * / a mean comment */
     """)
     builder = TermBuilder()
-    facts = builder.build(t)
+    fact, = builder.build(t)
+    assert fact.args[0].name == 'ASa0%!!231@~!@#%'
+    assert fact.args[1].name == 'a'
+    assert fact.args[2].name == '[]'
+    t = parse_file("""
+        'a'.
+        a.
+    """)
+    builder = TermBuilder()
+    fact1, fact2, = builder.build(t)
+    assert fact1.name == fact2.name
 
 def test_parenthesis():
     t = parse_file("""

prolog/interpreter/test/tool.py

         self.heaps = []
         self.vars = vars
 
-    def _call(self, engine):
-        self.heaps.append(dict([(name, var.dereference(engine.heap))
+    def activate(self, fcont, heap):
+        self.heaps.append(dict([(name, var.dereference(heap))
                                     for name, var in self.vars.iteritems()]))
         print "restarting computation"
         raise UnificationFailed