A
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
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
