1 Evaluation Model
A search runs a computation and reports a sequence of events. An event is an answer (the values that the computation returned), a pause, or the end. The computation takes part in the search through three effects:
A failure (amb-fail) ends the computation here, without an answer.
A pause (amb-pause) makes the search report a pause. The computation goes on when the search is asked for its next event.
A choice (make-amb, and the forms built on it: amb, for/amb, sequence->amb) runs the rest of the computation once for each alternative that is scheduled, and merges the events of those runs into one sequence. A choice among no alternatives, such as (amb), fails.
How the events of the alternatives are merged is the search strategy. It belongs to the choice: every choice merges its alternatives with the merger held by current-amb-merger where the choice is made. The four mergers of amb/merge differ in when they pass the turn from one alternative to the next:
merger |
| when the turn passes |
| strategy |
| after the first alternative ends |
| depth-first (the default) | |
| at each pause |
| interleaving, as in miniKanren | |
| at every event, answers included |
| alternating by event | |
| after every alternative reaches its next pause |
| breadth-first by pauses |
> (require amb/merge)
> (define (count-from n) (amb n (begin (amb-pause) (count-from (add1 n)))))
> (for/list ([x (in-amb (list (amb 'a 'b) (count-from 0)))] [_ 6]) x) '((a 0) (a 1) (a 2) (a 3) (a 4) (a 5))
> (parameterize ([current-amb-merger amb-interleave]) (for/list ([x (in-amb (list (amb 'a 'b) (count-from 0)))] [_ 6]) x)) '((a 0) (b 0) (a 1) (b 1) (a 2) (b 2))
A search is lazy. An alternative is not evaluated before it is chosen, an alternative that a merger has not turned to has not started, and after an event the search does nothing until it is asked for the next one.