2048 in Lisp

August 7, 2014

In my CPSC 220 course, I gave my students the task of writing a clone of the popular 2048 game in C++. Since I was busy at the time, and the assignment was not exactly trivial, I didn't do the assignment myself first - which I nearly always do. The students did really well on the assignment.

After the semester ended, I decided to write my own version, but I decided to do it Common Lisp - a language I had played around with, but hadn't done anything big with. The program was super-fun to write and Common Lisp might be my new favorite language. I'll detail some of the cool things about Lisp which makes it fun to work with.

One thing I love about languages like Lisp is that everything is an expression - there are no statements. This is in contrast to C-based languages where the following is not possible:


int x = if (a < b) 1 else 2;

That's because if is not an expression, it's a statement. In contrast, the ternary operator is an expression, so we can do this:


int x = (a < b) ? 1 : 2;

In Lisp, everything is an expression, so everything can be grouped however you like:


(setf x (if (< a b) 1 2))

The prefix syntax takes some getting used to, but I've grown fond of the consistency of it. After coding in Lisp for a little while, I start trying to use it in every language.

Another great about Common Lisp is that it's really a multi-paradigm language. As the first functional language, Lisp sometimes gets cast as being primarily functional, but Common Lisp really is not. It supports procedural and object-oriented programming very well. Qt, like nearly all GUI toolkits, is object-oriented and my 2048 game is too. It subclasses a couple of Qt classes, overrides methods, and so on. Here's some code that declares a class for each cell:


; this class represents a single cell in the game
(defclass cell-widget ()
    ((value :accessor value))
    (:metaclass qt-class)
    (:qt-superclass "QWidget")
    (:override ("paintEvent" paint-event)))

That said, Lisp does support functional programming quite well too, which can be a very effective way to program. I didn't use many functional techniques in this program, but did for the board-widget class's "rotate" method. This is a little trick I used to avoid writing code to move the 2048 board in all 4 directions. Instead, I just wrote code to move the board left. When it comes time to move the board up, we can just rotate the board 90 degrees counter-clockwise, move it left, then move it 90 degrees clockwise (or 270 degrees counter-clockwise). This method rotates the board (a 2D list) 90 degrees:


; this function rotates the board by 90 degrees counter-clockwise
(defmethod rotate ((this board-widget))
    (setf (board this) (reverse (apply #'mapcar #'list (board this)))))

This is a computation composed of several functions. "apply" takes a function and a list, and applies that function to each element. We pass the function "mapcar" which in turn takes a function as a parameter, the "list" function and two lists. It the combines elements from both lists according to the function. "list" takes a bunch of arguments and creates a list of them. So when we put this together, "mapcar" is applied with "list" to each row of the board, and it forms columns (because list just joins its arguments). Then the reverse function reverses the order of the columns which works out to rotate the grid.

The real killer feature of Lisp is macros. These are functions that take in Lisp code and produce different Lisp code as output. C and C++ have macros, but the language for producing them is extremely restricted. You can only do the simplest text substitutions. Lisp macros have the full Lisp programming language behind them.

I created a macro for looping through the board. Rather than write:


(loop for row from 0 to 3 do
    (loop for col from 0 to 3 do
        ; some code))

All over the place, I wanted a more succinct structure:


(board-loop (row 0 3) (col 0 3) do
    ; something)

This isn't a huge difference, but when it appears dozens of times throughout your code, it adds up. Adding custom control structures is not really feasible in most languages, but in Lisp it is easy:


(defmacro board-loop ((row a b) (col c d) form &body body)
    `(loop for row from ,a to ,b ,form
        (loop for col from ,c to ,d ,form
            (progn ,@body))))

This basically takes the short form and generates the long form automatically for us. Macros are actually so powerful that most Lisp control structures (including "loop" itself) are actually macros.

The full code (270 lines) is on github. I tried to keep the style as authentic as I could (also, I'm not terribly good at this game):