11–20 of 43 posts
All in all, this seems like a fun hack, but a catastrophically bad idea in practice.
amb without side-effects can also be expressed in terms of the List monad, e.g.: do x which can be equivalently reworded as the list comprehension: [(x, y) | x i.e., the underlying structure of amb without side-effects can also be understood as just a search of the input space for values that fulfill some criteria, rather than as backtracking via continuations.
This analogy misses something fundamental. See how the assignments to x and y are of very different character than the predicate? Notice the return path (`else []`). `amb` doesn't need this. `amb` merges the assignments and predicate - this is important because you may not know your argument count statically, i.e. if your arguments are a list. But beyond that, `amb` may backtrack an arbitrarily deep call stack, so th…
-- Lifts a list into Amb.
amb :: [a] -> Amb a
amb = id
amb [1, 2, 3] >>= \x ->
amb [4, 5, 6] >>= \y ->
if x * y /= 8 then amb [] else pure () >>
pure (x, y)
amb [1, 2, 3] >>= \x ->
amb [4, 5, 6] >>= \y ->
when (x * y /= 8) (amb []) >>
pure (x, y)
It ends up looking like continuation-passing style: conceptually, if we encounter `amb []` in the nested function, the nested computation ends and we start examining the next value in the list values being assigned to `x`: the implementation given in the original post does end up using callcc, so with some imagination you might be able to derive some kind of equivalence here :)
SICP spends many pages on this.
right, actually one of the topics were i stopped on my first readings. https://mitpress.mit.edu/sites/default/files/sicp/full-text/...
It supports first class macros, continuations, and has the amb "operator" (implemented using a macro of course!): https://github.com/Patient0/FirstClassLisp/blob/master/Lisp/...
amb without side-effects can also be expressed in terms of the List monad, e.g.: do x which can be equivalently reworded as the list comprehension: [(x, y) | x i.e., the underlying structure of amb without side-effects can also be understood as just a search of the input space for values that fulfill some criteria, rather than as backtracking via continuations.
This analogy misses something fundamental. See how the assignments to x and y are of very different character than the predicate? Notice the return path (`else []`). `amb` doesn't need this. `amb` merges the assignments and predicate - this is important because you may not know your argument count statically, i.e. if your arguments are a list. But beyond that, `amb` may backtrack an arbitrarily deep call stack, so th…
foo = do
x Earlier quoted context omitted.
This analogy misses something fundamental. See how the assignments to x and y are of very different character than the predicate? Notice the return path (`else []`). `amb` doesn't need this. `amb` merges the assignments and predicate - this is important because you may not know your argument count statically, i.e. if your arguments are a list. But beyond that, `amb` may backtrack an arbitrarily deep call stack, so th…
We can implement it with a single `amb` function, too (I took some shortcuts that might have hidden some of the nature of the implementation)! -- Lifts a list into Amb. amb :: [a] -> Amb a If we assume Amb is just List, then: amb = id If we write the example in the original article in desugared style, we get: amb [1, 2, 3] >>= \x -> amb [4, 5, 6] >>= \y -> if x * y /= 8 then amb [] else pure () >> pure (x, y) (we are…
You still get credit for solving the basic problem but let's not be misleading.
Also don't forget to call head.
amb without side-effects can also be expressed in terms of the List monad, e.g.: do x which can be equivalently reworded as the list comprehension: [(x, y) | x i.e., the underlying structure of amb without side-effects can also be understood as just a search of the input space for values that fulfill some criteria, rather than as backtracking via continuations.
This analogy misses something fundamental. See how the assignments to x and y are of very different character than the predicate? Notice the return path (`else []`). `amb` doesn't need this. `amb` merges the assignments and predicate - this is important because you may not know your argument count statically, i.e. if your arguments are a list. But beyond that, `amb` may backtrack an arbitrarily deep call stack, so th…
The McCarthy '63 paper referred to seems to be here: http://www-formal.stanford.edu/jmc/basis1/basis1.html
If you like this, you might also enjoy:
- Prolog: This is an entire language built around choice and backtracking. https://en.wikipedia.org/wiki/Prolog
- The Reasoned Schemer, which builds a Prolog-in-Scheme from first principles. This book is excellent, or even mind-blowing if you're never seen this before. https://mitpress.mit.edu/books/reasoned-schemer
- Oz/Mozart: This language takes the basic idea even further, adding concurrency and constraint solving. There's an older book about this that's nice: https://www.info.ucl.ac.be/~pvr/book.html It feels like Oz was an evolutionary dead end, but an interesting one.
- Probability monads. You can extend this general idea to include probability distributions over values. I have an older series of blog posts at http://www.randomhacks.net/probability-monads/ that explains this idea piece-by-piece, but there's been a ton of research in the past decade on probabilistic languages: http://www.probabilistic-programming.org/wiki/Home
It's definitely a fun topic!