Talk:Amb: Difference between revisions
→Go: new section
(→C) |
(→Go: new section) |
||
Line 62:
if that helps -- this uses setjmp/longjmp, and includes a few examples; no external code is required.
== Go ==
I added a solution inspired more by [http://www-formal.stanford.edu/jmc/basis.html| McCarthy's original paper] than the SICP presentation. McCarthy talks about functions which may be "undefined" in some cases and says, "...when the computation process fails to terminate, the result is undefined." (bottom of p. 7 in the PDF.) The Go version handles this with channels and goroutines.
He defines amb as a binary operator on x and y where either or both may be undefined. That is, x and y are separate computations which may or may not terminate. He talks of functions having possible values (plural) and while he doesn't specify that amb must enumerate its defined values, we assume so because we want to do backtracking. This binary enumerating amb can be composed into a form that works with multiple values. The result, in a context of computations that take an unknown amount of time, is a form that may yield a number of values, but perhaps not immediately, perhaps not all at once, perhaps never. A goroutine supplying values over a channel has this capability.
The function ambString shows this and gives us the enumerating property we need for searching. It takes a string slice and iterates over it, providing slices of length 1 on the result channel. If preparing the result slices were truly computations of unknown and potentially infinite duration, preparation of each slice could be done as a separate goroutine, but this would be overkill for the task. The important part is the result channel. The function creates the channel, starts the goroutine, and returns the channel without waiting for the goroutine to do anything. A caller of this function gets the channel back almost immediately, but then should assume that it might have to wait an unknown amount of time for an unknown number of results.
The function ambChain relies another concept of McCarthy's paper, "operator Am(x,π(x)) whose values are all x's satisfying π(x)." Here we understand that x is a computation with multiple possible values and π is a predicate that selects a subset of them. In ambChain, the call to ambString in the inner loop is the "x" of Am, and the boolean expression in the if statement on the next line is the predicate π. Just as the composed amb function of ambString runs as a separate goroutine, this Am operation runs as a separate goroutine. These goroutines started as the inner loop of the matching operation execute concurrently. The results of the Am operation are new, longer chains of words which are returned on a channel, maintaining amb behavior. ambChain has only a single result channel. The concurrent goroutines all send their matches on this common channel. The caller of ambChain does not know how many matches might be returned, but ambChain can recognize when it has enumerated all possibilities. It uses a sync.WaitGroup to track completion of goroutines and can close the result channel as ambString does.
The driver main enumerates the results of chaining the four word lists. If there were no matches, there would be no output. If there were multiple matches, it would print them all. If the computations were lengthy, results would be printed as the computations completed. The separate goroutines of ambString and ambChain ensure that even if some computations failed to terminate, any computations which could complete would, and return any found matches. —[[User:Sonia|Sonia]] 02:22, 29 February 2012 (UTC)
| |||