Home

The Reasoned Schemer with Oz

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.

By Chris Rathman at 2006-04-01 21:11 | Misc Books | other blogs | 13300 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

A footnote...

Not that it makes a big difference, but a truer translation would probably have the o-functions be procedures. miniKANREN uses these functions to unify the values, but doesn't really use the function to return a value. So the alternative in Oz would be:

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

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

It's probably more typical to wrap choices within functions for Oz, so that's why I chose that route instead.

P.S. I can't seem to edit my original story. Lot's of speling mistaaks that I let slip through.

[Edit Note: I finally found the edit story tab.]

By Chris Rathman at Sat, 2006-04-01 21:34 | login or register to post comments

A better explanation of Listo...

...can be found in Oleg's reply to a question I was asking on comp.lang.scheme. I think what he's saying about the way to think about assertions is also the proper way to think of the Oz code as well. But then when you mix functional and logic programming together, you have to expect people like me mixing their metaphors. :-)

By Chris Rathman at Sun, 2006-04-02 02:16 | login or register to post comments

Search Engine Definition in Oz

Chris Rathman wrote: I'm not expert enough at this point to modify the Solve function

Detailed information how to define search engines can be found in

Christian Schulte. Programming Constraint Services. High-Level Programming of Standard and New Constraint Services. Springer. 2002

An example solver is here (the definition Solve).

BTW: CTM (p. 622) recommends using constraint programming instead of relational programming with choice. The choice operation should be used mainly for small problems, as a testing tool, or for teaching purposes.

By Torsten Anders at Tue, 2006-04-04 06:32 | login or register to post comments

Relational Programming

Aren't indexes (as used in relational-databases) just methods of restricting the search space in much the same way as constraint services are? Relational programming doesn't mean that we examine the full cross product of choices necessarily does it?

By Gavin Mendel-Gleason at Wed, 2006-04-05 11:59 | login or register to post comments

Relational Programming vs Constraint Programming

I am not quite sure I got your question right. What do you mean be indices?

The advantage of constraint programming over relational programming (in the context of Oz) is efficiency. Constraints propagate, i.e. information is deduced without search -- which reduces the search space by magnitutes.

By Torsten Anders at Wed, 2006-04-05 14:33 | login or register to post comments

Indices

Database indices are just a performance tool, an implementation pecularity, and as such can be ignored when discussing relational programming.

By vc at Wed, 2006-04-05 17:23 | login or register to post comments

That was the point I was trying to make

The difference between CLP and Relational programming seems to be one of the types of performance tricks used.

If in fact we can ignore performance conciderations then I don't see there being any difference between CLP and relational programming.

Unless I'm missing something.

By Gavin Mendel-Gleason at Thu, 2006-04-06 11:44 | login or register to post comments