Thursday, December 13, 2012

Conway's Game of Life in SQL, Part 2

I showed my implementation of Conway's Game of Life in SQL to a few people, a co-worker pondered if it could be done without the stored procedure.  I gave it some thought, and came up with an implementation that relies on views. I used views for the simple reason that it made things easier to see and understand.  If a query can be written using views, the it can be written as straight SQL, but the results are generally uglier, messier, and can often be unreadable.  Since I'm using MySQL, I realize how bad views can be when it comes to performance, but since this is a proof of concept, and a toy anyway, I'm not too worried.  I honestly doubt any real-life application would ever require me to implement the Game of Life in SQL!

I started as I had earlier, by defining the table as holding all the live cells for each generation.
create table cell (
  generation int,
  x int, 
  y int,
  primary key (generation, x, y));
Then, I created a view to represent all the candidate position on the grids where we might find live cells on the next generation.  We can only find cells where there are cells for the current generation, and in all 8 neighbour positions of those cells:
create view candidate (generation, x, y) as 
  select generation, x-1, y-1 from cell union
  select generation, x,   y-1 from cell union
  select generation, x+1, y-1 from cell union
  select generation, x-1, y   from cell union
  select generation, x,   y   from cell union
  select generation, x+1, y   from cell union
  select generation, x-1, y+1 from cell union
  select generation, x,   y+1 from cell union
  select generation, x+1, y+1 from cell;
Next, I counted the number of live cells in the 3x3 square around each candidate.  This isn't quite the same as counting the neighbours, since it includes the current cell in the count.  We will need to take that into account in a bit.
create view neighbour_count (generation, x, y, count) as 
  select generation, x, y, 
         (select count(*) 
          from cell 
         where cell.x in (candidate.x-1, candidate.x, candidate.x+1)
           and cell.y in (candidate.y-1, candidate.y, candidate.y+1)
           and not (cell.x = candidate.x and cell.y = candidate.y)
           and cell.generation = candidate.generation)
    from candidate;
From the previous post, the rules of the game can be reduced to: a cell is alive in the next generation if

  1. it has 3 neighbours
  2. it has 2 neighbours and was alive in the current generation
Let's write this as a truth table:
Live? Neighbours Alive in the next generation
yes less than 2 no
yes 2 YES
yes 3 YES
yes more than 3 no
no less than 3 no
no 3 YES
no more than 3 no
If we count the cell in the neighbour count, we change our truth table:
Live? # cells in 3x3 square Alive in the next generation
yes less than 3 no
yes 3 YES
yes 4 YES
yes more than 4 no
no less than 3 no
no 3 YES
no more than 3 no
A cell will be alive in the next generation if it's alive and the number of live cells in the square is 3 or 4, or if the cell is dead and there are 3 cells in the square.  Let's rewrite the rules... again.

A cell will be alive in the next generation if
  1. The 3x3 square has exactly 3 cells
  2. The 3x3 square has exactly 4 cells and the current cell is alive.
So, we'll include a cell in the next generation according to these rules.  We can tell if a cell is alive by doing a left outer join on the cell table:
insert into cell (
  select neighbour_count.generation+1, neighbour_count.x, neighbour_count.y 
  from neighbour_count 
         left outer join cell 
              on neighbour_count.generation = cell.generation
             and neighbour_count.x = cell.x
             and neighbour_count.y = cell.y
  where neighbour_count.generation = (select max(generation) from cell)
    and (neighbour_count.count = 3 
         or (neighbour_count.count = 4 and cell.x is not null)));
Repeat the insert statement for each following generation.

Monday, December 10, 2012

The Code Retreat

On December 8th, I attended the Montréal edition of the 2012 Code Retreat.  It was organized by Mathieu Bérubé, to whom I'm very thankful.  He asked the attendees for comments on the event, so here I go.

The format of the code retreat is that during the day, there are 6 coding session, using pairs programming.  In each session, we try to implement Conways' Game of Life, using TDD principles.  We can use any language or framework we want.  Sometimes, only one of the partners knows the language used, and the other learns as we go.  For some of the session, the leader also adds a challenge or a new guideline.  After the session, we delete the code, and we all get together to discuss the session and the challenge.  Mathieu had some questions for us to guide the discussion and to make us think.

The goal of the even, however, is not to implement the game of life, but to learn something in the process.  I think we all learned a lot, technically.  Some of us learned new languages, some learned new ways to approach the problem.  I learned that the Game of Life is easier to solve in functional or functional-type languages, rather than with object oriented or procedural languages.  I learned the problem cannot be solved by storing and infinite 2D array.  I learned that MySQL has special optimisation for "IN" that it doesn't have for "BETWEEN".  I learned a smattering of Haskell.

But that's the sort of things one can learn in a book.  What else did I learn, that's less likely to be in technology books?  In all fairness, some of the following, I already knew, and is covered in management or psychology books, but those book tend to be less popular with developers.

The clock is an evil but useful master

By having only 45 minutes to complete the task, we can't afford to explore various algorithms and data structures to solve the problem - as soon as we see something that looks promising, we grab it, and run with it, until we notice a problem and try down a different path.  In some cases, we even started coding without knowing where we were headed.  I would normally think of this as a problem, because creativity is a good thing, and stifling it must be bad.  However, having too much time usually means I'll over-design, think of all possible ways, but in the end, I may still rush through the implementation.  Moreover, I assume that I'll have thought about all the possible snags that can come along, but some problems only rear their ugly heads after some code is written and the next step proves impossible.  Sometimes, it's better to start moving down the wrong path, than to just stay in one spot and do nothing at all.

This is somewhat related the the Lean Startup methodology - test your assumptions before you make too many.

At one point, I asked the organizer to put up, on the projector, how much time remained in the session.  He pointed out that it was a bad idea, because when we look at the clock, we're more likely to cut corners just to get something working, rather than focus on the quality of the code.  This was a hard habit to ignore!

Let go, and smell the flowers

Since my first partner and I solved the problem in the first session, I was really eager to solve it the second (and third, ...) time around, in part to prove that he didn't do all the work, and I was just there to fix the syntax.  But from the second session on, Mathieu gave us particular challenges to include in our coding, from "think about change-proofing your solution" to "naive ping-pong (one partner writes the test, the other does the least amount of work possible to pass the test)".  As it turns out, it was really hard to completely implement the solution, writing the tests first, and factoring in the challenge.  Something had to give.  It was really hard to let go "complete the solution" in favor of TDD and the challenges.  Recognizing that this is what I was doing certainly helped me let go, but the drive to finish the job kept nagging me.  So much so that when I got home, I just HAD to implement the Game of Life in Scala, because I was so upset I didn't finish during the event.

Another aspect of this is how I interacted with my partners.  When I thought I had the solution and they didn't, I just pushed on with my idea, so that we'd get the job done as fast as possible.  Rushing means I didn't listen as well as I could have to what the other person had to say.  You can't speak and listen at the same time.  The point of Code Retreat is not to write the Game of Life, that's been done thousands of times.  The point was to play with writing code, try different things, and  learn something in the process.

The tools make a difference on productivity

Session after session, it became clear that for this particular problem, a functional approach makes more sense than a procedural or object-oriented one.  While we can use functional programming concepts in most languages, functional languages make the task much simpler.  Even though we struggled setting up the test environment for Scala, we got further than with procedural language, because once started, we just added a test, added an implementation - everything seemed to work almost on the first try.

Another tool that affected productivity is the editor.  I'm not advocating for any particular tool, but in all the sessions, we used one participant's set up.  Whoever's setup that was would edit so much faster.  When using someone else's computer, I quickly got frustrated because I would type some editor command, only to realize that it's the wrong way to do what I want on that editor, or I had to slow down to avoid such mistakes.  This happened even though I knew how to use the other person's editor.  It may have worked better if we had used something like Dropbox so we could each use our own computer, but given that IDEs tend to organize the source/project differently, it may not have worked either.

I change depending on the personality of my partner

Each team I was on had a different dynamic.  This was due in part to the challenge proposed - ping-pong tends to do that, and in part to the personality of my partner.  It is likely that they also took cues from my personality as well, particularly since I was generally outspoken between the sessions, so I did not necessarily get to know them well in the process.  I tend to avoid being the leader of a group, but I'm also impatient.  At the beginning of a session, the my partner didn't suggest something immediately, an approach, a language, etc, I'd propose something.  This means that more often than not, I imposed my will on the other.  I should have listened more to my partners, and I might have, if I hadn't been so intent on finishing the problem in the 45 minutes!

Deleting the code

One of the instructions in the Code Retreat is that after each session, you delete the code.  This was hardest to do, the closer we got to finishing the solution.  It was particularly difficult in the session when we wrote in Scala, because after the initial fumbling with the test environment, the progress was steady and fast.  If only I had another 10 minutes, I'm positive we could finish!  Surprisingly, the working code in MySQL was very easy to delete, possibly because it felt complete, done, over with.

All in all, it was a useful, interesting and fun experience.  I highly recommend it to any programmer!

Sunday, December 9, 2012

Conway's Game of Life in... SQL?

Yesterday, I attended the Code Retreat hosted at Notman House and organized by Mathieu Bérubé.  It was a most enjoyable experience.  On the first session, I paired with Christian Lavoie, and we tried to implement Conway's Game of Life using... mysql.  Some people thought this was crazy, and I can't disagree.  At the same time, we were able to complete the solution in under 45 minutes, not a small feat.

Part of the rules of the Code Retreat is that you delete your code after each session.  We did, but I thought the solution was so easy to implement, I thought I'd try to recreate it at home.  I made some changes to the implementation, but the core of the idea is the same as what we wrote.

The first thing to consider is that in the Game of Life, we cannot have a fixed-length 2D array that holds the cells.  Indeed, the best way is to store only the coordinates of the live cells.  Any cell that's not live isn't store anywhere, since that's the state of all the cells in the infinite grid, and it's just impossible to store an infinite grid.  We assume a finite number of live cells to start with (which means we'll always have a finite number of cells).

These cells will be located in a rectangular area that's bounded by the minimum x, minimum y, maximum x and maximum y coordinates of the cells.  This means that we can restrict our processing to the positions within a rectangle that's just a little bigger than the bounding rectangle: we need to add a border one-position wide around the whole rectangle.

Then, for each cell within that rectangle, we decide if it should be alive in the next generation.  We simply ignore cells that die, by not adding them to the next generation.  The 4 rules of the game can be rewritten as two simpler rules:

  1. If the current cell is alive, it stays alive if it as exactly 2 or 3 neighbours who are also alive
  2. If the current cell is dead, it becomes alive if it has exactly 3 neighbours.
Using a little logic processing, we can further rewrite this as the following 2 conditions to be alive in the next generation:
  1. If a cells has 3 neighbours
  2. If a cell is alive and has 2 neighbours
So, we only add the cell to the next generation (insert it in the table) if it fits either of those rules.

Counting neighbours is also fairly easy.  We find how many cells exist that have their x and y coordinates one less, equal, or one more than the current x.  We have to include the current x and y to include cells exactly to the left, exactly to right, exactly above or exactly below the current cell.  We must, however, exclude the current cell, so if we know it's set, we subtract 1 from the total count.

Here is code close to what we came up with, with some modifications that came to me after the fact.

drop table if exists cells;
create table cells (
  generation int,
  x int,
  y int,
  primary key (generation, x, y));

drop procedure if exists iterate_generation;
delimiter $$
create procedure iterate_generation ()
  declare current_gen int;
  declare current_x int;
  declare current_y int;
  declare min_x int;
  declare max_x int;
  declare min_y int;
  declare max_y int;
  declare live int;
  declare neighbour_count int;

  select max(generation) into current_gen from cells;
  select min(x)-1, min(y)-1, max(x)+1, max(y)+1
    into min_x, min_y, max_x, max_y from cells
   where generation = current_gen;

  set current_x := min_x;
  while current_x <= max_x do
    set current_y := min_y;
    while current_y <= max_y do
      select count(1) into live from cells
       where generation = current_gen
         and x = current_x
         and y = current_y;
      select count(1) - live into neighbour_count from cells
       where generation = current_gen
         and x in (current_x - 1, current_x, current_x + 1)
         and y in (current_y - 1, current_y, current_y + 1);

      if neighbour_count = 3 || live = 1 and neighbour_count = 2
        insert into cells (generation, x, y)
                   values (current_gen+1, current_x, current_y);
      end if;
      set current_y := current_y + 1;
    end while;
    set current_x := current_x + 1;
  end while;
delimiter ;

Crazy? well, yes. And yet, surprisingly easy. And absolutely a whole lot of fun.

Monday, August 1, 2011

Grails, and seemingly dirty command objects

I love Grails, but sometimes, the magic is a little too much.

I was trying to debug a particularly strange oddity, and as far as I could tell, Grails was reusing a dirty command object.  That's not possible, right?  Further investigation showed that no, it's not using a dirty command object, well, not really.  Its only doing what it's supposed to: dependency injection and convention over configuration.
Here is the simplest form of the problem I have been able to put together.

The controller:
def debug = { DebugCommand d ->
render new JSON(d)

The command objects: I have nested commands, with DebugCommand being the outer command (used by the controller) and DebugMapCommand, a map holding some values.  I'm using a LazyMap since that's why I used in my real-life problem.

public class DebugCommand {
    int someNum
    DebugMapCommand debugMapCommand = new DebugMapCommand()

public class DebugMapCommand {
  Map things = MapUtils.lazyMap([:], FactoryUtils.instantiateFactory(String))

What happens here is that multiple calls to the controller/action result data being accumulated in the LazyMap between calls:

nancyd $ curl 'http://localhost:8080/library/rpc/debug?someNum=5\&debugMapCommand.things\[2\]=5'

nancyd $ curl 'http://localhost:8080/library/rpc/debug?someNum=5\&debugMapCommand.things\[1\]=5'

nancyd $ curl 'http://localhost:8080/library/rpc/debug?someNum=5\&debugMapCommand.things\[elephants\]=5'

If I gave a new value for a map entry, the new value was used.

So, what's happening?  The DebugCommand's reference to the DebugMapCommand is called debugMapCommand, and Grails thinks I want a DebugMapCommand injected, so it created a singleton, and passed it to all my DebugCommand instances. Oops.

Trying to prove this wasn't too easy.  It would seem that a number of factors are necessary for this particular issue to manifest:

  1. The field name must be the same as the class name with the first letter lowercased
  2. The inner/sub command, DebugMapCommand, must be annotated with @Validateable
  3. The inner/sub command must be in a package that is searched for "validateable" classes (in Config.groovy, you have to have grails.validateable.packages = ['com.example.yourpackage', ...])

So, what's the lesson here?

Don't name your fields after their class.

Sunday, June 12, 2011

Why is reading code so hard?

We've all been there.  Faced with lines and lines of code, written by an intern, a programmer long gone, or a vendor with whom you do not have a support contract.

Code can be quite hard to read.  Why is that?

Without looking at the language or frameworks used, some of which are easier to read than others, there are other, more human factors that make it had to puzzle out what code does.  I'm not talking about how the code was written, but how we attempt to read it.

1. Reading code usually involves two actions: identifying what the code does, and what it was actually meant to do.

When we approach code, it's rarely because we're just curious; we usually want to fix bugs or improve it.  We must know what the code does, but for the structure and implementation of the code to make sense, we have to figure out what the programmer intended to do.  It's usually easier to figure out the intent first, then work out the discrepancies - where we think the code doesn't do what it was meant to.

This can be particularly hard when we have to look at code that was edited multiple times, by multiple people with different approaches.  Then, it's more of an archeological expedition.  That's the situation that can lead to some pretty ugly or silly code.  I remember looking at code once that, I can only imagine, was the product of too many edits:

if (someCondition == true) {
  myVar = false;
} else {
  myVar = false;

2. We're talking too loud, and not listening enough

When we see code like the one above, we laugh, we point, and our opinion of the code (and the programmer(s)) goes down.  We start generalizing and thinking the worse.  How can code with that in it be any good?  And what were they thinking?  who would wrote such poor code?

And that's when we start losing faith in the code.  Our disdain takes over, and our ears close.  We see some odd code, and instead of genuinely asking "what were they trying to do here?", we throw our hands in the air and sigh, "what were they trying to do here!"

If you want to understand the code, you must listen to what the previous programmers were trying to say.  Withhold judgement, open your eyes, your mind, and assume they were trying to accomplish something.  They may even have something to teach you about how to solve problems, about the business, or about the history of the code.

3. It's not written how we think

If you've ever written in perl, (and even if you haven't) you know that there's more than one way to accomplish a task.  Sometimes, it's a simple syntax tweak, but sometimes it's a whole approach.  For example, if I were to put an apple and an orange on the table and ask you to describe what you see, would you start with "I see two fruits" or "there's an apple and an orange"?  Depending on your answer, chances are you approach problems differently.

The code may use programming techniques we're unfamiliar with (using functions as parameters, patterns, functional programming).  Unfortunately, if we're unfamiliar with the technique, we're unlikely to recognize it it the wild, unless the programmer was kind enough to leave comments about it.  This is where experience and breadth of knowledge will come handy.  Keep up to date with developments in the field.

4. We lose track

Not all code is nicely packaged, modular and cohesive.  More often than not, we start reading code in one spot, only to realize we need to find out what a function does in another file or module.  We leave the code here, investigate the code there, which takes us to another module,... and by the time we get back to the original spot, we've totally forgotten what we were reading or trying to do.å

Take notes.  Draw pictures.  Use your IDE to find relations between code, where functions are called from.  I find printing code is, unfortunately for the trees, helpful, as I then remember not only the code, but where the code is on the page; and I scribble all over the paper in various colours.

What can we do about it?
  • Try to find out what the programmer wanted to do
  • Then see if the code does it
  • Keep an open mind - don't let your prejudice get in the way
  • Learn new (to you) techniques and patterns
  • When you code, try to see more than one way to solve the problem; maybe next time you try to read someone's code, they'll have used your second or third choice, and you'll recognize it more easily
  • Try to remember code you've written, before you were perfectly fluent in a new language, or when you were too rushed to go back and fix some readability issue.  Maybe there's someone reading that code now; treat the code in front of you as you would have others treat yours.

Why do you think reading code is so hard? what helps you?

Monday, January 10, 2011

Scala building blocks part 2: imports and packages

If you're used to Java, Scala imports and packages look both familiar and all wrong and weird.


The first thing that you may notice in some code you're reading is the use of _ in imports. The best way I've found to deal with _ is to replace it in my head with "whatever". It works in imports, but it also works in other cases where you encounter _.

So, when you see

import com.nancydeschenes.mosaique.model._

it means "import whatever you find under com.nancydeschenes.mosaique.model"

You can lump together multiple imports from the same package:

import scala.xml.{ NodeSeq, Group }

Imports are relative:

import net.liftweb._
import http._

imports whatever's needed in net.liftweb, and whatever's needed from net.liftweb.http.

But what if I have a package called http, and don't want net.liftweb.http? use the _root_ package:

import net.liftweb._
import _root_.http._


Like Java, code goes in packages. Unlike Java, packages aren't dictated by the directory structure. You can put multiple public classes in one file, and the location of the file doesn't imply what package it will be in. Do keep things simple, tho, if you ever want to be able to re-read yourself.

You can use the same package statement you would with Java:

package com.nancydeschenes.mosaique.snippet

Or, you can use the package block:

package com.nancydeschenes.mosaique {
  // Some stuff

  package snippet {
    // stuff that ends up in com.nancydeschenes.mosaique.snippet

Sunday, January 9, 2011

Scala building blocks

When I first started reading about Scala, I saw a lot of very interesting looking code, but I felt lost.  It looked as if I was trying to learn a foreign language with a phrasebook.  I saw a number of examples, but I felt I was missing the building blocks of the language.

I've been using Scala for a little while now, and this is the introduction I wish I'd had then.  This post is not meant as a detailed "how things are" but just to provide a newcomer with the right frame of mind to understand the rest.  There are some over-simplifications, but I find they help me understand, so I'm sharing them.

Classes, traits, objects, companions

Everything in Scala is an object, and every object is of a particular class.  Just like Java (if you ignore the pesky primitives).  So, generally speaking, classes work the way you expect them.  Except that there's no "static".  No static method, no static values.

Traits are like interfaces, but they can include fields and method implementations.

Objects can be declared and are then known throughout the program, in a way that's reminiscent of dependency injection, particularly the Grails flavour.  Object declarations can even include implementation, and new fields and methods.

Companion objects are objects named the same as a class.  This is how you handle details that you would normally want to do as static methods/fields/etc.  This is very elegant: it makes it look as if you had access to static elements, while preserving a true object-oriented approach.

So you may encounter code such as

class Car extends Vehicle with PassengerAble {
   val numWheels = 4
   val numPassengerSeats = 6

object Car {
  def findByLicensePlate(String plate, String emitter) : Car = {

object MyOwnCar extends Car with PassengerSideAirbags, RemoteStarter {
  val numChildSeats = 2;
  def honk : Unit = {;

In that example, the first Car is a class.  The second Car is an object.  MyOwnCar is an object that can be addressed anywhere (same package rules apply as java), but MyOwnCar has extra stuff in it: PassengerSideAirbags and RemoteStarter are trait (you can guess that because of the with keyword).  It even defines a new method so that honking it MyOwnCar should remind you of the Dukes of Hazzard.


Unlike Java, in Scala, everything is an object.  There is no such thing as a primitive.

Basic types

At the top of the object hierarchy, we have Any.  Every object, either what you think of an object in a Java sense, or the types that are primitives in Java, every thing inherits from Any.

The hierarchy then splits into two: AnyVal and AnyRef.  Primitive-like types are under AnyVal and AnyRef is essentially the equivalent of java.lang.Object.  All Java and Scala classes that you define will be under AnyRef.

Strings are just like Java Strings.  Double-quoted.  But Scala defines a few additional methods on them, and treats them as collections, too, so your String is also a list of characters.  A particularly convenient method, I've found, is toInt.  There's toDouble and toBoolean too.

Unit is what a method returns when it doesn't return anything.  You can think of it as "void".

Null as you know it is a value, but in Scala, every value has type, so it's of type Null.  And Null extends every single class, so that null (the one and only instance of Null) can be assigned to any AnyRef object.  It sounds crazy, but if you let it sink in, it will make sense.  Null is actually a trait, not a class.

Nothing is the absolute bottom of the hierarchy.  Nothing doesn't have any instances.

Numeric Types

Integers are of type Int.

Doubles are Doubles, floats are Float.

A litteral in the code is treated an object of the appropriate type.  Things just work, without "autoboxing" or other convolutions.

Strings and numeric types are immutable.


Collections come in mutable and immutable variations.

The operation you can perform on collections are probably easier to understand and get used to when you remember lisp/scheme.  Or perl.  Try to view collections are a whole, and not so much as an object with a few methods, the way we tend to in Java.  The think of the methods as operations on the whole.  It may also help to dust out set theory concepts.

A special kind of collection is the Tuple.   It's an ordered group of N items that can be of the same or of different types.  They are defined for N=2 to N=22.  You can access the j-th element of the tuple with ._j   (ex: the first is myTuple._1, the third is myTuple._3)


The first thing you have to realize about options is that they're everywhere, so you better get used to the idea.  Lift uses Box instead, but it serves the same purpose.

The second thing you have to realize is that Options (or Box) is the right way to handle multiple scenarios, but you've spent your programming life working around that fact.

Let's take a simple example.  You want to implement a method that computes the square root of the parameter it receives.  What should that method return?  a Double.  So you start:

def sqrt (x: Double) : Double = {
 // ...

You start implementing, maybe by writing some tests first... Hm... what happens if x is a negative number?  you may think "I'll just return null" or "I'll throw an exception".  If you return null, chances are the caller wont bother checking, and bad things will happen.  If you throw an exception, you slow things down a bit (exceptions should be for exceptional condition).  If you throw an unchecked exception, who knows where in the caller's code that will be handled.  If you throw a checked exception, the caller's probably already sick of catching every exception every where and has a standard, no-thought solution (ignore, wrap in a RuntimeException, etc)

Options tell you that there are multiple outcomes possible.  The case where a regular value is returned, the Option is actually a Some (subclass of Option), with the value in it.  In cases when no value can be returned, the Option is actually None (an object).  Of course, Options can be used in contexts other than returning a value from a method, but that's an easy way to see their usefulness.

Once you have an Option, you can test it for Some or None, or you can try to find what's in it: myOption.get will return the content of the Some (or throw an exception if it's None, so don't do that unless you know).  If you're not sure, you can use myOption.getOrElse(defaultVal)  which will return the contents of the Some, or gracefully (and elegantly) use the default you provided.

Or, you can use matching to decide what to do:

MathHelper.sqrt(x) match {
  case Some(y) => "The square root of " + x + " is " + y
  case None => "The value " + x + " does not have a square root"