Dear Mark,
Constraint propagators are efficiently implemented in C++, as you
said. Still, you can do define constraints in Oz too. For example,
you can combine propagators to new constraints. You can also define
quasi constraints by means for logic programming (using unification).
You can even define constraint systems from scratch in Oz, though
this is not efficient. Here are a few examples.
Here is a simple example how to define new constraints be combining
existing constraints. The build-in constraint FD.max works for two FD
integers. The following constraint Max works for an arbitrarily long
list of FD integers. Internally it uses the FD.max build-in propgator.
/** %% Y is constrained to be the maximum element in Xs. Xs is a
list of FD integers and Y is (implicitely declared) a FD integer.
%% */
proc {Max Xs Y}
{Accum Xs
fun {$ X1 X2} {FD.max X1 X2} end
Y}
end
/** %% Binds the accumulation of the binary function Fn on all
neighbors in Xs to Y. E.g., Accum returns the sum in Xs if Fn is
Number.'+'.
% */
proc {Accum Xs Fn Y}
{List.foldL Xs.2 Fn Xs.1 Y}
end
Here is a simple example which uses unification in order to define a
constraint Cycle. The elements in Xs can be FD integers.
/** %% Unifies every element in Xs with its Lth predecessor.
%% */
proc {Cycle Xs L}
{Pattern Xs
proc {$ X Predecessors Ignore}
if {Length Predecessors} >= L
then X = {Nth Predecessors L}
end
end}
end
/** % Pattern constraints Xs to a pattern. Proc constraints a
single pattern item and is called recursively. Proc expects three
arguments: the current item, a list with all previous pattern items
in reverse order -- last is first), the number of generations
processed so far (i.e. Proc is called for all items in Xs.
%*/
proc {Pattern Xs Proc}
proc {Aux ToProcess Processed N}
{Proc ToProcess.1 Processed N}
if ToProcess.2 \= nil
then {Aux ToProcess.2 ToProcess.1|Processed N+1}
end
end
in
{Aux Xs nil 1}
end
%% example application
{ExploreOne
proc {$ Xs}
Xs = {FD.list 10 1#10}
{Cycle Xs 3}
{FD.distinct {List.take Xs 3}}
{FD.distribute ff Xs}
end}
Finally, here is an example which defines a little constraint system
from scratch in Oz. This example defines a constraint system for
universal domains: the domain of the variables can consist of
arbitrary values, e.g., floats. However, this example is not
efficient, due to missing propagation. Have a look at the definition
of Add: it is implemented simply by calling the + primitive. You
could even implement propagators (e.g. constraints performing
propagation) in Oz in principle (i.e. extend Add to implement some
propagation algorithms), but the gurus recommend for that you better
use C++. This example is only meant as a demonstration.
declare
MyName = {NewName}
functor UniversalDomain
export
make:MakeVariable
IsVar
isDet:IsDetVar
GetVal
GetDom
Add
number: NumberP float: FloatP int: IntP
Distribute
define
%% internal variable representation var(value:X domain:Xs)
fun {MakeVariable Domain}
MyName(value:_ domain:{NewCell Domain})
end
fun {IsVar X}
{IsRecord X} andthen {Label X}==MyName
end
fun {IsDetVar Var}
{IsDet Var.value}
end
fun {GetVal Var}
Var.value
end
fun {GetDom Var}
@(Var.domain)
end
proc {SetDom Var Xs}
(Var.domain) := Xs
end
%% Demo constraint
proc {Add X Y Z}
A = if {IsVar X} then {GetVal X} else X end
B = if {IsVar Y} then {GetVal Y} else Y end
C = if {IsVar Z} then {GetVal Z} else Z end
in
%% each constraint runs in its own thread
thread A + B = C end
end
%%
proc {Distribute Order Value Xs}
{Space.waitStable}
local Vars={Filter Xs fun {$ X} {Not {IsDetVar X}} end}
in
if Vars \= nil
then
%% !! tmp: sort does too much
Var = {Sort Vars Order}.1
N = {Value Var}
in
choice {GetVal Var}=N {SetDom Var nil}
[] {SetDom Var {Filter {GetDom Var} fun {$ X} {Not X==N} end}}
end
{Distribute Order Value Vars}
end
end
end
end
[UD]={Module.apply [UniversalDomain]}
%% demo CSP
{ExploreOne proc{$ Sol}
A = {UD.make [~1.0 ~0.5 0.0 0.5 1.0 1.5 2.0 2.5 3.0]}
B = {UD.make [~1.0 ~0.5 0.0 0.5 1.0 1.5 2.0 2.5 3.0]}
in
Sol = [A B]
%% Constraint
{UD.add A B 2.0}
%% naive distribution
{UD.distribute
fun {$ Var1 Var2} true end
fun {$ Var} {UD.getDom Var}.1 end
[A B]}
end}
HTH.
Best
Torsten
On May 22, 2008, at 9:11 PM, mark richardson wrote:
mark richardson wrote:
Hi,
I'm slowly working through tutorials on FD's and constraint based
programming, working up to a final year degree project next year and
there is something I'm not sure I understand fully.
I was trying to find details about user defined propagators. I know
that you can write your own in C++ but why can't you create one using
standard Oz? or can you?
For example, say you have a function {Between X} that returns true if
X is between 7 and 10.
Why can't this be used as a constraint? or if you can, how?
If some patient person could explain this a little I would be most
grateful (or even just point me to some reference I haven't found
yet).
Regards
Mark Richardson
_____________________________________________________________________
____________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
I'm getting this confused I think.
I want to use an Oz function to 'constrain' not propagate.
Sorry about that, but I'm still confused about whether I can use a
standard Oz function as a constraint.
Regards
Mark Richardson
______________________________________________________________________
___________
mozart-users mailing list mozart-
[EMAIL PROTECTED]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
--
Torsten Anders
Interdisciplinary Centre for Computer Music Research
University of Plymouth
Office: +44-1752-586227
Private: +44-1752-558917
http://strasheela.sourceforge.net
http://www.torsten-anders.de
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
