Non-Deterministic Evaluation In Under 300 Bytes

[Michael Hudson]

aahz at netcom.com (Aahz Maruch) writes:

> In article <m3og89qg94.fsf at atrus.jesus.cam.ac.uk>,
> Michael Hudson  <mwh21 at 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