9.3

7 Changes from Version 2🔗ℹ

Version 3 is a new design. A search is no longer a tree whose frontier a driver schedules, but a merge of generators, and the strategy is a value that belongs to each choice. Programs that only use amb, for/amb, amb-fail and in-amb with the default strategy behave as before.

The most visible change. In version 2, current-amb-fair? made a search complete over infinitely many alternatives without any change to the program. In version 3, fairness comes from the pauses of the program (Fairness Needs Pauses), so such a program, moved to version 3 unchanged, does not terminate. To port it, choose amb-interleave, and put an (amb-pause) in every alternative of an infinite choice and at the entry of every recursive procedure that can recur forever without an answer.

The differences, one by one:

Version 2

  

Version 3

current-amb-depth-first? set to #f gave breadth-first search by choices.

  

The parameter is removed. amb-level is breadth-first by pauses; in a program without pauses it is depth-first.

current-amb-fair?, set inside a computation, decided where the tree went back into the frontier of the whole search.

  

The parameter is removed. current-amb-merger belongs to the choice made under it, and merges the alternatives of that choice only.

The two parameters gave four strategies.

  

There are four mergers, which are different strategies. On programs without pauses, depth-first is amb-append, and depth-first with fairness is amb-alternate; the two breadth-first strategies have no counterpart.

(amb) was answered by the handler of #:empty-handler, and abandoned the rest of the computation. A pause was written (when (amb #t #f) (amb)).

  

(amb) fails. A pause is (amb-pause); the computation goes on after it, and the observer sees it through #:on-pause.

A choice with no alternatives, such as an empty for/amb, was answered by that handler too.

  

It fails.

The handler ran inside the search, where (amb) was called. Reaching (amb) of the same search from the handler was a reentry error.

  

The handler of #:on-pause is called by the observer, outside the search. An effect in it belongs to the search around the observer.

The shuffler was not called for a choice with no alternatives.

  

It is called once for every vector of alternatives, the empty one too.

A fair search needed no pauses.

  

It needs them; see above.

make-amb took two procedures, more? and get.

  

It takes one generator. sequence->amb is exported.

amb/private/amb exported unsafe-amb*.

  

The module is removed.

A choice or a failure in a clause of for/amb did something that depended on the implementation.

  

It is an error (Code That Supplies Alternatives).

After an exception in the search, reading on ran the same part of the search again.

  

Reading on is an error (After an Exception).