This is about white being to the left of green, but I have to work up to it. (Since I not yet sure I know how to think about Oz's search protocols, perhaps the following is nonsense.)
An hour ago (we have a Saturday class), I was explaining the palindrome project to my class as an introduction to Oz as a logic programming system. A piece of the code is
N1 = 10*{Digit} + {Digit}N2 = 10*{Digit} + {Digit}X = N1 * N2
where {Digit} generates all of the digits using choice. (This is from CTM chapter 9.) I said that the way to think about what's going on is that these two lines generate 10,000 threads, some of which get killed off later when X is found not to be a 4-digit palindrome. The ones that succeed produce results that are gathered together by SearchAll.
(In Prolog one would talk about backtracking. I gather that in Oz one imagines them all running at once. Is that reasonable?) (We then talked about how to kill threads early, e.g., by insisting that N1 =< N2.
If that's a reasonable way to think about Oz, then the two lines
local Rest in
{Append _ {Neighbor [color#white]} | Rest Nb}
{IsMember {Neighbor [color#green]} Rest}
end
generate all threads in which Nb is partially instantiated in such a way that the white neighbor is to the left of the green neighbor. So it's not just generate and test. It has much more of the flavor of CP but where multiple constraints are not gathered together as a range.
Is this a reasonable way to think about it?
-- Russ
On 10/8/05, Irene Langkilde-Geary <[EMAIL PROTECTED]> wrote:
Russ' solution to "Nb.green > Nb.white = true" has the same drawback
as this non-FD version---it only checks whether the constraint is true
AFTER the Nb list is instantiated. It will be much less efficient
than an FD version.
The tutorial fragment below by Denys Duchier, Claire Gardent and
Joachim Niehren nicely illustrates the difference between
generate-and-test, test-and-generate, and propagate-and-distribute for
the constraint X<Y. (See sections 2.1.2 - 2.1.4)
http://www.ps.uni-sb.de/~niehren/Web/Vorlesungen/Oz-NL-SS01/vorlesung/node5.html#subsection.constraint.combinatoric.explosion
As far as having symbolic FD and not just integer FD, the same
tutorial has code that helps bridge the gap somewhat. See 15.3.4 (and
the rest of section 15.3 might be helpful too).
http://www.ps.uni-sb.de/~niehren/Web/Vorlesungen/Oz-NL-SS01/vorlesung/node198.html#label84
But I confess, having syntactic support in Mozart itself for symbolic
FD values is my current #1 wish. Debugging a symbolic problem
expressed as integers is quite inconvenient.
Also, I don't know why no one else has mentioned it before, but if
you haven't seen the following, you might find it helpful:
"Logic Programming in Oz with Mozart" by Peter Van Roy
http://www.info.ucl.ac.be/people/PVR/iclp99_tutorial.ps
Irene
Date: Fri, 7 Oct 2005 18:38:32 -0700
From: Russ Abbott <[EMAIL PROTECTED]>
Subject: Re: What is Mozart-Oz
To: Raphael Collet < [EMAIL PROTECTED]>
Cc: [EMAIL PROTECTED]
Message-ID:
<[EMAIL PROTECTED] >
Content-Type: text/plain; charset="iso-8859-1"
Here (
http://cs.calstatela.edu/~wiki/index.php/Courses/CS_460/Fall_2005/Notes_for_Oct_8#Second_Zebra_solution)
is my version of Zebra using the list of records representation:
Nb = [neighbor(color:white dring:juice ...) neighbor(color:blue drink:tea
...) ...]
It seems quite intuitive to me.
Here's the code for green comes after white. (Since it's only used once,
it's inline.) The call
{Neighbor [color#white]}
creates a neighbor record in which color:white.
local Rest in
{Append _ {Neighbor [color#white]} | Rest Nb}
{IsMember {Neighbor [color#green]} Rest}
end
-- Russ
_________________________________________________________________________________
mozart-users mailing list [email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
