Skaro is a simplistic implementation of the BSD "robots" game that I've ported to a number of different lisps over the past few days. I started out putting together a version in Chicken Scheme just to get a feel for that environment, and I followed it up with one in Clojure, one in Racket, and one in Emacs Lisp.

My goal here was to explore what's idiomatic in each language, so while some of the programs could have been cleaner or shorter with third-party libraries, I limited myself to what shipped with the runtime in each case. In any lisp you end up shaping the language to your domain, but you still end up having to read lots of public code that may not share your same values about what's readable and maintainable, so the way the language feels out of the box is very important. I made no attempt to consider performance. Tuning and optimization are nuanced, application-specific tasks, and I'd be doing these languages a disservice if I attempted to generalized based on my experiences here.

The game's logic is pretty simple: you move around on a board, pursued by enemies who move towards you on every turn. When two enemies collide, they leave behind a pile of smoking refuse towards which you can lure more enemies. Finally, you can teleport to a random location on the board. In the interests of simplicity, this implementation doesn't support diagonal movement, making it a bit less fun to play, but we'll ignore that.

Scheme

So while I've played with implementing Scheme before, it's been quite a while; plus even while implementing it I never really used it for much. So the Scheme implementation of the game is pretty straightforward; it's a mostly-imperative version that uses mutable SRFI-9 records for board state, storing enemies, piles, and the player position as (x . y) cons cells. For display it loops over all positions, set-car!ing a list of lists which is then printed.

My original implementation used SRFI-69 hash-tables instead of records. While they are a bit more flexible due to not having to declare your fields up-front, they are a lot more verbose since every access has to go through the hash-table-ref function. A major annoyance was that neither records or hash-tables have a convenient literal syntax for printing and reading, making debugging cumbersome. With hash-tables I was able to send everything through hash-table->alist before printing, but the lack of literal syntax was a big annoyance.

The main earlier advantage in this codebase of using hash tables instead of records was the hash-table-update! function which takes a hash table and a key, and then takes an updater function which is passed the old value and returns the new value. This higher-order update is a nice touch, and I wish it was more common. For instance, without it in this case we must map to get the moved state of the enemies, and then set the record's field using board-enemies-set!:

(define (move-enemies! board)
  (board-enemies-set! board (map (cut move-enemy (board-player board) <>)
                                 (board-enemies board))))

While it's not a problem in this program, this could easily be a race condition in a concurrent context. An updater function could ensure this operation could be atomic.

Despite being mostly imperative, there are still a few places where it uses features commonly thought of as functional. While it updates data structures in place, the data structures are passed around as arguments rather than defined as top-level globals, meaning that from the perspective of embedding this code in a wider system, it can be treated a bit like a black box; none of the mutation escapes local scope. Also it uses SRFI-26's cut macro in a few places to specialize a few parameters for higher-order function usage. Here a collision is defined as when a specific position is occupied by more than one entity:

(define (collision? position obstacles)
  (> (count (cut equal? position <>) obstacles) 1))

(define (get-collisions enemies obstacles)
  (filter (cut collision? <> obstacles) enemies))

In this case cut returns a function which has the given arguments fixed, using the <> identifier as a placeholder for un-fixed args. It's similar to Clojure's partial or Emacs Lisp's apply-partially but a bit more flexible since it supports args in any position. However, it's a macro rather than a function, so there's a bit of a composability trade-off. For simple count or filter functions it works great though.

Racket

Racket started as a dialect of Scheme but has evolved into its own language, or more accurately into a collection of tools for creating languages. As such it's superficially very similar to the Scheme version. It uses curry, which has some subtle differences from cut's partial application, but for the purposes of this codebase is equivalent.

The main difference with this version is its use of immutable hash tables. The board here is simply a hash table with 'width, 'height, 'player, 'enemies, and 'piles keys. Updates are all purely functional, and we get the nice higher-order updater function from hash-update which was described above. Racket has records (aka structs) too, which can be immutable, but for the purpose of contrast I chose to stick with its hashes since from what I could tell they are a lot more capable than the SRFI equivalents. Structs in Racket also have the option of not being opaque, which means they have a nice readable syntax when printed. This is not the default, but I hear this will change in the future.[1]

Speaking of data structures, Racket's uniform sequence-handling functions (similar to Clojure's) stand out as a major advantage over Scheme and some other lisps. Having a single abstraction that works across all collection data types makes a huge difference; there's just much less to keep in your head when you decide to use something other than a list, which means you're more likely to choose the right data structure for the job.

The best example of where the functional approach shines is the way the game logic is built. The play loop checks for various end-game states and then calls round to get the next board state. Then it draws the board and recurses with new player input:

(define (play board input)
  (cond [(killed? board)
         (display "You died.\n")]
        [(eq? input 'quit)
         (display "Bye.\n")]
        [(null? (hash-ref board 'enemies))
         (display "You won. Nice job.\n")]
        [else (let ([board (round board input)])
                (draw-board board)
                (play board (read)))]))

So what does round do then? It's a simple composition of three functions: move-player which takes the board and player input and returns a board with the new player position, move-enemies which updates enemy positions to move toward the player, and collisions, which checks for any space with two enemies on it and returns a board with those enemies replaced with a pile. Because each of these functions simply takes arguments and returns a new board state, the compose function can combine them into one function for the play loop to call.

(define round (compose collisions move-enemies move-player))

In this particular codebase all the state updates happen on the stack, but when you do need mutable references to immutable data structures, Racket provides boxes for that purpose which wrap immutable data structures and can enforce atomic updates. This is quite nice, but it's a bit more cumbersome than Clojure's swap! since it's up to the caller to provide old and new values; for some reason there's no function which simply takes an updater function like hash-update.

Clojure

In the interest of full disclosure, Clojure is the one on this list I'm most familiar with, and it's also the shortest of these implementations: 59 lines vs 80 lines for each of the others. Whether these two facts are related is left as an exercise to the reader. The fact that you can destructure maps (aka hash tables) in argument declarations contributes the most to the reduction in lines. Racket and Emacs Lisp have pattern matching which can have a similar effect, but having it built-in to function definitions means it's used ubiquitously, whereas you're only likely to pull out an explicit pattern match in longer functions where you want to use it for control flow as well.

(defn move-enemies [{:keys [enemies player] :as board}]
  (update-in board [:enemies] (partial map (partial move-enemy player))))

The other thing making Clojure maps a lot more convenient is the fact that they can be called just like functions. I must admit to being baffled by the fact that other lisps don't support this. Hash tables (of the immutable variety) in fact have more in common with the mathematical definition of functions than functions[2] themselves, yet you can't call them like functions; you're stuck going through the hash-table-ref accessor function.[3]

Apart from these things the flow of the Clojure version is pretty similar to the Racket implementation. There's the same play loop with the same round composition of the steps. In Clojure the loop is done through an explicit recur form rather than a TCO'd self-invocation, which is arguably less elegant, but the result is the same. The board drawing code uses vectors, which we couldn't do in Racket because Racket's vectors are fixed-length; they're suitable for producing one-time read-optimized copies of lists but not for building up piece-by-piece from scratch.

Another downside here is that while Clojure supports partial application with partial, it can only support fixing arguments on the left, vs Racket's curryr which works on the right and Scheme's cut which can place them anywhere. This problem doesn't arise in this codebase, but it's worth pointing out.

Emacs Lisp

The Emacs implementation has the least in common with the others. Purists, avert your eyes—Emacs Lisp is not what you would call a functional language. Whereas the other implementations pass around state as function arguments, this one calls setq in several places on top-level defvars. Since Emacs Lisp is a Lisp-2, higher-order functions are fairly awkward. There's only a single higher-order function here in a remove-if-not call. Partial application was recently added to Emacs, but given that you usually need a funcall to actually invoke the partially applied function, it's seldom used, and a lot of basic functional mechanisms are simply absent. [4]

That said, this implementation possesses some compelling advantages that aren't obvious at first glance. The UI of the other implementations consists of a rudimentary loop in which a line is read from standard in and a representation of the board is printed out, with old boards simply scrolling up off the terminal, but in Emacs the user is presented with a buffer in which the board is updated directly. There's a proper asynchronous event loop (with user-customizeable key bindings, no less). All commands are discoverable, and fully cross-referenced documentation is easy to add. These benefits simply come for free by virtue of targeting the Emacs runtime.

The use of buffer-local defvars mitigates the perils of using top-level defvars to a degree. It's still not as elegant as the functional approach, but it means that the top-level state doesn't prevent multiple copies of the game from interfering with each other; you can invoke M-x skaro twice and have two instances running side-by-side in the same process.

So What?

This short demo program obviously barely scratches the surface of the strengths of each individual language/runtime. If you need to do a lot of interfacing with C code, Chicken Scheme is the obvious choice—in those situations an imperative style is less likely to be a hindrance. Emacs Lisp has a strong lead when writing UIs for certain geeks despite its lack of functional features. When you are shooting for functional elegance, Clojure and Racket are both solid contenders. Clojure's access to the JVM libraries gives it an edge for certain projects, but Racket has the edge in places where the bulky, slow-to-start JVM runtime isn't welcome. (Racket executables can be as small as 700kb.) Racket has by far the strongest story for beginners due to its friendly culture and emphasis on documentation. In any case it's a great time to be a lisper.

Update: I added an OCaml implementation after writing this post. In general I found it turned out very similar to the Clojure version, except with records instead of maps. I did not find the type system particularly interesting for this particular codebase because I had already written the complete program four times over, so I knew exactly how it should work while I was writing it. The type system is most helpful at catching mistakes while you make unexpected changes to the codebase, which didn't happen on this toy 80-line project.

---

[1] While I was writing this, I started having second thoughts about my use of hash tables here. I originally shied away from records after having poor experiences with them in Clojure and Emacs Lisp, but none of those issues come into play here. I'm starting to think that hash tables in Racket are really only appropriate when you don't know the keys up-front, which makes some of their quirks (like implicit quoting in their literal syntax) significantly less infuriating.

[2] In fact, Scheme and Racket both refer to functions as procedures, presumably to emphasize the fact that they are not functions in the mathematical sense.

[3] The third-party rackjure library adds callable hash tables to Racket as well as a number of other creature comforts from Clojure.

[4] Again, third-party libraries (like dash.el) help a lot here.

« older | 2013-07-17T21:54:49Z | newer »

Technomancy is © 2004 – 2014 Phil Hagelberg, Soli Deo Gloria. [ All posts | Résumé | Projects | Colophon | ]