Ilya Tsindlekht wrote
It may be useful to relate to imperative programming: m1 >>= (\x -> m2) is let x = m1 in m2 The analogy is not always straight-forward - try the list monad.
This equivalence holds even for the List Monad. Here is an example of non-determinism: http://caml.inria.fr/pub/ml-archives/caml-list/2007/02/1d4df471019050b89e20a... and here's an excerpt from that message, showing lets (aka bind): let numbers = List.map (fun n -> (fun () -> n)) [1;2;3;4;5];; let pyth () = let (v1,v2,v3) = let i = amb numbers in let j = amb numbers in let k = amb numbers in if i*i + j*j = k*k then (i,j,k) else failwith "too bad" in Printf.printf "got the result (%d,%d,%d)\n" v1 v2 v3;; Here, 'amb' is like 'msum' and any error is mzero. If we replace 'let' with 'do', and '=' with '<-' in some places, it looks almost like Haskell. Although the scheduler (the `run' function of the `monad') described in the message accumulates all possible worlds, it returns as soon as one `thread' made it successfully to the end. It is trivial to get the scheduler to run the remaining `treads' searching for more answers (by threads I certainly don't mean OS threads). The user code above stays as it is. The implementation of amb has been extended to annotate choices (and so possible worlds) with probabilities, which propagate in due course. The result not merely lists the answers but also their computed probabilities.
Filinski then showed that the latter seemingly missing aspect indeed only appears to be missing. Would this require some kind of macros doing extensive pre-processing of the code?
Hopefully the code above showed that no macros and no preprocessing required. In that code, addition, multiplication, if-then-else and all other OCaml operations remain as they have always been, with no modifications or redefinitions whatsoever. Delimited continuations suffice for everything, as Filinski proved in his paper.