Non-Deterministic Evaluation In Under 300 Bytes

Michael Hudson mwh21 at cam.ac.uk
Tue Mar 21 02:11:19 CET 2000

```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()()
_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 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
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

```