Amb: Difference between revisions

Line 220:

=={{header|E}}==

E does not (currently) have any kind of backtracking control flow. However, since (Almost) Everything Is Message Passing, we can create an object which represents a set of possible values.

E does not currently have any kind of backtracking control flow (though there is a proposal in the works to backtrack upon exceptions, for the sake of consistency). However, since (Almost) Everything Is Message Passing, we can create an object which represents a set of possible values.

This is complicated, however, by the fact that any given amb must appear to produce only one result; that is, <code>def x := amb(["a", "b"]); x + x</code> produces aa or bb, not aa,bb,ab,ba as <code>amb(["a", "b"]) + amb(["a", "b"])</code> would. Therefore, each choice is associated with the ''decisions'' which produced it: a map from ''amb'' objects to which member of them was chosen; any combination of two ambs discards any combination of choices which have inconsistent decisions.

Line 233:

def [ambS, ambU] := <elib:sealing.makeBrand>("amb")

var counter := 0 # Used just for printing ambs

/** Check whether two sets of decisions are consistent */

def consistent(decA, decB) {

def overlap := decA.domain() & decB.domain()

Line 242:

Line 244:

}

/** From an amb object, extract the possible choices */

def getChoices(obj, decisions) :List[Choice] {

if (decisions.maps(obj)) {

Line 252:

Line 255:

}

/** Construct an amb object with remembered decisions */

var counter := 0

def ambDec(choices :List[Choice]) {

def serial := (counter += 1)

Line 292:

Line 295:

}

/** Construct an amb object with no remembered decisions. (public interface) */

def amb(choices) {

return ambDec(accum [] for c in choices { _.with([c, [].asMap()]) })

}

/** Get the possible results from an amb object, discarding decision info. (public interface) */

def unamb(ambObj) {

return accum [] for [c,_] in getChoices(ambObj, [].asMap()) { _.with(c) }

Line 325:

Line 331:

This can be compared with the Haskell use of lists as a monad to represent choice.

* Haskell uses lazy evaluation; E does not. This implementation does not simulate lazy evaluation with thunks; it is eager (computes every intermediate choice before continuing) and therefore inefficient if you only need one successful result.

* Haskell does not need to track decisions. This is because when using a monad in Haskell, the points of choice are explicitly written, either by monadic operators or combinators. The analogues to the two "ab" operations given above are: <code>do x <- ["a","b"]; return (x + x)</code> and <code>do x <- ["a","b"]; y <- ["a","b"]; return (x + y)</code> — the relevant difference being the number of <code><-</code> operators. In this implementation, we instead absorb the choice into normal method calls; the Haskell analogue would be something like <code>instance Monoid a => Monoid (Amb a) where Amb ... `mconcat` Amb ... = ...</code>, which would have a similar need to track decisions.

* Haskell does not need to track decisions. This is because when using a monad in Haskell, the points of choice are explicitly written, either by monadic operators or combinators. The analogues to the two "ab" operations given above are: <code>do x <- ["a","b"]; return (x ++ x)</code> and <code>do x <- ["a","b"]; y <- ["a","b"]; return (x ++ y)</code> — the relevant difference being the number of <code><-</code> operators. In this implementation, we instead absorb the choice into normal method calls; the Haskell analogue would be something like <code>instance Monoid a => Monoid (Amb a) where Amb ... `mconcat` Amb ... = ...</code>, which would have a similar need to track decisions.

=={{Header|Haskell}}==