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.
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 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
.
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.
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 defvar
s. 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 defvar
s 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.
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.
๛