We’ve got yet another project announcement to share, as Google’s Summer of Code begins to pick up steam. The following announcement is from Andreas Launila about his project Gecode/R. Andreas is pursuing a masters in Computer Science at KTH (The Royal Institute of Technology - Sweden).

Announcing Gecode/R, by Andreas Launila

Hello, I’m working on Gecode/R, a Ruby interface to Gecode, 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) 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 naive 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, 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.