4 Mergers
| (require amb/merge) | package: amb |
A merger is a procedure that makes one generator of two; it is the strategy of a choice. The merger of a choice is the value of current-amb-merger where the choice is made.
All four mergers of this module agree on the end of the first generator (end ∨ t = t), and all except amb-alternate agree on answers too:
end ∨ t = t |
(a : s) ∨ t = a : (s ∨ t) (amb-alternate: a : (t ∨ s)) |
They differ in what a pause of the first generator does:
amb-append (pause s) ∨ t = pause (s ∨ t) s keeps the turn |
amb-interleave (pause s) ∨ t = pause (t ∨ s) the turn passes on |
amb-alternate (pause s) ∨ t = pause (t ∨ s) the turn passes on |
amb-level (pause s) ∨ (pause t) = pause (s ∨ t) both wait together |
4.1 What a Merger Must Do
Any procedure that takes two generators and returns a generator can be the value of current-amb-merger. The library requires three things of it.
It follows the generator protocol. Its results are lists, #f or positive integers; it calls each generator at most once; and it does not call a generator after its end.
It preserves equivalence of logical events. Replacing either input with one that produces the same logical events must preserve the merged events. Compare answers in order and count individual pauses. Reaching the end and diverging while producing the next event are distinct. For example, an input that returns 3 can be replaced with one that returns 1 three times. The library itself regroups batches of pauses.
It has no effects of a search. A merger must not call amb, amb-pause, amb-fail or any other choice. A merger runs outside the search whose alternatives it merges, from its first call on: first it is called by the caller of that search, later by whoever asks the merged generator for an event. Such an effect therefore never belongs to the search that the merger works for, but to whatever search surrounds its caller, if any, and the merger cannot know which. A merger pauses by returning a number.
Here is amb-interleave written out. It shows how a merger handles a batch of n pauses: it takes one pause of the batch, passes the turn, and leaves the other (- n 1) in front of s.
(define ((my-interleave s t)) (let-values ([(v s) (s)]) (cond [(list? v) (values v (my-interleave s t))] [(not v) (t)] [else (values 1 (my-interleave t (pauses (sub1 v) s)))]))) ; n pauses, then g (define (pauses n g) (if (zero? n) g (λ () (values 1 (pauses (sub1 n) g)))))
A version that returns (values v (my-interleave t s)) for a pause, passing the turn once for a whole batch, is wrong: it gives different events for 3 than for 1, 1, 1.
4.2 Laws That a Merger May Satisfy
These laws are optional. All the mergers of this module satisfy the first; amb-append and amb-level also satisfy the second. The examples below compare logical events, with a fixed merger and the default shuffler for every choice.
The end is a unit. Merging with a generator that ends at once changes no event. make-amb merges the last alternative with the end of the supply; under this law that merge is invisible, so (amb e) has the events of e, and an alternative that fails immediately can be added or removed without changing the events.
Associativity. Nested choices have the events of one flat choice: (amb (amb a b) c) and (amb a (amb b c)) are the same. This does not hold for amb-interleave and amb-alternate, where nesting decides how often each alternative gets the turn.
An empty choice ends the branch without invoking the merger. (amb (amb) (amb)) still merges its two alternatives. A merger without the unit law can make that difference visible.
> (require amb/merge)
> (define ((pause-before-append s t)) (values 1 (amb-append s t)))
> (parameterize ([current-amb-merger pause-before-append]) (list (stream->list (in-amb (amb) #:on-pause (λ () 'pause))) (stream->list (in-amb (amb (amb) (amb)) #:on-pause (λ () 'pause))))) '(() (pause pause))
Whatever the merger, the rest of the computation distributes over the alternatives of a choice: (f (amb a b)) has the events of (amb (f a) (f b)). This needs no law.
A merger that gives every alternative the turn again and again is fair. Fairness is a property of whole runs, not an equation. amb-append is not fair.
4.3 Fairness Needs Pauses
A merger can only pass the turn at an event. A computation that runs forever without an answer and without a pause keeps the turn, whatever the merger. A search with amb-interleave, amb-alternate or amb-level therefore finds every answer at a finite depth, provided that
every choice has finitely many alternatives (but see below);
every step of the computation, and of the supply of alternatives, terminates; and
every infinite path of the computation has infinitely many pauses.
The usual way to meet the last condition is to pause at the entry of every recursive procedure, as miniKanren does at every relation. The conditions concern all the choices and paths of the search: mixing in an unfair merger, or hiding the pauses inside a local observation, loses the guarantee.
A choice among infinitely many alternatives goes beyond those conditions. Suppose the supply produces one alternative at a time without pauses, each step of the supply terminates, and every alternative starts with a pause. That opening pause alone is not enough for every merger:
With amb-interleave, every scheduled remainder—each time an alternative is resumed—must pause or end after finite ordinary computation and finitely many answers. Otherwise one alternative can keep producing answers without ever giving later alternatives their turn.
With amb-alternate, every requested remainder must produce its next event or end after finite ordinary computation. Because answers pass the turn too, an alternative that produces infinitely many answers needs no further pauses.
With amb-level, a pause-free infinite supply cannot finish the first round: before returning the first merged pause, it would have to start infinitely many alternatives. Pauses in the supply itself can let each round finish when the supply pauses or ends after a finite prefix of new alternatives in each round and every active remainder pauses or ends after finite ordinary computation and finitely many answers.
As before, local observations must not hide the pauses needed for scheduling, and every choice involved must use the corresponding fair merger. Under these conditions, amb-interleave and amb-alternate reach every answer that lies at a finite position in the supply and after finitely many events. The following search meets these conditions for amb-interleave.
> (require amb/merge)
> (define (pythagorean) (define a (for/amb ([n (in-naturals 1)]) (amb-pause) n)) (define b (for/amb ([n (in-naturals 1)]) (amb-pause) n)) (define c (for/amb ([n (in-naturals 1)]) (amb-pause) n)) (unless (= (+ (* a a) (* b b)) (* c c)) (amb)) (list a b c))
> (parameterize ([current-amb-merger amb-interleave]) (stream-first (in-amb (pythagorean)))) '(3 4 5)
Without the pauses, or with amb-append, this search does not terminate.