I have just implemented the "amb" operator, as commonly found in
Scheme. It is often called the angelic, or ambiguous operator. It allows
to implement backtracking the easy way. It works by selecting the first
item in the given list and returning it, then the second one when
"amb-fail" is called, then the third one, and so on. When there are no
more alternatives, it either goes up one level if calls to "amb" have
been stacked, or signals an error if there are no more embedded "amb"
calls.
(scratchpad) { "foo" "bar" } amb
--- Data stack:
"foo"
(scratchpad) amb-fail
--- Data stack:
"bar"
(scratchpad) amb-fail
amb: no more alternatives
Let's assume we want to find an even value in a list. We will do this by
calling "amb-fail" on other (non-even) items:
(scratchpad) { 1 2 3 4 5 } amb dup odd? [ amb-fail ] unless
--- Data stack:
2
Now, we are not pleased with this value, so we would like the next one
satisfying this criteria:
(scratchpad) amb-fail
--- Data stack:
4
"amb" has saved the continuation and restarted from the same point with
the next value in the list.
Let's look for another one:
(scratchpad) amb-fail
amb: no more alternatives
Calls to "amb" can be nested, as demonstrated thereafter. We are looking
for all the couples (with one item in the first list and the other one
in the second list) such as their product is 30:
(scratchpad) { 1 2 3 4 5 6 } amb { 1 2 3 4 5 6 } amb 2dup * 30 = [ amb-fail ]
unless
--- Data stack:
5
6
(scratchpad) amb-fail
--- Data stack:
6
5
(scratchpad) amb-fail
amb: no more alternatives
Also, the "bag-of" word takes a quotation and runs it as long as it
returns result even when a failure is forced afterwards:
(scratchpad) [ { 1 2 } amb { 1 10 } amb * ] bag-of
--- Data stack:
V{ 1 10 2 20 }
The "amb", "amb-fail" and "bag-of" words are located in "extra/amb" (as
soon as Slava pulls it).
Sam
--
Samuel Tardieu -- s...@rfc1149.net -- http://www.rfc1149.net/
------------------------------------------------------------------------------
Register Now for Creativity and Technology (CaT), June 3rd, NYC. CaT
is a gathering of tech-side developers & brand creativity professionals. Meet
the minds behind Google Creative Lab, Visual Complexity, Processing, &
iPhoneDevCamp asthey present alongside digital heavyweights like Barbarian
Group, R/GA, & Big Spaceship. http://www.creativitycat.com
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
