Non-determinism from generators

UPDATE(7/3/2013) I’ve found an earlier use of this technique written about on a blog, Valued Lessons – Monads in Python from 2008. Please read it too!

~~~

I was tinkering a bit tonight with simulating nondeterminism a-la McCarthy’s Amb operator — in Python. This is peculiar as Amb is usually implemented using either first class continuations or syntactic abstractions. Python supports neither.

So what is non-deterministic programming?

Background

In John McCarthy’s well known paper from 1960, he makes mention of programming using a hypothetical nondeterministic choice operator. Where a normal (deterministic) computer must always make definite choices at each step of computation, a non-deterministic computer is allowed to defer making a choice an explore both options, as if by making one choice in one universe and a different choice in a parallel universe. In some ways, this parallels the many-worlds interpretation of quantum mechanics.

In any case, a non-deterministic program can produce multiple outputs, or possibly no outputs. To express this, the ‘amb’ operator takes a list of zero or more arguments, and then arbitrarily picks one of the values to be the sole return value. If we say

x = amb(1, 2)
print x

Then in one parallel universe, the value 1 is printed to console, while in another you instead see ’2′ printed.

Finally, one can express termination as amb() taking no arguments, which effectively “implodes” that alternate universe, so only the other universes remain. This is used (in)effectively in Quantum Bogosort to sort in O(n) time per universe (with O(n!) universes).

def quantum_bogosort(thelist):
  onelist = amb(*itertools.permutations(thelist))
  if not is_sorted(onelist):
    amb()
  return onelist

Ok, that code wasn’t real; it doesn’t work.

Working Code

A common beginners problem involves finding pythagorean triplets with amb instead of explicit search. Unfortunately, we can’t write amb in python. Fortunately, we can yield.

@nondet
def pythag (Return, amax, bmax,cmax):
  a = yield range(1, amax+1)
  b = yield range(a, bmax+1)
  c = yield range(b, cmax+1)
  if a*a + b*b == c*c:
    Return((a,b,c))

Try not to mind the Return variable too much. We’re using yielding for something else, so this extra parameter acts as a “return” operator. It’s in fact just another function.

The @nondet decorator wraps the user function with one that will progressively backtrack. The first time yield range(1,amax+1) is invoked, the @nondet decorator will immediately send the first element of that list. Eventually, Return will be invoked or control will leave the function, in which case, @nondet will start the function over again, save this time that first yield will return 2, and so forth.

The @nondet decorator is a thin wrapper around a pump routine. It creates an array to gather results into, and decorates the user function:

def nondet (fn):
  def replacement (*args):
    c = []
    def Return (x):
      c.append(x)
      raise StopIteration()
    nondet_pump(lambda:fn(Return, *args))
    return c

  replacement.__name__ = fn.__name__ + "_unyield"
  return replacement

The heart of non-determinism is found in this pump:

def nondet_pump (initiator, prefix=[]):
  it = initiator()
  xs = it.next()
  try:
    for p in prefix:
      xs = it.send(p)
    for x in xs:
      nondet_pump(initiator, prefix+[x])
  except StopIteration:
    pass

The initiator parameter is a curried wrapper around the user’s function. Each time pump is invoked, it will begin iteration, play back values (as results from ‘yield’) into the user’s function until it gets to the next yield. Then, for each list that the user yielded to nondet, another nested pump is started.

If the yielded list was empty, or if the user’s generator finishes iterating, we’ll escape out of this function normally, allowing the parent pump to move on to the next element for the particular yield it is servicing.

All this overhead comes at a price:

c0 = time.clock()
for triple in pythag(20,20,20):
  print triple
c1 = time.clock()
print "elapsed time: %s seconds"%(c1-c0)

Thankfully for us, modern computers are fast. On my computer, I get the results back instantaneously.

$ python nondet_example.py
(3, 4, 5)
(5, 12, 13)
(6, 8, 10)
(8, 15, 17)
(9, 12, 15)
(12, 16, 20)
elapsed time: 0.010161 seconds

Complete code on codepad, showing output.

Other works in this space:

4 Responses to Non-determinism from generators

  1. What if the choice is made in another function but rated in blub?

    def selc():
    yield range(1,21)

    @nondet
    def blub(Return):
    c=selc()
    if c>5:
    Return(c)

    How to achieve this?

    • It’s local to functions annotated @nondet, but you could annodate selc as well. Then you could say

      @nondet
      def selc(Return):
      r = yield range(1,21)
      Return(r)
      @nondet
      def blub(Return):
      c = yield selc()
      if c > 5:
      Return(c)

      Then, blub() returns the sequence 6 thru 20.

  2. Thank you, I should have seen that :)

    Your solution is very elegant, no comparison to the strange instances of amb-operators created for Python by others.

    With this it should be very easy to convert arbitrary randomized algorithms to systematically searching ones. Normally I used Prolog for nondeterminism and I was always wondering why this mighty concept never found its way to languages of different paradigm.

  3. Pingback: (Mostly) Imperative Packrat Parsing | Dysfunctional Programming

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>