"All of the classic examples of amb require some sort of global state to keep all of the continuation instances. But this is inelegant if you wanted to have multiple usages of (amb) which don't interfere with each other: suppose for example you want to create two threads - one for solving each Sudoku puzzle."
Woo! A kindred spirit! I scratched the same itch right when I was getting started with Arc:
I haven't ended up using this code, mainly because Arc isn't a great ecosystem for reentrant continuations. Arc's looping utilities use mutation, and one of the implementations of Arc which I like to support, Jarc, doesn't support reentrant continuations at all. Maybe you can give 'amb a better home.
"At the same time, you want (amb) to be a macro which lazily evaluates the possibilities"
Not me. My version of (make-amb) simply returns a procedure that chooses one of its arguments. Given that, we can get by with just one global macro for laziness:
(lazy-amb my-amb (foo a b c) (bar d e f) (baz g h i))
((my-amb (fn () (foo a b c)) (fn () (bar d e f)) (fn () (baz g h i))))
If you can stand to define a separate macro like 'lazy-amb and use it at each call site, it's a design pattern that obviates most use cases for fexprs.
"If you can stand to define a separate macro like 'lazy-amb and use it at each call site, it's a design pattern that obviates most use cases for fexprs."
Indeed. You and I had discussed this quite some time ago, about having convenience macros that expand into thunks. This thunkification is clunky and awful, but it does indeed give many of the benefits of vau.
I still think any new Lisp should use vau, but thunkification is a great way to retrofit many of the benefits of vaus into older (?) Lisps like Arc.