Non-Deterministic Evaluation In Under 300 Bytes

[Michael Hudson]

I was playing around with Chris Tismer's stackless python today, and
wondering what I could actually use continuations for, so I pulled my
copy of On Lisp off the bookshelf and came up with:

from continuation import caller

def choose(cs):
    if not cs:
        if _p:
            _p.pop()()
        raise "no answers found"
    _p.append( lambda c=cs[1:],k=caller():k(choose(c)) )
    return cs[0]

def amb_eval(f,*a):
    global _p; _p = []
    try:
        return apply(f,a)
    finally:
        _p = []

(that's actually 317 bytes, but if you take the indentation down to 1,
it's about 280).

It can be used like so:

Python 1.5.42 (#1, Mar 19 2000, 15:06:01)  ...
Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
>>> import short_amb # I have a more verbose, easier to use version...
>>> def trick(n):
...     x = short_amb.choose(range(2,11,2))
...     y = short_amb.choose(range(1,11))
...     if x + y <> n: short_amb.choose([])
...     return x,y
... 
>>> short_amb.amb_eval(trick,12)
(2, 10)

(the example's from On Lisp).

It's not fast, but I think it's cute, and quite a nice exposition of
just how powerful continuations can be.

Random thoughts:

1) excessive use of side effects in code being non-deterministically
   evaluated *will* make you're head explode.  
2) call-with-current-continuation is a *really bad* interface to the
   continuation world, at least from the point of actually
   understanding the code (I implemented the above by writing a
   call/cc function, transliterating the scheme version Graham
   presents in the book, and then "unwinding" the calls to
   call/cc. The result made more sense then the original - even than
   the scheme!). Chris's approach is better, at least for me.
3) The above does a depth-first search of the solution space, but can
   be made to do breadth first search with the addition of a single
   character ("_p.pop()()" -> "_p.pop(0)()").

Anybody feel like extending the above to unification/resolution and
hence embedding (possibly the slowest implementation the world has
ever seen of) a prolog-style language in Python?  I'd give it a stab,
but I don't know logic programming that well.

i-want-an-iopcc-ly y'rs
M.

-- 
very few people approach me in real life and insist on proving they are
drooling idiots.                         -- Erik Naggum, comp.lang.lisp