9.3

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

amb-append

  

after the first alternative ends

  

depth-first (the default)

amb-interleave

  

at each pause

  

interleaving, as in miniKanren

amb-alternate

  

at every event, answers included

  

alternating by event

amb-level

  

after every alternative reaches its next pause

  

breadth-first by pauses

Examples:
> (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.