DN600190793

Subject: Non-Deterministic Evaluation In Under 300 Bytes - DN [1]

Michael Hudson <mwh21@cam.ac.uk> - 21 Mar 2000 - comp.lang.python

 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