Recursion Is A Sexy Beast

I was chatting with my older brother last night about how to implement something in Clojure and he was talking about keeping track of state. We're making a tile game, and we need a way to change the list of unused tiles while the game is running.

The standard approach in the non-functional world is to have a variable in a class or (god forbid) a global variable that takes care of tracking the relevant pieces of state (in this case, the list of current tiles). This variable can then be referred to from whatever procedure needs to get a hold of it. However, functional programming is all about avoiding such state-based concepts, and to get there requires a new way of approaching problems.

A brief, four-month-long-or-so stint in the Erlang world brought me a more solid understanding of how to approach these problems. Not being too much of a functional programming buff, I suspect that this particular level of understanding is just skimming the top of the reorientation that functional style brings. Already I catch glimpses of higher-level thinking in Reginald Brathwaite's posts on homoiconic, and I'm hoping I'll slowly get to that level (I've still got about 15 years to catch up to that level ).

Anyway, for the purposes of posterity and my own understanding, a Better (tm) way to approach the problem of passing tile information around and keeping the data follows.

The tile data is basically a list of maps. Each map contains information about a given tile (such as its number and color). Thus, we can define the list of tiles as following (in Clojure):

(def tile-list '({ :number 5 :color "red" } { :number 4 :color "blue" }))

This defines a list of two tiles, one a red 5, and the other a blue 4, and puts them in the tile-list var.

An important thing to note is that Clojure and other functional languages typically provide an easy way to access the contents of a list in terms of the first element in the list and the `rest' of the list (a new list with everything but the first element). This allows us to look at the list elements one at a time while delegating the rest of the list to a recursive call to the same function.

Now, in an OO-style language, we would have some sort of Game object that keeps track of the current tile list for the current game. But we need to try to avoid this type of state-based programming. Instead, what we will do is create a play-game function that takes in a list of players and the initial tile list. This function will call itself recursively until someone wins, letting each player play at each point by calling a play-turn function that takes care of the semantics of taking tiles and such.

(defn play-game [tile-list player-list]
  (let [player (first player-list)
        [update-player updated-tiles] (play-turn player tile-list)]
    (play-game updated-tiles (concat (rest player-list) (updated-player)))))
 

Here play-game takes a tile list and a player list. The current player is defined as the first player in the list. The function then calls play-turn with the current player and the current tile list and expects it to return an updated player and an updated list of tiles. Then, play-game calls itself, passing itself the updated tile list and a new player list that has the updated current player at the end instead of the beginning. This means that the recursive call will run play-game with the next player, and ensures that players will continue to get called in the right order.

One last thing remains: as with any recursion (or, for that matter, any loop) we need a terminating condition that allows us to end the game. For now, let's define that terminating condition as a situation where the updated-player ends up with no tiles in their hand. One thing to note is that players are also tracked as maps. Their most important property is their list of tiles:

(def player-list '({ :tiles '() } { :tiles '() }))

So, we define our terminating condition as `whenever the updated player has a blank list of tiles for them'. If we were to go ahead and update our code for that:

(defn play-game [tile-list player-list]
  (let [player (first player-list)
        [update-tiles updated-player] (play-turn player tile-list)]
    (if (empty? (updated-player :tiles))
      (concat (updated-player) (rest player-list))
      (play-game updated-tiles (concat (rest player-list) (updated-player))))))

So here we introduce a new bit of semantics to play-game: when the game is over, it will return the final player list. The final tile list is assumed to be unimportant, though we could easily return that, too.

So here we have something that would probably be implemented by tracking state within a loop implemented instead with recursion. The recursion lets us keep things strictly stateless, with a function whose side-effects are reflected solely by its return values. To my eyes, this is wonderfully elegant.

Imagine also that you can technically then assemble tests that verify simply that a single turn play works (by calling play-turn) and then verify that play-game works once you're sure that play-turn will return the right values for a given state.

One thing that isn't immediately apparent above is what we can achieve with higher order functions. If play-game were to take as a third parameter a function that is used to play the turn, we gain two things:

1. We have a more general framework for playing any game whose turn involves a player that modifies a set of tiles and whose end is indicated by a player whose tiles list is empty.
2. We can now test play-game even more easily by giving it simple play-turn functions that induce the specific behaviors that we are looking to test.

In this case, if we wanted to test a turn whose play returned a winning player, we would have to be fairly knowledgeable about the internals of play-turn so as to devise a player and tile list that would definitely win (alternatively, we could override play-turn manually, but that's just dirty). If, instead, we took in play-turn as an externally provided function, we could actually pass in a play-turn function that just returned a player with an empty tile list to induce the winning condition. As the final code example, here's a play-game that takes in a play-turn function:

(defn play-game [tile-list player-list play-turn]
  (let [player (first player-list)
        [update-tiles updated-player] (play-turn player tile-list)]
    (if (empty? (updated-player :tiles))
      (concat '(updated-player) (rest player-list))
      (play-game updated-tiles
                 (concat (rest player-list) (updated-player))
                 play-turn))))

A tremendously simple change, all we did was take in a play-turn parameter and then make sure we pass it to the recursive call to play-game.

One thing to note in the above examples is that, though the syntax is basically Clojure, I didn't really bother writing it using the recurse form that actually optimizes the tail recursion. This is because I find this gets in the way of the point, which is how recursion is being used. Clojure, unlike other functional languages, doesn't automatically optimize tail recursion. This is due to limitations on the JVM where it runs. So, it introduces the `recur' form to allow you to optimize tail recursion.

Anyway, I went ahead and ignored that here so I could expose the concepts rather than the implementation details. The point of the post: recursion is a sexy beast.