Tetris Analyzer in Clojure - part 2

A short introduction to Clojure
Part 1

In my initial Clojure implementation of Tetris Analyzer I chose to represent the board as a one-dimensional vector, then in my second attempt I tried a two-dimensional vector.
The result for both was disapointingly ugly, and when it's ugly - then it's wrong!

Ugly code is often complex. The first met all my criterias of complex code: 
  • Code that is hard to read and understand
  • Code that is hard to change
  • When it's too much code
We will compare the rejected versions with the chosen one at the end of this post.

The new board model

After some thinking I realized that the board could be represented as a hash map where each key corresponds to a position on the board, stored as a vector "pair", [y x]:

Let's go through the improved solution and look at the first board related function in core.clj.

row->str

This function converts a board row to a string:
(defn- row->str [row]
  (apply str (map (fn [[_ piece]] (piece->char piece)) row)))
If we feed the inner map function with a board row, we get:
(map (fn [[_ piece]] (piece->char piece)) {[1 0] 9, [1 1] 0, [1 2] 1, [1 3] 2 })
;= (\# \- \I \Z)
The next two functions, apply and str, convert the list of characters to a string:
(apply str '(\# \- \I \Z))
;= "#-IZ"

board->str

This function converts a board into a printable string format. It uses the ->> macro which allows us to arrange the functions in the order they are executed:
(defn board->str [board width]
  (->> board
       sort
       (partition width)
       (map row->str)
       (clojure.string/join "\n")))
...which is equivalent to:
(defn board->str [board width]
  (clojure.string/join "\n" (map row->str (partition width (sort board)))))

It's a matter of taste which one you prefer. Let's try to explain this function, one step at a time, by calling it with a 5 x 2 board:
1. sort the board based on the order of the keys:
(sort { [0 1] 0, [0 0] 9, [1 2] 1, [0 3] 0, [0 4] 9,
        [1 1] 0, [1 0] 9, [0 2] 1, [1 3] 2, [1 4] 9 })
;=    ( [0 0] 9, [0 1] 0, [0 2] 1, [0 3] 0, [0 4] 9,
        [1 1] 9, [1 0] 0, [1 2] 1, [1 3] 2, [1 4] 9 )
2. partition into rows:
(partition 5 '( [0 0] 9, [0 1] 0, [0 2] 1, [0 3] 0, [0 4] 9 ,
                [1 1] 9, [1 0] 0, [1 2] 1, [1 3] 2, [1 4] 9 ))
;= ( ([[0 0] 9] [[0 1] 0] [[0 2] 1] [[0 3] 0] [[0 4] 9]) 
     ([[1 0] 9] [[1 1] 0] [[1 2] 1] [[1 3] 2] [[1 4] 9]) )
3. map each row to a string:
(map row->str '( ([[0 0] 9] [[0 1] 0] [[0 2] 1] [[0 3] 0] [[0 4] 9]) 
                 ([[1 0] 9] [[1 1] 0] [[1 2] 1] [[1 3] 2] [[1 4] 9])) )
;= ("#-I-#" "#-IZ#")
4. join the rows into a board, concatenate with "\n":
(clojure.string/join "\n" '("#-I-#" "#-IZ#"))
;= ("#-I-#\n#-IZ#")
And if printed, we get the "board":
#-I-#
#-IZ#

set-piece

The set-piece function can set a piece on a board:
(defn set-piece [board piece rotation x y]
  (apply assoc board (rotate-and-move-piece piece rotation x y)))

The function's test explains pretty well what it does:
;; Returns a new board with a piece set, e.g.:
;;
;;              board       piece rotation x y
;;              ----------- ----- -------- - -
;;   (set-piece empty-board    2      0    3 1)
;;
;;    piece = 2      piece Z
;;    rotation = 0   no rotation
;;    x,y = 3,1      position on the board
;;
(expect (str "#------#\n"
             "#--ZZ--#\n"
             "#---ZZ-#\n"
             "#------#\n"
             "#------#\n"
             "########")
        (board->str (set-piece empty-board 2 0 3 1) 8))

The inner form of the function produces a list with elements that has the same format as the board cells;  [y x] value:
(rotate-and-move-piece 6 1 4 2)
;= ([2 4] 6, [3 4] 6, [3 5] 6, [4 4] 6)
...the resulting list is used by apply and assoc to put a piece on the board. Note that the original board is left untouched and that a new board is returned. What makes this possible is the immutable collections in Clojure.

str->row

This function is defined as private by defn- as it's only used by new-board:
(defn- str->row [row y]
  (map-indexed #(vector [y %1] (char->piece %2)) row))
...and converts a board row to board cells:
(str->row "#-TZ#" 1) 
;= ([[1 0] 9] [[1 1] 0] [[1 2] 6] [[1 3] 2] [[1 4] 9])

The #( ) syntax is the shortcut form for anonymous functions in Clojure. The map-indexed function is similar to map except that it also offers an index to each element (0, 1, 2...here represented by %1.

new-board

The last function is used to create a new board:
(defn new-board
  ([] (new-board 12 21))
  ([rows] (into {} (mapcat #(str->row %1 %2) rows (range))))
  ([width height]
    (into {} (for [y (range height) x (range width)
                   :let [wall? (or (zero? x) (= x (dec width)) (= y (dec height)))]]
                   [[y x] (if wall? 9 0)]))))
This overloaded function can be called in three ways. If called with no arguments, we get a 10 x 20 board:
(board->str (new-board) 12)
;= "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "#----------#\n"
   "############"
The function board->str was added to get a more readable format in this example. The second way to call this function is by giving the board size:
(board->str (new-board 6 4) 6)
;= "#----#\n"
   "#----#\n"
   "#----#\n"
   "######"
The last way is to call it with a board position, which is done by the corresponding tests:
(expect { [0 0] 9, [0 1] 0, [0 2] 6, [0 3] 0, [0 4] 0, [0 5] 9,
          [1 0] 9, [1 1] 6, [1 2] 6, [1 3] 0, [1 4] 2, [1 5] 9,
          [2 0] 9, [2 1] 9, [2 2] 9, [2 3] 9, [2 4] 9, [2 5] 9 }
         (new-board ["#-T--#"
                     "#TT-Z#"
                     "######"]))
The new-board function uses these functions: forintomapcatrange, zero?, = and dec (for is actually a macro). It would take up too much space here to explain them all, especially as the official documentation is excellent with lot of examples!

The rejected design

I started by representing the board as a vector (the complete source can be found here). This seemed to be a good design choice, and was used in the C++ version.
Looping collections by index is a natural thing to do in imperative languages like C++ or Java. The problem is that it's not as natural in a functional language like Clojure.

A telling example is the set-piece function in the version that represents the board as a two dimensional vector:
(defn set-piece [board x y p piece]
  (reduce (fn [new-board [py xprow]]
          (assoc new-board py (apply assoc (new-board py) xprow))) board
        (map #(vector %2 (prow->xprow % x p)) piece (iterate inc 0))))

The code is complex and hard to read and understand. The new solution is much more elegant:
(defn set-piece [board piece rotation x y]
  (apply assoc board (rotate-and-move-piece piece rotation x y)))

The lesson from this is to choose your core models with care and change the design before it's too late!

Best regards,
Joakim Tengstrand


Tetris Analyzer in Clojure - part 1

The last couple of weeks have been a whole lot of fun, and the reason is that I have started to learn Clojure! Clojure syntax is very different from languages like C or Java but if you give it a chance, you will soon realize that the language and the ideas behind it, are actually very powerful and elegant!

This is the first of a series of blog posts where I'm going to implement a program in Clojure that can play Tetris. I have already made different versions of Tetris Analyzer in other languages with focus on performance, but the Clojure version will prioritize readability and simplicity.

In this and the next blog post, we will reach the first goal to put a piece on a board (represented as text):


I will go through all the code in detail and no previous knowledge in functional programming is required. It's recommended, however that you read the previous post A short introduction to Clojure and optionally Going Functional where I describes what caught my interest in Clojure. It's also recommended that you have some experience in at least one other programming language!

On the one hand, this is not a course in Clojure, but on the other hand, I will do my best to explain all new concepts that are needed to understand the code. I have left out some basic concepts like immutability, homoiconicity, macros and the reader which may be introduced in future blog posts.

Project structure

The project is hosted at GitHub and has the following structure:
langs/clojure/unoptimized/src/tetrisanalyzer/core.clj
langs/clojure/unoptimized/test/tetrisanalyzer/core_test.clj
langs/clojure/unoptimized/project.clj
langs/cpp/...
langs/java/...
langs/scala/...
The file project.clj is used by Leiningen to build the project and seems to be the de-facto standard in the Clojure community. The core.clj file contains the source code of the program and core_test.clj contains the unit tests. I have used Light Table as development environment and Expectations to execute the unit tests (which runs in the background and executes the tests every time a test is changed).

I will not explain how to set up a development environment, but a good start is to take a look at this screen cast by James Trunk where he explains the basics about Clojure and how to get started with Light Table and TDD using Expectations.

The program

The program is stored in the file core.clj and I recommend you to take a brief look at it right now. In the first statement you'll find the namespace macro ns:
(ns tetrisanalyzer.core)

Namespaces are used to group code, just as packages are in Java:
package tetrisanalyzer;

You may noticed that the file itself (core.clj) is included in the namespace name. In object oriented languages like Java, you group "functions" as methods in classes. A more natural thing to do, in a functional language like Clojure, is to use the file itself as a placeholder for data and functions.

Comments

The next statement is a comment:
;; ===== Pieces =====

One way to write a comment in Clojure is to begin with a semicolon. A convetion is to write double semicolons if the comment stands by itselt and a single semicolon if it is preceded by a statement on the same row.
;; some code
(def x 123) ; my favourite value

...in Java you would write:
// some code
int x = 123; // my favourite value

Pieces

All pieces is stored in a multi dimensional vector:

(def pieces [ nil
  ;; I (1)
  [[[0 0] [1 0] [2 0] [3 0]]
   [[0 0] [0 1] [0 2] [0 3]]]

  ;; Z (2)
  [[[0 0] [1 0] [1 1] [2 1]]
   [[1 0] [0 1] [1 1] [0 2]]]

  ;; S (3)
  [[[1 0] [2 0] [0 1] [1 1]]
   [[0 0] [0 1] [1 1] [1 2]]]

  ;; J (4)
  [[[0 0] [1 0] [2 0] [2 1]]
   [[0 0] [1 0] [0 1] [0 2]]
   [[0 0] [0 1] [1 1] [2 1]]
   [[1 0] [1 1] [0 2] [1 2]]]

  ;; L (5)
  [[[0 0] [1 0] [2 0] [0 1]]
   [[0 0] [0 1] [0 2] [1 2]]
   [[2 0] [0 1] [1 1] [2 1]]
   [[0 0] [1 0] [1 1] [1 2]]]

  ;; T (6)
  [[[0 0] [1 0] [2 0] [1 1]]
   [[0 0] [0 1] [1 1] [0 2]]
   [[1 0] [0 1] [1 1] [2 1]]
   [[1 0] [0 1] [1 1] [1 2]]]

  ;; O (7)
  [[[0 0] [1 0] [0 1] [1 1]]]])

The variable pieces is defined by using the special form def. The first element at index zero has the value nil and corresponds to the undefined value null in Java. This value is put here to let the pieces start at index 1.

Tetris has seven different pieces, each made of four squares. A piece can be rotated 90 degrees a number of times until reaching the start position, resulting in these 19 combinations:


We can get the shape of Z (piece 2) in its start possition (index 0) by writing:
((pieces 2) 0)
;= [[0 0] [1 0] [1 1] [2 1]]

...the returned vector corresponds to this shape:
If we put rotation 0 and 1 in a vector, we get:
  ;; Z (2)
  [[[0 0] [1 0] [1 1] [2 1]]
   [[1 0] [0 1] [1 1] [0 2]]]

Maps

The next statement in core.clj is used to convert from a "piece character" to an index:
(def char->piece { \- 0 \I 1 \Z 2 \S 3 \J 4 \L 5 \T 6 \O 7 \x 8 \# 9 })

Commas are treated as white spaces as a way to enchance readability, and we might as well have written:
(def char->piece { \- 0, \I 1, \Z 2, \S 3, \J 4, \L 5, \T 6, \O 7, \x 8, \# 9 })

The statement defines a map with the name char->piece (-> tries to imitate an arrow). Hyphen and > (amongst others) are fully legal characters to be used in names.
Maps work as you would expect, except maybe that they are immutable just as all other data structures in Clojure.

We can "calculate" the index of a piece by writing:
(char->piece \Z)
;= 2

Clean code

The Clojure version:
(def char->piece { \- 0 \I 1 \Z 2 \S 3 \J 4 \L 5 \T 6 \O 7 \x 8 \# 9 })
(char->piece \Z)
...is much cleaner than the Java version:
Map<Character, Integer> charToPiece = new HashMap<Character, Integer>();
  charToPiece.put('-', 0);
  charToPiece.put('I', 1);
  charToPiece.put('Z', 2);
  charToPiece.put('S', 3);
  charToPiece.put('J', 4);
  charToPiece.put('L', 5);
  charToPiece.put('T', 6);
  charToPiece.put('O', 7);
  charToPiece.put('x', 8);
  charToPiece.put('#', 9);

  charToPiece.get('Z');
...and the latter makes me think of my first design principle:

If it's ugly - then it's wrong!

Functions

The next statement defines a function that converts from a piece index to a piece character:
(defn piece->char [piece] (nth "-IZSJLTOx#" piece))

The function is defined by the macro defn. A call to the function will delegate to the nth function and return the corresponding character, e.g.:
(piece->char 2)
;= Z

The java version could look something like this:
public char pieceToChar(int piece) {
    return "-IZSJLTOx#".toCharArray()[piece];
}

In Java we use the reserved word return to return a value from the method. That is not needed in Clojure since it's always the last statement of the function body that is returned, in this case the call to nth.

Unit testing

To better understand the purpose of the next statement, the definition of the function rotate-and-move-piece, we can have a look at the corresponding test in core-test.clj:
;; This function returns a list of "pairs": [y x] piece
;; that can be used by the function assoc
;; (via set-piece) to put a piece on a board.
;;
;;                         piece rotation x y
;;                         ----- -------- - -
;;  (rotate-and-move-piece    6      1    4 2)
;;
;;        123456           (6 = T)
;;    0  #------#
;;    1  #------#
;;    2  #---T--#   [2 4] 6
;;    3  #---TT-#   [3 4] 6 [3 5] 6
;;    4  #---T--#   [4 4] 6
;;       ########
(expect '([2 4] 6, [3 4] 6, [3 5] 6, [4 4] 6)
        (rotate-and-move-piece 6 1 4 2))

If you are familiar with any XUnit testing framework like JUnit, then the function expect corresponds to assertEquals where the first argument is the expected outcome and the second is the statement under test.

We have to put a ' in front of the expected list, otherwise it will be treated as a function call and we get:


This call failed because we used too many arguments. We can fix this by changing the number of arguments to one:
([2 4] 1)
;= 4

The map function

The first example in the map documentation looks like this:
(map inc [1 2 3 4 5])
;= (2 3 4 5 6)

The map function takes two arguments, in this example the function inc and the collection [1 2 3 4 5]. The function inc is applied to each element in the collection to generate the resulting list.

It's also possible to inline our own version of inc:
(map (fn [x] (+ 1 x)) [1 2 3 4 5])
;= (2 3 4 5 6)
...where the statement:
(fn [x] (+ 1 x))
...is an anonymous function defined by fn. There is also a shorter syntax for anonymous functions, that will be described in the next blog post!

The mapcat macro

The first example in the mapcat documentation looks like this:
(mapcat reverse [[3 2 1 0] [6 5 4] [9 8 7]])
;= (0 1 2 3 4 5 6 7 8 9)

If we use the map function instead, we get:
(map reverse [[3 2 1 0] [6 5 4] [9 8 7]])
;= ((0 1 2 3) (4 5 6) (7 8 9))
The difference between map and mapcat is that the latter concatenates the result into a single list.

rotate-and-move-piece

Now when we know more about anonymous functions and the mapcat macro, it's time to look at the next statement in core.clj:
(defn rotate-and-move-piece [piece rotation x y]
  (mapcat (fn [[px py]] [[(+ y py) (+ x px)] piece]) ((pieces piece) rotation)))

This statement consists of four parts:


Let's take a closer look at the function body:


The statement ((pieces piece) rotation) will return a shape of a pice, e.g. [[0 0] [1 0] [1 1] [2 1]]. The construct [px py] is destructuring each element in that vector into the variables px and py to be used by the anonymous function body.

If you are totally new to Clojure this was probably too much to take in! My recommendation is therefor that you install a development environment like Light Table and start playing around with the language. Another nice way to get started with Clojure is by following this 5 min online tour.

The resulting list of the call to rotate-and-move-piece can be used to put a piece on a board, which is the topic of the next blog post!

Best regards,
Joakim Tengsrand


A short introduction to Clojure

Clojure was released in 2007 and is a dialect of Lisp which is an old langauge from the 50s that is based on lambda calculus. The real challange when it comes to learn Clojure is not to get used with the syntax but to switch from an imperative mindset to a functional one (if you come from the OO world like me).

Why should you care?

There are a lot of reasons why you should care about Clojure:

  • When you get used to it, Clojure code is very clean, readable and powerful!
  • Immutability is default which makes your life a lot easier and the code more stable with fewer bugs.
  • Functions are simpler and more composable than classes and is a better ground to build systems on, in my opinion! 
  • Clojure is homoiconic and uses macros to "extend" the language in a way that does not require an update of the compiler. Macros replaces techniques like AOP and code generation that is used in other languages to create internal DSLs.
  • Clojure runs on the JVM, CIL and in the web browser (Clojure script). Virtual machines decouples the software from the hardware which is a good thing!
  • You can basically represent everything with Clojure, from data files and build scripts to back-end and front-end code.
  • Clojure is designed with concurrency and parallell execution in mind which is not the case for most other languages.
I would be very surprised (and disappointed) if Clojure and similar languages are not main stream within the next five or ten years!

Best regards,
Joakim Tengstrand



Going Functional


Context Driven Developent was an experiment to see if object orientation could be improved by separating state and behavior. While working with CDD  I became more and more convinced that this separation was a good idea, but that intertwining data structures and functions into classes and objects was reducing composablity and code reuse. The information hiding we strive for in object orientation is introducing new problems and often misses its goal to preserve encapsulation, which often is broken when the context needs to be changed.

Some years ago I was at the JFokus conference and listened to Neal Ford  He was excited about a relatively new functional language called Clojure  When he showed us the syntax of the language, I thought "That can't be right!" because it differed too much from what I was used to (assembler, C, C++, Java and Scala).

A couple of years later I came across a few videos that I can highly recommend: Simple made easyThe value of values and Are we there yet? all by Rich Hickey. I immediately fell in love with the concepts presented in these videos and realised that this was a man who knew what he was talking about. It was particularly interesting that he was talking about foundational concepts, such as time and values, but which weren't a common subject for software engineering talks.

So now I became a little puzzled; how could the author of all these excellent ideas about software engineering have created a language that was so crappy? Then I realised that it might not be Clojure that's the problem, but rather my years of indoctrination with imperative programming and object orientation. I figured that now would be a good time to explore this theory by learning functional programming through Clojure.

I will soon begin a series of blog posts where you can follow my steps into the land of Clojure and the functional world!

Regards,
Joakim Tengstrand


Context Driven Development

Context Driven Development (CDD) summarizes in many ways the design ideas I have previously written about in this blog:
  • The Context Switcher pattern adds the concept context to OO. This pattern is now improved in CDD so that state and behaviour are fully separated.
  • The Chained Creator pattern is used in CDD to improve the way state is built.
  • CDD has been inspired by the State guard pattern. I regret that I called this a pattern even if it solves an important problem. The cleaner separation between state and behaviour in CDD is more refined and solves the same problem in a more elegant way!
I started to play around with these patterns to see if they could be improved and used together and found that they could. I also found that manually maintaining all the code needed to integrate the different parts was both difficult and tedious!

When I came up with the idea to let the code generator Laja solve the integration problems I realized that I had something! Read more about the CDD design paradigm here.