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 Q. #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] Ruby Quiz - Magic Squares (#124)

[2] http://gecoder.lokorin.org/dev/wiki/Syntax_ideas