Lambda the Ultimate

Probably would have posted this to the previous LtU story on The Reasoned Schemer, but since Ehud requested that we post some (cool) stories...

As I've mentioned in a couple of posts, I've been working on an Oz Translation of the example code in the book. At this juncture, I've got large chunks of the first seven chapters translated. It probably shouldn't be surprising that the logic programming in miniKANREN and Oz are eerily similar, given that both have been influenced by Prolog (and also given the fact that great minds think alike). Because I spent more time on the example in 3.10-3.13 then all the others combined, I think it useful in seeing the parallel. In miniKANREN, we have:

(define listo
  (lambda (l)
    (conde
      ((nullo l) succeed)
      ((pairo l)
       (fresh (d)
         (cdro l d)
         (listo d)))
      (else fail))))

(run 5 (x)
 (listo `(a b c . ,x)))

For the same examples, we have the Oz code of:

fun {Listo L}
   choice
      L = nil
   [] H T in
      L = H|T
      H|{Listo T}
   end
end

{SolveN 5 
   fun {$} X in 
      _ = {Listo a|b|c|X} 
      X
   end}

From this code, I've concluded that "run" translates to "Solve" and that "conde" corresponds to "choice". Some may find the correlation of the languages to be useful in working their way through the book, being able to tap into another way of expressing the ideas. The main difference between the two languages has to do with the various alternative search strategies. "conde" specifies a depth-first search strategy, while "condi" is a breadth-first strategy. The all, alli, conda, and condu are other variations on strategies. While Oz gives one a lot of flexibility to vary the search strategy for computation spaces, the actual strategy is determined by the Solve function (which corresponds to the "run" function in Scheme), not in the declaration of choice (conde, condi, conda, condu).

Although the other search strategies can be programmed in Oz, I'm not expert enough at this point to modify the Solve function. The remainder of the translation will have to wait until I get edumacated, or someone else completes the thought.