[plt-scheme] Another amb question

From: Mark Engelberg (mark.engelberg at gmail.com)
Date: Tue Apr 1 00:23:44 EDT 2008

Danny's post about amb got me thinking about amb and the
implementation in the planet repository.

SICP describes a version of amb in which amb actually keeps track of
any set! you perform, and restores the initial state upon
backtracking.  The planet version doesn't do this, and it seems to me
like you'd need to change the whole evaluation process to modify the
way set! works.  However, maybe it's possible to make a macro called
amb-set! which adds undo information to the current amb continuation.
That way, any mutation performed with amb-set! would get undone upon
backtracking.  Does that sound feasible, or is there something I'm
overlooking?  I'm thinking it might be a little tricky to make sure
that the correctly scoped variables get undone, but off the top of my
head, it seems workable.

I'm also curious whether anyone has implemented a multithreaded
version of amb that spins off different threads to explore the
choices.  I think the Mozart programming language does something
analogous to this.  Are PLT Scheme's threads lightweight enough to
handle this kind of thread proliferation, or does it rely on OS


Posted on the users mailing list.