Gecode/R - Request for syntax feedback

[Andreas Launila]

Hello, I'm working on Gecode/R, a Ruby interface to Gecode[0], allowing
constraint programming in Ruby. I'm currently trying to set some
goals/direction for the syntax, and would appreciate feedback from
anyone that has the interest and time. The interface is intended for
people with no previous experience of constraint programming, and should
be fairly easy for an average ruby programmer (i.e. someone familiar
with Ruby) to pick up and use.

I begin with a short introduction and example, I will then highlight
some problems and things to consider. I have formulated some actual
questions in the end of some paragraph, but those are mostly there as
aid for the reader. Feel free to disregard them and comment on any thing
that you think of, any sort of feedback is welcome.


== Introduction and example ==

Using constraint programming basically means that you model the problem
by specifying the constraints that have to hold for something to be a
solution to the problem. The underlying engine then solves the problem
by searching for solutions satisfying all the constraints. Lets take
Ruby Quiz #124 (Magic Squares)[1] as an example. For something to be a
solution to that problem we require that the elements are distinct,
between 1 and n^2, and that the sum of the rows, columns and two main
diagonals are equal. So we model that with some code and then let the
underlying engine do a search.

The following is an example of how solving the problem might look.


# A naïve model of the magic square problem with square size n.
class MagicSquare < Gecode::Model
# n is the size of the magic square.
def initialize(n)
# This models that all elements are in 1..(n**2) and are all
# distinct. IntVar.matrix produces an instance of Matrix filled
# with instances of IntVar.
squares = IntVar.matrix(n, n, 1..(n**2))
all_distinct squares

# The following models the part about various sums being equal. We
# know the magic sum (row sum) since we know the sum of all
# elements.
magic_sum = n*(1 + n**2) / 2
n.times do |i|
squares.row(i).to_a.sum == magic_sum
squares.column(i).to_a.sum == magic_sum
end
squares.diagonal(0, 0).sum == magic_sum
squares.diagonal(0, squares.column_size - 1).sum == magic_sum

# We need to select a branching strategy, this is used when we can
# no longer prune impossible values by deduction and have to make a
# guess.
branch_on squares, :variable => :min_size, :value => :min
end
end

# A couple of utility methods for Array and Matrix to make the above a
# bit more readable.
class Array
# Folds the elements in the array using the + method.
def sum
inject{ |sum, element| sum + element }
end
end
class Matrix
# Returns an array containing the element found in the diagonal which
# contains the element in the specified row and column and contains no
# element with a strictly smaller row-index. nil is returned if such a
# diagonal does not exist.
def diagonal(row, column)
# Out of bounds.
return nil unless row < row_size and column < column_size
# Does not exist.
return nil if row > 0 and column != 0 and column != column_size - 1

diag_length = [row_size - row, column_size - column].min
elements = []
diag_length.times do |offset|
elements << self[row + offset, column + offset]
end
return elements
end
end

# Print a solution (the first we find). This assumes that the solution
# has some decent default to_s method.
puts MagicSquare.new(9).solution.to_s


With the above syntax each problem is described as a class inheriting
from some common superclass. The actual model is defined in the
constructor. Each model has a number of variables that define the space
that the engine should search through, in our case we have a n*n matrix
with integers which can take values in the range 1..n**2 . Ruby's Array
and Matrix are used as collections (so IntVar.matrix is just a
convenience method for creating an instance of Matrix and filling it
with instances of IntVar). The advantage with that is that we get all
the utility that we're used to, along with Array's special syntax for
construction.


== Issues ==

=== Describing (linear) constraints ===

In the above example we describe our constraints with lines such as
"squares.diagonal(0, 0).sum == magic_sum". In this case we define a
linear equation that has to hold. These are not lines that are evaluated
to true or false, rather they have the side effect of creating a
constraint that has to hold. The instances of IntVar define arithmetic
methods to create a temporary representation which can then be further
added on to by e.g. more use of arithmetic methods. The representations
are kept track of behind the scenes and translated to real constraints
in the end. Lets take an example:

x,y,z = IntVar.array(3, 0..9) # Three variables with domain 0..9.
x + y == z

"x + y" would evaluate to a temporary representation which is stored and
then has "== z" applied to it.

A problem with the above is that people might look at it and
instinctively think that it's something that does not have a side
effect. Therefore prepending some sort of method might convey that
intention better. For instance we could allow people to write the following.

constrain x + y == z

Fitting words other than "constrain" might be "assert", "post" and
"add". One could also go a bit further and make using such a prepended
method compulsory for consistency. I guess the real question is how
disturbing it is for an average Ruby programmer to have arithmetic
methods that have side effects. Do you see it as natural, disturbing or
something in between? Can you think of any way of making the intention
of there being a side effect clearer?

Using arithmetic and comparison methods is of course only one way of
many to describe these (linear) constraints. One drawback with it is
consistency. Since != can't be redefined to be something other than !(x
== y) inequality has to be treated differently. In this case I'm
considering using something similar to "x.not_equal(y)", i.e. just
replace "!=" with "not_equal". There are a lot of constraints, but these
linear constraints are amongst the most common. Can you think of better
ways to represent them?

=== Variable access ===

Something that the above example doesn't really bother with is some way
to allow the variables to be accessed as something other than local
variables. For instance we might want to write a better to_s method
where we need access to the variables in the squares matrix (which hold
that information).

One way that should be familiar is to have the user save squares in an
instance variable (e.g. @squares) that can then be accessed other where.
Other approaches might include trying to save all instance variables
created in the constructor that refer to instances of e.g. IntVar and
then create methods for accessing them. Yet another would be to have the
user explicitly declare variables (possibly on a class level), which
would then be accessible anywhere in the instance. What would you suggest?

=== Describing distinct constraints ===

The "all_distinct squares" line adds a constraint that says that all
variables contained in squares have to be pairwise inequal. Other names
than "all_distinct" could be used, for example "distinct" and
"all_different" (Gecode uses "distinct"). Other ways of specifying the
constraint could also be imagined, such as "squares.all_distinct". The
latter could make things a bit more consistent by allowing a method to
be prepended, such as "constrain squares.all_distinct" (assuming such a
prepended method is used for the linear constraints). What feels more
natural/readable?

=== Overall syntax ===

Every model has at least three parts:
* Declaration of variables (in the example that would be "squares = ...")
* Definition of constraints (all the lines from "all_distinct ..." down
to "squares.diagonal..." in the example).
* Selection of branching strategy (the line starting with "branch_on" in
the example)

Maybe that could be used to produce some other overall syntax? E.g.
something other than throwing it all into a constructor.


== Conclusion ==

Any feedback (pointing out flaws, suggesting modifications, suggesting a
completely different syntax, anything) is appreciated. Questions about
the project, constraint programming, what has to be covered by the
syntax etc are also welcome.

There are more issues that I would like feedback on, but I figured that
it might be best to start with these and then introduce other areas as
the discussion progresses. I'm trying to collect syntax ideas on a
wiki-page[2], that page gives an overview of the majority of the areas
that the syntax will have to cover. It's more of a collection of notes
and thoughts than proposals though, so it might be hard to read but
possibly interesting to someone.


[0] http://www.gecode.org/
[1] http://www.rubyquiz.com/quiz124.html
[2] http://gecoder.lokorin.org/dev/wiki/Syntax_ideas

 

[ara.t.howard]

Hello, I'm working on Gecode/R, a Ruby interface to Gecode[0],
allowing
constraint programming in Ruby. I'm currently trying to set some
goals/direction for the syntax, and would appreciate feedback from
anyone that has the interest and time. The interface is intended for
people with no previous experience of constraint programming, and
should
be fairly easy for an average ruby programmer (i.e. someone familiar
with Ruby) to pick up and use.

I begin with a short introduction and example, I will then highlight
some problems and things to consider. I have formulated some actual
questions in the end of some paragraph, but those are mostly there as
aid for the reader. Feel free to disregard them and comment on any
thing
that you think of, any sort of feedback is welcome.

would you mind posting something about this on sciruby?

http://sciruby.codeforpeople.com/

??

-a

 

[James Edward Gray II]

Hello, I'm working on Gecode/R, a Ruby interface to Gecode[0],
allowing
constraint programming in Ruby. I'm currently trying to set some
goals/direction for the syntax, and would appreciate feedback from
anyone that has the interest and time. The interface is intended for
people with no previous experience of constraint programming, and
should
be fairly easy for an average ruby programmer (i.e. someone familiar
with Ruby) to pick up and use.

I begin with a short introduction and example, I will then highlight
some problems and things to consider. I have formulated some actual
questions in the end of some paragraph, but those are mostly there as
aid for the reader. Feel free to disregard them and comment on any
thing
that you think of, any sort of feedback is welcome.

would you mind posting something about this on sciruby?

http://sciruby.codeforpeople.com/

??

Perhaps that would be a better idea after the Google SoC project is a
little farther along with definite syntax to show off? Just a thought.

James Edward Gray II

 

[Andreas Launila]

Hello, I'm working on Gecode/R, a Ruby interface to Gecode[0], allowing
constraint programming in Ruby. I'm currently trying to set some
goals/direction for the syntax, and would appreciate feedback from
anyone that has the interest and time. The interface is intended for
people with no previous experience of constraint programming, and should
be fairly easy for an average ruby programmer (i.e. someone familiar
with Ruby) to pick up and use.

I begin with a short introduction and example, I will then highlight
some problems and things to consider. I have formulated some actual
questions in the end of some paragraph, but those are mostly there as
aid for the reader. Feel free to disregard them and comment on any thing
that you think of, any sort of feedback is welcome.

would you mind posting something about this on sciruby?

http://sciruby.codeforpeople.com/

??

-a

I can, when the project is something beyond mere plans (i.e. when it can
be used for something).

 

[James Edward Gray II]

== Issues ==

=== Describing (linear) constraints ===

A problem with the above is that people might look at it and
instinctively think that it's something that does not have a side
effect. Therefore prepending some sort of method might convey that
intention better. For instance we could allow people to write the
following.

constrain x + y == z

RSpec works a lot like this. It has you define expectations with
syntax like:

some_obj.should equal(whatever)
some_obj.should_not equal(whatever)

Fitting words other than "constrain" might be "assert", "post" and
"add".

I like the word "constrain." If you go the RSpec route though, you
will probably also want a negative form and I don't know what that
would be.

One could also go a bit further and make using such a prepended
method compulsory for consistency.

I think that's a sound strategy. That's pretty much the point of
should/should_not in RSpec. It gives the user a visual queue that
says something like, "We're now switching into defining constraints
mode."

I guess the real question is how
disturbing it is for an average Ruby programmer to have arithmetic
methods that have side effects. Do you see it as natural,
disturbing or
something in between?

I don't think it's too shocking. I think most programmers can accept
that objects can override methods. You see that the variables are
created as IntVar objects, and it's not a far leap that IntVar
redefines some operators.

If I had to choose though, I think I prefer the RSpec-like context
changing method prefix.

One drawback with it is consistency. Since != can't be redefined to
be something other than !(x == y) inequality has to be treated
differently.

I do like consistency, so, for what it's worth, I prefer equal/
not_equal since we can't have both == and !=.

=== Variable access ===

One way that should be familiar is to have the user save squares in an
instance variable (e.g. @squares) that can then be accessed other
where.

This feels pretty natural to me. It works on the knowledge we
already have.

Yet another would be to have the user explicitly declare variables
(possibly on a class level), which would then be accessible
anywhere in the instance. What would you suggest?

This could be another interesting option. See my comment below about
a DSL...

=== Describing distinct constraints ===

Other ways of specifying the constraint could also be imagined,
such as "squares.all_distinct". The latter could make things a bit
more consistent by allowing a method to be prepended, such as
"constrain squares.all_distinct" (assuming such a prepended method
is used for the linear constraints). What feels more natural/readable?

I worry that the syntax purposed above requires you to add some
methods to Array and/or Matrix. This seems like a slope you want to
avoid.

As an idea, again using RSpec for inspiration:

constrain distinct(some_enum)

=== Overall syntax ===

Every model has at least three parts:
* Declaration of variables (in the example that would be "squares
= ...")
* Definition of constraints (all the lines from "all_distinct ..."
down
to "squares.diagonal..." in the example).
* Selection of branching strategy (the line starting with
"branch_on" in
the example)

Maybe that could be used to produce some other overall syntax? E.g.
something other than throwing it all into a constructor.

Reading this definitely made me wonder over a DSL. That's pretty
much what you have with the class system though. If constrain()
becomes the constraint definer and branch_on() represents the
branching strategy, the only thing you haven't really wrapped is the
variable declaration.

I don't know what that would look like, but maybe something like:

variable :some_name, :int, accepted_range_of_values

Then I guess you could later refer to them by name. Of course,
that's just not as convenient when it comes to accessing them.
Iterating over rows and columns shows this well.

Whatever way you go with this though, you may want to consider
providing a DSL wrapper for your classes, something like:

magic_square = problem do |model|
# ...
end

That just might be nice when you don't need to define a full class.

James Edward Gray II

 

[Andreas Launila]

RSpec works a lot like this. It has you define expectations with syntax
like:

some_obj.should equal(whatever)
some_obj.should_not equal(whatever)


I like the word "constrain." If you go the RSpec route though, you will
probably also want a negative form and I don't know what that would be.

That would be a nice solution. The best word I can think of for
"constrain" is "constrain_negation", which is probably far from perfect.

constrain_negation x + y == z

or maybe

constrain (x + y == z).negate

Another variation would be to use a combination of constrain and RSpec's
should/should_not.

constrain (x + y).must == z
constrain (x + y).must_not == z

It might chop up the constraint a bit, but it reads well. One could
possibly also drop the constraint part. It would be nicer with a
negative form of constrain though (or some other fitting word) since it
would make it easier to be consistent. As an example there's a domain
constraint which basically says that x must be in a given range.
Negating the constraint is possible and might be written as follows.

constrain x.in(1..17)
constrain x.not_in(1..17)

The above takes a different form than the linear constraints. To make it
consistent with the mixed variation of linear constraint syntax one
could rewrite it as.

constrain (1..17).must(include(x))
constrain (1..17).must_not(include(x))

But that feels a bit clunky and requires changes to Range.

With a negative form of constraint the constraints would look rather
good while being consistent.

constrain x + y == z
constrain_negation x + y == z
constrain x.in(1..17)
constrain_negation x.in(1..17)

I worry that the syntax purposed above requires you to add some methods
to Array and/or Matrix. This seems like a slope you want to avoid.

As an idea, again using RSpec for inspiration:

constrain distinct(some_enum)

Sounds good to me.

Reading this definitely made me wonder over a DSL. That's pretty much
what you have with the class system though. If constrain() becomes the
constraint definer and branch_on() represents the branching strategy,
the only thing you haven't really wrapped is the variable declaration.

I don't know what that would look like, but maybe something like:

variable :some_name, :int, accepted_range_of_values

Then I guess you could later refer to them by name. Of course, that's
just not as convenient when it comes to accessing them. Iterating over
rows and columns shows this well.

I don't understand the part about not being as convenient to access. I'm
assuming that one could define matrices just as well as single variables
with such a syntax, which would basically give the same level of
convenience. An example to see if I understood you correctly (possibly
with some keys for the parameters beyond the name and type):

class MagicSquare < Gecode::Model
def initialize(n)
variable :squares, :int_matrix, n, n, 1..(n**2)
squares.row(0)
...
end
end

I mentioned declaring these kinds of variables on a class level before,
but I see now that doing so would make it hard to initialize the matrix
size in the example. One could however change that part so that the
problem parameters are used to create the class rather than instances of
the class.

Whatever way you go with this though, you may want to consider providing
a DSL wrapper for your classes, something like:

magic_square = problem do |model|
# ...
end

That just might be nice when you don't need to define a full class.

Aye, thanks for the idea.

 

[Andreas Launila]

Another variation would be to use a combination of constrain and RSpec's
should/should_not.

constrain (x + y).must == z
constrain (x + y).must_not == z

It might chop up the constraint a bit, but it reads well. One could
possibly also drop the constraint part. It would be nicer with a
negative form of constrain though (or some other fitting word) since it
would make it easier to be consistent. As an example there's a domain
constraint which basically says that x must be in a given range.
Negating the constraint is possible and might be written as follows.

constrain x.in(1..17)
constrain x.not_in(1..17)

The above takes a different form than the linear constraints. To make it
consistent with the mixed variation of linear constraint syntax one
could rewrite it as.

constrain (1..17).must(include(x))
constrain (1..17).must_not(include(x))

Not necessarily. It could also be written as

constrain x.must(be_in(1..17))
constrain x.must_not(be_in(1..17))

Which is both consistent and reads well (possibly apart from the
parenthesis).

Another way of making it clear that we're specifying constraints could
be to place them all in a block. E.g. something like the following.

in_a_solution do
(x + y).must == z
x.must > z
y.must_not be_in(1..4)
distinct x,y,z
end

Possibly also sending the variables through the method with the block
(which would clearly declare which variables that constitute a solution).

in_a_solution_with(x,y,z) do |x,y,z|
(x + y).must == z
x.must > z
y.must_not be_in(1..4)
distinct x,y,z
end

 

[James Edward Gray II]

That would be a nice solution. The best word I can think of for
"constrain" is "constrain_negation", which is probably far from
perfect.

constrain_negation x + y == z

Yuck. And I mean that in the nicest possible way.

Another variation would be to use a combination of constrain and
RSpec's
should/should_not.

constrain (x + y).must == z
constrain (x + y).must_not == z

That's not too bad. I think my biggest complaint there is that it
makes the flow of the line a little hard to follow. Perhaps must/
must_not could replace constrain altogether though:

must x + y == z
must_not x + y == z

That doesn't read too well though, does it?

As an example there's a domain
constraint which basically says that x must be in a given range.
Negating the constraint is possible and might be written as follows.

constrain x.in(1..17)
constrain x.not_in(1..17)

This seems like a very viable solution to me. If it's possible to
just negate all of the tests, that should work:

equal/not_equal
in/not_in
includes/does_not_include

I don't understand the part about not being as convenient to
access. I'm
assuming that one could define matrices just as well as single
variables
with such a syntax, which would basically give the same level of
convenience. An example to see if I understood you correctly (possibly
with some keys for the parameters beyond the name and type):

class MagicSquare < Gecode::Model
def initialize(n)
variable :squares, :int_matrix, n, n, 1..(n**2)
squares.row(0)
...
end
end

I think this makes it more complicated to support custom data
structures. What if I want a MyUniqueDataStructure full of IntVars,
for example?

Beyond that, it doesn't seem in anyway superior to:

class MagicSquare < Gecode::Model
def initialize(n)
@squares = ...
end
attr_reader :squares
end

I think it's probably best not to override core Rubyisms if we can't
significantly add to them.

James Edward Gray II

 

[James Edward Gray II]

Another way of making it clear that we're specifying constraints could
be to place them all in a block. E.g. something like the following.

in_a_solution do
(x + y).must == z
x.must > z
y.must_not be_in(1..4)
distinct x,y,z
end

Possibly also sending the variables through the method with the block
(which would clearly declare which variables that constitute a
solution).

in_a_solution_with(x,y,z) do |x,y,z|
(x + y).must == z
x.must > z
y.must_not be_in(1..4)
distinct x,y,z
end

This could possibly be an option. You could choose to write:

constrain ...
constrain ...
constrain ...

or:

constrain do
...
...
...
end

James Edward Gray II

 

[Andreas Launila]

This seems like a very viable solution to me. If it's possible to just
negate all of the tests, that should work:

equal/not_equal
in/not_in
includes/does_not_include

Yes, that could work. I was probably locking myself in a bit too much
trying to make everything read as must/must_not. I will sketch how other
constraints could be expressed on a similar form to see if there are any
consistency problems.

There doesn't exist support for negating all constraints. One example is
a sorting constraint, which basically says that some variables, when
sorted, are equal to some other variables. Which could be expressed
something like:

constrain xs.sorted.equal(ys)
or
constrain sorted(xs).equal(ys)
or
constrain sort(xs).equal(ys)

The last couple avoid having to modify Enumerable. Using this form I
prefer the second version.

The point however is that there's no simple way to negate that
constraint using Gecode, beyond hacking together several constraints
that express that a single element is out of order and saying that at
least one of them must hold. To me it would seem accepatable to simply
throw an exception in those cases (or translate it to something
inefficient behind the scenes, but I would rather not do that).

I think this makes it more complicated to support custom data
structures. What if I want a MyUniqueDataStructure full of IntVars, for
example?

True, I didn't think about custom data structures.

 

[Andreas Launila]

Yes, that could work. I was probably locking myself in a bit too much
trying to make everything read as must/must_not. I will sketch how other
constraints could be expressed on a similar form to see if there are any
consistency problems.

If I understood the suggestion of the syntax correctly then constraints
would basically be given on the form "constrain
variable.predicate(argument)" when variable is a single (finite-domain)
variable and "constrain function(variable).predicate(argument)" when
variable is something enumerable.

I have written down some examples of how constraints could look with
that syntax at http://gecoder.lokorin.org/dev/wiki/Syntax_test . There
are some constraints there which I couldn't get especially readable or
self-evident. I will go through them below.


== Element constraints ==

This is basically the array access of constraints. It takes an array of
constant integers, selects the i:th one where i is decided by a
variable, and constrains that variable to be equal to another variable.
This can typically be used to convert e.g. an identifier to a quantity
of some sort, for instance the price of a fruit.

A short example:

fruit_selection = IntVar.new(0..3) # We can pick one of four fruits.
prices = [45, 60, 764, 45] # The prices of each fruit.
price_to_pay = IntVar.new((prices.min)..(prices.max))
constrain prices[fruit_selection].equal(price_to_pay)
constrain price_to_pay > 500

The above example will force fruit_selection to equal 2 (no branching
required) since it's the only fruit with a price > 500.

I would imagine the above syntax of "constrain array[x].equal(y)" to be
easily understandable, but it would require modification to Enumerable
to define/wrap []. Something more on the form of the rest of the syntax
would probably be

constrain element(array, x).equal(y)

It just doesn't read as well to me. Maybe there's a better way of
representing constraints where the function has to take multiple
arguments, such as returning an helper with only one method, i.e. as
follows.

constrain element(x).in(array).equal(y)


== Channel constraints ==

This is a constraint that I have little idea of how to produce something
readable for. The constraint links two enumerables with variables to
each other so that the xs_i = j <=> ys_j = i forall i where xs and ys
are enumerables.

It's used to represent a model from two different viewpoints. Lets say
that you have a problem involving a sequence of length n with numbers in
0..(n-1) that all have to be distinct (for instance magic sequence).
Naturally you might model this as an array where element i is the value
at position i (so if you print the array you get the actual sequence).
You could also model it as an array where element i is the position of
value i in the sequence. These are two different viewpoints of the same
problem. Below what the two arrays might contain when the problem is solved.

First viewpoint: xs = [2,0,1,3] (the actual sequence)
Second viewpoint: ys = [2,1,0,3] (the positions of the different
numbers, e.g. the position of 0 in xs is 2, hence ys[0] == 2)

The important part is that some constraints might be easier to model
using the first viewpoint and others might be easier in the second one.
The channel constraint is used to give the person modeling access to
both viewpoints at the same time. The second viewpoint can be
constructed from the first one by using the channel constraint. The best
syntax I can think of for it is.

constrain channel(xs, ys)

That is probably because I can't think of any common concept that
conveys the intention in a few words.


== Sort constraints ==

There's a special form of sort constraint that operates on three
enumerables: xs, ys and zs. What it does is that it constrains e.g. xs
to be ys sorted using the positions specified in zs. Once again it's the
problem of conveying a function with multiple arguments. Using the
suggestion for element constraints this could become something like

constrain sort(xs).with_indices(zs).equal(ys)

I'm not sure how readable that is.


== Cardinality constraints ==

This is a fairly straightforward constraint, it counts the number of
occurrences in an array. For instance I might specify that an array of
variables must contain 3 instances of 5 (3 and 5 can also be replaced by
variables).

Again it's multiple arguments for a function. Maybe it's more readable
as the following.

constrain number_of(y).in(xs).equal(z)


== Beyond ==

There are more constraints to worry about, but the ones in the syntax
test page represents the commonly used ones for finite domain integers
and booleans. Hence it's probably best to hammer out a good syntax for
them and then adapt it for the other constraints and set variables.

 

[James Edward Gray II]

If I understood the suggestion of the syntax correctly then
constraints
would basically be given on the form "constrain
variable.predicate(argument)" when variable is a single (finite-
domain)
variable and "constrain function(variable).predicate(argument)" when
variable is something enumerable.

I have written down some examples of how constraints could look with
that syntax at http://gecoder.lokorin.org/dev/wiki/Syntax_test . There
are some constraints there which I couldn't get especially readable or
self-evident. I will go through them below.

I'm liking this direction, for what it's worth. I'm worried about the
ones that require changes to core classes though and I think we
generally want to avoid that. That may be an argument for the
earlier proposed variable(), since it could wrap the data structures
in proxy objects supporting the extra calls.

Random thoughts from that page:

* We probably shouldn't use sort(), because a class my inherit a sort
() from Enumerable.
* Could all_equal() be same()? I was just wondering if that paired
better with distinct(). I don't hate all_equal() though. Just a
thought.

== Element constraints ==

This is basically the array access of constraints. It takes an
array of
constant integers, selects the i:th one where i is decided by a
variable, and constrains that variable to be equal to another
variable.
This can typically be used to convert e.g. an identifier to a quantity
of some sort, for instance the price of a fruit.

A short example:

fruit_selection = IntVar.new(0..3) # We can pick one of four fruits.
prices = [45, 60, 764, 45] # The prices of each fruit.
price_to_pay = IntVar.new((prices.min)..(prices.max))

Could this line also be:

price_to_pay = IntVar.new(*prices)

? Just curious as it made more sense to me that way.

constrain prices[fruit_selection].equal(price_to_pay)
constrain price_to_pay > 500

The above example will force fruit_selection to equal 2 (no branching
required) since it's the only fruit with a price > 500.

I would imagine the above syntax of "constrain array[x].equal(y)"
to be
easily understandable, but it would require modification to Enumerable
to define/wrap [].

The []() method is defined in Array, actually.

Something more on the form of the rest of the syntax
would probably be

constrain element(array, x).equal(y)

It just doesn't read as well to me. Maybe there's a better way of
representing constraints where the function has to take multiple
arguments, such as returning an helper with only one method, i.e. as
follows.

constrain element(x).in(array).equal(y)

I would say avoiding core class modification is important. If that
means we need element(), that's probably just a price we need to pay,
in my opinion.

See my earlier comment about proxy objects for another option though.

== Channel constraints ==

The best syntax I can think of for it is.

constrain channel(xs, ys)

That is probably because I can't think of any common concept that
conveys the intention in a few words.

Looks reasonable to me, at least as far as I understood this one.

== Sort constraints ==

There's a special form of sort constraint that operates on three
enumerables: xs, ys and zs. What it does is that it constrains e.g. xs
to be ys sorted using the positions specified in zs. Once again
it's the
problem of conveying a function with multiple arguments. Using the
suggestion for element constraints this could become something like

constrain sort(xs).with_indices(zs).equal(ys)

I'm not sure how readable that is.

What about taking a page from the Rails book and doing something like:

constrain sorted(xs, :indices => zs).equal(ys)

?

== Cardinality constraints ==

This is a fairly straightforward constraint, it counts the number of
occurrences in an array. For instance I might specify that an array of
variables must contain 3 instances of 5 (3 and 5 can also be
replaced by
variables).

Again it's multiple arguments for a function. Maybe it's more readable
as the following.

constrain number_of(y).in(xs).equal(z)

Here again parameters seem like they might be OK. What's nice is
that we can get more variations this way. For example count(enum)
could count all elements while count(enum, :element => y) would be
just the y elements in enum.

James Edward Gray II

 

[Andreas Launila]

I'm liking this direction, for what it's worth. I'm worried about the
ones that require changes to core classes though and I think we
generally want to avoid that. That may be an argument for the earlier
proposed variable(), since it could wrap the data structures in proxy
objects supporting the extra calls.

Random thoughts from that page:

* We probably shouldn't use sort(), because a class my inherit a sort()
from Enumerable.

True, I have switched to sorted.

* Could all_equal() be same()? I was just wondering if that paired
better with distinct(). I don't hate all_equal() though. Just a thought.

Certainly, I have updated the page with this suggestion and all the
others in your mail.

== Element constraints ==

This is basically the array access of constraints. It takes an array of
constant integers, selects the i:th one where i is decided by a
variable, and constrains that variable to be equal to another variable.
This can typically be used to convert e.g. an identifier to a quantity
of some sort, for instance the price of a fruit.

A short example:

fruit_selection = IntVar.new(0..3) # We can pick one of four fruits.
prices = [45, 60, 764, 45] # The prices of each fruit.
price_to_pay = IntVar.new((prices.min)..(prices.max))

Could this line also be:

price_to_pay = IntVar.new(*prices)

? Just curious as it made more sense to me that way.

Yes.

Something more on the form of the rest of the syntax
would probably be

constrain element(array, x).equal(y)

It just doesn't read as well to me. Maybe there's a better way of
representing constraints where the function has to take multiple
arguments, such as returning an helper with only one method, i.e. as
follows.

constrain element(x).in(array).equal(y)

I would say avoiding core class modification is important. If that
means we need element(), that's probably just a price we need to pay, in
my opinion.

See my earlier comment about proxy objects for another option though.

I will write up some similar syntax examples with proxy objects to see
how big the difference is.

Looks reasonable to me, at least as far as I understood this one.

Actually I made a mistake in the examples of the two different
viewpoints which might have confused a bit. It should be the following.

First viewpoint: xs = [2,0,1,3] (the actual sequence)
Second viewpoint: ys = [1,2,0,3] (the positions of the different
numbers, e.g. the position of 0 in xs is 1, hence ys[0] == 1)

What about taking a page from the Rails book and doing something like:

constrain sorted(xs, :indices => zs).equal(ys)

?

Yes, especially since indices is optional.

Here again parameters seem like they might be OK. What's nice is that
we can get more variations this way. For example count(enum) could
count all elements while count(enum, :element => y) would be just the y
elements in enum.

I'm not sure if count(enum) would be used since it's basically the same
as counting the number of elements in enum and constraining z to be
equal to it (and since you constructed the enum you already know the
size and could thereby replace z with that constant). But the form with
an hash option is more readable than the form with just two arguments.

 

[Andreas Launila]

I will write up some similar syntax examples with proxy objects to see
how big the difference is.

Examples: http://gecoder.lokorin.org/dev/wiki/Syntax_test#Proxy_objects

I have assumed that it's in this case okay to shadow methods such as
#sort since if the enum is passed to a wrapping method then it should
only be used with finite-domain variables, which do not have any defined
way of comparison (similarly for min and max).

 

[James Edward Gray II]

Examples: http://gecoder.lokorin.org/dev/wiki/
Syntax_test#Proxy_objects

That page talks about how we loose some convenience in that we need
to now wrap simple IntVars. I'm not sure that's 100% necessary
though. If we built the class, we should be able to count on it
having what we need. The wrapper could just be for Enumerables and/
or custom data structures, I think. Double-check my logic there though.

James Edward Gray II

 

[Andreas Launila]

That page talks about how we loose some convenience in that we need to
now wrap simple IntVars. I'm not sure that's 100% necessary though. If
we built the class, we should be able to count on it having what we
need. The wrapper could just be for Enumerables and/or custom data
structures, I think. Double-check my logic there though.

Your conclusion is correct. But my intent with the text is that we have
to wrap enumerables before use, I'm not sure how to reach the other
interpretation.

 

[James Edward Gray II]

Your conclusion is correct. But my intent with the text is that we
have
to wrap enumerables before use, I'm not sure how to reach the other
interpretation.

Oh yes, I misread. Sorry.

I'm not giddy with the idea either. Maybe we're getting too
complicated here. Let's back up.

Our current pattern is:

constrain function(...).predicate(...)

First of all, can't function() always return the needed proxy object,
without an need to wrap? Or is the issue when we don't use the
function()?

If we want to get rid of the need to wrap, we need to eliminate the
calls on random objects. That's not so bad, because we really want
or constraint builders worrying about the details for us.

Maybe the issue is that I led us down the wrong path with my RSpec
suggestions. What if we tried something more like Test::Unit's
assertions. I'm now thinking of a pattern like:

constrain_...(args, hash_style_options)

Translating the examples I come up with:

constrain_equal x, y
constrain_not_equal x, y
constrain_in x, enum
constrain_not_in x, enum
constrain_same enum
constrain_distinct enum

The operators are a little clumsier. We could do constrain_less_than
(), constrain_greater_than(), etc. This might be a better option
though:

constrain_relationship x, :>, y

The symbol could be replaced with the other logical comparisons as
needed.

For things like sorted(), I'm wondering if we could add that as an
option:

constrain_equal enum, other_enum, :sorted => true

What do we think about this direction, on the whole?

James Edward Gray II

 

[Andreas Launila]

Yuck. And I mean that in the nicest possible way.


That's not too bad. I think my biggest complaint there is that it makes
the flow of the line a little hard to follow. Perhaps must/must_not
could replace constrain altogether though:

must x + y == z
must_not x + y == z

That doesn't read too well though, does it?

I think that must/must_not would make a fairly interesting syntax in the
sense that it reads very well. Therefore I have tried some examples at
http://gecoder.lokorin.org/dev/wiki/Syntax_test#must.2Fmust_not .

They probably require skipping "constrain" though and replacing it with
something block-like, it just doesn't read right otherwise.

 

[James Edward Gray II]

I think that must/must_not would make a fairly interesting syntax
in the
sense that it reads very well. Therefore I have tried some examples at
http://gecoder.lokorin.org/dev/wiki/Syntax_test#must.2Fmust_not .

They probably require skipping "constrain" though and replacing it
with
something block-like, it just doesn't read right otherwise.

I like how this reads in the early examples and worry about that
amount of core hacking we have to do to support the later examples:

whatever.with_offsets ...
whatever.sorted ...
whatever.sorted_with ...
whatever.occurrences_of ...
whatever.any ...
whatever.all ...
whatever.implies ...
whatever.equivalent_to ...

James Edward Gray II

 

[Andreas Launila]

I like how this reads in the early examples and worry about that amount
of core hacking we have to do to support the later examples:

whatever.with_offsets ...
whatever.sorted ...
whatever.sorted_with ...
whatever.occurrences_of ...
whatever.any ...
whatever.all ...
whatever.implies ...
whatever.equivalent_to ...

Unless the enumerables are wrapped before use as in the other example
(or the variables are sent through as parameters alongs with the block
as in some earlier example).