Sudoku in Loco

The Obligatory Sudoku Example

No discussion about constraint solvers is complete without the obligatory sudoku example. Unfortunately, sudoku is such a basic exercise for a constraint solver that it doesn’t really tell you much about the engine. But if anything, because sudoku is so standard, it has become a good way to get a feel for the style of the constraint DSL.

The Loco (0.2.0) version is concise and readable, with a nice separation between the core set of constraints that underlie all sudoku puzzles, versus the additional starter numbers provided by the puzzle.

In most constraint solvers, the constraint operators imperatively impose constraints on a variable store. In Loco, the constraint operators simply produce Clojure data structures. Since we’re working with Clojure data, assembling the full model is simply a matter of concatenating the sequence of constraints describing the fundamental rules of sudoku with the sequence of constraints specific to a given puzzle. This is a good example of how Loco lets you easily build portions of your model separately and then combine them or otherwise manipulate them with standard Clojure functions.

To follow the example, the main thing you need to know about Loco is that the notion of a subscripted variable, like $grid_{i,j}$, is represented in Loco as a vector, e.g., [:grid i j]

First, here’s how we’re going to ultimately input the Sudoku grids to our solver:

;http://www.mirror.co.uk/news/weird-news/worlds-hardest-sudoku-puzzle-ever-942299
(def worlds-hardest-puzzle
  [[8 - - - - - - - -]
   [- - 3 6 - - - - -]
   [- 7 - - 9 - 2 - -]
   [- 5 - - - 7 - - -]
   [- - - - 4 5 7 - -]
   [- - - 1 - - - 3 -]
   [- - 1 - - - - 6 8]
   [- - 8 5 - - - 1 -]
   [- 9 - - - - 4 - -]])

Here’s the solving code:

(def basic-model
  (concat
    ; range-constraints
    (for [i (range 9) j (range 9)] 
      ($in [:grid i j] 1 9)),
    ; row-constraints
    (for [i (range 9)]
      ($distinct (for [j (range 9)] [:grid i j]))),
    ; col-constraints
    (for [j (range 9)]
      ($distinct (for [i (range 9)] [:grid i j]))),
    ; section-constraints
    (for [section1 [[0 1 2] [3 4 5] [6 7 8]]
          section2 [[0 1 2] [3 4 5] [6 7 8]]]
      ($distinct (for [i section1, j section2] [:grid i j])))))

(defn solve-sudoku [grid]
  (solution
    (concat basic-model
            (for [i (range 9), j (range 9)
                  :let [hint (get-in grid [i j])]
                  :when (number? hint)]
              ($= [:grid i j] hint)))))

Let’s test it out in the REPL:

=> (solve-sudoku worlds-hardest-puzzle)
{[:grid 4 0] 3, [:grid 5 1] 8, [:grid 6 2] 1, [:grid 7 3] 5, 
 [:grid 8 4] 1, [:grid 3 0] 1, [:grid 4 1] 6, [:grid 5 2] 7, 
 [:grid 6 3] 9, [:grid 7 4] 2, [:grid 8 5] 8, [:grid 2 0] 6,
 [:grid 3 1] 5, [:grid 4 2] 9, [:grid 5 3] 1, [:grid 6 4] 7,
 [:grid 7 5] 6, [:grid 8 6] 4, [:grid 1 0] 9, [:grid 2 1] 7,
 [:grid 3 2] 4, [:grid 4 3] 8, [:grid 5 4] 6, [:grid 6 5] 4,
 [:grid 7 6] 9, [:grid 8 7] 5, [:grid 0 0] 8, [:grid 1 1] 4,
 [:grid 2 2] 5, [:grid 3 3] 2, [:grid 4 4] 4, [:grid 5 5] 9,
 [:grid 6 6] 3, [:grid 7 7] 1, [:grid 8 8] 2, [:grid 0 1] 1,
 [:grid 1 2] 3, [:grid 2 3] 4, [:grid 3 4] 3, [:grid 4 5] 5,
 [:grid 5 6] 5, [:grid 6 7] 6, [:grid 7 8] 7, [:grid 0 2] 2,
 [:grid 1 3] 6, [:grid 2 4] 9, [:grid 3 5] 7, [:grid 4 6] 7,
 [:grid 5 7] 3, [:grid 6 8] 8, [:grid 0 3] 7, [:grid 1 4] 8,
 [:grid 2 5] 1, [:grid 3 6] 8, [:grid 4 7] 2, [:grid 5 8] 4,
 [:grid 0 4] 5, [:grid 1 5] 2, [:grid 2 6] 2, [:grid 3 7] 9,
 [:grid 4 8] 1, [:grid 0 5] 3, [:grid 1 6] 1, [:grid 2 7] 8,
 [:grid 3 8] 6, [:grid 0 6] 6, [:grid 1 7] 7, [:grid 2 8] 3,
 [:grid 0 7] 4, [:grid 1 8] 5, [:grid 0 8] 9, [:grid 8 0] 7,
 [:grid 7 0] 4, [:grid 8 1] 9, [:grid 6 0] 5, [:grid 7 1] 3,
 [:grid 8 2] 6, [:grid 5 0] 2, [:grid 6 1] 2, [:grid 7 2] 8,
 [:grid 8 3] 3}

On my machine, this “hardest Sudoku” takes about 17ms to solve. Benchmarking against your favorite constraint solver on your machine, and pretty-printing the output as a readable grid are left as an exercise for the reader.

Appointment scheduling in Clojure with Loco

Loco makes it easy to declaratively build constraint satisfaction models. In this blog post, we’ll look at a common use for constraint programming – appointment scheduling – and in so doing, we’ll see some of the ways that Loco goes beyond the features found in other Clojure constraint libraries.

(use 'loco.core 'loco.constraints)

Scheduling appointments with no conflicts

Imagine you have four people coming in for an interview, and you’ve set aside four timeslots in your day to conduct these interviews. You ask each person to list the timeslots when he/she can potentially come in.

Let’s use 0-based indexing to refer to the people, and 1-based indexing to refer to the timeslots.

Person 0 says she can come in at any of the four timeslots: 1, 2, 3, or 4.
Person 1 says he can come in at timeslot 2 or 3.
Person 2 says she can come in at timeslot 1 or 4.
Person 3 says he can come in at timeslot 1 or 4.

So the availability data looks like this:

(def availability
  [[1 2 3 4]
   [2 3]
   [1 4]
   [1 4]])

Let the variable [:person 0] denote the timeslot when person 0 is scheduled to come in, [:person 1] when person 1 comes in, etc.

(def person-vars
  (for [i (range (count availability))] [:person i]))

We want to constrain each [:person i] variable to the available timeslots.

(def availability-constraints
  (for [i (range (count availability))]
    ($in [:person i] (availability i))))

We want to ensure we don’t schedule two people in the same timeslot.

(def all-different-constraint
  (apply $all-different? person-vars))

For convenience, let’s assemble the constraints into one big list (the order doesn’t matter in Loco):

(def all-constraints 
  (conj availability-constraints all-different-constraint))

Now we’re ready to solve. Let’s dump the solution into a sorted-map for easy readability.

=> (into (sorted-map) (solution all-constraints))
{[:person 0] 3, [:person 1] 2, [:person 2] 4, [:person 3] 1}

So there you have it. Once we’ve played around with this example interactively in the REPL, and are confident in the model, we can easily abstract this into a function that takes availability data, and returns the schedule:

(defn schedule [availability]
  (->>
    (solution
      (conj
        (for [i (range (count availability))]
          ($in [:person i] (availability i)))
        ($distinct
          (for [i (range (count availability))] [:person i]))))
    (into (sorted-map))))

=> (schedule
     [[1 3 5]
      [2 4 5]
      [1 3 4]
      [2 3 4]
      [3 4 5]])
{[:person 0] 5, [:person 1] 4, [:person 2] 1, [:person 3] 2, [:person 4] 3}

I think the declarative Loco way of modeling constraints is concise and elegant, but this example could just as easily be done in, say, core.logic. So let’s push beyond, into an area that (as far as I know) can’t be done with core.logic.

Scheduling appointments minimizing conflicts

The above scheduler is somewhat naive.

=> (schedule 
     [[1 2 3 4]
      [1 4]
      [1 4]
      [1 4]])
{}

This doesn’t work because there’s no way to satisfy the constraint that no two people can be scheduled in the same timeslot.

But let’s say, hypothetically, that if absolutely necessary, we can potentially squeeze two candidates into the same timeslot. We’d rather not, but we can do it if we have to. Can we build a model for this?

Again, let’s start exploring the problem interactively with global defs and playing around with it at the REPL. Here’s the problematic availability example:

(def availability
  [[1 2 3 4]
   [1 4]
   [1 4]
   [1 4]])

As before, we’ll want to constraint each person’s timeslot to his/her availability schedule:

(def availability-constraints
  (for [i (range (count availability))]
    ($in [:person i] (availability i))))

Let’s define a few names for convenience. Let timeslots be a list of all the timeslot numbers.

(def timeslots (distinct (apply concat availability)))

Let person-vars be the list of all [:person i] variables.

(def person-vars
  (for [i (range (count availability))] [:person i]))

Now for the interesting part. We want to allow up to 2 people in a given timeslot. So we’ll let the variable [:num-people-in-timeslot 1] be the number of people signed up for timeslot 1, and so on. Let people-in-timeslot-vars be the list of all such variables.

(def people-in-timeslot-vars
  (for [i timeslots] [:num-people-in-timeslot i]))

Now, we create a list of constraints that state that each of these [:num-people-in-timeslot i] variables ranges between 0 and 2.

(def conflict-constraints
  (for [i timeslots]
    ($in [:num-people-in-timeslot i] 0 2)))

To give these :num-people-in-timeslot variables the appropriate meaning, we need to bind each [:num-people-in-timeslot i] variable to the number of times i occurs among the variables [:person 1], [:person 2], etc. Loco’s $cardinality constraint allows us to do exactly that. For example,

($cardinality [:x :y :z] {1 :number-of-ones})

will bind :number-of-ones to the number of times 1 occurs among :x, :y, and :z. So, the following constraint will bind all the [:num-people-in-timeslot i] variables to their appropriate values.

(def number-in-timeslots
  ($cardinality person-vars
                (zipmap timeslots people-in-timeslot-vars)))

To minimize the number of conflicts, we need to count the number of conflicts.

Let the variable :number-of-conflicts stand for the number of timeslot conflicts we have. We need two constraints on :number-of-conflicts. The first constraint just sets up the finite domain that the variable could range over (i.e., 0 to the total number of timeslots). We need to do this because in Loco, every variable must be declared somewhere in the model. The second constraint binds :number-of-conflicts to the number of times 2 appears in the variables [:num-people-in-timeslot 1], [:num-people-in-timeslot 2], etc.

(def number-of-conflicts
  [($in :number-of-conflicts 0 (count timeslots))
    ($cardinality people-in-timeslot-vars {2 :number-of-conflicts})])

We built the constraints in parts; now building the model is simply a matter of concatting all the constraints together. (Note that number-in-timeslots is a single constraint, so we concatenate [number-in-timeslots] in with the other lists of constraints).

(def all-constraints (concat availability-constraints
                             conflict-constraints
                             [number-in-timeslots]
                              number-of-conflicts))

Now, we’re all set up to solve the model.

=> (solution all-constraints
             :minimize :number-of-conflicts)
{[:person 0] 2,
 [:person 1] 4,
 [:person 2] 4,
 [:person 3] 1,
 :number-of-conflicts 1,
 [:num-people-in-timeslot 1] 1,
 [:num-people-in-timeslot 2] 1,
 [:num-people-in-timeslot 3] 0,
 [:num-people-in-timeslot 4] 2}

In the final version, we really only want to see the [:person i] variables; Loco allows us to hide the other variables from the output by prepending an underscore character in front of the variable names.

So let’s abstract this into a more robust schedule-with-conflicts function.

(defn schedule-with-conflicts [availability]
  (let [timeslots (distinct (apply concat availability)),

        availability-constraints
        (for [i (range (count availability))]
          ($in [:person i] (availability i))),

        person-vars
        (for [i (range (count availability))] [:person i]),

        people-in-timeslot-vars
        (for [i timeslots] [:_num-people-in-timeslot i]),

        conflict-constraints
        (for [i timeslots]
          ($in [:_num-people-in-timeslot i] 0 2)),

        number-in-timeslots
        ($cardinality person-vars 
                      (zipmap timeslots people-in-timeslot-vars)),

        number-of-conflicts
        [($in :_number-of-conflicts 0 (count timeslots))
          ($cardinality people-in-timeslot-vars {2 :_number-of-conflicts})]

        all-constraints (concat availability-constraints
                                conflict-constraints
                                [number-in-timeslots]
                                number-of-conflicts)]

    (into (sorted-map)
          (solution all-constraints :minimize :_number-of-conflicts))))

Let’s give it a spin:

=> (schedule-with-conflicts
       [[1 2 3 4]
        [1 4]
        [1 4]
        [1 4]])
{[:person 0] 2, [:person 1] 4, [:person 2] 4, [:person 3] 1}

Written with StackEdit.

Optimization with Loco

I had the pleasure of beta-testing Loco, which was announced today. Loco is a Clojure constraint solver library built on top of the Java library Choco. There are several constraint libraries available for Clojure, including core.logic, propaganda, and clocop, each with a slightly different focus.

The features that make Loco shine are the performance of the constraint engine, the fully declarative API, the ease with which one can build models, support for several interesting global constraints, and the ability to find an optimal solution for models with multiple solutions.

This is the first article of what I hope to be a series, detailing some of the interesting problems you can solve with Loco.

Scheduling Buses with Loco

(use 'loco.core loco.constraints)

Loco is a powerful and expressive constraint solver, but it can also be used to solve certain kinds of integer linear programs.

One classic example is bus scheduling. Imagine that we are city transportation planners and we want to minimize the number of buses we need to operate in order to meet demand. We know the number of buses demanded for four-hour blocks of time.

(def demands
  {:12am-4am  8
   :4am-8am  10
   :8am-12pm  7
   :12pm-4pm 12
   :4pm-8pm   4
   :8pm-12am  4})

So for example, this map tells us that there is sufficient demand for 8 buses operating between 12am and 4am.

The interesting twist is that buses operate for 8 hours at a time. So, if we set a bus into operation at 12am, it operates an 8-hour shift from 12am-8am. So the question is, how many buses do we need to run from 12am-8am, and from 4am-12pm, etc. in order to meet the above demands.

We can represent this by a series of variables, each of which must be an integer from 0 through 12 (since 12 is the maximum overall demand).

So with loco, we can get the solution quite simply:

(solution
  [($in :bus-12am-8am 0 12)
   ($in :bus-4am-12pm 0 12)
   ($in :bus-8am-4pm 0 12)
   ($in :bus-12pm-8pm 0 12)
   ($in :bus-4pm-12am 0 12)
   ($in :bus-8pm-4am 0 12)
   ($>= ($+ :bus-8pm-4am :bus-12am-8am) (demands :12am-4am))
   ($>= ($+ :bus-12am-8am :bus-4am-12pm) (demands :4am-8am))
   ($>= ($+ :bus-4am-12pm :bus-8am-4pm) (demands :8am-12pm))
   ($>= ($+ :bus-8am-4pm :bus-12pm-8pm) (demands :12pm-4pm))
   ($>= ($+ :bus-12pm-8pm :bus-4pm-12am) (demands :4pm-8pm))
   ($>= ($+ :bus-4pm-12am :bus-8pm-4am) (demands :8pm-12am))]
  :minimize
  ($+ :bus-12am-8am :bus-4am-12pm :bus-8am-4pm 
      :bus-12pm-8pm :bus-4pm-12am :bus-8pm-4am))

which yields

{:bus-8pm-4am 0, :bus-4pm-12am 4, :bus-12pm-8pm 7, 
 :bus-8am-4pm 5, :bus-4am-12pm 2, :bus-12am-8am 8}

Let’s see if we can generalize this to handle an arbitrary number of evenly-spaced time periods. Clearly, to do this we’ll need to get away from demands and variables that directly name the timespan. Instead, for our example in which we sliced the day into six 4-hour time periods, we can imagine indexing these blocks of time (0-based) as “Time period 0” through “Time period 5”. So we can just use a vector for our demands, for example:

[8 10 7 12 4 4]

means that 8 buses are demanded for time period “0” (corresponding to 12am-4am), 10 buses are demanded for time period “1” (corresponding to 4am-8am),… up to a demand of 5 buses for time period “5”.

We’ll make use of Loco’s ability to treat vectors as subscripted variables. So [:buses 0] denotes , which is our variable for how many buses we schedule starting at the beginning of time period 0 (i.e., 12am). [:buses 1] (i.e., ) is the variable for the number of buses starting at the beginning of time period 1, etc.

We will also need an input, span which indicates how many consecutive time periods are spanned by the bus’s shift. In our example, span would be 2 (because a bus works for 2 of our 4-hour time periods).

(defn minimize-buses
  "Takes a vector of the demands for any number of equally-spaced time slots.
   span is the number of time slots that a bus's operating time spans"
  [demands span]
  (let [time-slots (count demands),
        max-demand (apply max demands),

        declarations
        (for [i (range time-slots)]
          ($in [:buses i] 0 max-demand))

        constraints
        (for [i (range time-slots)]
          ($>=
            (apply $+ (for [j (range (inc (- i span)) (inc i))]
                        [:buses (mod j time-slots)]))
            (demands i)))]

    (solution
      (concat declarations constraints)
      :minimize (apply $+ (for [i (range time-slots)] [:buses i])))))

Let’s test it out on our original sample demand:

=> (minimize-buses [8 10 7 12 4 4] 2)
{[:buses 5] 0, [:buses 4] 4, [:buses 3] 7, [:buses 2] 5, [:buses 1] 2, [:buses 0] 8}

Hmmm, it’s a little hard to read. We can fix that:

=> (into (sorted-map) (minimize-buses [8 10 7 12 4 4] 2))
{[:buses 0] 8, [:buses 1] 2, [:buses 2] 5, [:buses 3] 7, [:buses 4] 4, [:buses 5] 0}

Good, same answer as before. But now we can easily adjust to alternative demand schedules. For example, here’s a solution for a demand schedule based on 2-hour time periods, while buses still work 8-hour shifts:

=> (into (sorted-map)
      (minimize-buses [1 5 7 9 11 12 18 17 15 13 4 2] 4))

{[:buses 0] 0, [:buses 1] 1, [:buses 2] 2, [:buses 3] 6, [:buses 4] 2,
 [:buses 5] 2, [:buses 6] 8, [:buses 7] 5, [:buses 8] 0, [:buses 9] 0,
 [:buses 10] 0, [:buses 11] 4}

Now, let’s try a demand schedule with 1-hour time periods, with buses working 8-hour shifts:

=> (into (sorted-map)
      (minimize-buses
        [1 3 5 7 9 11 12 13 14 15 16 19
         18 17 15 13 15 16 10 8 6 5 4 2]
        8))

Uh oh, this seems to run forever. We can fix this with the timeout feature. In the definition of minimize-buses, we change the call to solution as follows:

(solution
      (concat declarations constraints [constraint])
      :minimize (apply $+ (for [i (range time-slots)] [:bus i]))
      :timeout 1000)

The :timeout keyword specifies a number of milliseconds, after which the solver should return the best solution it has found so far:

=> (into (sorted-map)
      (minimize-buses
        [1 3 5 7 9 11 12 13 14 15 16 19
         18 17 15 13 15 16 10 8 6 5 4 2]
        8))

{[:bus 0] 1, [:bus 1] 2, [:bus 2] 2, [:bus 3] 2, [:bus 4] 2, [:bus 5] 2,
 [:bus 6] 1, [:bus 7] 1, [:bus 8] 2, [:bus 9] 3, [:bus 10] 3, [:bus 11] 5,
 [:bus 12] 1, [:bus 13] 1, [:bus 14] 2, [:bus 15] 2, [:bus 16] 2, [:bus 17] 0,
 [:bus 18] 0, [:bus 19] 0, [:bus 20] 0, [:bus 21] 0, [:bus 22] 0, [:bus 23] 0}

Written with StackEdit.

Frustrations with namespaces in Clojure

I have a long laundry list of things about Clojure I find irritating. That shouldn’t be too surprising; I have a similar list for every language that I have used to a serious degree. Most of the things on my list are relatively minor gripes and, overall, Clojure remains one of the most enjoyable programming languages I’ve worked with. Namespaces, however, are one of the aspects of Clojure that cause me the greatest pain.

Namespaces are Clojure’s tool for preventing name collisions between files. The most common way to organize your files is with a one-namespace-per-file policy, where the namespace matches the folder-file hierarchy. For example puzzler.sudoku.grid would be the namespace for the grid.clj file in a puzzler/sudoku directory in the classpath. A namespace can require other namespaces, which ensures that the code in those namespaces is loaded and accessible.

It’s a simple enough scheme, but in practice, I find there are several problems with namespaces, as implemented in Clojure.

No circular dependencies

Most programs start off small. At the beginning, it’s pretty easy to break the program cleanly into a few files with a clear, acyclic dependency hierarchy. But then your program grows. And when that happens, Clojure’s inability to handle namespaces with circular dependencies will cause you pain, as you struggle to refactor your entire codebase.

Here are the most common scenarios where I’ve got bitten by this:

1. Namespace b depends on namespace a. I’m adding a function foo to a and realize that I would really benefit from using a function bar that already exists in b. What to do? One option is to move the function from b into a. If I do this, I have to make sure to also move over everything in b that bar uses in its implementation. Next, I need to check every one of my namespaces that are downstream from b and use any of the moved functions, and add a dependency on a, and update any references to b/bar (or other moved functions) to a/bar.

   Another option is to try to figure out if there’s a way to move portions of code from b and a into a new namespace c, where both b and a will now depend on c. If you do this, you might be able to get away with moving only the underlying private helper functions. If you can avoid moving your public functions, that at least saves you the hassle of changing all the downstream consumers of the API to point to the new locations.

   Keep in mind that none of the Clojure IDEs are sophisticated enough to help with intelligently handling these sorts of refactorings. The really sad part is that sometimes the hassle factor is so huge, I feel tempted to just copy and paste function bar over to a so it exists in both locations. It makes me want to curse at Clojure just for making me consider such a horrible thing.

2. Records and protocols cause tremendous problems with the circular dependency restriction. Naturally, your records and protocols are something you want to use throughout your project. So it makes sense to have a namespace such as myproject.types to put these common records and protocols in one place. For efficiency, it is common to implement some of the protocols inline in the record definitions. However, implementing the protocols can at times be very complex, so in those inline implementations, we want to be able to call helper functions that handle the complex implementation details. Namespaces are all about organization, so it’s reasonable to want to implement those helper functions in another namespace. But therein lies the problem. myproject.types depends on myproject.protocol-implementation-details which in turn depends on myproject.types (for example, if you want to implement push on a Stack you need to be able to return a new Stack, so you need that Stack record in scope).

A number of Clojure programmers have responded to this constraint by simply keeping the bulk of their code in one monolithic namespace. It is possible to split one namespace across multiple files, but then you’ve lost out on one of the desirable properties of namespaces — to know where to look for the definition of a function from the namespace/function reference.

No standard mechanism for re-providing required dependencies

The need for this manifests in several contexts:

1. Creating a public API relying on functions spread across other namespaces. The simplest technique is to just create new vars that refer to the ones in the other namespaces, for example, (def public-foo private/foo). The main problem is that public-foo metadata won’t match the metadata of private/foo.

   The best library for dealing with this is potemkin, which handles the details of migrating the metdata over to the new var. This is an important enough issue, there should be a standard solution built into Clojure.

2. When dealing with a complex project built out of multiple libraries and namespaces, it’s easy to end up with massively long headers, listing out dozens of dependencies. We need some way to group related dependencies into something that can be conveniently required as a single entity.

   In the early days of Clojure, Konrad Hinsen did some interesting work building some ns libraries supporting the notion of “namespace cloning” and other related ideas. I don’t know whether these tools are maintained these days, but again, it would be great to see a solution incorporated into Clojure.

3. In the discussion above about breaking up circular dependencies, I talked about how much of the pain revolves around needing to update all the references to a function that has been moved from one namespace to another. If there were a convenient way to leave behind a link to the new location, it wouldn’t be quite so painful. Again, potemkin is currently the way to deal with this.

No parameterized namespaces

My first two complaints shouldn’t come as any surprise to anyone who has built a complex project in Clojure. But this last point is more subtle.

To illustrate the point, let’s imagine your boss tasks you with writing a program to generate sudoku puzzles. As you code your sudoku generator, it’s obvious that certain numbers show up again and again. Remembering the rule-of-thumb “no magic constants”, you decide to create some definitions at the top of your namespace:

;; Constants
(def section-size 3)
(def symbols (range 1 10)) ; might want to use something other than numbers
(def grid-size (* section-size section-size)) ; derived constant

Imagine that these constants are used throughout the many functions in your sudoku namespace.

Later your boss comes along and says he wants you to generate a bunch of 4x4 sudokus, using letters instead of numbers. No problem, you just change the constants and recompile, right?

But now, let’s imagine that you need to do a task that involves a mixture of generating 9x9 and 4x4 sudokus. Suddenly, you have a major problem.

Probably most Clojurians would quickly rework the main constants as follows:

;; Constants
(def ^:dynamic section-size 3)
(def ^:dynamic symbols (range 1 10)) 

And what to do about the derived constant? Possibly you could use a symbol macro (see clojure.tools.macro), or maybe rework it into a function and change all uses of the constant to a function call.

(defn grid-size [] (* section-size section-size))
; Change all uses of grid-size to (grid-size)

Then, you use your generator to generate five of each type of puzzle as follows:

(concat
  (sudoku/generate-puzzles 5)
  (binding [sudoku/section-size 2, sudoku/symbols [\A \B \C \D]]
     (sudoku/generate-puzzles 5)))

The problem here is that binding almost always leads towards more pain. Inevitably, you forget that, for example, generate-puzzles returns a lazy sequence, so when the sequence is realized, the binding no longer holds, and the vars revert back to their defaults, so you just get ten 9x9 puzzles.

binding simply isn’t a reliable way to parameterize your namespace, i.e., to customize your namespace’s “global variables” that all the functions rely upon.

How do other languages deal with this?

Classes can be thought of as a very richly-featured namespace. Even if you don’t use inheritance and mutable state, classes make great namespaces. In an OO language, the sudoku namespace could be a class, with section-size and symbols as properties/fields set by the class constructor. The functions in the class all “see” those fields.

This means that you can think of objects as special instances of this parameterized namespace. For example, (ab)using a mixture of java and clojure syntax, imagine:

sudoku4 = new Sudoku(2, [\A \B \C \D])
sudoku9 = new Sudoku(3, (range 1 10))
(concat (sudoku4.generate-puzzles 5) (sudoku9.generate-puzzles 5))

There’s no good way to do this in Clojure. Really, your only option is to explicitly pass these parameters in and out of every function in your namespace. To do this, you’d need to change every single one of your functions to take an additional input of the form:

{section-size :section-size symbols :symbols :as grid-options}

and passing grid-options to every function call.

This also changes the calling convention for all downstream consumers of this API.

This is a disaster. The problem is that projects usually start off just like this, with a few “global definitions” that later turn into actual parameters as the project evolves. binding is not an adequate solution because it interacts poorly with laziness. Threading the values through the functions can be a major ordeal. We need some way to produce a namespace that is derived from another namespace with certain parameters set in a given way.

I’m not an ML expert, but I believe that ML functors are an example of parameterized namespaces in the functional language world. Perhaps Clojure could draw inspiration from this.

Summary

All of these issues have one thing in common: part of Clojure’s appeal is that it creates an environment where you can dive in and start creating without having every detail of your final design planned out. Clojure lets you start simply with small projects and evolve a more complex structure as necessary. However, the details of how namespaces work means that as your project evolves, I inevitably hit a point where new additions become painful to make due to extensive refactoring. I find that when this happens, I’m psychologically steered towards avoiding those new additions, and that’s no good.

In order to create an environment where projects scale more seamlessly from small to large, Clojure’s namespaces are desperately in need of richer features.