tag:blogger.com,1999:blog-73212733244122294822024-03-18T23:46:51.581-07:00Thoughts on ProgrammingMark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-7321273324412229482.post-18451407971125415092014-03-07T12:40:00.001-08:002014-03-07T12:40:17.419-08:00Sudoku in Loco<h1 id="the-obligatory-sudoku-example">The Obligatory Sudoku Example</h1>
<p>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 <em>style</em> of the constraint DSL.</p>
<p>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. </p>
<p>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.</p>
<p>To follow the example, the main thing you need to know about Loco is that the notion of a subscripted variable, like <span class="MathJax_Preview"></span><span style="" aria-readonly="true" role="textbox" id="MathJax-Element-3-Frame" class="MathJax"><nobr><span style="width: 3.232em; display: inline-block;" id="MathJax-Span-25" class="math"><span style="display: inline-block; position: relative; width: 2.592em; height: 0px; font-size: 124%;"><span style="position: absolute; clip: rect(1.725em, 1000em, 3.059em, -0.508em); top: -2.592em; left: 0em;"><span id="MathJax-Span-26" class="mrow"><span style="font-family: MathJax_Math; font-style: italic;" id="MathJax-Span-27" class="mi">g<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span style="font-family: MathJax_Math; font-style: italic;" id="MathJax-Span-28" class="mi">r</span><span style="font-family: MathJax_Math; font-style: italic;" id="MathJax-Span-29" class="mi">i</span><span id="MathJax-Span-30" class="msubsup"><span style="display: inline-block; position: relative; width: 1.339em; height: 0px;"><span style="position: absolute; clip: rect(1.725em, 1000em, 2.775em, -0.485em); top: -2.592em; left: 0em;"><span style="font-family: MathJax_Math; font-style: italic;" id="MathJax-Span-31" class="mi">d<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.003em;"></span></span><span style="display: inline-block; width: 0px; height: 2.592em;"></span></span><span style="position: absolute; top: -2.385em; left: 0.515em;"><span id="MathJax-Span-32" class="texatom"><span id="MathJax-Span-33" class="mrow"><span style="font-size: 70.7%; font-family: MathJax_Math; font-style: italic;" id="MathJax-Span-34" class="mi">i</span><span style="font-size: 70.7%; font-family: MathJax_Main;" id="MathJax-Span-35" class="mo">,</span><span style="font-size: 70.7%; font-family: MathJax_Math; font-style: italic;" id="MathJax-Span-36" class="mi">j</span></span></span><span style="display: inline-block; width: 0px; height: 2.535em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.592em;"></span></span></span><span style="border-left: 0em solid; display: inline-block; overflow: hidden; width: 0px; height: 1.368em; vertical-align: -0.436em;"></span></span></nobr></span><script id="MathJax-Element-3" type="math/tex">grid_{i,j}</script>, is represented in Loco as a vector, e.g., <code>[:grid i j]</code></p>
<p>First, here’s how we’re going to ultimately input the Sudoku grids to our solver:</p><div class="se-section-delimiter"></div>
<pre class="prettyprint"><code class="language-clojure hljs "><span class="hljs-comment">;http://www.mirror.co.uk/news/weird-news/worlds-hardest-sudoku-puzzle-ever-942299</span>
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">def</span></span> worlds-hardest-puzzle
<span class="hljs-collection">[<span class="hljs-collection">[8 - - - - - - - -]</span>
<span class="hljs-collection">[- -<span class="hljs-number"> 3</span><span class="hljs-number"> 6</span> - - - - -]</span>
<span class="hljs-collection">[-<span class="hljs-number"> 7</span> - -<span class="hljs-number"> 9</span> -<span class="hljs-number"> 2</span> - -]</span>
<span class="hljs-collection">[-<span class="hljs-number"> 5</span> - - -<span class="hljs-number"> 7</span> - - -]</span>
<span class="hljs-collection">[- - - -<span class="hljs-number"> 4</span><span class="hljs-number"> 5</span><span class="hljs-number"> 7</span> - -]</span>
<span class="hljs-collection">[- - -<span class="hljs-number"> 1</span> - - -<span class="hljs-number"> 3</span> -]</span>
<span class="hljs-collection">[- -<span class="hljs-number"> 1</span> - - - -<span class="hljs-number"> 6</span><span class="hljs-number"> 8</span>]</span>
<span class="hljs-collection">[- -<span class="hljs-number"> 8</span><span class="hljs-number"> 5</span> - - -<span class="hljs-number"> 1</span> -]</span>
<span class="hljs-collection">[-<span class="hljs-number"> 9</span> - - - -<span class="hljs-number"> 4</span> - -]</span>]</span>)</span></code></pre>
<p>Here’s the solving code:</p>
<pre class="prettyprint"><code class="language-clojure hljs "><span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">def</span></span> basic-model
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">concat</span></span>
<span class="hljs-comment">; range-constraints</span>
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[i <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span> j <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span>]</span>
<span class="hljs-list">(<span class="hljs-title">$in</span> <span class="hljs-collection">[<span class="hljs-attribute">:grid</span> i j]</span><span class="hljs-number"> 1</span><span class="hljs-number"> 9</span>)</span>)</span>,
<span class="hljs-comment">; row-constraints</span>
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[i <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span>]</span>
<span class="hljs-list">(<span class="hljs-title">$distinct</span> <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[j <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span>]</span> <span class="hljs-collection">[<span class="hljs-attribute">:grid</span> i j]</span>)</span>)</span>)</span>,
<span class="hljs-comment">; col-constraints</span>
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[j <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span>]</span>
<span class="hljs-list">(<span class="hljs-title">$distinct</span> <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[i <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span>]</span> <span class="hljs-collection">[<span class="hljs-attribute">:grid</span> i j]</span>)</span>)</span>)</span>,
<span class="hljs-comment">; section-constraints</span>
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[section1 <span class="hljs-collection">[<span class="hljs-collection">[0<span class="hljs-number"> 1</span><span class="hljs-number"> 2</span>]</span> <span class="hljs-collection">[3<span class="hljs-number"> 4</span><span class="hljs-number"> 5</span>]</span> <span class="hljs-collection">[6<span class="hljs-number"> 7</span><span class="hljs-number"> 8</span>]</span>]</span>
section2 <span class="hljs-collection">[<span class="hljs-collection">[0<span class="hljs-number"> 1</span><span class="hljs-number"> 2</span>]</span> <span class="hljs-collection">[3<span class="hljs-number"> 4</span><span class="hljs-number"> 5</span>]</span> <span class="hljs-collection">[6<span class="hljs-number"> 7</span><span class="hljs-number"> 8</span>]</span>]</span>]</span>
<span class="hljs-list">(<span class="hljs-title">$distinct</span> <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[i section1, j section2]</span> <span class="hljs-collection">[<span class="hljs-attribute">:grid</span> i j]</span>)</span>)</span>)</span>)</span>)</span>
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">defn</span></span> solve-sudoku <span class="hljs-collection">[grid]</span>
<span class="hljs-list">(<span class="hljs-title">solution</span>
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">concat</span></span> basic-model
<span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">for</span></span> <span class="hljs-collection">[i <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span>, j <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">range</span></span><span class="hljs-number"> 9</span>)</span>
<span class="hljs-attribute">:let</span> <span class="hljs-collection">[hint <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">get-in</span></span> grid <span class="hljs-collection">[i j]</span>)</span>]</span>
<span class="hljs-attribute">:when</span> <span class="hljs-list">(<span class="hljs-title"><span class="hljs-built_in">number?</span></span> hint)</span>]</span>
<span class="hljs-list">(<span class="hljs-title">$=</span> <span class="hljs-collection">[<span class="hljs-attribute">:grid</span> i j]</span> hint)</span>)</span>)</span>)</span>)</span></code></pre>
<p>Let’s test it out in the REPL:</p>
<pre class="prettyprint"><code class="language-clojure hljs "><span class="hljs-prompt">=> </span>(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}</code></pre>
<p>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.</p>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com5tag:blogger.com,1999:blog-7321273324412229482.post-21015642925364168862014-03-05T22:34:00.001-08:002014-03-09T11:05:34.161-07:00Appointment scheduling in Clojure with Loco<p>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.</p>
<pre><code>(use 'loco.core 'loco.constraints)
</code></pre><div class="se-section-delimiter"></div>
<h1 id="scheduling-appointments-with-no-conflicts">Scheduling appointments with no conflicts</h1>
<p>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. </p>
<p>Let’s use 0-based indexing to refer to the people, and 1-based indexing to refer to the timeslots.</p>
<p>Person 0 says she can come in at any of the four timeslots: 1, 2, 3, or 4. <br>
Person 1 says he can come in at timeslot 2 or 3. <br>
Person 2 says she can come in at timeslot 1 or 4. <br>
Person 3 says he can come in at timeslot 1 or 4.</p>
<p>So the availability data looks like this:</p>
<pre><code>(def availability
[[1 2 3 4]
[2 3]
[1 4]
[1 4]])
</code></pre>
<p>Let the variable <code>[:person 0]</code> denote the timeslot when person 0 is scheduled to come in, <code>[:person 1]</code> when person 1 comes in, etc.</p>
<pre><code>(def person-vars
(for [i (range (count availability))] [:person i]))
</code></pre>
<p>We want to constrain each <code>[:person i]</code> variable to the available timeslots.</p>
<pre><code>(def availability-constraints
(for [i (range (count availability))]
($in [:person i] (availability i))))
</code></pre>
<p>We want to ensure we don’t schedule two people in the same timeslot.</p>
<pre><code>(def all-different-constraint
(apply $all-different? person-vars))
</code></pre>
<p>For convenience, let’s assemble the constraints into one big list (the order doesn’t matter in Loco):</p>
<pre><code>(def all-constraints
(conj availability-constraints all-different-constraint))
</code></pre>
<p>Now we’re ready to solve. Let’s dump the solution into a sorted-map for easy readability.</p>
<pre><code>=> (into (sorted-map) (solution all-constraints))
{[:person 0] 3, [:person 1] 2, [:person 2] 4, [:person 3] 1}
</code></pre>
<p>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:</p>
<pre><code>(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}
</code></pre>
<p>I think the declarative Loco way of modeling constraints is concise and elegant, but this example could just as easily be done in, say, <code>core.logic</code>. So let’s push beyond, into an area that (as far as I know) can’t be done with <code>core.logic</code>.</p><div class="se-section-delimiter"></div>
<h1 id="scheduling-appointments-minimizing-conflicts">Scheduling appointments minimizing conflicts</h1>
<p>The above scheduler is somewhat naive.</p>
<pre><code>=> (schedule
[[1 2 3 4]
[1 4]
[1 4]
[1 4]])
{}
</code></pre>
<p>This doesn’t work because there’s no way to satisfy the constraint that no two people can be scheduled in the same timeslot.</p>
<p>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?</p>
<p>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:</p>
<pre><code>(def availability
[[1 2 3 4]
[1 4]
[1 4]
[1 4]])
</code></pre>
<p>As before, we’ll want to constraint each person’s timeslot to his/her availability schedule: </p>
<pre><code>(def availability-constraints
(for [i (range (count availability))]
($in [:person i] (availability i))))
</code></pre>
<p>Let’s define a few names for convenience. Let <code>timeslots</code> be a list of all the timeslot numbers. </p>
<pre><code>(def timeslots (distinct (apply concat availability)))
</code></pre>
<p>Let <code>person-vars</code> be the list of all <code>[:person i]</code> variables.</p>
<pre><code>(def person-vars
(for [i (range (count availability))] [:person i]))
</code></pre>
<p>Now for the interesting part. We want to allow up to 2 people in a given timeslot. So we’ll let the variable <code>[:num-people-in-timeslot 1]</code> be the number of people signed up for timeslot 1, and so on. Let <code>people-in-timeslot-vars</code> be the list of all such variables. </p>
<pre><code>(def people-in-timeslot-vars
(for [i timeslots] [:num-people-in-timeslot i]))
</code></pre>
<p>Now, we create a list of constraints that state that each of these <code>[:num-people-in-timeslot i]</code> variables ranges between 0 and 2.</p>
<pre><code>(def conflict-constraints
(for [i timeslots]
($in [:num-people-in-timeslot i] 0 2)))
</code></pre>
<p>To give these :num-people-in-timeslot variables the appropriate meaning, we need to bind each <code>[:num-people-in-timeslot i]</code> variable to the number of times <code>i</code> occurs among the variables <code>[:person 1]</code>, <code>[:person 2]</code>, etc. Loco’s <code>$cardinality</code> constraint allows us to do exactly that. For example,</p>
<pre><code>($cardinality [:x :y :z] {1 :number-of-ones})
</code></pre>
<p>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 <code>[:num-people-in-timeslot i]</code> variables to their appropriate values.</p>
<pre><code>(def number-in-timeslots
($cardinality person-vars
(zipmap timeslots people-in-timeslot-vars)))
</code></pre>
<p>To minimize the number of conflicts, we need to count the number of conflicts. </p>
<p>Let the variable <code>:number-of-conflicts</code> stand for the number of timeslot conflicts we have. We need two constraints on <code>:number-of-conflicts</code>. 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 <code>:number-of-conflicts</code> to the number of times <code>2</code> appears in the variables <code>[:num-people-in-timeslot 1]</code>, <code>[:num-people-in-timeslot 2]</code>, etc.</p>
<pre><code>(def number-of-conflicts
[($in :number-of-conflicts 0 (count timeslots))
($cardinality people-in-timeslot-vars {2 :number-of-conflicts})])
</code></pre>
<p>We built the constraints in parts; now building the model is simply a matter of concatting all the constraints together. (Note that <code>number-in-timeslots</code> is a single constraint, so we concatenate <code>[number-in-timeslots]</code> in with the other lists of constraints).</p>
<pre><code>(def all-constraints (concat availability-constraints
conflict-constraints
[number-in-timeslots]
number-of-conflicts))
</code></pre>
<p>Now, we’re all set up to solve the model. </p>
<pre><code>=> (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}
</code></pre>
<p>In the final version, we really only want to see the <code>[:person i]</code> variables; Loco allows us to hide the other variables from the output by prepending an underscore character in front of the variable names.</p>
<p>So let’s abstract this into a more robust <code>schedule-with-conflicts</code> function.</p>
<pre><code>(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))))
</code></pre>
<p>Let’s give it a spin:</p>
<pre><code>=> (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}
</code></pre>
<blockquote>
<p>Written with <a href="https://stackedit.io/">StackEdit</a>.</p>
</blockquote>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com29tag:blogger.com,1999:blog-7321273324412229482.post-83739031340483696522014-03-05T01:33:00.001-08:002014-03-09T11:16:37.942-07:00Optimization with Loco<p>I had the pleasure of beta-testing <a href="https://github.com/aengelberg/loco">Loco</a>, 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.</p>
<p>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.</p>
<p>This is the first article of what I hope to be a series, detailing some of the interesting problems you can solve with Loco.</p><div class="se-section-delimiter"></div>
<h1 id="scheduling-buses-with-loco">Scheduling Buses with <a href="https://github.com/aengelberg/loco">Loco</a></h1>
<pre><code>(use 'loco.core loco.constraints)
</code></pre>
<p><a href="https://github.com/aengelberg/loco">Loco</a> is a powerful and expressive constraint solver, but it can also be used to solve certain kinds of integer linear programs.</p>
<p>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.</p>
<pre><code>(def demands
{:12am-4am 8
:4am-8am 10
:8am-12pm 7
:12pm-4pm 12
:4pm-8pm 4
:8pm-12am 4})
</code></pre>
<p>So for example, this map tells us that there is sufficient demand for 8 buses operating between 12am and 4am.</p>
<p>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.</p>
<p>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).</p>
<p>So with loco, we can get the solution quite simply:</p>
<pre><code>(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))
</code></pre>
<p>which yields</p>
<pre><code>{:bus-8pm-4am 0, :bus-4pm-12am 4, :bus-12pm-8pm 7,
:bus-8am-4pm 5, :bus-4am-12pm 2, :bus-12am-8am 8}
</code></pre>
<p>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:</p>
<pre><code>[8 10 7 12 4 4]
</code></pre>
<p>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”.</p>
<p>We’ll make use of Loco’s ability to treat vectors as subscripted variables. So <code>[:buses 0]</code> denotes <a href="http://www.codecogs.com/eqnedit.php?latex=buses_0" target="_blank"><img src="http://latex.codecogs.com/gif.latex?buses_0" title="buses_0"></a>, which is our variable for how many buses we schedule <em>starting</em> at the beginning of time period 0 (i.e., 12am). <code>[:buses 1]</code> (i.e., <a href="http://www.codecogs.com/eqnedit.php?latex=buses_1" target="_blank"><img src="http://latex.codecogs.com/gif.latex?buses_1" title="buses_1"></a>) is the variable for the number of buses starting at the beginning of time period 1, etc.</p>
<p>We will also need an input, <code>span</code> which indicates how many consecutive time periods are spanned by the bus’s shift. In our example, <code>span</code> would be 2 (because a bus works for 2 of our 4-hour time periods).</p>
<pre><code>(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])))))
</code></pre>
<p>Let’s test it out on our original sample demand:</p>
<pre><code>=> (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}
</code></pre>
<p>Hmmm, it’s a little hard to read. We can fix that:</p>
<pre><code>=> (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}
</code></pre>
<p>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:</p>
<pre><code>=> (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}
</code></pre>
<p>Now, let’s try a demand schedule with 1-hour time periods, with buses working 8-hour shifts:</p>
<pre><code>=> (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))
</code></pre>
<p>Uh oh, this seems to run forever. We can fix this with the timeout feature. In the definition of <code>minimize-buses</code>, we change the call to <code>solution</code> as follows:</p>
<pre><code>(solution
(concat declarations constraints [constraint])
:minimize (apply $+ (for [i (range time-slots)] [:bus i]))
:timeout 1000)
</code></pre>
<p>The <code>:timeout</code> keyword specifies a number of milliseconds, after which the solver should return the best solution it has found so far:</p>
<pre><code>=> (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}
</code></pre>
<blockquote>
<p>Written with <a href="https://stackedit.io/">StackEdit</a>.</p>
</blockquote>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com4tag:blogger.com,1999:blog-7321273324412229482.post-8346243287082065452013-12-25T17:07:00.001-08:002013-12-25T17:07:16.052-08:00Frustrations with namespaces in Clojure<h1 id="frustrations-with-namespaces-in-clojure">Frustrations with namespaces in Clojure</h1>
<p>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. </p>
<p>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 <code>puzzler.sudoku.grid</code> would be the namespace for the <code>grid.clj</code> file in a puzzler/sudoku directory in the classpath. A namespace can <code>require</code> other namespaces, which ensures that the code in those namespaces is loaded and accessible.</p>
<p>It’s a simple enough scheme, but in practice, I find there are several problems with namespaces, as implemented in Clojure.</p><div class="se-section-delimiter"></div>
<h2 id="no-circular-dependencies">No circular dependencies</h2>
<p>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.</p>
<p>Here are the most common scenarios where I’ve got bitten by this:</p>
<ol>
<li><p>Namespace <code>b</code> depends on namespace <code>a</code>. I’m adding a function <code>foo</code> to <code>a</code> and realize that I would really benefit from using a function <code>bar</code> that already exists in <code>b</code>. What to do? One option is to move the function from <code>b</code> into <code>a</code>. If I do this, I have to make sure to also move over everything in <code>b</code> that <code>bar</code> uses in its implementation. Next, I need to check every one of my namespaces that are <em>downstream</em> from <code>b</code> and use any of the moved functions, and add a dependency on <code>a</code>, and update any references to <code>b/bar</code> (or other moved functions) to <code>a/bar</code>.</p>
<p>Another option is to try to figure out if there’s a way to move portions of code from <code>b</code> and <code>a</code> into a new namespace <code>c</code>, where both <code>b</code> and <code>a</code> will now depend on <code>c</code>. 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.</p>
<p>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 <code>bar</code> over to <code>a</code> so it exists in both locations. It makes me want to curse at Clojure just for making me consider such a horrible thing.</p></li>
<li><p>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 <code>myproject.types</code> 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. <code>myproject.types</code> depends on <code>myproject.protocol-implementation-details</code> which in turn depends on <code>myproject.types</code> (for example, if you want to implement <code>push</code> on a <code>Stack</code> you need to be able to return a new <code>Stack</code>, so you need that <code>Stack</code> record in scope). </p></li>
</ol>
<p>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.</p>
<h2 id="no-standard-mechanism-for-re-providing-required-dependencies">No standard mechanism for re-providing required dependencies</h2>
<p>The need for this manifests in several contexts:</p>
<ol>
<li><p>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, <code>(def public-foo private/foo)</code>. The main problem is that <code>public-foo</code> metadata won’t match the metadata of <code>private/foo</code>. </p>
<p>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.</p></li>
<li><p>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. </p>
<p>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.</p></li>
<li><p>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 <em>link</em> to the new location, it wouldn’t be quite so painful. Again, potemkin is currently the way to deal with this.</p></li>
</ol>
<h2 id="no-parameterized-namespaces">No parameterized namespaces</h2>
<p>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.</p>
<p>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:</p>
<pre class="prettyprint"><code class="clojure"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment">;; Constants</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>
<span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in">def</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"> section-size</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"><span class="list"><span class="number"> 3</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>
<span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in">def</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"> symbols </span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in">range</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"> 1</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"> 10</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> <span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment">; might want to use something other than numbers</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>
<span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in">def</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"> grid-size </span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="list"><span class="title"><span class="built_in">*</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"> section-size section-size)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> <span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment"><span class="comment">; derived constant</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></code></pre>
<p>Imagine that these constants are used throughout the many functions in your sudoku namespace.</p>
<p>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?</p>
<p>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.</p>
<p>Probably most Clojurians would quickly rework the main constants as follows:</p><div class="se-section-delimiter"></div>
<pre class="prettyprint"><code class="python">;; Constants
(<span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword">def</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"> ^:</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>dynamic section-size <span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">3</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>)
(<span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword"><span class="function"><span class="keyword">def</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"><span class="function"> ^:</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>dynamic symbols (range <span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">1</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> <span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">10</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>)) </code></pre>
<p>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.</p>
<pre class="prettyprint"><code class="mel">(defn <span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">grid</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>-<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">size</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> [] (* section-<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">size</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> section-<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">size</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>))
; Change all uses of <span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">grid</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>-<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">size</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> to (<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">grid</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>-<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">size</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>)</code></pre>
<p>Then, you use your generator to generate five of each type of puzzle as follows:</p>
<pre class="prettyprint"><code class="clojure"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in"><span class="list"><span class="title"><span class="built_in">concat</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">
</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title">sudoku/generate-puzzles</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="number"> 5</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">
</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="title">binding</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"> </span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection">[sudoku/section-size</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"><span class="list"><span class="list"><span class="collection"><span class="number"> 2</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection">, sudoku/symbols </span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="collection">[\A \B \C \D]</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection"><span class="list"><span class="list"><span class="collection">]</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">
</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">(</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title"><span class="list"><span class="list"><span class="list"><span class="title">sudoku/generate-puzzles</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"><span class="list"><span class="list"><span class="list"><span class="number"> 5</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list"><span class="list">)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></code></pre>
<p>The problem here is that <code>binding</code> almost always leads towards more pain. Inevitably, you forget that, for example, <code>generate-puzzles</code> 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.</p>
<p><code>binding</code> simply isn’t a reliable way to <em>parameterize your namespace</em>, i.e., to customize your namespace’s “global variables” that all the functions rely upon.</p>
<p>How do other languages deal with this?</p>
<p>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 <code>section-size</code> and <code>symbols</code> as properties/fields set by the class constructor. The functions in the class all “see” those fields.</p>
<p>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:</p>
<pre class="prettyprint"><code class="vhdl">sudoku4 = <span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">new</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> Sudoku(<span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">2</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>, [\A \B \C \D])
sudoku9 = <span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">new</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> Sudoku(<span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">3</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>, (<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">range</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> <span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">1</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> <span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">10</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>))
(concat (sudoku4.<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">generate</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>-puzzles <span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">5</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>) (sudoku9.<span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword"><span class="keyword">generate</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>-puzzles <span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number"><span class="number">5</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>))</code></pre>
<p>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:</p>
<pre class="prettyprint"><code class="ruby">{section-size <span class="symbol">:section-size</span> symbols <span class="symbol">:symbols</span> <span class="symbol">:as</span> grid-options}</code></pre>
<p>and passing <code>grid-options</code> to every function call.</p>
<p>This also changes the calling convention for all downstream consumers of this API.</p>
<p>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. <code>binding</code> 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.</p>
<p>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.</p><div class="se-section-delimiter"></div>
<h2 id="summary">Summary</h2>
<p>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.</p>
<p>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.</p>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com31tag:blogger.com,1999:blog-7321273324412229482.post-78220964708124867062013-12-24T00:34:00.001-08:002013-12-24T00:34:32.206-08:00Clojure vs ScalaLast week, someone posted a question on the Clojure group asking for a comparison between Clojure and Scala. Since my most popular blog post, by far, is my <a href="http://programming-puzzler.blogspot.com/2010/08/racket-vs-clojure.html">Racket vs Clojure</a> post from three years ago, I thought it would be good to post my response here.
<p/>
Ten years ago, I would have said that my ideal dream language is one that provides the flexibility to program in any style. I want to be able to choose object-oriented or functional, immutable or mutable, high-level abstractions or low-level speed. With respect to this ideal, Scala clearly wins, supporting more programming styles than Clojure.
<p/>
I've definitely changed my tune, though, and now I actually prefer the way that Clojure constrains and shapes my thinking. I argue that even though Scala may provide me with more options on how to tackle a given programming problem, Clojure guides me towards a simpler solution. If this intrigues you, read on...
<p/>
The following text is only slightly paraphrased from what I posted to the group:
<blockquote>
All or nearly all of the functional aspects of Clojure have counterparts in Scala. On top of that, Scala provides mutable flavors of everything, so you can pick and choose your approach. So that makes Scala better, right?
<p/>
But the difference between Clojure and Scala is bigger than a feature-to-feature comparison -- they have very different philosophies, and programs developed in Clojure consequently have a very different feel to them than those developed in Scala. I find Clojure programs to be dramatically simpler.
<p/>
Just as one example, consider modeling a deck of cards. In Clojure, you'd be more likely to come up with a simple representation for a card, perhaps: [10 :spades]. Depending on the card game, you might choose to represent a face card as [:king :clubs] or [13 :clubs]. A deck would likely be modeled as just a sequence of cards, and all the built-in sequence functions would apply, for example, shuffle, take, drop, etc. Serializing the data (for example, if you want to keep a database tracking all the shuffled decks you've ever used in a given game) comes for free.
<p/>
On the other hand, in Scala, you'd be more likely to create a card Class with a rank and suit field. The Suit class would be comprised of four case classes, because the philosophy is to enumerate all the possible suits as separate entities -- there's nothing in Scala like Clojure's convenient keywords. For the rank, you'd be steered towards representing all the ranks as integers. The possibility of representing face cards with a name would likely never occur to you, because it would be too complicated to go through the effort of defining the type of a rank to be a "integer or a class comprised of four case classes -- jack,queen,king,ace". For modeling the deck, you probably wouldn't say a Deck <i>is-a</i> sequence, because composition is favored over inheritance. So you'd probably have a Deck class which would <i>contain</i> a sequence of cards. This means that you'd have to reimplement methods like shuffle, take, and drop on your Deck class to turn around and dispatch those methods to the underlying sequence of cards. If you're not careful, years of object-oriented training might kick in and before you know it, you're representing the deck as a class where methods like shuffle, take, and drop destructively update the underlying sequence -- it feels so natural to do that once you've encapsulated the underlying sequence of cards in a class. If you want to serialize a deck, that's more code to write (although general "pickling" of a Scala object is an active area of research).
<p/>
This example pretty much sums up what I prefer about Clojure. I like to tell people that a big part of what makes Clojure special is its philosophy of <i>lightweight data modeling</i>. It leads to delightfully simple systems. Scala remains deeply rooted in the OO philosophy, which all too often leads to an over-engineered muddle.
</blockquote>
<h2> Further thoughts </h2>
After posting the above message, a couple people pointed out that Scala doesn't force you to build the more complicated model. That's absolutely true. But due to its highly detailed static type system, Scala attracts the kind of programmers that like to carefully categorize and enumerate all the possible data structures that will occur in their programs. Sure, you could eschew objects in Scala and mimic Clojure by using generic maps/vectors/lists/sets for all your structured data needs, but that's clearly not how Scala is meant to be used, and numerous little details of the language psychologically steer you towards developing a more rigorous type taxonomy.
<p/>
In my post, I mentioned <i>lightweight data modeling</i>. I can't stress this term enough. I'd like to see it become the new catchphrase for Clojure. When I used to give my "elevator pitch" for Clojure, I'd talk about how it was a functional programming language, a dialect of Lisp on the JVM, with some interesting concurrency constructs. I'd get a lot of blank stares. Most people don't know what it means to be functional, and many don't know about Lisp. But once I started talking about <i>lightweight data modeling</i>, people's interest perked up. People get it, or think they get it, or at least get it enough to be curious to ask for more details.
<p/>
At that point, I often say something like, "Do you know JSON?" After getting acknowledgment, I continue with, "Well, imagine if you could represent all your data as JSON, rather than a complex hierarchy of objects and methods, and the language was designed around making that kind of data super-easy to work with." I find I get a much more positive response from this kind of explanation. It gives a hint of what it feels like to work in Clojure and think in Clojure.
<p/>
I find it interesting that in Scala's early days, Scala had a similar orientation. They proudly boasted that XML manipulation was going to be Scala's killer feature. You could drop XML in your code as a data literal; the language was oriented around making XML easy to work with. Now, this has fallen by the wayside. Martin Odersky (the designer of Scala) has been quoted as saying, "Seemed a great idea at the time, now it sticks out like a sore thumb."
<p/>
I admit, there are times where I'm envious of Scala's versatility versus Clojure: the ease of using a mutable variable, the ease of working with Java primitives and arrays, the speed that comes from static typing, the richness of classes versus Clojure's namespaces. (Actually, this last point is probably worthy of its own blog post -- Clojure's namespaces are quite limited in ways that frequently cause me pain). Whenever I run up against one of these rough spots in Clojure, I feel like an ascetic monk, suffering because I've chosen to deny myself the additional tools that Scala brings to the table. But overall, I feel happier programming in Clojure because the additional constraints imposed by Clojure guide me more quickly towards a simple design.Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com128tag:blogger.com,1999:blog-7321273324412229482.post-28569261187169722052013-09-24T00:05:00.001-07:002013-09-24T00:05:36.052-07:00Defeating stack overflows<p>I've mentioned in the past that Clojure's stack limitation is a frequent pain point for me. A recent question on the Clojure group got me thinking again about this issue, and this seems like a good opportunity to summarize some of my thoughts on how to work around stack limitations.</p>
<p>To illustrate the problem, consider the following mathematical function:</p>
<pre><code>f(n) = { 1 if n < 5
{ f(n-5)+f(floor(n/2)) if n >= 5
</code></pre>
<p>I picked this function for no particular reason other than that it is a fairly simple doubly-recursive formula (a la fibonacci), but sufficiently unfamiliar that it's not obvious what the closed formula for this function is. These sorts of functions come up all the time when trying to analyze the performance of complex algorithms; you might need to compute something like f(200000) to figure out how long it will take a certain algorithm to run on a list of 200000 items. There is an <a href="https://www.coursera.org/course/ac">entire branch of mathematics</a> devoted to converting functions like this into closed formulas, but for the sake of argument, let's assume that you actually need to compute f(200000).</p>
<p>So let's try the obvious thing:</p>
<pre><code>(defn f [n]
(if (< n 5) 1 (+' (f (- n 5)) (f (quot n 2)))))
</code></pre>
<p>But even (f 2000) starts the CPU churning forever. Well, this is an easy fix, we just memoize.</p>
<pre><code>(def f (memoize f))
</code></pre>
<p>(f 2000) now works like a charm, but if you go to (f 20000), you get a stack overflow.</p>
<p>Because of the double recursion, it's quite difficult to express this function with tail recursion and an accumulator. One technique to convert to tail recursion is continuation-passing style, but that doesn't really solve the stack overflow problem. Even though it is tail recursive to build up the continuation, the continuation you build is so deep that you blow the stack as soon as you try to execute it. One possibility is to combine continuation-passing style with trampolining, but that gets hairy real fast. Is there an easier way?</p>
<p>I've touched on two techniques in previous blog posts, but in both posts I was dealing with a simpler recursive function. Lets revisit those techniques in the context of this more challenging example.</p>
<h3 id="technique-1-priming-the-pump">Technique 1: Priming the pump</h3>
<p>(described in my <a href="http://programming-puzzler.blogspot.com/2012/11/coin-change-kata-in-racket-and-clojure.html">blog post about the coin kata</a>)</p>
<p>"Priming the pump" is a technique that makes a memoized function behave like a bottom-up dynamic programming algorithm. Put simply, you call the function on all the inputs from 0 up to n, and then return f(n).</p>
<p>However, in our above example, clearly there are a lot of "holes" in terms of what inputs are needed to compute f(200000). If we compute f for every input from 0 up to n, we're doing a lot of extra computation we don't need, and using up memory for our cache that we don't need. In theory, if we weren't limited by the stack, the recursive formulation of <code>f</code> would compute precisely the values that were needed, no more, no less. So we haven't really "defeated the stack problem" unless we can emulate that behavior. The naive "priming the pump" strategy does too much extra work.</p>
<p>So what we need to do is compute the dependencies explicitly. To do this, you need to perform a <em>reverse topological sort</em>. For our purposes, I'm calling the function <code>all-dependencies</code>, but it is a general purpose search that you can use for many purposes, so it's worth keeping an algorithm like this around in your toolbox.</p>
<p>Here's the function:</p>
<pre><code>(defn all-dependencies
"Takes a dependencies function that maps inputs to a sequence of other inputs that it is dependent upon,
as well as the initial input n"
[dependencies n]
(loop [stack []
unprocessed [n]
processed {}]
(if (empty? unprocessed) stack
(let [i (peek unprocessed)
status (processed i)]
(case status
:done (recur stack (pop unprocessed) processed),
:seen-once (recur (conj stack i) (pop unprocessed) (assoc processed i :done)),
(recur stack (into unprocessed (dependencies i))
(assoc processed i :seen-once)))))))
</code></pre>
<p>To apply this function, first we need to come up with the dependencies function that reflects the dependencies of our function <code>f</code>.</p>
<pre><code>(defn f-dependencies [n] (if (< n 5) [] [(- n 5) (quot n 2)]))
</code></pre>
<p>Let's see it in action:</p>
<pre><code>=> (all-dependencies f-dependencies 30)
[3 2 7 0 5 10 15 1 6 12 20 25 30]
</code></pre>
<p>Notice how computing <code>f</code> for each value in the sequence is dependent only on computing <code>f</code> on the values found to the left in the sequence. So now we can prime the pump with this list of values.</p>
<pre><code>(defn priming-the-pump-f [n]
(last (map f (all-dependencies f-dependencies n))))
</code></pre>
<p>Note that the <code>f</code> in that function needs to be the memoized version of f. That's what makes the priming technique work. At this point, computing <code>f</code> via our new, improved version is no longer bound by the stack.</p>
<pre><code>=> (time (priming-the-pump-f 200000))
"Elapsed time: 369.838633 msecs"
1257914963951830159969139754N
</code></pre>
<h4 id="exercise-1">Exercise 1</h4>
<p>Consider the pair of functions f and g, where</p>
<pre><code>f(n) = { 1 if n<5
{ f(n-5)+g(n-3) if n>=5
g(n) = { 2 if n<7
{ f(n-7)+g(floor(n/2)) if n>=7
</code></pre>
<p>Compute f(200000).</p>
<p>Hint: Write a function <code>fg-dependencies</code> that you can plug into the <code>all-dependencies</code> function. For example,</p>
<pre><code>=> (all-dependencies fg-dependencies [f 30])
[[g 6] [f 6] [g 13] [g 5] [f 3] [g 10] [f 13] [f 20] [g 27] [f 5] [g 12] [g 4] [f 2] [g 9] [f 4] [f 11] [f 18] [f 25] [f 30]]
</code></pre>
<p>(f and g here are meant to be the actual functions f and g, so would actually print in a more verbose manner; I've manually edited the output so the intent is clear. If you prefer to work with symbols or keywords, rather than the functions themselves, that can work also.)</p>
<p>Then adjust the priming technique to interpret these function/input ordered pairs to prime the pump for the memoized f and g functions.</p>
<h3 id="technique-2-coreasync">Technique 2: core.async</h3>
<p>(described in my <a href="http://programming-puzzler.blogspot.com/2013/07/stackless-clojure-with-coreasync_7.html">blog post about core.async</a>)</p>
<p>In the previous article about using core.async to defeat stack overflow, the example was a simple length function with no double-recursion and no need for memoization. Part of the appeal of the core.async approach was that it allowed us to get rid of the stack limitation with a very minimal transformation of the recursive algorithm. However, we'll find that dealing with these new wrinkles will, unfortunately, require a somewhat deeper transformation. Nevertheless, the transformation is fairly straightforward to implement.</p>
<p>First, because this algorithm requires memoization, we'll need to memoize. Unfortunately, the built-in memoize doesn't seem to work effectively with the go-block strategy, I'm not entirely sure why. We'll have to encode our own memoization strategy directly into the go-blocks.</p>
<pre><code>(def mt (atom {})) ; Memoization table
(defn cache-and-return [in out]
(swap! mt assoc in out)
out)
</code></pre>
<p>With these memoization helper functions in place, we can code a go-block version of our function <code>f</code></p>
<pre><code>(defn go-f [n]
(go (if (< n 5) 1
(let [in1 (- n 5) ; dependency 1
out1 (if (contains? @mt in1) (@mt in1)
(cache-and-return in1 (<! (go-f in1))))
in2 (quot n 2) ; dependency 2
out2 (if (contains? @mt in2) (@mt in2)
(cache-and-return in2 (<! (go-f (quot n 2)))))]
(+' out1 out2)))))
</code></pre>
<p>Finally, we can present our core.async version of f, which takes an input n, kicks off the underlying go block.</p>
<pre><code>(defn async-f [n] (<!! (go-f n)))
=> (time (async-f 200000))
"Elapsed time: 385.745275 msecs"
1257914963951830159969139754N
</code></pre>
<p>Note that the two running times are roughly comparable, suggesting that choosing between the two approaches is largely a matter of taste. One advantage of the core.async approach is that you don't have to explicitly code up a dependencies function, it "just works". However, the structure of <code>go-f</code> doesn't cleanly reflect the structure of the original <code>f</code> function, so arguably it is harder to write and be confident that it is correct. I personally prefer technique 1, except for certain classes of recursive functions that really require technique 2 (see exercise 3 below).</p>
<h4 id="exercise-2">Exercise 2</h4>
<p>Implement the mutually-recursive f and g functions from Exercise 1, using the core.async technique. Which of the two techniques is less ugly for mutal recursion? Discuss.</p>
<h4 id="exercise-3">Exercise 3</h4>
<p>Consider the following function f:</p>
<pre><code>f(x) = { 1 if n<5
{ f(n-5) + f(floor(n/2)) if n>=5 and f(n-3) is a multiple of 4
{ f(floor(n/3)) if n>=5 and f(n-3) is not a multiple of 4
</code></pre>
<p>There is no way to use technique 1 without computing a lot of unnecessary computations. Why? Try implementing the above function using technique 2.</p>
<h4 id="exercise-4-advanced">Exercise 4 (advanced)</h4>
<p>Implement a library that automatically converts a recursive function into one of the stackless forms given above (either technique 1 or 2).</p>
<h2 id="other-tricks">Other Tricks</h2>
<p>Right now, these are my two favorite tricks for defeating stack overflows. I've also resorted at times to a combination of continuations with trampolining, but that's too complicated to discuss here, and I haven't yet decided how well that approach generalizes to complicated recursions.</p>
<p>Are there any other tricks I've missed? Discuss in the comments below.</p>
<blockquote>
<p>Written with <a href="http://benweet.github.io/stackedit/">StackEdit</a>.</p>
</blockquote>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com3tag:blogger.com,1999:blog-7321273324412229482.post-62916664424434388832013-07-07T01:47:00.001-07:002013-07-07T01:47:51.406-07:00Stackless Clojure with core.async<p>Let's start off by writing a <code>length</code> function that computes the length of a sequence.</p>
<pre><code>(defn length [l]
(if (empty? l)
0
(inc (length (rest l)))))
</code></pre>
<p>In many dialects of Scheme, this recursive strategy would be the idiomatic way to write the function. However, in Clojure, this gives us a stack overflow:</p>
<pre><code>=> (time (length (range 20000)))
StackOverflowError clojure.lang.ChunkedCons.more (ChunkedCons.java:48)
</code></pre>
<p>Clojure's stack limitation is something I often wrestle with. One idiomatic way to translate this code to Clojure is to write the function <em>accumulator-style</em>, using <code>loop</code> and <code>recur</code> to avoid stack consumption.</p>
<pre><code>(defn accumulator-style-length [l]
(loop [size 0
l l]
(if (empty? l) size
(recur (inc size) (rest l)))))
</code></pre>
<p>But sometimes the translation to accumulator-style is not so straightforward, and I find myself wishing for a way to eliminate stack consumption while preserving the flow of the original code.</p>
<p>When I first read the announcement of core.async, I was struck by the comment that behind the scenes, it is converting go blocks into a combination of state machines and continuations. It occurred to me that this had a lot of similarity to the kind of continuation-passing transform one can do to turn stack-consuming code into tail-recursive code.</p>
<p>Just for fun, I wanted to see if core.async could be used to preserve the shape of a recursive function, while removing the stack limitation. Here's what I came up with:</p>
<pre><code>(use 'clojure.core.async)
(defn go-length [l]
(go (if (empty? l)
0
(inc (<! (go-length (rest l)))))))
(defn length [l]
(<!! (go-length l)))
</code></pre>
<p>Notice that <code>go-length</code> follows the shape of the original recursive <code>length</code> function. We've wrapped the recursive call in <code><!</code> and wrapped the entire body of the function in a go block. This function alone, however, will not produce the result we need. So we use this as a helper function to the <code>length</code> function which simply extracts the value from the call to <code>go-length</code>.</p>
<pre><code>=> (time (length (range 20000)))
"Elapsed time: 54.570256 msecs"
20000
</code></pre>
<p>Hallelujah! It works. No stack overflow. Let's compare against the accumulator version:</p>
<pre><code>=> (time (accumulator-style-length (range 20000)))
"Elapsed time: 1.500303 msecs"
20000
</code></pre>
<p>OK, so we're not going to win any performance awards with our core.async version of length, which means that this little stunt will probably remain more in the realm of "nifty little trick" than "practical way to code recursive functions", but I still think it's very cool that it works.</p>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com5tag:blogger.com,1999:blog-7321273324412229482.post-27402526877616534642013-03-06T23:29:00.001-08:002013-03-06T23:29:24.864-08:00Logic programming is overrated<p>
Logic programming is experiencing something of a resurgence in the Clojure community, sparked by core.logic, a port of miniKanren, an embedding of Prolog in Scheme. When Clojure programmers first hear about core.logic, they go rushing off for a problem to solve like a hammer in search of a nail.
</p>
<p>
This means that every few months, we see a new blog post demonstrating how to use core.logic to solve a logic puzzle. The latest one to catch my attention was <a href="http://blog.jenkster.com/2013/02/solving-logic-puzzles-with-clojures-corelogic.html">this blog post</a> by Kris Jenkins detailing a logic puzzle tackled by the London Clojure group. The blog post begins by describing the puzzle and says:
<blockquote>It cries out, "Logic Programming", doesn't it?</blockquote>
</p>
<p> <b>NO, NO, NO!!!!</b> It doesn't cry out logic programming, for reasons I'll get into in a moment.
The blog post explains that the London group was unable to solve the puzzle in a single session, and goes on to explain the complications they ran into -- for example, negation rules and rules involving inequalities prove harder than expected to encode. They also needed to introduce macros to make it more readable. You'd think that after detailing all these problems, the post would end with the observation that logic programming turned out to be a convoluted way to express the logic puzzle, and failed to live up to expectations; yet amazingly, it does not.
</p>
<p>
The reason why logic programming is so rarely useful is that, essentially, core.logic is just a complex DSL for doing exhaustive search. Clojure already <i>has</i> an elegant, compact DSL for doing exhaustive search -- it is called the <code>for</code> comprehension.
</p>
<p>
So let's take a look at just how much more cleanly and easily <a href="http://blog.jenkster.com/2013/02/solving-logic-puzzles-with-clojures-corelogic.html">this logic puzzle</a> can be solved just using Clojure's built-in for comprehension. Take a look at this code. To run it, you'll need to: <br>
<code>(use 'clojure.math.combinatorics)</code> <br>
for the <code>permutations</code> function.
</p>
<p>
As you read the code, I want you to look at how clear and concise the translation is from the English constraints to Clojure. You've got a few lines setting up the variables, and then every single line of Clojure code is a straightforward expression of the original problem statement. Notice how trivial it is to handle things like negation, ordering, and inequalities.
</p>
<script src="https://gist.github.com/Engelberg/5105806.js"></script>
<p>
Now go back and read <a href="https://github.com/krisajenkins/LogicPuzzles/blob/master/src/logicpuzzles/core.clj">the core.logic version</a>. Admit it, it's ugly in comparison.</p>
<p>I think a lot of people mistakenly believe that core.logic is working some magic behind the scenes to solve puzzles in some amazingly efficient manner. On the contrary, it's just brute force search, using complex machinery which just slows it down versus a for comprehension. Not only is the for version elegant, but it's also faster.
</p>
<p>
But the disadvantages of core.logic for solving logic puzzles don't end there. core.logic is very sensitive to the way that goals are ordered, in a bad way. <a href="http://stackoverflow.com/questions/14307187/goal-ordering-in-clojures-core-logic">Certain orderings, for example, will cause the program to go into an infinite loop, and the DSL is complex enough that this is not always readily apparent.</a>
</p>
<p>
The for comprehension version is also sensitive to ordering, but in a good way. In the for version, the code is evident and there is no mystery about how it will execute, so it is a trivial matter to rearrange the rules to <i>improve the program's running time</i>. The rule of thumb is simple: move each constraint up so that it occurs just after the definition of any variables it depends on. Here is a version where the rules have been shifted around in this straightforward way, making the search run ten times faster.
</p>
<script src="https://gist.github.com/Engelberg/5105820.js"></script>
<p>
So all this is to say that I think logic programming is overrated, at least for solving logic puzzles. I write logic puzzles for a living, and I haven't yet found a practical use for core.logic. So far, every blog post I've seen that demonstrated core.logic on a logic puzzle could have been solved just as easily or better with a for comprehension.
</p>
<p>
Does that mean core.logic is useless? Of course not. Logic programming is good for running programs backwards (I've seen some wonderful toy examples of this, like the program that generates Quines, but have yet to find a real-world example where this is useful), unification is important for writing type checkers, and the new constraint programming piece of core.logic based on cKanren has wonderful potential to be directly useful to me for the kinds of things I program (although probably not until it comes with tools for guiding and visualizing the search strategy).
</p>
<p>
So the purpose of this article is not to demean core.logic, but rather, to elevate the level of discourse surrounding it. Can we move past solving logic puzzles which would be better solved with a for comprehension? Please, show me things I can do with core.logic that would be hard to express any other way. I look forward to it!
</p>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com27tag:blogger.com,1999:blog-7321273324412229482.post-66837911988843224472012-11-19T02:16:00.000-08:002012-11-19T09:40:09.389-08:00Coin Change Kata in Racket and ClojureThere's a Code Kata that is being discussed in the Clojure community right now -- the <a href="http://craftsmanship.sv.cmu.edu/katas/coin-change-kata-1" target="_blank">Coin Change Kata</a>. As someone who programs regularly in both Racket and Clojure, I thought it would be fun to demonstrate how to tackle this problem in both languages, highlighting the differences. The Racket version is a little more straightforward, so let's begin with that.<br />
<br />
The basic idea of the Coin Change Kata is that you are given a list of coin denominations and an amount of money, and you need to find the way to achieve that amount of money in the smallest amount of coins. For example, if you want to make 18 cents out of standard U.S. coin denominations, the best way would be one dime, one nickel, and three pennies. The official description of the kata gives some latitude about how to express the output of your function. I think a dictionary (aka hash table) is a perfectly sensible way to do it.<br />
<br />
So, in Racket terminology, we're looking for a function that behaves like this:<br />
<span style="font-family: "Courier New",Courier,monospace;">(make-change '(1 5 10 25) 18)</span> produces <span style="font-family: "Courier New",Courier,monospace;">#hash((1 . 3) (5 . 1) (10 . 1))</span><br />
<br />
Most beginners, when faced with this problem, immediately reason about the problem using the most obvious example they are familiar with: U.S. coin denominations. In our experience counting out money, we know that the best strategy is to first use as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and finally, finish off with pennies.<br />
<br />
So the strategy seems straightforward. Sort the denominations in descending order, then work your way down the list, using as many as possible of the big coin denominations first. Many of the solutions that others have provided for this kata employ this strategy, known as the "greedy strategy". <i>Those solutions are wrong.</i> <br />
<br />
To see this, consider <span style="font-family: "Courier New",Courier,monospace;">(make-change '(1 20 25) 80)</span>. If you start by counting out quarters, you'll get to 75 cents, and then you make up the difference with pennies, for a total of 8 coins. Clearly, you're better off just using four 20 cent coins. So a more thorough search algorithm is required.<br />
<br />
There's one other confounding factor that is often overlooked by beginners -- what if the problem is impossible? For example, what should <span style="font-family: "Courier New",Courier,monospace;">(make-change '(2 10) 13)</span> return? With that in mind, let's refine our contract for <span style="font-family: "Courier New",Courier,monospace;">make-change</span> and say that it either returns a dictionary of how to make change, or it returns false if the problem is impossible.<br />
<br />
Before we get into the meat of the problem, there are a couple helper functions that we're going to want to have. First, it seems clear that a big part of what we'll be doing is comparing solutions to see which one uses the fewest coins. So we need a way to count the coins in a "change dictionary".<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>;; count-coins: dict -> nat
;; counts how many coins are in the change dictionary
(define (count-coins change)
(apply + (dict-values change)))
</code></pre>
<br />
<br />
It would also be helpful to have a way to increment the coin count of a single denomination in a change dictionary. For example,<br />
<span style="font-family: "Courier New",Courier,monospace;">(change-increment #hash((10 . 1) (25 . 2)) 25)</span> gives <span style="font-family: "Courier New",Courier,monospace;">#hash((10 . 1) (25 . 3))</span><br />
<br />
This is also straightforward:<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>;; change-increment: dict nat -> dict
;; Takes a change dictionary and a coin, returns the
;; change dictionary with that coin's count incremented
(define (change-increment change coin)
(dict-update change coin add1 0))</code></pre>
<br />
<br />
Now we're ready to dive in. I am aware of two basic recursive strategies for tackling this problem.<br />
<br />
<h3>
Strategy 1: Include the first coin denomination, or not</h3>
To illustrate this idea, let's go back to U.S. denominations. If I want to find the best way to make 15 cents with the denominations '(1 5 10 25), I have two scenarios to consider.<br />
<br />
The first scenario is to include the first denomination, i.e., find the best way to make 14 cents with '(1 5 10 25) and then increment the penny count of that solution by 1. The best way to make 14 cents with '(1 5 10 25) is #hash((1 . 4) (10 . 1)). Increment the penny count, and you get #hash((1 . 5) (10 . 1)). So this is one of our candidate solutions.<br />
<br />
The second scenario is that I ignore the penny completely and find the best way to make 15 cents out of '(5 10 25). The best way to do this is #hash((5 . 1) (10 . 1)).<br />
<br />
In this example, the second scenario yields the superior solution, so that's the answer.<br />
<br />
An outline of this algorithm would look like this:<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>(define (make-change denominations amount)
(cond
;; Insert base cases here
[else
;; Case 1: Use the first denomination
(define option1 (change-increment
(make-change denominations
(- amount (first denominations)))
(first denominations)))
;; Case 2: Or not
(define option2 (make-change (rest denominations) amount))
;; Which is best?
(argmin count-coins (list option1 option2))]))</code></pre>
<br />
<br />
It's not entirely obvious what the base cases are, but if you have experience with recursive algorithms, you can see that this algorithm either reduces the length of the denomination list, or reduces the target amount of money with each step. So there are really two separate base cases to consider: either the denomination list gets to empty or the amount reaches zero (or maybe even becomes negative!).<br />
<br />
Filling in the base cases looks like this:<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>(define (make-change denominations amount)
(cond
[(negative? amount) false]
[(zero? amount) #hash()]
[(empty? denominations) false]
[else
(define option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)))
(define option2 (make-change (rest denominations) amount))
(argmin count-coins (list option1 option2))]))
</code></pre>
<br />
<br />
Uh oh. There's a problem here. make-change can potentially return false, and the helper functions we created (i.e., change-increment and count-coins) don't handle false values. There are several possible ways to tackle this, but I think the simplest way is to just modify the helper functions to handle the false value gracefully.<br />
<br />
change-increment is easy to modify -- false in should mean false out.<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>;; change-increment: dict-or-false nat -> dict-or-false
(define (change-increment change coin)
(if change
(dict-update change coin add1 0)
false))
</code></pre>
<br />
<br />
It's a little less obvious how to modify count-coins. However, we're using count-coins within an argmin in order to find the solution with the fewest coins. To make this work, we just need to ensure that when count-coins is passed a false value, the output is something that can never be a "minimum". A standard trick to accomplish this is to set the output to "infinity".<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>;; count-coins: dict-or-false -> nat-or-infinity
(define (count-coins change)
(if change
(apply + (dict-values change))
+inf.0))
</code></pre>
<br />
<br />
Now, we have a working make-change function that passes all test cases. Unfortunately, as you test the make-change function with larger and larger amounts, it gets really, really sloooooow. Functional programmers know that there's a simple trick to get around this -- memoization. A quick and easy way to add memoization is to add the line:<br />
<span style="font-family: "Courier New",Courier,monospace;">(require (planet dherman/memoize:3:1))</span><br />
to the top of your file and change define to define/memo in the definition of make-change.<br />
<br />
[The first time you include the memoization library, Racket will churn for several minutes and print out hundreds of error messages as it downloads and compiles the library locally on your machine. After that, the library will be available on your system, and future inclusions will be speedy.]<br />
<br />
The final Racket version of Strategy 1:<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>#lang racket
(require rackunit)
(require (planet dherman/memoize:3:1))
;; count-coins: dict-or-false -> nat-or-infinity
;; counts how many coins are in the change dictionary
;; or returns infinity if input is false
(define (count-coins change)
(if change
(apply + (dict-values change))
+inf.0))
;; change-increment: dict-or-false nat -> dict-or-false
;; Takes a change dictionary and a coin, returns the
;; change dictionary with that coin's count incremented
;; or false if change input is false
(define (change-increment change coin)
(if change
(dict-update change coin add1 0)
false))
;; make-change: list-of-nats nat -> dict-or-false
;; Takes a list of coin denominations and an amount that
;; needs to be broken up into change. Returns a
;; "change dictionary", i.e., a hash table that maps
;; coin denominations to counts, corresponding to the
;; most efficient way that sums to the desired amount.
;; Returns false if impossible.
(define/memo (make-change denominations amount)
(cond
[(negative? amount) false]
[(zero? amount) #hash()]
[(empty? denominations) false]
[else
(define option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)))
(define option2 (make-change (rest denominations) amount))
(argmin count-coins (list option1 option2))]))
(check-equal? (make-change '(1 5 10 25) 18)
#hash((1 . 3) (5 . 1) (10 . 1)))
(check-equal? (make-change '(1 20 25) 80)
#hash((20 . 4)))
(check-equal? (make-change '(1 24 25) 98)
#hash((24 . 2) (25 . 2)))
(check-equal? (make-change '(2 10) 13) false)
</code></pre>
<br />
<h3>
Strategy 2: Which coin to use next?</h3>
<span style="font-size: small;">Going back to our <span style="font-size: small;">example of finding the best way to make 15 cents out of '(1 5 10 25), there's a completely different strategy we could take. <span style="font-size: small;">The first coin I use could either be <span style="font-size: small;">a pe<span style="font-size: small;">nny, nickel, dime, or quarter. So if I knew the best way to make 14 cents<span style="font-size: small;">, 10 cents, 5 cents, and -10 cents <span style="font-size: small;">out of</span></span></span></span></span></span></span> '(1 5 10 25) [note that these values are 15-1, 15-5, 15-10, and 15-25, respectively], then I take the best of those ways, and increment the count of the corresponding coin to get the best way to make 15 cents.<br />
<br />
Using the same helper functions as Strategy 1, here is the final Racket implementation of make-change, Strategy 2:<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>(define/memo (make-change denominations amount)
(cond
[(negative? amount) false]
[(zero? amount) #hash()]
[(empty? denominations) false]
[else
(define options (for/list ([coin (in-list denominations)])
(change-increment
(make-change denominations (- amount coin))
coin)))
(argmin count-coins options)]))
</code></pre>
<br />
<br />
In my benchmarking, the Racket version of Strategy 1 performed 10x better than the Racket version of Strategy 2 for large target amounts.<br />
<br />
<br />
<h2>
<span style="font-size: large;">Clojure versions</span></h2>
Now, let's take a look at the Clojure versions of the same code. We'll begin with Strategy 1. In Clojure, hash maps are written using curly braces and we can insert commas anywhere we like to increase readability, so the change dictionaries look like {1 3, 5 1, 10 1}. Keeping with Clojure's conventions, the input list of denominations is now a vector rather than a list. Also, in Clojure we use nil as the output when there is no solution, rather than false. Overall, the code is almost the same (although this is not quite the final version):<br />
<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>(use 'clojure.test)
(defn count-coins [change]
(if change
(apply + (vals change))
Double/POSITIVE_INFINITY))
(defn update [m k f default]
(assoc m k (f (get m k default))))
(defn change-increment [change coin]
(when change
(update change coin inc 0)))
(defn make-change [denominations amount]
(cond
(neg? amount) nil
(zero? amount) {}
(empty? denominations) nil
:else
(let [option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)),
option2 (make-change (rest denominations) amount)]
(min-key count-coins option1 option2))))
(def make-change (memoize make-change))
(deftest make-change-tests
(are [x y] (= x y)
(make-change [1 5 10 25] 18) {1 3, 5 1, 10 1}
(make-change [1 20 25] 80) {20 4}
(make-change [1 24 25] 98) {24 2, 25 2}
(make-change [2 10] 13) nil))
</code></pre>
<br />
Let's enumerate some of the differences:<br />
<ol>
<li>count-coins is essentially the same -- infinity has a longer name.</li>
<li>Clojure does not have a built-in update function for hash-maps, so we have to roll our own. Frankly, I find this to be one of the most glaring omissions in Clojure's core library. Given the richness of Clojure's core, I find it baffling that Clojure is up to version 1.5, and this function still has not been added.</li>
<li>In change-increment, we can leverage the fact that Clojure's when returns nil when the condition is false/nil, thus saving a line relative to Racket. This is a common idiom in Clojure for writing "nil in means nil out" functions.</li>
<li>No internal define in Clojure, so instead in the else clause, we use let (which is similar to Racket's let*).</li>
<li>In Racket, argmin takes a function and a list. In Clojure, the corresponding function is min-key which takes a function and a variable number of arguments. </li>
<li>memoize is built-in to Clojure. The above technique of defining the function normally and then rebinding the function name to the memoized version is a common idiom, somewhat different than Racket's define/memo.</li>
</ol>
Not a whole lot of differences. Even the unit test code looks similar. However, there's a very big difference lurking beneath the surface: if you try make-change on a large target amount, you get a StackOverflow error. This is a definite problem.<br />
<br />
Racket uses a very clever technique to simulate an unlimited stack (or more to the point, limited only to the overall memory you've allocated to Racket, rather than some arbitrary stack limit). My understanding is that Racket achieves this trick by catching the error thrown when the stack overflows, moving the stack to the heap, and continuing. Even if those details aren't quite right, the main point here is that in Racket, you just don't spend any time worrying about stack overflows. In Clojure, it's a very salient issue that you absolutely must contend with.<br />
<br />
So how to deal with it? One option is to switch the code over to memoization's bottom-up cousin, dynamic programming. The idea is that you allocate an array large enough to store the computations of make-change for all possible values up to amount, and fill up this array in sequence using the values that have been computed before. This will solve our stack overflow problem, but requires writing the code in a very different style. It would be nice if we could solve the problem without changing much of our existing code.<br />
<br />
Any other options? How about we do a CPS transform on the entire program so that it doesn't consume any stack space, only heap? Blech.<br />
<br />
Fortunately, there is a quick trick that I like to call "priming the pump". We just call the memoized function on all numbers up to the target amount, achieving a similar bottom-up effect as the dynamic programming approach in a way that allows us to build off our existing code. For clarity, I've left the original function alone, and created a new prime-the-pump version called make-change-fast. This new function, make-change-fast, is the one we would expose publicly; the original make-change function would become private.<br />
<br />
Final Clojure version of Strategy 1:<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>;;Basic helper functions remain unchanged
(defn count-coins [change]
(if change
(apply + (vals change))
Double/POSITIVE_INFINITY))
(defn update [m k f default]
(assoc m k (f (get m k default))))
(defn change-increment [change coin]
(when change
(update change coin inc 0)))
;; This is now the private helper function, don't use this directly
(defn ^:dynamic make-change [denominations amount]
(cond
(neg? amount) nil
(zero? amount) {}
(empty? denominations) nil
:else
(let [option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)),
option2 (make-change (rest denominations) amount)]
(min-key count-coins option1 option2))))
;; This is the new public function we use to make change.
(defn make-change-fast [denominations amount]
(binding [make-change (memoize make-change)]
(last
(for [i (range (inc amount))]
(make-change denominations i)))))
</code></pre>
When writing make-change-fast, I decided to demonstrate an alternative memoization idiom in Clojure. Rather than rebinding make-change with (def make-change (memoize make-change)), we can declare make-change to be a dynamic var, and then in make-change-fast, we achieve memoization within a binding construct.
Why do it this way? Well, I actually prefer this idiom for this particular use case because it means that every make-change-fast creates its own memoized version of make-change with its own cache, and this cache can be garbage collected when the computation is complete. This becomes important if you use make-change in a long running process with very different denomination lists. It also ensures that if you run make-change in multiple threads, the caches will stay isolated from one another. Of course, if you are always using the same denomination list, the other way would be better because you'd want to keep the cache around and share it across threads.<br />
<br />
<h3>
Strategy 2:</h3>
No real surprises here, and only a few lines differ from Strategy 1, but for completeness, here is the final Clojure version of Strategy 2:<br />
<pre style="background-color: #eeeeee; border: 1px dashed #999999; color: black; font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; font-size: 12px; line-height: 14px; overflow: auto; padding: 5px; width: 100%;"><code>(defn count-coins [change]
(if change
(apply + (vals change))
Double/POSITIVE_INFINITY))
(defn update [m k f default]
(assoc m k (f (get m k default))))
(defn change-increment [change coin]
(when change
(update change coin inc 0)))
(defn ^:dynamic make-change [denominations amount]
(cond
(neg? amount) nil
(zero? amount) {}
(empty? denominations) nil
:else
(let [options (for [coin denominations]
(change-increment
(make-change denominations (- amount coin))
coin))]
(apply min-key count-coins options))))
(defn make-change-fast [denominations amount]
(binding [make-change (memoize make-change)]
(last
(for [i (range (inc amount))]
(make-change denominations i)))))
</code></pre>
<br />
<br />
Interestingly, in Clojure, Strategy 2 is twice as fast Strategy 1 for large target amounts (whereas in Racket, Strategy 1 was substantially faster).<br />
<br />
<br />
<h2>
<span style="font-size: large;">Final Thoughts</span></h2>
On my computer, both Clojure versions were faster than all the Racket versions I came up with (both the ones I displayed above, and other ones I tried, for example, employing the priming-the-pump strategy on Racket even though it is not needed). Specifically, my slowest Clojure version was twice as fast as the fastest Racket version.<br />
<br />
I find Racket's #hash notation to be awkward to work with relative to Clojure's simple {} syntax for hash tables.<br />
<br />
I wrote the Racket versions first, and they were error-free the first time. I wrote the Clojure versions second, and they took me longer to write, <i>even though I spend more time programming Clojure than Racket, </i>in part because there were two errors I needed to debug. First, I made a mistake when writing the update helper function (I initially tried to use Clojure's related update-in function, not realizing that it doesn't allow for a default value when the key is not found). Second, I always forget that min-key is a variable argument function, rather than a list function like in Racket -- to me it seems far more intuitive to have that kind of function behave on a list, since that is the most common use case. In both cases, Clojure's error messages were spectacularly unhelpful, which sadly, is par for the course in Clojure.<br />
<br />
The other reason the Clojure code took longer to write is that I needed to figure out how I wanted to deal with the stack overflow, and that ate up some time. I can't stress enough how freeing it is to not have to worry about those sorts of issues on Racket.<br />
<br />
Clojure gives you better control over memoization strategies and even more options are available in clojure.core.memoize. Racket doesn't even have a built-in memoization library, and the one on planet is weak relative to Clojure.<br />
<br />
Usually, when comparing Clojure to Racket, I find that Clojure has the richer set of built-ins: more versatile data structures and functions that operate over them. For this particular example, however, most of the built-in functions I relied on had counterparts in both languages, so the code looks nearly identical between the two languages. Oddly enough, this time it was Clojure that was missing something I wanted, namely the hash-map update function.<br />
<br />
Looking at this as a Clojure vs Racket battle, there's not a clear winner on this example since both allowed me to compactly express the approaches I had in mind and there were some advantages and disadvantages on both sides. I'd probably give Clojure the nod because Clojure gave me better speed and more control over the memoization caching behavior. (Yes, I realize that if I drop down to C, I'd get even better speed and control over caching strategies, but that's not my point. My point is that if you can get better speed and control for a similar level of effort, why not?) Nevertheless, with no stack overflows and better error messages, writing the code in Racket was a noticeably more pleasant experience.<br />
<br />
For those who have not tried Code Katas, I encourage you to do so. Code Katas usually are simple enough that they exercise fundamental skills that every programmer should possess, but are just tricky enough that there are several viable solutions and it is therefore interesting to compare those solutions with one another and across languages.<br />
<br />
For those who enjoyed this particular Kata, I would recommend reading Doctor Ecco's Cyberpuzzles by Dennis E. Sasha. The first chapter deals with a fascinating, related problem of trying to find the optimal denomination list of a given list that minimizes the average number of coins needed across a range of possible target amounts.Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com10tag:blogger.com,1999:blog-7321273324412229482.post-8894393512222545692012-11-15T15:52:00.001-08:002012-11-15T15:53:04.123-08:00Clojure makes quines way too easyA popular programming challenge is to, in your favorite programming language, write a <a href="http://en.wikipedia.org/wiki/Quine_%28computing%29" target="_blank">Quine</a> -- a program/function that prints its own source code. Usually, writing a Quine is an incredibly mindbending effort. However, yesterday, it was pointed out to me that in Clojure, this task is ridiculously simple:<br />
<br />
(defn self-source<br />
"prints the source of itself"<br />
[]<br />
(source self-source))<br />
<br />
Where's the challenge in that? :-)Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com11tag:blogger.com,1999:blog-7321273324412229482.post-8049676569145673382012-06-17T14:18:00.000-07:002012-06-17T19:29:33.531-07:00<div style="text-align: justify;">
</div>
<h2 style="margin-bottom: 0in; text-align: justify;">
I Feel Sorry For Computer Science
Departments</h2>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
There's a popular meme that it takes
ten years of effortful study to become an expert at something. I'm
sure that in reality, the number of years varies a bit from subject
to subject and from one individual to the next, but one thing is
clear – expertise takes time.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
Therein lies the problem. Most
students who enter college and decide to take computer science have
minimal, if any, prior exposure to computer science. Colleges have 4
years to try to instill some meaningful level of expertise in
students, but that's simply not enough time. Compounding the
problem, many students are hoping to go out and get internships after
their first year. This leads to a series of unfortunate, yet
inevitable compromises.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
CS departments are forced to choose:
do we focus on foundational skills and the big picture of what
computer science is all about, or do we focus on technical training
to try to produce graduates who have skills with immediate appeal to
companies? Talk to any CS professor and you'll hear plenty of
stories of bitter, divisive debates about this very issue within
departments and across the entire community of computer science
educators.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
The very best schools are constantly
reassessing this question and retooling their program. <a href="http://matt.might.net/articles/what-cs-majors-should-know/">Matt Might published a great wishlist of topics that every computer science student should know</a>.
I also have a special admiration for Carnegie Mellon in this regard.
Despite being consistently ranked as one of the very top
universities for computer science in the country, they<a href="http://reports-archive.adm.cs.cmu.edu/anon/2010/CMU-CS-10-140.pdf"> refused to rest on their laurels and recently did a complete overhaul of their introductory classes</a>. </div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
My own two cents on the topic is that
if a choice has to be made, it is better to err on the side of
teaching foundational subjects. I admire curricula such as <a href="http://programbydesign.org/">Program by Design</a>,
which takes a bold stand, teaching introductory classes in a
non-mainstream programming language (Racket, a dialect of Scheme).
They do this because the language is a particularly good choice for
teaching design and program construction at a deep level. Knowledge
of this language isn't likely to be immediately useful for a summer
internship, but colleges who use this curriculum <a href="http://www.ccs.neu.edu/home/matthias/Thoughts/coop.html">report that down the road, their students come out much stronger and much more sought after by companies. </a></div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
But the sad truth is that no matter how
many times CS departments debate this issue and retool, there are no
good answers. Four years is simply not enough time to become an
expert in computer science. Colleges are stuck between a rock and a
hard place and it's a bad situation all around. Companies are
distinctly unimpressed and disappointed with the vast majority of
graduates that colleges are producing. Ideally, companies want to
hire someone with the exact skills for a given job (one can argue
that this is a bad hiring strategy for long-term growth, but often,
it's what makes the most short-term economic sense). However, there
aren't enough of those to go around, so companies try to make the
best of the situation by just trying to find the smartest students
they can, figuring the smart ones can hopefully compensate for their
lack of experience by picking things up quickly on the job. More
often than not, the knowledge gained from a CS education is viewed by
companies as being so insufficient as to be almost irrelevant –
nevertheless, graduating from a well-known school can be seen as a
kind of proxy for the kind of drive and innate smarts they really are
looking for.
</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
Flipping this around and looking at it
from the perspective of students, many graduating students are
finding out the hard way that they lack the real-world skills
companies are seeking. If they can get that first job, sometimes
they discover that they lack the background necessary to keep up with
the tectonic shifts in the industry; when that first job goes away,
it can be very tricky to make the transition to something new. If
you don't have the exact skills companies are looking for, and you're
no longer in that bucket of entry-level, fresh-out-of-school
applicants that companies might be willing to take a chance on,
hunting for that second job can be especially tough.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
How do other departments solve this
problem? Well, many domains are able to leverage the significant
number of years that students have already invested in grade school
in English, math, and science. For example, most students who go
into mechanical engineering have already had the opportunity to learn
math up through calculus and have learned physics as well. Imagine
how many years it would take to become a mechanical engineer with
absolutely no prior math or science instruction, and you'll begin to
appreciate the problem that CS departments face. Also, many other
disciplines require significant post-graduate study and
apprenticeships in a way that computer science does not. Arguably,
computer science has one of the greatest disparities between the
demand for expertise, and the level of expertise that is actually
attained before one goes into the business.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
But wait a second... computer science
is an engineering discipline. Shouldn't computer science benefit
from kids' math and science education as much as any other
science/tech subject? Unfortunately, no. Calculus, the pinnacle of
grade school math education as it is currently structured, is the
least relevant type of math for computer scientists. Computer
scientists need a strong background in <a href="http://en.wikipedia.org/wiki/Discrete_mathematics">Discrete Math</a>
and these topics are poorly covered in grade school, if at all.
</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
To further illustrate the point, there
is not a single programming class offered in the elementary and
middle schools near my home. At the closest high school, most of the
tech ed classes are about how to use Microsoft Office and Powerpoint
to write reports; programming offerings are fairly lightweight. Keep
in mind that I live in a part of the country that is fairly rich with
tech companies, less than 30 miles from Microsoft, Amazon, Facebook,
Google, Nintendo, and Boeing. Despite my complaints about the meager
offerings in my school district, there's no doubt in my mind that
most places probably have it much worse in terms of providing kids
with early exposure to programming.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
So for the most part, computer science
curricula start from scratch. However, Program by Design, the intro
CS curriculum I mentioned earlier, stands out from the pack. Unlike
most other approaches to teaching CS, they intentionally try to
leverage students' existing math knowledge by portraying programming
as a kind of executable algebra. This is a clever strategy for
trying to maximize how far students can get towards expertise in just
four years of college.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
Once the problem has been laid bare
like this – four years provides insufficient preparation for a
career in computer science – it is obvious that there are only a
couple long-term solutions. One possibility is to extend the
duration of CS education, another possibility is to incorporate more
CS topics and exposure to programming into the grade school
curriculum.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
I think a strong case can be made that
our society would benefit from more CS in grade school, so that's the
direction I would be inclined to go. Programming is rapidly becoming
a foundational skill that has value across a wide range of
disciplines. An understanding of data, functions, and algorithms can
play an important role, right alongside mathematics and the
scientific method, for developing problem-solving skills that are
essential in our modern world.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
Another helpful change would be to
incorporate more discrete math into the grade school curriculum. A
stronger background in discrete math would make it much more feasible
for computer science students to make rapid progress in just four
years of college. Why should we make a change in the math curricula
that just benefits future computer science students? Well, the short
answer is that it wouldn't just benefit future computer science
students. <a href="http://www.ted.com/talks/arthur_benjamin_s_formula_for_changing_math_education.html">Arthur Benjamin makes the case in his TED talk that discrete math (logic, statistics, etc.) is far more relevant to most walks of life than, say, calculus</a>.</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
So in the abstract sense, it's
relatively clear what needs to change in order to solve the problem.
But we all know that implementing such a solution may well be
intractable. Even if grade schools were motivated to incorporate
more discrete math and programming into their classes, how do you go
about finding and recruiting qualified teachers?
</div>
<div style="margin-bottom: 0in; text-align: justify;">
<br /></div>
<div style="margin-bottom: 0in; text-align: justify;">
Therefore, this is likely to remain a
problem for a long time to come. In the meantime, I feel sorry for
college CS departments, I feel sorry for CS students, I feel sorry
for the people who would love programming but never get exposed to
it, and I feel a sense of loss that there's so much more our society
could achieve if we could narrow the gap between supply and demand in
computer science expertise. My hat's off to everyone who works hard
at making the best out of this bad situation.</div>Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com4tag:blogger.com,1999:blog-7321273324412229482.post-57544083626574687522011-11-20T02:54:00.000-08:002011-11-20T03:40:41.105-08:00Review of 2011 free Stanford online classesOver the summer, Stanford announced that they would be offering their AI class online for free. It made headlines, and a few weeks later they announced that they would be offering their intro to databases class and their machine learning class as well.<br /><br />I've been working through the material for all three classes so that I would know whether they were worth recommending to the high school students I work with, and also to satisfy my own personal curiosity about how the online classes would be conducted. Summary: The database and machine learning classes are excellent. Ironically, the AI class is pretty bad, even though it was the poster child for this wave of online offerings.<br /><br />The database class is the most accessible. I believe it is a freshman class at Stanford, and I think most CS-oriented high schoolers would do just fine with it. As with many CS classes, it certainly helps to have a strong background in discrete math. Specifically, prior exposure to mathematical logic, set theory, and relations makes it significantly easier to follow the discussions of relational algebra and relational design theory. The videos are fast-paced and interesting. The randomized quizzes that you can take over and over until you get 100% are a brilliant way to empower students to keep working until they have achieved mastery. The online homework system for practicing queries against a live database works quite well, and the exercises cover a nice range of difficulty from easy to hard. The teacher's weekly "screenside chats" and vibrant forum community really make it feel like you're "taking a class" rather than just working through a sterile set of videos and exercises. The material is well organized and is generally posted two to three weeks ahead of time for those who want to get ahead. All in all, it's the best example I've ever seen of what online education can potentially be.<br /><br />The machine learning class is of similarly high quality. It shares the same video technology and the same quiz engine. The machine learning class also features weekly programming assignments, using the free language Octave. The programming write-ups are very clear, and you can keep submitting your program until you get it perfect. The submission process is very easy. Unfortunately, I won't be able to recommend this class to many high school students. This class is a very math-centric approach to machine learning, and I think to fully appreciate the material you need to have a certain comfort level with the basics of linear algebra, and it helps to have seen multivariate calculus. I doubt many high school students have that mathematical background.<br /><br />Interestingly, just a few months ago, I watched some videos on "iTunes University" of the Stanford machine learning class, taught by the same professor (Andrew Ng). It is instructive to contrast my experience watching those classroom videos with my experience in the online class. The classroom videos tended to be quite long and slow, watching the professor scrawl long mathematical derivations on multiple blackboards. Without being able to see and do the related homeworks and programming assignments, it became difficult to follow the material. In contrast, the online course videos are much more briskly paced (because they know you can pause or rewatch the video if you don't get something), and the assignments do a great job of solidifying the knowledge before moving on to the next topic. It's amazing how much better the overall experience is with the online class than just watching the videos of the classroom lectures.<br /><br />As I said up top, the AI class is astonishingly bad compared to the other two. This is all the more surprising given that it is the one that gained the most widespread attention when it was announced. The website is much more poorly organized than the sites for the other two classes. The videos are poor quality - I mean this in both the literal sense (the video image is of a dimly lit piece of paper and the audio is muffled) and the content sense (the pace is much slower, failing to take advantage of the medium's ability to be paused or rewound). The questions interspersed in the video don't seem to be particularly well chosen to solidify knowledge; instead the questions are often just prompts to motivate the next topic -- you're not really expected to know the answer to the question when it is asked. This means that the only means to really solidify the knowledge is the homework quiz. These quizzes are poorly presented (rather than a clearly expressed, written statement, you have to listen to the instructor verbally explain the question) and there is no immediate feedback. Unlike the other two classes, the quiz is not randomized, so there is one set of questions and then you must wait a week to compare your answers against the correct answers (and the mechanism for checking your answers is somewhat clunky). The whole thing seems like the profs weren't ready to go prime time with this class. Three weeks into the class, the classroom forum section was still "coming soon", for example. In fact, when I last looked, they had completely punted on the forum section, and the page just said to "use Reddit" instead. Also, the videos tend to be posted quite late. Honestly, if I had nothing to compare it to, I might think it was okay, but relative to the other two classes, it is mediocre at best.<br /><br />If I were to judge the AI class solely in terms of its content, rather than on its presentation, my review wouldn't be any better. The class is really a breadth survey of various topics in AI, with no programming to back it up. Unless you're going to dig in and actually program some of these things, I really don't see the point. I believe the actual Stanford version of the class offered a programming component, but that it was dropped from the online class for logistical reasons. This is understandable, but it really takes away from the value of the class. One reason the machine learning class is so much better is because they did find a way to incorporate programming assignments.Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com10tag:blogger.com,1999:blog-7321273324412229482.post-2922933962580786672010-08-10T22:13:00.000-07:002010-08-10T22:20:39.162-07:00Racket vs. ClojureI've been asked by several people to explain why I use Clojure for my professional work rather than Racket.<br /><br /><h2>ABOUT RACKET</h2><br />I have been using Racket (a dialect of Scheme) for several years to teach kids how to program. Although Racket is a great first language, it's definitely not a "toy language". In fact, Racket offers a number of interesting features not found in other languages, making it an attractive option for real-world work. Racket puts into practice state-of-the-art research on macros, continuations, contracts, and interoperation between static and dynamically typed code. The integrated Scribble system makes it easy to provide high-quality documentation and/or write literate programs. It comes with a pleasant, lightweight IDE complete with an integrated debugger and profiler (as well as innovative features such as a specialized macro debugger).<br /><br />I'm a fan of functional programming and dynamic typing. I know how to write and think in Racket from my many years teaching it, so with all these features, it should be a slam dunk for me to use it professionally, right?<br /><br />Well, no....<br /><br /><h2>IT'S ALL ABOUT THE DATA STRUCTURES</h2><br />I have discovered that for me, the #1 factor that determines my programming productivity is the set of data structures that are built-in to the language and are easy to work with. For many years, Python set the standard for me, offering easy syntax to manipulate extensible arrays (called lists in Python), hash tables (called dictionaries in Python), tuples (an immutable collection that can serve as keys in a hash table), and in recent versions of Python, sets (mutable and immutable), heaps, and queues.<br /><br />Racket, as a dialect of Scheme, places the greatest importance on singly-linked lists. OK, that's a reasonable starting point -- you can do a lot with linked lists. It also offers a vector, which is an old-fashioned non-extensible array that is fixed in length. (Who wants fixed-length arrays as a primary data structure any more? Even C++ STL offers an extensible vector...)<br /><br />Vectors are mutable, which is both a plus and a minus. On the plus side, it allows you to efficiently write certain classes of algorithms that are hard to write with linked lists. It serves a purpose that is different from linked lists, so there is value to having both in the language. The huge minus is that Racket simply isn't oriented towards working conveniently with mutable vectors. Working with mutable data structures conveniently demands certain kinds of control structures, and certain kinds of syntaxes. You can write vector-based algorithms in Racket, but they look verbose and ugly. Which would you rather read:<br />a[i]+=3 or (vector-set! a i (+ (vector-ref a i) 3)) ?<br />But if you can get past the more verbose syntax, there's still the fundamental issue that all the patterns change when you move from using a list to a vector. The way of working with them is so fundamentally different that there is no easy way to change code from using one to another.<br /><br />Racket goes further than most Scheme implementations in providing built-in data structures. It also offers, for example, hash tables (and recently sets were added). But the interface for interacting with hash tables is a total mess. The literals for expressing hash tables use dotted pairs. If you want to construct hash tables using the for/hash syntax, you need to use "values". If you want to iterate through all the key/value pairs of a hash table, it would be nice if there were an easy way to recursively process the sequence of key/value pairs the way you would process a list. Unfortunately, Racket provides no built-in lazy list/stream, so you'd need to realize the entire list. But even if that's what you'd want to do, Racket doesn't provide a built-in function to give you back the list of keys, values or pairs in a hash table. Instead, you're encouraged to iterate through the pairs using an idiosyncratic version of its for construct, using a specific deconstructing pattern match style to capture the sequence of key/value pairs that is used nowhere else in Racket. (Speaking of for loops, why on earth did they decide to make the parallel for loop the common behavior, and require a longer name (for*) for the more useful nested loop version?) Put simply, using hash tables in Racket is frequently awkward and filled with idiosyncracies that are hard to remember.<br /><br />There are downloadable libraries that offer an assortment of other data structures, but since these libraries are made by a variety of individuals, and ported from a variety of other Scheme implementations, the interfaces for interacting with those data structures are even more inconsistent than the built-ins, which are already far from ideal.<br /><br />I'm sure many programmers can live with the awkwardness of the built-in data structures to get the other cool features that Racket offers, but for me, it's a deal breaker.<br /><br /><h2>ENTER CLOJURE</h2><br />Clojure gets data structures right. There's a good assortment of collection types built in: lists, lazy lists, vectors, hash tables, sets, sorted hash tables, sorted sets, and queues. ALL the built-in data structures are persistent/immutable. That's right, even the *vectors* are persistent. For my work, persistent vectors are a huge asset, and now that I've experienced them in Clojure, I'm frustrated with any language that doesn't offer a similar data structure (and very few do). The consistency of working only with persistent structures is a big deal -- it means you use the exact same patterns and idioms to work with all the structures. Vectors are just as easy to work with as lists. Equality is simplified. Everything can be used as a key in a hash table.<br /><br />Data structures in Clojure get a little bit of syntactic support. Not a tremendous amount, but every little bit helps. Code is a little easier to read when [1 2 3] stands out as a vector, or {:a 1, :b 2, :c 3} stands out as a hash table. Lookups are a bit more terse than in Racket -- (v 0) instead of (vector-ref v 0). Hash tables are sufficiently lightweight in Clojure that you can use them where you'd use Racket's structs defined with define-struct, and then use one consistent lookup syntax rather than type-specific accessors (e.g., (:age person) rather than (person-age person)). This gets to be more important as you deal with structures within structures, which can quickly get unwieldy in Racket, but is easy enough in Clojure using -> or get-in. Also, by representing structured data in Clojure as a hash table, you can easily create non-destructive updates of your "objects" with certain fields changed. Again, this works just as well with nested data. (Racket structs may offer immutable updates in future versions, but none of the proposals I've seen address the issue of updating nested structured data.) Furthermore, Clojure's associative update function (assoc) can handle multiple updates in one function call -- contrast (assoc h :a 1 :b 2) with (hash-set (hash-set h 'a 1) 'b 2).<br /><br />Even better, the process for iterating through any of these collections is consistent. All of Clojure's collections can be treated as if they were a list, and you can write algorithms to traverse them using the same pattern of empty?/first/rest that you'd use on a list. This means that all the powerful higher-order functions like map/filter/reduce work just as well on a vector as a list. You can also create a new collection type, and hook into the built-in sequence interface, and all the built-in sequencing functions will automatically work just as well for your collection.<br /><br />Although the sequencing functions work on any collection, they generally produce lazy lists, which means you can use good old recursion to solve many of the same problems you'd tackle with for/break or while/break in other languages. For example, (first (filter even? coll)) will give you the first even number in your collection (whether a list, vector, set, etc.) and it will do so in a space-efficient manner -- it doesn't need to generate an intermediate list of *all* the even numbers in your collection. Some garbage is generated along the way, but it can be garbage collected immediately and with relatively little overhead. Clojure also makes it easy to "pour" these lazy sequences into the collection of your choice via into. Racket's lack of a built-in lazy list makes it difficult to use map/filter/etc. for general processing of collections. If you use map/filter/etc., you potentially generate a lot of intermediate lists. You can use a stream library, but it was probably designed for other Scheme dialects with a naming scheme for the API that doesn't match Racket's built-in list functions or integrate well with Racket's other sequencing constructs. So often you end up writing the function you need from scratch (e.g., find-first-even-number) rather than composing existing building blocks. In some special cases, you can use one of the new for constructs, like in this case, for/first.<br /><br />A polymorphic approach is applied through most of Clojure's design. assoc works on vectors, hash tables, sorted hash tables, and any other "associative" collection. And again, you can hook into this with custom collections. This is far easier to remember (and more concise to write) than the proliferation of vector-set, hash-set, etc. you'd find in Racket. It also makes the various collections more interchangeable in Clojure, making it easier to test different alternatives for performance implications with fewer, more localized changes to one's code.<br /><br />Summary:<br /><ul><br /><li> Clojure provides a full complement of (immutable!) data structures you need for everyday programming and a bit of syntactic support for making those manipulations more concise and pleasant.<br /><li> All of the collections are manipulated by a small number of polymorphic functions that are easy to remember and use.<br /><li> Traversals over all collections are uniformly accomplished by a sequence abstraction that works like a lazy list, which means that Clojure's higher order sequence functions also apply to all collections.<br /></ul><br /><br /><h2>CLOJURE'S NOT PERFECT</h2><br />The IDEs available for Clojure all have significant drawbacks. You can get work done in them, but any of the IDEs will probably be a disappointment relative to what you're used to from other languages (including Racket).<br /><br />Debugging is difficult -- every error generates a ridiculously long stack trace that lists 500 Java functions along with (maybe, if you're lucky) the actual Clojure function where things went awry. Many of Clojure's core functions are written with a philosophy that they make no guarantees what they do with bad input. They might error, or they might just return some spurious answer that causes something to blow up far far away from the true origin of the problem.<br /><br />Clojure inherits numerous limitations and idiosyncracies from Java. No tail-call optimization, no continuations. Methods are not true closures, and can't be passed directly to higher-order functions. Proliferation of nil and null pointer exceptions. Slow numeric performance. Compromises with the way hashing and equality works for certain things to achieve Java compatibility. Slow startup time.<br /><br />Some people love Clojure specifically because it sits on top of Java and gives them access to their favorite Java libraries. Frankly, I have yet to find a Java library I'd actually want to use. Something about Java seems to turn every library into an insanely complex explosion of classes, and Java programmers mistakenly seem to think that JavaDoc-produced lists of every single class and method constitutes "good documentation". So for me, the Java interop is more of a nuisance than a help.<br /><br />Clojure has a number of cool new ideas, but many of them are unproven, and only time will tell whether they are truly valuable. Some people get excited about these features, but I feel fairly neutral about them until they are more road-tested. For example:<br /><ul><br /><li> Clojure's STM implementation - seems promising, but some reports suggest that under certain contention scenarios, longer transactions never complete because they keep getting preempted by shorter transactions.<br /><li> agents - if the agent can't keep up with the requests demanded of it, the agent's "mailbox" will eventually exhaust all resources. Perhaps this approach is too brittle for real-world development?<br /><li> vars - provides thread isolation, but interacts poorly with the whole lazy sequence paradigm that Clojure is built around.<br /><li> multimethods - Clojure provides a multimethod system that is far simpler than, say CLOS, but it requires you to explicitly choose preferences when there are inheritance conflicts, and early reports suggest that this limits extensibility.<br /><li> protocols - This is an interesting variation on "interfaces", but it's not clear how easy it will be to compose implementations out of partial, default implementations.<br /><li> transients - Nice idea for speeding up single-threaded use of persistent data structures. Transients don't respond to all the same interfaces as their persistent counterparts, though, limiting their usefulness. Transients are already being rethought and are likely to be reworked into something new.<br /></ul><br /><br />So it's hard for me to get excited about these aspects of Clojure when it remains to be seen how well these features will hold up under real-world use.<br /><br />I'm sure that for many programmers, Clojure's drawbacks or unproven ideas would be a deal breaker. We all care about different things. But for me, Clojure's clean coherent design of the API for working with the built-in data structures is so good, that overall, I prefer working in Clojure to working in Racket.Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com35tag:blogger.com,1999:blog-7321273324412229482.post-83550223975559067272010-07-26T19:59:00.000-07:002010-07-26T20:59:32.273-07:00Translating Code from Python and Scheme to ClojureWhen coming to Clojure from another language, it takes a while before you start "thinking in Clojure". While ramping up, it helps to understand how to solve a problem in a language you're already familiar with, and then translate the code in some methodical fashion into Clojure.<br /><br />This article will look at a simple function, remove-first, and look at how you would implement that function in Python and Scheme, and then how to methodically transform those implementations into Clojure. In all of these implementations, I'm going to ignore ways to write the function using shortcuts provided by the standard library, and focus on the implementations using standard iteration and/or recursive techniques. This will provide the clearest example of how the translation process works and can generalize to other types of functions.<br /><br />Problem Statement: remove-first takes an item and a collection, and returns a new collection which is identical to the original, except the first instance of item (if any) has been removed from the collection. If item is not in the collection, the new collection should be identical to the original (since nothing needs to be removed).<br /><br />First, let's look at the Python implementation. Python's primary collection data structure is called a "list", but this is a bit of a misnomer, because in most languages, the term "list" is used to describe some sort of linked or doubly-linked list. Python's list is nothing of the sort. Python's list allows fast (destructive) insertion and removal at the back end of the list, and fast lookup by index. In most languages, this would be called an extensible array or extensible vector (in Java, it's called an ArrayList).<br /><br />The problem statement for remove-first calls for returning a new copy of the collection with the first instance of item removed. Is this really idiomatic for Python? It is certainly possible to write remove-first as a destructive function that actually modifies the original collection by removing the first instance of item. In fact, such a destructive method is built-in to the list class (list.remove(item)). But removing from the middle of a Python list is not an especially efficient operation, and Python has a culture of slices, comprehensions, and many other list operations that return fresh copies. So yes, I think it is reasonable to talk about how to write a non-destructive removal in Python.<br /><br />Now remember, for the purposes of this article, we're trying to look at how to translate iterative algorithms, so it's a cheat to use built-in constructs that work around this.<br /><br />So this doesn't count, because it uses the built-in destructive removal:<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>def removeFirst(itemToRemove, coll):<br /> newColl = coll[:] # copies the collection<br /> try:<br /> newColl.remove(itemToRemove) # throws an error if item is not present<br /> return newColl<br /> except:<br /> return newColl<br /></code></pre><br /><br />Nor does this, although this is arguably the most idiomatic Python version of removeFirst, because it uses the built in index function which handles the iteration behind the scenes:<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>def removeFirst(itemToRemove, coll):<br /> try:<br /> i = coll.index(itemToRemove)<br /> return coll[:i] + coll[i+1:]<br /> except:<br /> return coll[:]<br /></code></pre><br /><br />In Python, the standard practice for writing such a function in an iterative fashion is to create a new list, and then iterate over the items of the initial list, adding the appropriate ones to the new list, and then returning the new list at the end. This pattern of setting up an accumulator, and then using a for loop to add things to the accumulator, is a common one in Python. For this particular problem, in English you might say, "I'm going to go through the items, adding them one at a time to the new collection. If I hit one that matches the item to remove, I skip it and add the rest of the items directly to the new collection."<br /><br />But is it better to iterate directly over the items, or is it better to iterate over the indices and access the items through the indices? When possible, it's preferred to iterate directly over the items, but unfortunately, Python has no good way to express "the rest of the items" once you hit an item that matches the one to remove. You can only get at "the rest of the items" if you know the index in order to take a slice from there to the end. So iterating through items versus iterating through indices yield slightly different strategies for this particular problem.<br /><br />If you really wanted to iterate directly over the items, you'd probably need to use a flag to track whether you've already removed the first occurrence of the item:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>def removeFirst(itemToRemove, coll):<br /> newCollection = []<br /> alreadyRemovedItem = False<br /> for item in coll:<br /> if (alreadyRemovedItem):<br /> # We've already removed the first instance of item<br /> # so we're just in "copy" mode<br /> newCollection.append(item)<br /> else:<br /> # We need to test whether the item matches itemToRemove<br /> if (item == itemToRemove):<br /> # don't copy this item over, but set alreadyRemovedItem flag<br /> alreadyRemovedItem = True<br /> else:<br /> newCollection.append(item)<br /> return newCollection<br /></code></pre><br /><br />which could be refactored by reorganizing the if/else branches into the shorter:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>def removeFirst(itemToRemove, coll):<br /> newCollection = []<br /> alreadyRemovedItem = False<br /> for item in coll:<br /> if (alreadyRemovedItem or item != itemToRemove):<br /> newCollection.append(item)<br /> else:<br /> alreadyRemovedItem = True<br /> return newCollection<br /></code></pre><br /><br />Alternatively, if you iterate through the indices, then you can use a list slice to capture the notion of "the rest of the list".<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>def removeFirst(itemToRemove, coll):<br /> newCollection = []<br /> for index in range(len(coll)):<br /> item = coll[index]<br /> if (item == itemToRemove):<br /> # skip this item and rather than add the rest of the items<br /> # one by one, we can just add the rest to newCollection<br /> # all in one step<br /> newCollection.extend(coll[index+1:])<br /> # We're done now<br /> return newCollection<br /> else:<br /> newCollection.append(item)<br /> return newCollection<br /></code></pre><br /><br />Admittedly, this last version is a bit of a cheat by my own definition of avoiding built-ins that bypass iteration, since that's effectively what extend is doing. But I don't mind it as much since we at least had to iterate until we found the item to remove, so it sufficiently demonstrates iteration techniques.<br /><br />I think either of these versions (iterating through items or iterating through indices) are good examples of common patterns that occur in Python, and are worth knowing how to translate to Clojure.<br /><br />Let's begin by translating the version that iterates through items.<br /><br />Clojure has a built-in datastructure that corresponds very closely to Python's lists. In Clojure, it is called a vector. Like Python lists, it allows fast access to an element by index, and allows fast insertion and removal at the back end of the collection. The main difference is that a Clojure vector, like all built-in Clojure data structures, is persistent and immutable. That means that any operation on a Clojure vector returns some sort of fresh copy -- the original remains unchanged. At first, this might sound wildly inefficient, but altered Clojure vectors can share a lot of internal structure with their source, precisely because of this guarantee of immutability, so it's actually pretty fast.<br /><br />But this requires a different way of thinking about algorithms. We can't just create a new empty vector and destructively add things to it and return it, as we do with Python. (Well, of course, since Clojure sits on top of Java, you can easily use Clojure to create a Java ArrayList and use exactly the same pattern as Python, but you're here to learn "the Clojure way", right?)<br /><br />Perhaps the most naive way to translate the code is to simulate a mutable vector in Clojure by wrapping a vector in some sort of mutable reference type (e.g., an atom). You'd need to do the same thing to the already-removed-flag. The @ sign is then used to look at the current contents of the mutable reference. This is very bad form for this kind of algorithm, and not particularly efficient, but it works, and has an almost exact parallel to the Python code:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>; This is bad style, don't do this!!!<br />(defn remove-first [item-to-remove coll]<br /> (let [new-collection (atom []),<br /> already-removed-item (atom false)]<br /> ; doseq is just like Python's for loop<br /> (doseq [item coll]<br /> (if (or @already-removed-item (not= item item-to-remove))<br /> (swap! new-collection conj item) ; just like append<br /> (reset! already-removed-item true))) ; sets flag to true<br /> @new-collection))<br /></code></pre><br /><br /><br />The better way to tackle this translation is to closely analyze the original, and identify any accumulator or variable that changes as you loop, and then thread those through the loop. I'll explain shortly what I mean by threading values through the loop, but there's one other issue that needs to be considered. You've already seen Clojure's doseq construct in action as a counterpart to Python's for loop, but it's only relevant for triggering destructive or side-effect-filled actions -- it's not the right tool for the job when trying to build up a persistent Clojure vector. Clojure has a for construct but it's not a general looping construct, rather, it corresponds to Python's list and generator comprehensions.<br /><br />Clojure really only has one general-purpose looping construct, known as loop/recur. In time, you'll be able to see how to go directly from a Python-style for loop to a Clojure loop/recur, but initially, it's far easier to see how to go from a Python-style while loop to a Clojure loop/recur. So as an intermediary step in translating our Python code to Clojure, let's begin by rewriting the Python for loop into a while loop. Here is one way to do that rewrite:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>def removeFirst(itemToRemove, coll):<br /> newCollection = []<br /> alreadyRemovedItem = False<br /> collIterator = iter(coll)<br /> while(True):<br /> try:<br /> item = collIterator.next()<br /> if (alreadyRemovedItem or item != itemToRemove):<br /> newCollection.append(item)<br /> else:<br /> alreadyRemovedItem = True<br /> except:<br /> # next() triggers an error when the end of the list is reached<br /> # so we're done<br /> return newCollection<br /></code></pre><br /><br />The advantage of rewriting as a while loop is that it helps us identify a couple of very important things. First, it let's us see the exit condition. The exit condition occurs when you've reached the end of the list, at which point newCollection holds the answer and can be returned. Second, it makes it a tad easier to analyze which things from outside the loop are being updated while inside the loop. The assignment to item is just creating a local variable within a given iteration of the loop, so that's not really the kind of thing we're looking for. But we should take note that newCollection, initialized outside the loop, is destructively extended within the loop, and the flag alreadyRemovedItem can also change from within the loop. Furthermore, it's now quite obvious that something needs to track the iteration through coll; this is done by collIterator which is updated each time through the while loop by the call to its next() method. So collIterator, newCollection and alreadyRemovedItem are the things we're going to need to thread through our Clojure loop/recur structure.<br /><br />Once these things have been identified, we're ready to tackle the Clojure translation. Iterators in Clojure work quite differently than in Python. Almost any collection in Clojure can be converted to a "seq" (short for sequence) by calling a function called, you guessed it, seq. For the moment, go ahead and think of it as an iterator. The iterator will be nil when the collection is exhausted. You call first to get the item the iterator is pointing at, and next to (non-destructively) advance the iterator.<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br />; Start a loop, identifying and initializing the things that will change in the loop<br /> (loop [coll-iterator (seq coll),<br /> new-collection [],<br /> already-removed-item false]<br /> ; coll-iterator is nil when you're at the end of the collection.<br /> ; Clojure treats all non-nil, non-false values as true.<br /> (if coll-iterator<br /> ; We haven't reached the end of the collection<br /> (let [item (first coll-iterator)]<br /> (if (or already-removed-item (not= item item-to-remove))<br /> ; update new-collection and advance coll-iterator. We do this using recur<br /> ; to jump back to loop, rebinding coll-iterator to (next coll-iterator),<br /> ; new-collection to (conj new-collection item), and<br /> ; leaving already-removed-item unchanged<br /> (recur (next coll-iterator) (conj new-collection item) already-removed-item)<br /><br /> ; else, advance iterator, leave new-collection unchanged,<br /> ; and set already-removed-item to true<br /> (recur (next coll-iterator) new-collection true)))<br /> ; We have reached the end of collection, so new-collection is the answer<br /> new-collection)))<br /></code></pre><br /> <br />Note that nothing destructive is happening here; it's all mutation-free. (next coll-iterator) actually returns a new iterator object, (conj new-collection item) actually creates a new vector with item appended to the end. Clojure makes these operations cheap, and recur lets us pass the new objects back to the top of the loop and reuse the names given in the loop construct.<br /><br />Now I'll let you in on a little secret. Rather than thinking of (seq coll) as returning an iterator, you can think of it as returning a linked-list-style view of the collection. Better yet, virtually all sequential-style functions in Clojure call seq implicitly, so that means, for all practical purposes, you can pretend that any Clojure collection is a linked list. Lists are able to answer three important questions: are you empty, what is your first element, and what are the rest of your elements? These correspond to empty?, first, and rest in Clojure. So just by thinking of our collection as a list, we have an extremely powerful way to iterate through it using recursion. We can rewrite the above Clojure code with this in mind:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (loop [coll coll, ; no explicit call to seq is needed, <br /> ; we can reuse the name coll for clarity<br /> new-collection [],<br /> already-removed-item false]<br /> (if (empty? coll)<br /> new-collection<br /> (let [item (first coll)]<br /> (if (or already-removed-item (not= item item-to-remove))<br /> (recur (rest coll) (conj new-collection item) already-removed-item)<br /> (recur (rest coll) new-collection true))))))<br /></code></pre><br /><br />This concludes our mechanical translation of the iterate-through-items Python version. It may look odd to you if you've never seen this kind of looping before. Some programmers actively prefer this style of looping because it makes it abundantly clear which things are changing each time through the loop, and how, and precisely what the exit condition is and what value you exit with. In other words, it's arguably more explicit and easier to analyze a loop/recur structure than a for loop that's mucking around with mutable objects located outside the loop. There's truth to this, but I also sympathize with those who find loop/recur to be less readable. For loops nest well and allow for some pretty intricate control flow with judicious use of continue and break; complex nested for loops like that can be hard to analyze, but the equivalent loop/recur can be even worse. Nevertheless, loop/recur is the way general looping is done in Clojure, so for now, we'll just accept it along with its advantages and disadvantages and move on.<br /><br />Now it's time to look at the iterate-through-indices version. Again, we begin by converting the Python for loop to a Python while loop.<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>def removeFirst(itemToRemove, coll):<br /> newCollection = []<br /> index = 0<br /> while (True):<br /> if (index == len(coll)):<br /> # We're done now<br /> return newCollection<br /> else:<br /> item = coll[index]<br /> if (item == itemToRemove):<br /> # Add the rest of the elements all at once and we're done.<br /> newCollection.extend(coll[index+1:])<br /> return newCollection<br /> else:<br /> newCollection.append(item)<br /> index += 1<br /></code></pre><br /><br />This time, we see the things that change while looping are newCollection and index. The above code can now be mechanically translated to:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (loop [new-collection [],<br /> index 0]<br /> (if (= index (count coll))<br /> new-collection<br /> (let [item (coll index)]<br /> (if (= item item-to-remove)<br /> ; into is like Python's extend, subvec is like Python's slice<br /> (into new-collection (subvec coll (inc index)))<br /> (recur (conj new-collection item) (inc index)))))))<br /></code></pre><br /><br />Notice how in Clojure code, we don't need to explicitly call return, return is implied.<br /><br />In Python we had two basic strategies, iterate by items and iterate by indices, and both had an analog in Clojure. But remember, the reason why we needed two strategies in Python was that there was no way to capture the "add the rest of the items to the collection" concept in the version that iterated through items, so we were forced to choose between iterating through items and use a flag to go into "copy items until reaching the end of the list"-mode, or use indices so we could take a slice.<br /><br />But Clojure offers us a way to fuse these two strategies together, because its basic iteration mechanism (the linked-list-style view) DOES make it extremely easy to work with the notion of "the rest of the items" without any index manipulation or slicing.<br /><br />Fusing the two Python strategies in Clojure, we get this:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (loop [coll coll,<br /> new-collection []]<br /> (if (empty? coll)<br /> new-collection<br /> (let [item (first coll)]<br /> (if (= item item-to-remove)<br /> ; Extend new-collection with rest of coll and return in one step<br /> (into new-collection (rest coll))<br /> (recur (rest coll) (conj new-collection item)))))))<br /></code></pre><br /><br />There's one downside to this implementation, namely, we're paying a performance penalty for gradually building up this vector by extending an immutable object one item at a time, when we don't care about and will never use the intervening steps between the empty vector and the final new collection. It's not a huge penalty, but it's real. Fortunately, Clojure offers a "recipe" to convert such functions. Upon entering the loop, you initialize the thing you're building to a transient (somewhat more mutable) vector. Then you append to it using conj! rather than conj, and finally you convert it back to immutable at the end using persistent!. The result looks like this:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (loop [coll coll,<br /> new-collection (transient [])]<br /> (if (empty? coll)<br /> (persistent! new-collection)<br /> (let [item (first coll)]<br /> (if (= item item-to-remove)<br /> (into (persistent! new-collection) (rest coll))<br /> (recur (rest coll) (conj! new-collection item)))))))<br /></code></pre><br /><br />Note that the overall shape of the code has not changed, we've just added a few annotations that improve performance. But remember this step is optional, the previous version is perfectly fine for most purposes.<br /><br />Although we were mainly trying to mimic the Python code, it's worth noting that Clojure code is highly polymorphic. Whereas the Python code only takes Python lists (and maybe some of the above versions would take strings), this Clojure algorithm will work on any collection (arrays, lists, lazy lists, vectors, sets, maps, strings, etc.) because all have that wonderful property of being viewable as lists. However, the returned collection is specifically a vector, no matter the input, so depending on the context, the polymorphism of the input may have limited utility.<br /><br />Now it's time to move on to Scheme. We'll look at a standard Scheme implementation of remove-first, and see how to translate that into Clojure. These examples have been tested in the Racket dialect of Scheme.<br /><br />In Scheme, the most basic, native collection type is the linked list. The three fundamental operations on a Scheme list are empty?, first, and rest (sound familiar?) and you can also non-destructively add an item to the front of the list with (cons item list). Adding to the back of a list is a slow operation, so the strategy of building up a new collection by adding to the back is not a particularly desirable one in Scheme. Instead, the strategy is to use recursion, essentially allowing the call stack to build the sequence of items that need to be added, eventually, to the front of an empty list. It sounds confusing, but once you have your head wrapped around recursion, it all makes perfect sense (and if you don't understand recursion, head directly to htdp.org).<br /><br />In any case, a typical Scheme implementation looks like this:<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(define (remove-first item-to-remove coll)<br /> (if (empty? coll)<br /> empty<br /> (let ([item (first coll)])<br /> (if (equal? item item-to-remove)<br /> (rest coll)<br /> (cons (first coll) (remove-first item-to-remove (rest coll)))))))<br /></code></pre><br /><br />Clojure also has a list collection, and the translation is about as straightforward as it could possibly be, requiring only a couple syntactic changes:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (if (empty? coll)<br /> () ; literal name for empty list<br /> (let [item (first coll)]<br /> (if (= item item-to-remove)<br /> (rest coll)<br /> (cons (first coll) (remove-first item-to-remove (rest coll)))))))<br /><br /></code></pre><br /><br />But there's a catch. Because Scheme relies on this kind of programming style, Scheme implementations are designed in such a way so that the stack has rather huge limits, basically being limited by your overall memory rather than some specific call-stack memory limitation. In other words, if the resulting list is small enough to fit in your computer's memory, than in all likelihood the call stack necessary to process it with recursion will fit as well. So call stack limitations are mostly a non-issue in Scheme.<br /><br />However, Clojure is limited to Java stack limits, so this style of writing will definitely place a limit on the size of collection that can be processed by this function. Fortunately, there is a rather simple solution. Clojure offers seamless interoperation between lazy lists and regular lists. Lazy lists solve the stack problem by avoiding the recursive step, returning immediately with a list-like object that can be probed on-demand for first and rest information by the consumer. Further elements will be computed as needed, and will be driven by the consumer's looping process.<br /><br />This is accomplished by wrapping a call to lazy-seq around some part of the computation. There are at least three reasonable places to place the call to lazy-seq. You can put lazy-seq around the full body of the function. <br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (lazy-seq (if (empty? coll)<br /> ()<br /> (let [item (first coll)]<br /> (if (= item item-to-remove)<br /> (rest coll)<br /> (cons (first coll) (remove-first item-to-remove (rest coll))))))))<br /><br /></code></pre><br /><br />You can place it around the cons.<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (if (empty? coll)<br /> ()<br /> (let [item (first coll)]<br /> (if (= item item-to-remove)<br /> (rest coll)<br /> (lazy-seq (cons (first coll) (remove-first item-to-remove (rest coll))))))))<br /></code></pre><br /><br />You can place it around the recursive call to remove-first.<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(defn remove-first [item-to-remove coll]<br /> (if (empty? coll)<br /> () ; literal name for empty list<br /> (let [item (first coll)]<br /> (if (= item item-to-remove)<br /> (rest coll)<br /> (cons (first coll) (lazy-seq (remove-first item-to-remove (rest coll))))))))<br /></code></pre><br /><br />Each choice results in slightly different laziness behavior, i.e., when various elements are computed, but the overall semantics of the sequence remains the same and stack overflows will be avoided. Placing the lazy-seq around the recursive function call will cause remove-first to compute the first element right away, and delay the rest. Placing the lazy-seq around the full body will prevent any computation until it is asked for by a consumer. Placing the lazy-seq around the cons results in in immediate behavior for the nil and removable-item-at-front-of-list case, and delayed behavior otherwise.<br /><br />All are acceptable choices, but preferences vary. Probably placing lazy-seq around the full body is the most common style you'll see in Clojure, although I tend to place it where the laziness is actually required (like around the recursive call, or around the cons).<br /><br />Converting remove-first so that it returns lazy lists definitely generates some additional overhead than a strict list. However, this overhead pays for itself if you ever end up using just part of the list, because no time is spent generating the parts you don't need. There's something very refreshing, freeing, and efficient about writing functions that find the first object with some particular property by using the strategy of taking the first item from the list of ALL objects with that particular property, knowing full well that the complete list will never be generated. Lazy lists can be used as an alternative to many traditional control structures (the above example of taking the first item from a lazy-list of objects satisfying a given description is an elegant substitute for something that would require a for-loop-break iteration in a traditional language). Generally speaking, lazy lists are more useful than strict lists, and for that reason, lazy lists are the norm in Clojure rather than the exception.<br /><br />Since Clojure offers both vectors (similar to Python's lists) and lists (similar to Scheme's lists), we have seen that it is possible to convert both algorithmic styles into Clojure. With Python, the main thing that needed to be dealt with was adapting the algorithm to build an immutable, rather than a mutable, vector. This was further complicated by the fact that Clojure's general loop/recur looping construct doesn't exactly match up with Python's for loop construct and a conversion process is needed. But the final result captured the spirit of the Python code well. Coming from Scheme was easier, and the only real modification that was necessary was to output a lazy list rather than a strict list. Both versions can take any collection as an input, but one produces vectors and the other produces lazy lists. Both implementations are legitimate choices, depending on the desired usage.Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com13tag:blogger.com,1999:blog-7321273324412229482.post-16814751097018236602009-04-21T01:39:00.000-07:002009-04-21T03:53:56.508-07:00ADTs in ClojureToday on the Clojure mailing list, a user asked:<br />"Is the concept of Abstract Data Types useful in Clojure?<br />If yes, how would you implement one?"<br /><br />This is an important question because coding to interfaces and abstractions, rather than concrete data, is a key aspect to writing scalable programs.<br /><br />My favorite treatment of ADTs is in <a href="http://www.info.ucl.ac.be/~pvr/book.html">Concepts, Techniques, and Models of Programming by Peter Van Roy and Seif Haridi</a>. This book shows all the variations of ADTs: stateful and declarative (aka functional), bundled and unbundled, open and secure. I'm going to walk through a few of these variations in Clojure.<br /><br />Let's consider a classic stack ADT. Since Clojure primarily emphasizes functional programming, I'm going to focus on functional implementations of this ADT, i.e., versions in which pushing and popping a stack are non-destructive and actually return a new stack.<br /><br /><h2>Open unbundled</h2><br /><br />Now the whole point of an ADT is to separate the implementation from the interface, but for starters, let's implement a stack ADT using an underlying implementation of a list. In an "unbundled" implementation, the stack data is completely separate from the functions that operate on it. It is "open" because we make no attempt to hide the implementation details of the stack. We are simply going to trust the programmer to use our interface and ignore those details.<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code><br />(defn stack-new [] nil)<br />(defn stack-push [s e] (cons e s))<br />(defn stack-top [s] (first s))<br />(defn stack-pop [s] (rest s))<br />(defn stack-empty? [s] (empty? s))<br /></code><br /></pre><br /><br />This open, unbundled implementation is probably the simplest way to code an ADT in Clojure. Because it is the simplest, this is probably the most common kind of coding you'll see in Clojure, and thus many would argue it is the most idiomatic. But just because it's the easiest to code doesn't mean it's the best.<br /><br />The most obvious problem with an open implementation is that it is a leaky abstraction. In other words, client code can easily see that this stack is implemented as a list. And it would be all too easy to forget that this implementation is supposed to be hidden, and call a list function on our stack (e.g., count).<br /><br />I have seen several comments on the clojure mailing list suggesting that it is inevitable that any ADT written in Clojure will be inherently leaky. But that is not the case...<br /><br /><h2> Secure unbundled </h2><br /><br />The idea is to wrap the data structure in something that effectively locks it with a unique key, so it can only be unwrapped with the correct key. The only functions that know the key are the ones that serve as the interface for the ADT, so nothing else can inspect or tamper with the contents of the data structure. For optimum security you'd need to use cryptographic techniques, but for illustration purposes, I've simply used gensym to generate a unique key.<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code>(let [security-key (gensym),<br /> wrap (fn [x]<br /> (fn [k]<br /> (if (= security-key k) x (throw (new Exception))))),<br /> unwrap (fn [x] (x security-key))]<br /><br /> (defn stack-new [] (wrap nil))<br /> (defn stack-push [s e] (wrap (cons e (unwrap s))))<br /> (defn stack-top [s] (first (unwrap s)))<br /> (defn stack-pop [s] (if (stack-empty? s) nil<br /> (wrap (rest (unwrap s)))))<br /> (defn stack-empty? [s] (empty? (unwrap s))))<br /></code></pre><br /><br />Notice how wrap and unwrap are local to these functions. If you play around with these stack functions, you'll see that the stacks you generate appear to the outside world as functions, and you need to pass it the right key to get at the innards. In this case, a gensym is relatively easy to forge, but you should get the idea. The innards are very well protected and there is essentially no way to manipulate the stack other than through the approved interface functions.<br /><br />One problem with unbundled ADTs is that they lack polymorphism. If you have multiple stack implementations, each one will require its own set of interface functions with different names (or the same names in different namespaces). If you want to write a function that operates over any stack implementation, it will first require you to pass in some sort of map of the interface functions to use. Although this technique is relatively common in functional languages (especially in the ML family), it's a fairly clunky way to achieve polymorphism.<br /><br /><h2> Secure bundled </h2><br /><br />The next logical step is to bundle the data along with the functions that know how to operate on it. This looks something like this:<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code><br />(let [stack-object (fn stack-object [s]<br /> (let [push (fn [e] (stack-object (cons e s))),<br /> top (fn [] (first s)),<br /> pop (fn [] (if (seq s) (stack-object (rest s)) nil)),<br /> empty? (fn [] (empty? s))]<br /> {:push push, :top top, :pop pop, :empty? empty?}))]<br /> (defn stack-new [] (stack-object nil)))<br /></code></pre><br /><br />In this implementation, a stack is an associative map of four interface functions. The actual data of the stack is hidden by lexical scoping so that only the interface functions can see it. <br /><br />The big problem here is that the syntax for manipulating these bundled stacks is fairly unpleasant. For example,<br /><code><br />(def stack1 (stack-new))<br />(def stack2 ((stack1 :push) 2))<br />(def stack2-top ((stack2 :top)))<br /></code><br /><br />You can improve the readability by providing interface functions that look like the unbundled version:<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><br /><code><br />(defn stack-push [s e] ((s :push) e))<br />(defn stack-top [s] ((s :top)))<br />(defn stack-pop [s] ((s :pop)))<br />(defn stack-empty? [s] ((s :empty?)))<br /></code></pre><br /><br />But there's a big difference between this and the unbundled version. Mainly, we get polymorphism. If you have two different concrete implementations of the ADT, your client code doesn't care. When you call stack-push, for example, the function looks up the correct push function for this given implementation in the bundle, i.e., (s :push) and calls <i>that</i> to do the pushing.<br /><br /><h2> Secure bundled, another way </h2><br /><br />You may have noticed that the secure bundled approach is essentially the way that OO languages provide ADTs. Since Clojure interoperates with Java, it stands to reason that you should be able to use Java to implement your ADTs. Yes, you can.<br /><br />The first step is to define your interface. You can either do this directly in Java, or use Clojure's ability to generate Java interfaces with something like this:<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code><br />(gen-interface<br /> :name adt.IStack<br /> :methods [[push [Object] adt.IStack]<br /> [top [] Object]<br /> [pop [] adt.IStack]<br /> [empty? [] Boolean]])<br /></code></pre><br /><br />This code would need to be compiled with Clojure's compile function, and that requires a bit of tricky setting up of classpaths and namespaces, but it's doable. Then, the bundled ADT looks very similar to above:<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code><br />(let [stack-object (fn stack-object [s]<br /> (proxy [adt.IStack] []<br /> (push [e] (stack-object (cons e s)))<br /> (top [] (first s))<br /> (pop [] (if (seq s) (rest s) nil))<br /> (empty? [] (empty? s))))]<br /> (defn stack-new [] (stack-object nil)))<br /></code></pre><br /><br />You could also make it even more Java-like by using gen-class. The dot syntax is a bit cleaner than the map-based syntax of the previous version, for example:<br /><code><br />(. s top)<br />(. s push 2)<br /></code><br />And as before, you can clean it up even more by creating unbundled interface functions that actually call the bundled versions behind the scenes.<br /><br />This is how most of the Clojure core interfaces and data structures are implemented, so in some sense, one could argue that this is the most idiomatic approach of all. However, I think many Clojurians would prefer to get away from the Java approach if there is a better way.<br /><br />And bundled versions are not without their problems. The CTM book gives a great example of a collection ADT and the challenge of writing a union function on the two collections. The problem with the bundled version is that bundles must dispatch on one input, so the union function, when written from the perspective of the first collection, doesn't have access to the private parts of the second collection. A version of the ADT that can see the innards of both inputs might be considerably more efficient.<br /><br /><h2> Secure unbundled, revisited </h2><br /><br />If the primary limitation of bundled ADT implementations is their single-dispatch nature, perhaps there is a way to go back to the secure unbundled version, but leverage Clojure's multimethods to gain a more sophisticated kind of polymorphism.<br /><br />In this final, most sophisticated variant, I'm going to go ahead and show two concrete implementations, the list-based one we've been working with as well as a vector-based implementation, so you can see how the two implementations coexist side by side. <br /><br />First, we define the interface as multimethods that dispatch on the type of stack. Notice how we don't include the constructor stack-new as part of the polymorphic interface. We'll need a separate constructor for each concrete implmentation.<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code><br />(defmulti stack-push (fn [s e] (type s)))<br />(defmulti stack-top type)<br />(defmulti stack-pop type)<br />(defmulti stack-empty? type)<br /></code></pre><br /><br />Since we're dispatching on type, we can't quite use the same wrapping representation as before (because functions can't have metadata). This time, the wrapped representation of the stack will be a map with one field (:wrapped-stack) and metadata with the appropriate type.<br /><br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><code><br />(let [security-key (gensym),<br /> wrap (fn [x]<br /> (with-meta<br /> {:wrapped-stack<br /> (fn [k]<br /> (if (= security-key k) x (throw (new Exception))))}<br /> {:type ::list-stack})),<br /> unwrap (fn [x] ((x :wrapped-stack) security-key))]<br /><br /> (defn list-stack-new [] (wrap nil))<br /> (defmethod stack-push ::list-stack [s e] (wrap (cons e (unwrap s))))<br /> (defmethod stack-top ::list-stack [s] (first (unwrap s)))<br /> (defmethod stack-pop ::list-stack [s] (if (stack-empty? s) nil<br /> (wrap (rest (unwrap s)))))<br /> (defmethod stack-empty? ::list-stack [s] (empty? (unwrap s))))<br /></code></pre><br /><br />The vector-based version is almost the same:<br /><pre style="font-family: Andale Mono, Lucida Console, Monaco, fixed, monospace; color: #000000; background-color: #eee;font-size: 12px;border: 1px dashed #999999;line-height: 14px;padding: 5px; overflow: auto; width: 100%"><br /><code><br />(let [security-key (gensym),<br /> wrap (fn [x]<br /> (with-meta<br /> {:wrapped-stack<br /> (fn [k]<br /> (if (= security-key k) x (throw (new Exception))))}<br /> {:type ::vector-stack})),<br /> unwrap (fn [x] ((x :wrapped-stack) security-key))]<br /><br /> (defn vector-stack-new [] (wrap []))<br /> (defmethod stack-push ::vector-stack [s e] (wrap (conj (unwrap s) e)))<br /> (defmethod stack-top ::vector-stack [s] (peek (unwrap s)))<br /> (defmethod stack-pop ::vector-stack [s] (if (stack-empty? s) nil<br /> (wrap (pop (unwrap s)))))<br /> (defmethod stack-empty? ::vector-stack [s] (empty? (unwrap s))))<br /></code></pre><br /><br />In fact, they are so similar, it seems clear you could write a macro to abstract out some of the commonalities.<br /><br />In my mind, this is definitely the most interesting implementation of ADTs. By using multimethods, there is the potential to implement ADTs that would be rather difficult to implement efficiently in other languages. Unfortunately, it is also quite clear that this version is considerably more work to write than the naive, open unbundled version we started out with.<br /><br />I would very much like to see additional syntactic support for making secure, unbundled ADTs easier to write. Something that can simplify or eliminate the need for explicit wrapping and unwrapping would be essential, and of course, a better system for generating security keys than gensym. It's not clear to me whether this support could be provided entirely by a library, or whether additional constructs in the core would be needed.<br /><br /><h3> What about equality? </h3><br />Another big open question in my mind is, "What happens when you try to add equality?" When you use Clojure's open structures to store your data (like maps), you get equality and hash codes for free. But how hard would it be to add equality and hash code functionality to these secure implementations of ADTs? Is it easier with some of these implementation styles than others? I haven't played around with this aspect of Clojure enough to give an answer yet. I'd love to hear comments from those who have.Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com8tag:blogger.com,1999:blog-7321273324412229482.post-23017003386292612942009-01-08T01:08:00.000-08:002009-01-08T02:29:20.667-08:00Laziness in Clojure – Traps, workarounds, and experimental hacks<span style="font-size:180%;">The power of laziness</span><br /><br />Consider the following snippet of Clojure code, which is similar to code found in several Clojure blogs, and code found in Clojure's contributed code base:<br /><br /><code>(def whole-numbers (iterate inc 0))</code><br /><br />This defines whole-numbers to a lazy sequence of all the numbers 0, 1, 2, …. Laziness is a powerful concept, and it allows us to simulate an infinite sequence. As you need more numbers, more are generated.<br /><br />So for example, let's say you want to find the first whole number that satisfies a given predicate function (let's call it pred). In an imperative language, you might do something like this:<br /><br /><pre><br />i = 0<br />while not pred(i):<br /> i += 1<br />return i<br /></pre><br /><br />On the other hand, with laziness, you can do something like this:<br /><br /><code>(first (filter pred whole-numbers))</code><br /><br /><span style="font-size:180%;">Gotcha!</span><br /><br />But there is a subtle problem with the definition of whole-numbers. Do you see it? I'll give you a hint: (iterate inc 0) does in fact produce the lazy sequence of whole numbers.<br /><br />The problem is that we gave a name to it. Huh? How could that make a difference? Yes, as surprising as it may seem, (first (filter pred (iterate inc 0))) works just fine, whereas (first (filter pred whole-numbers)) is likely to run slowly, and may even crash your program at runtime for certain inputs.<br /><br />How is this possible? How could giving something a name break your code? That's just crazy, right?<br /><br />Well, this pitfall stems from a design decision in Clojure that all lazy sequences are cached. In other words, as Clojure expands the sequence, it automatically caches the values in a linked list, so that they never have to be computed again. The next time you traverse the sequence, you are just seeing the values that were previously cached.<br /><br />Caching has a number of benefits. If your sequence is very computation-intensive, and you plan to traverse it multiple times, then caching can give a huge performance boost. If your sequence represents a traversal of some sort of non-persistent data structure, caching is essential to ensure that repeat calls to first and rest always yield the same result.<br /><br />But Clojure caches all lazy sequences, which creates a number of traps for the unwary. The “unnamed” version of the code works because the garbage collector collects the cached cells as it goes. (Even though it is somewhat wasteful to cache all these cells and immediately throw them away, Java's collection of short-lived garbage is very fast, and it's not as much of a performance hit as you might expect). However, when you give a name to the whole-numbers, the garbage collector can't do any collection. As you traverse the whole-numbers sequence, you'll have a huge performance hit as massive gobs of memory are allocated. And eventually, you'll go too far, run out of memory, and your program crashes.<br /><br />To see this in action, go compare the following on your Clojure setup:<br /><br /><pre><br />(nth (iterate inc 0) 20000000)<br />(nth whole-numbers 20000000) <br />;uses the above def of whole-numbers<br /></pre><br /><br />On my machine, the first example completes in just a few seconds. The other crashes.<br /><br />Sometimes cached lazy sequences are very useful, but in this case, caching just gets in the way. No one would ever want to cache the whole-numbers sequence. It's significantly faster to generate the sequence via incrementing every time you need to traverse the sequence, than it is to cache and hold the values. Furthermore, because the sequence represents an infinite sequence, there's no upper limit to the memory consumption. If you use a named version of the whole numbers in your program, there's a good chance that eventually, your program will break with certain large enough inputs.<br /><br /><span style="font-size:180%;">Workarounds</span><br /><br />Programming is all about abstracting out commonalities in code, so it's rather frustrating that you can't give a name to the whole-numbers sequence and need to type (iterate inc 0) everywhere. This is a fairly short definition, but you can imagine how with a more complex sequence, giving a name might really be essential.<br /><br />Fortunately, there is a workaround. Instead of giving the whole-numbers sequence a name, you give a name to a function that knows how to produce the sequence. In other words,<br /><br /><code>(defn whole-numbers [] (iterate inc 0))</code><br /><br />Now, you have to change all your uses of whole-numbers to a function call as well:<br /><br /><code>(nth (whole-numbers) 20000000) ;This works!</code><br /><br />The reason this works is that every time you call this function, it produces a brand new sequence of whole-numbers, which is unnamed, so the garbage collector can collect as it goes.<br /><br />So when you're writing code in Clojure, every time you create a lazy sequence, you need to ask yourself two questions:<br /><br />1. What will happen to my code if the entire sequence becomes realized in memory? Is the sequence too big to be accommodated?<br />2. Is it cheaper to generate the items in the sequence from scratch each time, than to allocate the memory necessary to cache the items?<br /><br />If the answer to either of these questions is yes, then you should avoid naming your sequence, or wrap it in a function.<br /><br />If you plan to program in Clojure, you need to be aware of this pitfall, and you must know the workaround. From what I can tell from the various blogs and posts on Clojure's google group, many new users are falling into this trap and naming potentially large sequences, creating fragile code with a very real danger of failure.<br /><br /><span style="font-size:180%;">Not Satisfied</span><br /><br />There are several reasons why I find this workaround unsatisfying.<br /><br />1. It imposes a signifcant cognitive burden because it not only affects the way you name a sequence (by wrapping it in a function), but it also affects every place you use the sequence. In fact, once you have a library filled with a combination of regular lazy sequences, and some of these function-wrapped lazy sequences, then every time you use one of your sequences, you have to remember which kind it is in order to call it correctly.<br />2. It's not perfect. Although wrapping a sequence in a function prevents any global var from pointing at the sequence, it is still possible for some function that manipulates the sequence to accidentally hold onto a reference to some portion of the sequence, causing a memory crash. For example,<a href="http://groups.google.com/group/clojure/browse_thread/thread/15f0463d96d8f4f0/4e255850cf2d29f5?q=lazy&lnk=ol&"> it was recently pointed out on the google group</a> that when filtering a large sequence (even if the sequence is unnamed), the filter function, as it is filtering, holds onto a portion of the sequence as it scans ahead to find the next element for the filtered sequence. If the elements that pass the filtering test are spread out too far, the program crashes. Several people looked closely at the code, and couldn't figure out why it was crashing. Eventually, Rich Hickey, the designer of the language pointed out what was going on. He plans to write a more complicated version of filter in a future version of Clojure that will avoid this particular problem, but that's not really the point. The concern here is that even knowing the function-wrapping trick, cached lazy sequences represent a certain kind of danger that is difficult to isolate and understand. When several Clojure programmers have trouble finding the source of a memory crash in a one-line piece of code, you can imagine how difficult it will be on a large body of code.<br />3. If you know for sure in advance that you'd rather not have the sequence be cached, there is currently no way to express that in Clojure. This workaround doesn't actually suppress caching, it just makes it so the garbage collector can throw away the cached values right away. You're still incurring a (small, but measurable) performance penalty from the unnecessary caching.<br />4. Even if the workaround worked reliably, this is a pretty big “gotcha” for newcomers to the language.<br /><br /><span style="font-size:180%;">Is there another way?</span><br /><br />A few weeks ago, <a href="http://groups.google.com/group/clojure/msg/23f782085801f784">I posted about this topic on the Clojure google group</a>, questioning the wisdom of this design decision to have all lazy sequences cache their values. I argued that it would be a cleaner design if lazy sequences did not cache their values, unless the programmer explicitly asked for the sequences to be cached. Basically, my argument revolved around two main points. First, it's easier to convert an uncached sequence to a cached sequence than vice versa. Second, if you forget to cache something that should be cached, it's merely a performance optimization problem, but if you forget to uncache something that needs to be cached, your program can crash. So, it's safer if the language defaults to uncached.<br /><br />Rich Hickey, the designer of Clojure, responded by saying that he had already experimented with uncached lazy sequences, and that such a choice causes a different set of problems with performance problems and code breaking – problems which he found to be even more common than the ones I've raised here. He encouraged me to try my own experiments, and report back. The rest of this blog post goes into more details about the nature of my experiments since that thread.<br /><br /><span style="font-size:180%;">Four categories of sequences</span><br /><br />Before taking the plunge and doing some experimenting, my first step was to analyze the various use cases of lazy sequences that need to be dealt with. I found that lazy sequences fall into one of four categories:<br />1. A sequence where the function to generate the sequence is very fast to compute, and the function is a “pure” function in the sense that it always generates the same output. For this use case, you never want to cache, and it becomes especially important if the sequence is large.<br />2. A sequence that will only be traversed once. If you really know for sure in advance that you will only be traversing it once, then you're better off not caching. Again, this is especially important if the sequence is large.<br />3. A sequence where it is slow to compute successive elements, and you'll possibly need to do this more than once. Caching in this case is important for performance.<br />4. A sequence where the function to generate successive elements is not guaranteed to return the same values. This can come up with Java interop, with I/O, and other sequence views of a non-persistent data structure. Caching is essential here to impose a sane, consistent view on the data.<br /><br />RH seemed especially concerned about how category 4 sequences break without caching. Now I'll be the first to admit that I haven't written a huge body of work in Clojure, but looking through my code from the past few weeks, I discovered that I didn't have any category 4 sequences in my code. First, I don't tend to deal with Java interop; I write entirely using the core Clojure data structures, which are all immutable. So any lazy sequence I write is guaranteed to be consistent, even without caching. I also don't do much with I/O. I tend to just write functions that I can use interactively from the REPL.<br /><br />Now if I were going to create a lazy sequence from an ephemeral source, I would almost certainly be using one of Clojure's built-in functions that do this conversion for you, such as line-seq, resultset-seq, file-seq, iterator-seq, enumeration-seq, etc., rather than using lazy-cons directly. So as long as those functions return a cached sequence, I pretty much don't have to worry about category 4. Furthermore, RH has said that he is working on a completely new abstraction (tentatively called streams), that (as I understand it) is a better fit for I/O and other ephemeral sources than the sequence abstraction. I speculate that once he has developed this new abstraction, the concerns about category 4 sequences will largely go away. People will generally write “streams” over ephemeral sources, and then convert them to cached lazy sequences with a one-time call to stream-seq. So as long as stream-seq builds a lazy sequence, category 4 is well supported, and we can analyze the relative merits of cached vs. uncached sequences for categories 1-3 separately.<br /><br />Since category 4 sequences aren't really present in my own code base, my experiments mainly revolve around trying to discover what feels natural for categories 1-3.<br /><br /><span style="font-size:180%;">Experiment #1 – Totally Uncached</span><br /><br />Since RH experimented with uncached laziness in a previous version of Clojure, the code for an uncached lazy sequence builder is right there in the existing Clojure codebase, but the corresponding macro (lazy-seq as opposed to lazy-cons), has been commented out. So for my first experiment, I wanted to look at what it would feel like to code in an environment where everything in Clojure built from lazy-cons (except the ones that represent ephemeral “streams”) is uncached.<br /><br />To do this, I created a namespace called uncached, in which I copied over most of Clojure's core constructs that use lazy-cons (but not file-seq, enumerator-seq, etc.). Within this namespace, I modified lazy-cons to create an uncached LazySeq rather than LazyCons. In other words,<br /><br /><pre><br />(defmacro lazy-cons [first-expr rest-expr]<br />(list 'new 'clojure.lang.LazySeq<br />(list `fn (list [] first-expr) (list [(gensym)] rest-expr))))<br /></pre><br /><br />So anything I import from this namespace will build an uncached sequence. To make the experiment as extreme as possible, I then went to every bit of Clojure code I've written (which I admit isn't that much, but hey, experiments have to start somewhere), and excluded all these functions from the core, using my uncached imported functions instead.<br /><br />I found that by using uncached sequences, my code felt a little zippier from a performance standpoint. I found that the vast majority of the sequences that I construct are only used for one pass. Furthermore, most of my sequences are very long (possibly infinite), and can be generated quickly, so the uncached behavior was a great default fit for me.<br /><br />One interesting example from my code is a function I wrote that produces a sequence of all the permutations of a given collection. Now generating the next permutation in the sequence is not exactly a trivial operation. So caching does in fact speed things up if you're going to traverse the permutation sequence multiple times. However, what I discovered is that there's such a huge time hit from allocating the memory for caching purposes the first time through, that you'd have to traverse the permutation sequence at least 20 times to begin to make up for the time lost from caching. Even so, caching becomes completely impractical once you hit permutations of 10+ items, so I've concluded that a permutations sequence should just be uncached.<br /><br />Now at one point, I applied a filter to my permutation sequence, to extract permutations that had a certain property. This filtered sequence is something that did in fact make sense to cache, provided I intended to use it more than once Fortunately, the Clojure api already includes a function called cache-seq which does exactly that. I found it very easy to get the caching behavior I wanted for this specific case – at the point where I defined the filtered sequence, I wrapped it in a call to cache-seq. Alternatively, I could have called vec on the sequence to explicitly realize the sequence.<br /><br /><code>(def fs (cache-seq (filter pred (permutations (range 10)))))</code><br /><br />So, at least in my own code, the default of not caching sequences worked rather well. There was one instance where I needed to cache the sequence, and it was easy to accomplish that. But again, I need to admit that I've only written a small amount of Clojure code (probably no more than 2kloc). So I can't claim this proves anything. I'm providing my <a href="http://www.filepanda.com/file/1pycyhc2ynvb/">simple uncached library</a> so that others can also try this very interesting experiment.<br /><br /><span style="font-size:180%;">Experiment #2 – Take your pick</span><br /><br />If we assume that defaulting to uncached isn't right for everyone, there's still the open question of what it would be like to program in a version of Clojure that offers a choice between cached and uncached versions of lazy-cons and its core sequence functions. To explore this option, I made use of the same “uncached” library, but rather than excluding the core functions and overriding them with the uncached versions, I just “require”d my uncached library so that both versions of functions were available to me. So I could call lazy-cons or uncached/lazy-cons, map or uncached/map, for or uncached/for.<br /><br />One really nice aspect of Clojure's design is the way that anything that adheres to the sequence interface works just fine with all the sequence functions. So the amazing thing is that whether you choose to build a cached or uncached sequence, it makes not one bit of difference to the consumers of your sequence. So once you make your decision as to whether a sequence should be cached or uncached, you can basically just forget about it and everything works seamlessly as you pass that sequence around.<br /><br />Despite that, at first it felt like a burden to have to constantly think about whether I needed a cached or uncached version of a sequence. But then again, I had already been doing similar analysis to avoid getting burned by a memory crash from caching, so really it wasn't much different than before. The main difference was that now I could really specify that I wanted something uncached, rather than using the function-wrapping workaround. Consuming the two types of sequences was now equally easy, and I got a slight performance boost as well.<br /><br />I also noticed something rather interesting in the patterns of when I tended to call cached vs. uncached versions of the core functions.<br /><br />For some of the functions, I was always calling the uncached versions, namely cycle, repeat, replicate, interleave, interpose, take, take-while, butlast, concat, and lazy-cat. And as I think about it further, I honestly can't think of any time you'd want a cached version of these functions. Remember that if your underlying sequences that you are operating on are cached, these functions will be equally persistent, so it's really a question of how time-consuming their operations are, and these have very little overhead. For this reason, I believe that, even if Clojure makes no other changes in its approach to laziness, it would be a simple, non-breaking, but significant improvement to change the above core functions to internally use lazy-seq as opposed to lazy-cons.<br /><br />On the other hand, I found that distinct, filter, remove, and drop-while were the most likely to need to be cached.<br /><br />If everything cleanly fell into the category of either definitely needing to be cached, or definitely needing to not be cached, things would be simple. Alas, that is not the case. For things like map, for, drop, and take-nth, it all totally depends on how complex the functions are (or how big the n is).<br /><br />So for those functions, it is very useful to be able to choose cached or uncached. But this begs the question of what will happen when other programmers start creating sequence-producing functions. In some cases they'll be able to make an executive decision in advance as to whether the resulting sequence is cached or uncached. But what about the cases where the consumer will need to be able to make a choice. Do we expect the programmer to provide both a cached and an uncached version?<br /><br />Contrast this with experiment #1, in which lazy-cons always produces uncached sequences. With such behavior, the programmer of a new sequence-producing function just uses (uncached) lazy-cons – the consumer knows it will be uncached, and can easily turn it into cached at point of naming, if necessary.<br /><br />Summarizing Experiment #2, I'll say that I really liked having added control, and the ability to select cached or uncached sequences, but I just can't imagine how people will easily write libraries that provide both options.<br /><br /><span style="font-size:180%;">Experiment #3 – Intelligent auto-selection</span><br /><br />Since some of the sequences should clearly be cached, and some clearly not cached, it would be ideal if the borderline cases could be chosen intelligently by the language in ordrer to completely remove the cognitive burden of constantly having to choose. At first, I thought maybe a scheme would work in which the cached/uncached behavior of the lazy-cons depends on the nature of the thing you're consing onto. But this isn't really useful. The desired cached/uncached behavior depends more on the complexity of the delayed function. After some experimentation, I feel that it is not possible to automate the decision. So this experiment was definitely a failure.<br /><br /><span style="font-size:180%;">Experiment #4 – Uncaching a cached sequence</span><br /><br />The major problem with Experiment #2 is that it forces library writers to supply two flavors of their sequence generating functions, which is impractical. So I tried to get really clever. For this experiment, I went back to the standard lazy-cons behavior, i.e., caching by default. But then, I tried to write a macro that would suppress caching for any sequence built with lazy-cons. I did this by setting up a global *cached* var that has a root binding of true. Lazy-cons does whatever behavior the *cached* var is set to. A special uncached macro binds the var to false. Like this:<br /><br /><pre><br />(def *cached* true)<br /><br />(defmacro lazy-cons<br />[first-expr rest-expr]<br />(list 'if '*cached*<br /> (list 'new 'clojure.lang.LazyCons<br /> (list `fn (list [] first-expr)<br /> (list [(gensym)] rest-expr)))<br /> (list 'new 'clojure.lang.LazySeq<br /> (list `fn (list [] (list 'binding ['*cached* 'false]<br /> first-expr))<br /> (list [(gensym)] (list 'binding ['*cached* 'false]<br /> rest-expr))))))<br /><br />(defmacro uncached [& rst]<br />`(binding [*cached* false]<br /> ~@rst))<br /></pre><br /><br />This basically works, in the sense that you can say something like (uncached (map * (iterate inc 0) (iterate inc 1)))) and the uncached macro affects all the calls to lazy-cons within map and iterate, so you've forced this thing to be uncached “all the way down”. But the way my macro works, uncached sequences become extremely slow. Because bindings aren't captured by the closures, the instruction to rebind *cached* has to be threaded through the delayed closures. This noticeably hinders the performance of uncached sequences. If you flipped it around and made uncached the default, then cached sequences would suffer the performance hit. Is there a better way to write this macro? If not, I must decree this experiment to be a failure.<br /><br /><span style="font-size:180%;">Conclusions</span><br /><br />I find Clojure's current cache-by-default-with-no-option-for-uncached laziness to be unsatisfying. I genuinely hope there is a better solution, and I want to help find it. Clearly sequences generated from ephemeral stream-like entitities must always be cached. But dealing with the other types of sequences, I find that my experiments with uncached-by-default-with-option-for-cached laziness turned out to be quite pleasant. This may very well be a function of my own programming niche, so I've provided a <a href="http://www.filepanda.com/file/1pycyhc2ynvb/">simple uncached library</a> so others can try to replicate this experiment with their own code. If more people report success with uncached-by-default, maybe a stronger case can be made for change.<br /><br />My other experiments were less successful, although I learned quite a bit from trying them, which is why I reported on those experiments as well. Most importantly, I gained a deeper understanding of what types of functions tend to produce sequences that need to be cached and which ones tend to produce sequences that should be uncached. This suggests that, at a minimum, some of the core library functions would benefit from being changed to produce uncached sequences.<br /><br />Perhaps someone else will see a way to turn one of these approaches into something workable, or provide an entirely new solution.Mark Engelberghttp://www.blogger.com/profile/05992502488191304160noreply@blogger.com8