Amb in JavaScript

Great post but it's the language and syntax hoop-jumping that is required in JavaScript to do paradigm experimentation (or playing as Feynman would call it) that's pushed me to take the time to explore other languages.

Here's the Fish/Zebra/Einstein puzzle in my Clojure logic programming library based on miniKanren, this program is solved on my machine in 2 milliseconds - even though this version involves unification and logic variables. It also reads better IMO and should look familiar to the Prologist:

  (defn-e first-o [l o]
    ([[?a . ?d] ?a]))

  (defn-e member-o [x l]
    ([_ [x . ?tail]])
    ([_ [?head . ?tail]]
       (member-o x ?tail)))

  (defn-e on-right-o [x y l]
    ([_ _ [x y . ?r]])
    ([_ _ [_ . ?r]] (on-right-o x y ?r)))

  (defn next-to-o [x y l]
    (cond-e
     ((on-right-o x y l))
     ((on-right-o y x l))))

  (defn zebra-o [hs]
    (macro/symbol-macrolet [_ (lvar)]
     (all
      (== [_ _ [_ _ 'milk _ _] _ _] hs)                         
      (first-o hs ['norwegian _ _ _ _])                         
      (next-to-o ['norwegian _ _ _ _] [_ _ _ _ 'blue] hs)       
      (on-right-o [_ _ _ _ 'ivory] [_ _ _ _ 'green] hs)         
      (member-o ['englishman _ _ _ 'red] hs)                    
      (member-o [_ 'kools _ _ 'yellow] hs)                      
      (member-o ['spaniard _ _ 'dog _] hs)                      
      (member-o [_ _ 'coffee _ 'green] hs)                      
      (member-o ['ukrainian _ 'tea _ _] hs)                     
      (member-o [_ 'lucky-strikes 'oj _ _] hs)                  
      (member-o ['japanese 'parliaments _ _ _] hs)              
      (member-o [_ 'oldgolds _ 'snails _] hs)                   
      (next-to-o [_ _ _ 'horse _] [_ 'kools _ _ _] hs)          
      (next-to-o [_ _ _ 'fox _] [_ 'chesterfields _ _ _] hs))))

  (run 1 [q] (zebra-o q))

Here is a nice paper on how to prune the execution tree when using amb: Non-deterministic lisp with dependency-directed backtracking; http://www.aaai.org/Papers/AAAI/1987/AAAI87-011.pdf

I've not played much with amb or Prolog, but it would be cool to try out some alternative strategies for exhausting the search tree, perhaps simulated annealing or something like that.

This is the sort of language feature that looks very neat at first, but there are simpler ways to solve the same problems. If you want to search a space by trying all possibilities ("generate and test"), the most straightforward way is a nested for loop with an if statement.

The advantage of using nested for loops is that it's pretty clear that there's a performance problem and most programmers will have a good idea what to do about it. (Perhaps change the order of the loops, do checks in the outer loops to avoid running the inner loops, and so on. For larger problems, figure out how to parallelize.)

Of course, a for loop isn't very modular, so something like Python's generator expressions might be more suitable for building pipelines. In Java, this can be done with iterators and some good iterator utility methods, such as those in Guava.

Haven't seen this operator before; reminds me of angelic programming. (see eg. http://portal.acm.org/citation.cfm?id=1706339)

This also seems like a very natural application of monads.