Non-Deterministic Evaluation In Under 300 Bytes

0 views
Skip to first unread message

Michael Hudson

unread,
Mar 21, 2000, 3:00:00 AM3/21/00
to
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

Christian Tismer

unread,
Mar 26, 2000, 3:00:00 AM3/26/00
to Michael Hudson

Michael Hudson wrote:
>
> 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:

[A really nice example that I could never imagine!]

Thank you, this is incredible.

...


> 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.

On the call/cc issue: I have been tinkering with this
at length. It is easy to write your own call/cc with
Stackless Python, but it turned out to be not so very useful,
for a couple of reasons:

- Having an explicit continuation as a parameter can cause
unwanted circular references which are hard to remove.
- Python gives you an implicit continuation all the time:
You always have a caller. Tis is the frame where the
return statement would usually return to.
This makes it easy to catch your caller just when it
is needed.
- You still *can* use direct call/cc style if you need it.
This is about 3 lines of Python code.

All in all, it turned out to be more natural to use just
the continuations which Python gives you for free. A major
problem was how to access them easily. The most powerful
and complication-less functions are:

continuation.caller() - get me my caller
continuation.return_current() - return *me* to my caller

The latter is new with Version 1.1, and it was exactly
the missing counterpart for caller. It allows you to
initialize a function via the normal call interface
and then jump back immediately, returning your own
continuation as a callable object.

see you soon at http://www.stackless.com with SLP 1.1 - chris

--
Christian Tismer :^) <mailto:tis...@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaunstr. 26 : *Starship* http://starship.python.net
14163 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
we're tired of banana software - shipped green, ripens at home


Aahz Maruch

unread,
Mar 26, 2000, 3:00:00 AM3/26/00
to
In article <m3og89q...@atrus.jesus.cam.ac.uk>,

Michael Hudson <mw...@cam.ac.uk> wrote:
>
>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:

For those of us who don't have _On Lisp_, could you explain what the
code does?
--
--- Aahz (Copyright 2000 by aa...@netcom.com)

Androgynous poly kinky vanilla queer het <*> http://www.rahul.net/aahz/
Hugs and backrubs -- I break Rule 6

Member of the Groucho Marx Fan Club --Aahz

Neel Krishnaswami

unread,
Mar 26, 2000, 3:00:00 AM3/26/00
to
Michael Hudson <mw...@cam.ac.uk> wrote:
>
> 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.

Heh -- probably the slowest prolog in the universe is Mini-Prolog run
under the Hugs Haskell interpreter.


Neel

Michael Hudson

unread,
Mar 27, 2000, 3:00:00 AM3/27/00
to
aa...@netcom.com (Aahz Maruch) writes:

> In article <m3og89q...@atrus.jesus.cam.ac.uk>,
> Michael Hudson <mw...@cam.ac.uk> wrote:
> >
> >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:
>
> For those of us who don't have _On Lisp_, could you explain what the
> code does?

I can try.

Here's a somewhat expanded version of what I posted.

from continuation import caller

_paths = []

class Path:
def __init__(self,choices):
self.cont = caller(2)
self.choices = choices
def fail(self):
self.cont( choose( self.choices ) )

def choose(choices):
if not choices:
fail()
_paths.append( Path(choices[1:]).fail )
return choices[0]

def fail():
if _paths:
_paths.pop()()
else:
raise "no answers found"

def require(cond):
if not cond:
fail()

def amb_eval(func,*args):
global _paths
_paths = []
try:
return apply(func,args)
finally:
_paths = []

And consider this (which is an example Graham uses in On Lisp):

def trick(n):
x = choose(range(1,10))
y = choose(range(1,10))
require(x + y == n)
return x,y

>>> amb_eval(trick,8)
(1, 7)

The amb_eval driver is just to make sure that no junk is left behind
after the evaluation finishes, and can be ignored when trying to
understand how this works.

When you execute choose(some_list) the first item of some_list is
returned, and a thunk is stashed away that contains the rest of the
list, and where this execution of choose is returning to.

If you then call choose again with some other list, then another thunk
is stored which stores where *this* execution of choose returns to.

If then execution proceeds without a call to `fail()' (or
`choose([])', they're synonymous) - eg. if you call amb_eval(trick,2)
- then nothing interesting happens.

When fail does get called, the most recent thunk is retrieved and
activated. This examines the list it contains (the tail of the list
originally passed to choose) and if it is non-empty stores the rest of
the (rest of the) list and the continuation in another thunk, and then
returns the head of its list to the where the first choose was called
from. If the thunk contains the empty list, it calls fail again which
retrieves the next thunk from the stack, and so on. If the thunk
stack is exhausted, then an exception is thrown.

If you execute `amb_eval(trick,11)' then the line

require(x + y == n)

will get executed nine time with x=1 (as y ranges from 1 to 9), then
eight more x=2 (as y ranges from 1 to 8), all of which result in a
call to fail(), and the manipulation of thunks as described above, and
then gets executed with x=2, y=9, which doesn't call fail(), so
execution proceeds on to the return statement and back out into the
Deterministic World.

Is this helping?

Cheers,
M.

--
well, take it from an old hand: the only reason it would be easier
to program in C is that you can't easily express complex problems
in C, so you don't. -- Erik Naggum, comp.lang.lisp

Reply all
Reply to author
Forward
0 new messages