Sunday, February 26, 2012

Client Communication

I'll be posting an incremental StrifeBarge update later this week, but I wanted to think aloud about a particular piece of it first. My last article concluded with a paragraph which included the action-item

figure out a good way to periodically notify clients about new developments in the game

Don't worry if you missed it, that post may just have shatter the "most words" record for Langnostic, so it's perfectly understandable if you just read up the point where I begin talking about the code and then went to do something else. I quote it above because that quote just about sets the stage for this.

It turns out that periodic notifications from the server are still a pain in the ass. Your options, as of almost-March 2012 are Websockets, Comet (aka Long Poll, aka (God help me) "Reverse Ajax"), Ajax Polling and HTML5 Server-Sent-Events.

Websockets

seem to have gotten the most press, but have so far failed to materialize. If you're familiar with network programming[1], this will be intuitive to you. Instead of relying on the standard request/response architecture of the web, a client and server do a handshake and establish something like a traditional, secure, bi-directional socket through which they can send each other data. In theory, that completely eliminates the need for any of the other methods. In practice, I'm not convinced.

The big problem is that the word "secure" in the previous sentence should have been in quotes, because that's been a big point of contention among implementations. Websockets seem to be, right now, where JavaScript was circa 2002. The various clients are all doing crazy or semi-crazy things their own way, which means that a server either has to make peace with the fact that a large number of visitors won't be using the tool correctly, or it has to try to disambiguate between individual versions of various browsers and provide a tailored protocol for most of them. Fun times, huh?

The first place I heard of this concept was way back when Joe Armstrong posted a[2] Websocket example using YAWS, outright proclaiming the death of all the other options. I'm going to have to respectfully disagree, three years later. Of the big language implementations out there right now, only node.js has a decent solution for Websocket use. Essentially, they have a server and client framework that simplifies the interface, and provides automatic fallback behavior for clients that speak an older version of the protocol, or don't speak it at all, or speak it but disable it by default. Worryingly, the ultimate fall-through is a Flash applet that establishes that same socket connection, which means some people won't be getting this either, but at least it works most of the time. No one else seems to have thought it out quite as far[3].

In any case, this is a decent choice where you need true bi-directional communication, but it seems like implementing it here would cause me some unnecessary headaches, and I don't think turn-based games strictly require it.

Comet

This is just a bending of the standard request/response protocol that the web is built out of. Usually, the client sends a request and the server responds to it right away, either with the requested information or an error code. "Comet" is a name for the situation where the server instead sits on the request until there's something new to send over, at which point it responds and the client immediately sends a new request that the server will respond to at its leisure. That's actually a pretty good option, except that I happen to be using a server[4] that spawns a new thread per connection. In a Comet situation, this gets out of hand, because you essentially have a thread running constantly per user[5]. If I were running a single threaded server, this may be a better option, but as it stands, it seems like I'd have to do a lot more work for what I was hoping would be a simple project. So, no dice here either, sadly.

Ajax Polling

I'm reasonably sure everyone who cares knows what this is by now. You have a specific page built to send out updates, and each client has code that looks something like

setInterval(5000, "updateFoo()");

function updateFoo(){
    $.get("/update-url", function (data) {
              $("#result").html(data);
          });
}

The end result being that you can fake bi-directional communication by just having the client poke the server repeatedly and integrate data from the responses as it goes. The only issue with this approach is the overhead; go ahead and take a look at this breakdown of the process. Calling complexity aside[6], by my count, a request ends up transferring twice and a bit the obvious amount of data involved[7]. Some issues also arise from naive use of the method, which I'll get into with the final option I considered.

Server-Sent-Events

are basically formalized, lightweight Ajax polling with a few small benefits. The bad part is that you're still basically instructing the client to poke the server at a given interval, but the response is structured differently. Something like

data: Foo bar baz

with options, instead of the giant XML response. The options include multi-lining the message[8]

data: Foo bar
data: baz

providing each message with an identifier for synchronization purposes

id: 1
data: Foo bar
data: baz

letting the server specify when the next ping should happen

retry: 10000
data: Stop bothering me

and specifying event types

event: question
data: How I parse HTML with regular expression
event: deathThreat
data: Fuck off and die

Putting it all together, this communication method seems to be passable for writing turn-based web games.

id: 2
event: join
data: Bazmonkey
event: shot
id: 3
data: { "player" : "Bazmonkey", "result": "miss", "x" : "10", "y" : "32" }
event: turn
id: 4
data: You
event: shot
id: 5
data: { "player" : "You", "result": "hit", "x" : "23", "y" : "14" }
event: turn
id: 6
data: Bazmonkey

The id message is automatically used by the client to sync messages[9], the event message can be used to set up different client behavior based on what kind of event happened on the server, and the retry message gives the server a way to tap out if too many users are pile-driving it at the moment. It still doesn't "solve" the fundamental asymmetry between client and server in HTTP, and it will never be as responsive as an actual socket connection, but it seems to be a Good Enough™ solution that address most of the issues I'd be thinking about if I tried to implement StrifeBarge using Ajax polling.

In addition to working on StrifeBarge for the next little while, I'll also be poking semi-seriously at node.js[10], so I may end up using websockets for something, but SSE wins it for the time being.


Footnotes

1 - [back] - As opposed to just web-programming.

2 - [back] - Since thoroughly outdated.

3 - [back] - Though, as usual, someone has taken it upon themselves to clone relevant bits in Common Lisp, so there.

4 - [back] - Hunchentoot, at the moment.

5 - [back] - Typically, each thread lives just long enough to send a response, but since we're sleeping on each Comet request, they pile up fast.

6 - [back] - Which has largely been smoothed out by modern JS frameworks.

7 - [back] - Since the raw response contains that data twice, and HTTP headers are sent each way.

8 - [back] - Though I can't find a line limit anywhere in the spec, so that seems pointless unless you plan to manually format text you're sending in this fashion.

9 - [back] - So if for some reason your connection blows, you won't miss the fact that your opponent fired, or end up getting 27 separate notifications of the same event.

10 - [back] - Thanks in part to some links from a friend from the Toronto Lisp Group, if you'll believe that.

Monday, February 20, 2012

StrifeBarge - Turn Based Web-games in Common Lisp

I've been in kind of a blah mood lately. To the point that I didn't really feel like struggling for huge new insights at all this weekend. Hopefully, that passes, because I really don't want to get mired in mediocrity any time soon. Anyway, you didn't come here to hear me being a whiny little bitch, so let me share the small insights I have had the energy to pursue.

First off, quickproject is fairly useful. It's missing some stuff I obsess over (I'm specifically thinking license boilerplate generators and an automatic git init+.gitignore call), and it does one or two small details in a way I don't like (mainly to do with the README file), but it still beats writing the package and asd file by hand. Next time I don't particularly feel like hunting down large insights, I'll probably fork this little utility and add the stuff I want. Between this and quicklisp, it's about high time I get a reasonably-sized pile of money together and send it to Zach, because that fucker earned it if anyone has.

With that out of the way, here's what I ended up using a chunk of my weekend to do. Unlike my previous piece on Hunchentoot development, this is meant to be less a lesson and more of an open code review by the invisible peanut gallery. Pot shots and patches are welcome. I've had this idea of putting together a turn-based web-game for a while now, and that's the sort of thing that doesn't really require any kind of deep learning. Just some straightforward thinking from first principles, and some light iteration. So, I whipped out quickproject and whipped up an 0.01. Lets start with the asd and package

;;;; strifebarge.asd

(asdf:defsystem #:strifebarge
  :serial t
  :depends-on (#:hunchentoot
               #:cl-who
               #:ironclad
               #:parenscript
               #:cl-css
               #:swank
               #:clsql)
  :components ((:file "package")
               (:file "util")
               (:file "model") (:file "space") (:file "board") (:file "game")
               (:file "strifebarge")))
;;;; package.lisp

(defpackage #:strifebarge
  (:use #:cl #:cl-who #:clsql #:hunchentoot #:parenscript)
  (:import-from #:swank #:find-definition-for-thing)
  (:import-from #:ironclad 
                #:encrypt-in-place #:decrypt-in-place #:make-cipher #:digest-sequence 
                #:octets-to-integer #:integer-to-octets
                #:ascii-string-to-byte-array #:byte-array-to-hex-string)
  (:shadow #:get-time))

(in-package #:strifebarge)

(defparameter *web-server* (start (make-instance 'hunchentoot:easy-acceptor :port 5050)))

And actually, now that I look at them, those clearly include things I haven't used, and may not for a while yet. I'll keep them around for the moment, but I'm leaving a mental note here that I really don't need anything past :hunchentoot and :cl-who just yet.

By the way, a significant chunk of this was quickproject-generated. I added the :import-from clauses, and some of the :file declarations, but that's pretty much it. The rest of it was created by running quickproject:make-project with the appropriate inputs. Moving right along, lets start with the meat of this thing

;;;; strifebarge.lisp

(in-package #:strifebarge)

(defparameter *game* nil)

(define-easy-handler (index :uri "/") ()
  (let ((players (list (make-player 'carrier 'cruiser 'destroyer)
                       (make-player 'carrier 'cruiser 'destroyer))))
    (echo (apply #'make-game players) (car players))))

(define-easy-handler (new-game :uri "/new-game") (player-count)
  (let* ((p-count (if player-count (parse-integer player-count) 2)) 
         (players (loop for i from 1 to p-count
                        collect (make-player 'carrier 'cruiser 'destroyer))))
    (setf *game* (apply #'make-game players))
    (redirect "/join-game")))

(define-easy-handler (join-game :uri "/join-game") ()
  (assert (and (not (null (waiting-for *game*)))
               (null (session-value :player))))
  (setf (session-value :player) (pop (waiting-for *game*)))
  (redirect "/show-game"))

(define-easy-handler (show-game :uri "/show-game") ()
  (assert (not (null (session-value :player))))
  (echo *game* (session-value :player)))

(define-easy-handler (quit-game :uri "/quit-game") ()
  (assert (not (null (session-value :player))))
  (push (waiting-for *game*) (session-value :player))
  (setf (session-value :player) nil)
  "You have quit the game")

(define-easy-handler (turn :uri "/turn") (x y)
  (assert (and (eq (car (turn-stack *game*)) (session-value :player))
               (stringp x) (stringp y)))
  (advance-turn *game*)
  (fire *game* (session-value :player) (parse-integer x) (parse-integer y))
  (redirect "/show-game"))

strifebarge contains all the HTTP handlers this project uses. I've implemented a test handler (index), which does nothing now that I'm past working up the echo methods. It's also possible to create a new-game, join or quit a game, show the current state of a game board, and take a turn[1].

I did mention that this was an 0.01, so the intense lack of usability should come as no surprise to you. Firstly, there is only one *game*, stored in the global variable of the same name. For the moment, if anyone starts a new game, the old one gets clobbered. Secondly, note that turn order is maintained through an error mechanism. In the final game, those should actually display a little note along the lines of "It's not your turn yet", rather than vomiting a stack dump[2].

Lets take a closer look at how the turn mechanism is approached. It actually starts at the join-game handler.

(define-easy-handler (join-game :uri "/join-game") ()
  (assert (and (not (null (waiting-for *game*)))
               (null (session-value :player))))
  (setf (session-value :player) (pop (waiting-for *game*)))
  (redirect "/show-game"))

The assert here makes sure of two things:

  • The game is waiting for at least one more player to join
  • You have not already joined a game

As noted, if an assert statement fails, you get an error. If they both succeed, you are assigned a player record, stored in your session, to track who you are for the duration of the game[3]. This is relevant in two ways. Firstly, the board is displayed differently based on which player is looking; we'll see more about this later, the only hint you get from this file is the call to echo in show-game.

(define-easy-handler (show-game :uri "/show-game") ()
  (assert (not (null (session-value :player))))
  (echo *game* (session-value :player)))

and secondly the player record in your session determines when it's your turn.

(define-easy-handler (turn :uri "/turn") (x y)
  (assert (and (eq (car (turn-stack *game*)) (session-value :player))
               (stringp x) (stringp y)))
  (advance-turn *game*)
  (fire *game* (session-value :player) (parse-integer x) (parse-integer y))
  (redirect "/show-game"))

Notice both that the assert in this handler makes sure that the top player on the turn-stack is the same as the player in your session, and that part of the handler body calls the method advance-turn on the current game before calling fire and re-displaying the game board. That segues nicely into

;;;; game.lisp

(in-package :strifebarge)

;;;;;;;;;;;;;;;;;;;; game creation and setup
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun make-player (&rest ship-types)
  (let ((p (make-instance 'player)))
    (setf (ships p)
          (mapcar (lambda (s) (make-instance s :player p)) ship-types))
    p))

(defun make-game (&rest players)
  (let ((board (make-board (mapcan #'ships players))))
    (make-instance 'game :board board 
                         :players players 
                         :waiting-for players 
                         :turn-stack players)))

;;;;;;;;;;;;;;;;;;;; display
;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defmethod echo ((g game) (p player))
  (with-html-output-to-string (*standard-output* nil :prologue t :indent t)
    (:html (:body (echo (board g) p)))))

;;;;;;;;;;;;;;;;;;;; actions
;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defmethod advance-turn ((g game))
  (if (cdr (turn-stack g))
      (pop (turn-stack g))
      (setf (turn-stack g) (players g))))

(defmethod fire ((g game) (p player) x y)
  (let ((result (make-instance 
                 (if (empty-space-at? (board g) x y) 'miss 'hit)
                 :player p :x x :y y)))
    (push result (history g))
    (setf (move (space-at (board g) x y)) result)
    result))

The creation and setup functions give you a pretty good idea of how players and games are represented. For now, a player is just an object that has one or more ships[4]. A game is a slightly more complex construct; it has a board as well as a collection of players, a turn-stack and list of players that haven't shown up yet[5]. We'll discuss the board a bit later, lets get into how players and the game function. Um. I mean: function.

For the moment, echoing a game just passes the buck to echoing a board for the current player. There will eventually be things other than the board, such as various stat displays, and a turn counter. The interesting stuff here is advance-turn and fire.

(defmethod advance-turn ((g game))
  (if (cdr (turn-stack g))
      (pop (turn-stack g))
      (setf (turn-stack g) (players g))))

After reading this, it should be perfectly obvious what the turn stack is, and how it enforces actions. It just starts off as a copy of the list of players participating in the game, and we pop the top record off each time a turn is passed. Once we get down to the last player in the stack, we copy out the list of players instead of poping again. That keeps the game circular.

(defmethod fire ((g game) (p player) x y)
  (let ((result (make-instance 
                 (if (empty-space-at? (board g) x y) 'miss 'hit)
                 :player p :x x :y y)))
    (push result (history g))
    (setf (move (space-at (board g) x y)) result)
    result))

fire makes a new hit or miss marker[6] and attaches it to the space ... I mean, space... at the given coordinates. It also records the move in the games history.

Again, 0.01, so neither of these functions actually deal damage to a given ship, or end the game if a player has been eliminated. The turn sequence just goes on until all the players stop playing. Note one very intentional effect of this architecture though; the game supports n players by default. It's not a two-player affair, but rather, as many as you like[7], as hinted at by the new-game handler[8].

Before we deal with the space and board files, we should probably take a look at the model. There are some non-obvious interactions, and I want to lay them bare before getting into how I put together the actual front end and hit tracking.

;;;; model.lisp

(in-package :strifebarge)

(defclass ship ()
  ((space-count :reader space-count :initarg :space-count)
   (player :reader player :initarg :player)
   (damage :accessor damage :initform 0)
   (coords :accessor coords :initarg :coords)
   (direction :accessor direction :initarg :direction)))

(defclass carrier (ship) ((space-count :initform 5)))
(defclass cruiser (ship) ((space-count :initform 3)))
(defclass destroyer (ship) ((space-count :initform 2)))

(defclass move ()
  ((player :reader player :initarg :player)
   (x :reader x :initarg :x)
   (y :reader y :initarg :y)))

(defclass hit (move) ())
(defclass miss (move) ())

(defclass player ()
  ((score :accessor score :initform 0)
   (sunken :accessor sunken :initarg :sunken)
   (ships :accessor ships :initarg :ships)))

(defclass board-space ()
  ((x :reader x :initarg :x)
   (y :reader y :initarg :y)
   (contents :accessor contents :initform nil)
   (move :accessor move :initform nil)))

(defclass board ()
  ((width :reader width :initarg :width)
   (height :reader height :initarg :height)
   (spaces :accessor spaces :initarg :spaces)))

(defclass game ()
  ((board :accessor board :initarg :board)
   (players :accessor players :initarg :players)
   (waiting-for :accessor waiting-for :initarg :waiting-for)
   (turn-stack :accessor turn-stack :initarg :turn-stack)
   (history :accessor history :initform nil)))

You probably inferred the shape of the game, player and move classes based on stuff I've already shown you. The reason that move, hit and miss are implemented like this is twofold. First, it makes echoing simple[9], and second, it will eventually let me do clever things like color-coding shot markers per player.

The new stuff here is the ship and associated classes. I've only implemented 3; a 5-space, a 3-space and a 2-space vessel, each of which just inherits from ship and sets its space-count. As you can see, they're already prepared to take damage, in addition to tracking their position, orientation and owner. Now that I really think about it, I'm not sure why I have a ship track its coordinates after being placed; it becomes completely irrelevant to the ship at that point. The space-count matters[10], but it makes no difference what specific spaces a given ship occupies and won't for a rather long while. That's definitely something I'll be removing after I finish this write-up.

The other new bits, which may help understand the rest of the files so I'll dwell on them a moment, are the board and space classes.

(defclass board-space ()
  ((x :reader x :initarg :x)
   (y :reader y :initarg :y)
   (contents :accessor contents :initform nil)
   (move :accessor move :initform nil)))

A board-space has an x and y coordinate, as well as initially empty contents and move slots. You already saw what move does; when a space is fired upon, it's marked as either a hit or a miss using a shot flag[11]. The contents are exactly what you'd expect; each occupied space carries a pointer to the ship it contains.

(defclass board ()
  ((width :reader width :initarg :width)
   (height :reader height :initarg :height)
   (spaces :accessor spaces :initarg :spaces)))

Last one, and then we can round out the methods. A board caches its width and height, as well as keeping the full spaces grid. What a grid looks like is non-obvious from just the class declaration, so this is actually the perfect segue into

;;;; board.lisp

(in-package :strifebarge)

;;;;;;;;;;;;;;;;;;;; board creation
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun empty-grid (width height)
  (loop for y from 0 to height
        collect (loop for x from 0 to width collect (make-space x y))))

(defun empty-board (width height)
  (make-instance 'board 
                 :spaces (empty-grid width height)
                 :width width
                 :height height))

;;;;;;;;;;;;;;;;;;;; board setup
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defmethod space-at ((b board) x y) (nth x (nth y (spaces b))))

(defmethod assign-ship-spaces ((s ship) direction x y)
  (loop for i from 0 to (- (space-count s) 1)
        if (eq :vertical direction)
          collect (cons x (+ i y))
        else
          collect (cons (+ i x) y)))

(defmethod position-ship ((s ship) (b board))
  (let* ((x (random (- (width b) (space-count s))))
         (y (random (- (height b) (space-count s))))
         (direction (pick '(:vertical :horizontal)))
         (ship-spaces (assign-ship-spaces s direction x y)))
    (if (every (lambda (p) (empty-space-at? b (car p) (cdr p))) ship-spaces)
        (progn 
          (setf (coords s) ship-spaces
                (direction s) direction)
          (loop for (x . y) in ship-spaces
                do (setf (contents (space-at b x y)) s)))
        (position-ship s b))))

(defun make-board (list-of-ships)
  (let* ((width (+ 5 (* 2 (length list-of-ships))))
         (height (+ 5 (* 2 (length list-of-ships))))
         (board (empty-board width height)))
    (dolist (s list-of-ships) (position-ship s board))
    board))

;;;;;;;;;;;;;;;;;;;; display
;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defmethod echo ((b board) (p player))
  (with-html-output (*standard-output* nil :indent t)
    (:table :id "game-board"
            (mapc (lambda (row) 
                    (htm (:tr (mapc (lambda (s) (echo s p)) row)))) 
                  (spaces b)))))

As you can see, that's the chunkiest single file in the package, and that's because it implements creating a board as well as placing ships[12]. Firstly, looking at empty-board and space-at should clear up what a board looks like. It's a list of lists of spaces[13].

The ship placement methods are worth a slightly closer look

(defmethod assign-ship-spaces ((s ship) direction x y)
  (loop for i from 0 to (- (space-count s) 1)
        if (eq :vertical direction)
          collect (cons x (+ i y))
        else
          collect (cons (+ i x) y)))

(defmethod position-ship ((s ship) (b board))
  (let* ((x (random (- (width b) (space-count s))))
         (y (random (- (height b) (space-count s))))
         (direction (pick '(:vertical :horizontal)))
         (ship-spaces (assign-ship-spaces s direction x y)))
    (if (every (lambda (p) (empty-space-at? b (car p) (cdr p))) ship-spaces)
        (progn 
          (setf (coords s) ship-spaces
                (direction s) direction)
          (loop for (space-x . space-y) in ship-spaces
                do (setf (contents (space-at b space-x space-y)) s)))
        (position-ship s b))))

The position-ship method takes a ship and a board and positions the ship on the board. It does this by randomly picking a starting x/y coordinate and direction. Those are fed into assign-ship-spaces which returns a list of (x . y) corresponding to the spaces this ship will take up[14]. Once we have that, we check whether all of the generated spaces are currently empty, and if they aren't[15], we try again. If the given spaces are clear, we[16] store those spaces in the ships' coords and the direction in direction[17] before assigning ship pointers to the appropriate spaces on the board. Tadaah! That was the most complicated piece of this game.

make-board is fairly self-explanatory; it takes a list of ships and determines width/height of the map based on how many there are, then places each ship and returns the resulting board instance. The boards' echo method should make perfect sense now that you've seen what a board is; in order to echo one, we start an HTML table and map echo over each space in each row of the board. Before we look at space, lets just zoom in on one part of position-ship. Specifically, the part that reads

...
(direction (pick '(:vertical :horizontal)))
...

pick isn't actually a Lisp primitive, but it's fairly simple to define. Here's

;;;; util.lisp

(in-package :strifebarge)

(defun pick (a-list)
  "Randomly selects an element from the given list with equal probability."
  (nth (random (length a-list)) a-list))

(defun range (a b)
  "Returns a list of numbers starting with a and ending with b inclusive."
  (loop for i from a to b collect i))

Both are fairly self-explanatory. range is a second utility function I defined for an earlier iteration of the codebase, but ended up refactoring out all calls to it. I'm still keeping it, probably more out of superstition than anything else. In fact, never mind, I'm adding one to the list of things I need to trim once I finish writing this.

Ok, all that out of the way, lets finally take a look at

;;;; space.lisp

(in-package :strifebarge)

;;;;;;;;;;;;;;;;;;;; creation and setup
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun make-space (x y) 
  (make-instance 'board-space :x x :y y))

;;;;;;;;;;;;;;;;;;;; predicates
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defmethod empty-space? ((s board-space)) (null (contents s)))
(defmethod empty-space-at? ((b board) x y) (null (contents (space-at b x y))))

;;;;;;;;;;;;;;;;;;;; display
;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defmethod echo ((s board-space) (p player))
  (with-html-output (*standard-output* nil :indent t)
    (:td (cond ((move s) (echo (move s) p))
               ((and (contents s) (eq (player (contents s)) p)) (str "#"))
               (t (htm (:a :href (format nil "/turn?x=~a&y=~a" (x s) (y s)) "~")))))))

(defmethod echo ((m hit) (p player))
  (with-html-output (*standard-output* nil :indent t)
    "X"))

(defmethod echo ((m miss) (p player))
  (with-html-output (*standard-output* nil :indent t)
    "O"))

I told you the hard part concluded with make-board earlier. make-space is a self-explanatory shortcut to using the raw make-instance[18]. The empty predicates are shorthand for checking whether a given space (or a space given by specified coordinates on a board) is empty.

The last mystery is solved with the echo methods here. A space is echoed as a td tag, but its contents depends on certain properties of the space. First, if this space has been fired upon, we echo its shot marker[19]. Second, if the space hasn't been fired upon, but contains a ship belonging to the current player, we echo a marker for a ship[20]. Finally, if all else fails, we output a shot link with the coordinates of the current space, and wrap it around "~" which looks sufficiently wave-like for this stage of development.

As an architectural aside, that last one is why we needed the more complex representation of spaces. I initially toyed with just having a simple 2-dimensional list of '([move] [contents]), but that would have been both more difficult to abstract from other parts of the program[21], and it would have complicated emitting the coordinate link to /turn.

So there, putting it all together, we've got a very simple[22] implementation of an HTTP-using multiplayer, turn-based, guessing/strategy game in Common Lisp with a grand total of 220 lines including comments[23]. Hopefully this step-by step has been useful to someone. If nothing else, it helped me figure out where I'm going next in a much more concrete way. I need to trim a few things, add some re-direction constructs to use in place of the assertions, get cracking on a sprite-set[24], and figure out a good way to periodically notify clients about new developments in the game[25]. That's it for the short term, once that's all done, I'll do another one of these little reflection/code-review articles.

If you feel like poking around the codebase for your own education, or for the purposes of patching, check out the github repo. I haven't actually decided what license I'm using yet, so maybe hold off on hacking on it until I get that cleared up.[26]


Footnotes

1 - [back] - Which fires a single shot on the specified space and passes the turn.

2 - [back] - Which is what failed assertions do.

3 - [back] - Incidentally, this is why I wanted to include :ironclad right out of the gate; as far as I know, Hunchentoot sessions aren't particularly spoof-resistant, so in a real game I'd want better player verification than this approach gives me. I'm assuming the final solution will take the form of IP and user-agent recording combined with a Diffie-Hellman handshake.

4 - [back] - It also has some other tracking slots, like score and how many ships they sank, but those don't get tracked quite yet.

5 - [back] - That'd be waiting-for.

6 - [back] - Depending on whether the space being fired into is empty or not, obviously.

7 - [back] - Though I probably should have the option of limiting the count through a config variable somewhere in the final.

8 - [back] - Which actually takes player-count as an input, and defaults to 2.

9 - [back] - As you'll see when we get to the space file.

10 - [back] - Or rather, will matter, once I start tracking ship damage.

11 - [back] - An instance of the move class.

12 - [back] - Which is only non-trivial because we're breaking tradition by placing all ships on the same board, necessitating both random placing and preventing ship collisions.

13 - [back] - Subject to change to arrays in the final, but I can't be bothered to optimize at this point. On the upside, defining space-at explicitly means that when I change the representation of a board, I'll only have to change that single function and the empty- functions rather than tracking down every call to nth.

14 - [back] - Taking into account this particular ships' length.

15 - [back] - Which would signal a collision with another ship.

16 - [back] - Uselessly

17 - [back] - The direction will actually be useful sooner rather than later; it will help figure out how to render a ship once I start using sprites instead of the plain grid display going on currently.

18 - [back] - This technique both saves some typing, and lets you be flexible about re-defining the representation of the object in question later. In this case, I could completely change how the game thinks of board-spaces, and all I'd really need to change is the code in this file.

19 - [back] - Currently, a hit is represented as "X" and a miss is "O".

20 - [back] - The current representation is "#" for all ships, this will eventually get complicated enough to call for another echo method specializing on ship, but that can wait until I actually get some graphics up ins.

21 - [back] - In the sense that changing a particular spaces' move or contents would have necessitated at least a little grubbing around with car and cdr.

22 - [back] - And still unplayable.

23 - [back] - And that's even before the cuts trims I said I'd make.

24 - [back] - Or try to find one.

25 - [back] - My intuition tells me that long-poll/comet won't be a very good fit for Hunchentoot's view of the world, so I'll need to figure something out.

26 - [back] - It'll definitely be an open one, I'm just not sure which, though currently leaning towards the AGPL since the point of this is a hobby-horse/educational project. In other words, definitely hold off if you're a GNU hater.

Thursday, February 16, 2012

Self Titled

I read a question on SO the other day that asks "Why choose Lisp for a project?". It was closed with an almost surprisingly swift consensus, but not before three answers were thrown in (and one accepted). And that's pretty good because, as far as I'm concerned, it's the wrong question. "Why choose a language for a project?" is closely related to a second question, which I'll let Peter Norvig describe the shape of:

I guess the way I look at it is; the best language to use is the one that you and your friends are most productive with. It just turned out that when Google was started, the four programmers that were there first were all C++ programmers, and they were very effective with that, and they kept going with it. -Peter Norvig, Ask Me Anything

I agree with his sentiments here. The language you should use when you're working on a professional project[1] is one that your team knows and already thinks in. It would be a mistake for me, today, to start something serious up at the office using Smalltalk because I don't think in it naturally yet. Norvig's response to "What language should I choose?" begs a second question though, because if the best language is one you're already familiar with, then you need to ask

When Should I Choose a Language?

Ideally (from the perspective of making the best choice possible), you'd choose it as late as possible because, even though it's fairly difficult to explain this to non-computer people, different languages do have different trade-offs. So you either want to pick your language at the point where you have the most possible information about what the shape of your project is going to be, or you want to pick a language that's flexible enough to be used for pretty much anything.

The trouble is, if you subscribe to the Norvig Awesome Language Theory, you come to the conclusion that either

  • your choice has been made for you quite a while ago, or
  • you should make your choice before even getting a team together (let alone deciding what you want to do)

The first option happens if you're an x programmer, or if all your friends are x programmers[2]. That's not particularly interesting to me, given how I think about development, but I may come back to it later.

The second option is hard because, I'll lay this down as an axiom, at no point in a project will you know less about what shape the output will take than you do before you've assembled a team. That situation screams "Lisp" at me, although I guess any language with sufficient ease of DSL creation would do. Perhaps it screams other things to other people; I knew a guy at a former place who said

As far as I'm concerned, unless there's a really good reason not to, you should just use PHP for web development.

I'm not poking fun of the guy either; his reasoning is that since the standard LAMP stack is in place at half a scrillion servers around the world and counting, any bugs likely to bite over the course of a development cycle have already been found. That's the same principle as Raymond's statement of Linus' Law. The trouble is that it leaves you faffing about with PHP even when the entire team knows a more powerful, more abstract language like Python or Ruby.

In fact, applied globally, this principle would have every developer on earth using some combination of Java, C, C++ and/or C#, because odds are that every developer could scrape up ten buddies that are at least marginally proficient with those. There's a tension between "powerful languages" and "popular languages", because each brings benefits to the table. Powerful means you'll be more likely to crack through whatever problem you run into, while Popular means that a lot of problems have been pre-solved for you. Power means you'll be able to move mountains with small teams, Popularity means you'll be able to get big teams together reliably. That begs a third question, because if you've got a specific project in mind, you have to ask

What kind of Project will this Be?

Are you trying to solve problems for which there are no existing solutions (or for which no satisfactory solutions exist) or are you looking to create incremental improvements to existing solutions? Do you want the ability to scale to hundreds of developers under your roof, or do you want a team of 5, 10 at the outside? Do you know specifically what you want, or is the spec going to change dramatically as you move on? Do you already have a team put together, or have you resigned yourself to the hell of Hiring Humans? You will want different languages depending on your answers to these questions, regardless of what language you currently happen to know. But that begs a fourth question, because if the objectively right thing to do on a project is use a language you don't know, you have to ask

When Should I Switch Languages?

Graham says that "[a]fter a certain age, programmers rarely switch languages voluntarily". Which is perfectly understandable, because in light of NALT, it's really only reasonable to switch once you and all your friends are more effective with a new language than with your current language, and that takes the sort of off-hours dedication that I'm already having trouble finding at ~27[3]. The "why" of it, pragmatically, is also hidden in the statement (although it's a different opinion from Graham than it is from Norvig). The Graham Awesome Language Theory states that there is a pyramid of languages, and you should switch when you realize that there's a higher one than what you already know. That fails to take the team dynamic into account though. If "switch" means "start practising the higher language on your own time", well, sure, sounds reasonable. But if you've got a team of 10[4], is it not a mistake to kneecap short-term progress and set yourself up for pain later[5] in exchange for potential gains at the language level?

Norvig says (in effect): switch with your friends. Which may explain why people switch away from Lisp, even if Graham is right about the shape of the language pyramid. What good is knowing the superior language, if no other human you know speaks it?

When Should I Switch Languages?

A couple of days ago, my dad called me up. Apparently, he got a web design offer from a friend of his, but the requirements weren't exactly his field. What they meant was "Web UI Developer", and would I be interested? I asked for the specifics; it's a big company, I'd be working for a billing department somewhere, the pay was excellent, and the skill/experience requirements were

  • Javascript
  • Java
  • JSTL/JSP
  • Spring MVC Framework

This is the point where the language argument hit home for me. My dad isn't a programmer (he considers manual CSS/HTML to be too technical for him), and knows how much I make. So when I told him that I'd see if one of my friends wanted a Java Job because it really isn't my language, he was understandably confused.

"What do you mean, it isn't your language? What difference does it make?"

All the difference.

Because NALT tells me that if I take a Java Job, I'll be dealing with people who take Java Jobs. By and large[6], that means people who believe in getting through the day rather than burning with the desire to write brilliant software or exceed themselves. It means dealing with the One True Way to do Anything, which always coincidentally seems to lead through three layers of XML declarations, Eclipse plugins and/or magic. And it means having to deal with design patterns instead of abstracting away the problems that call for those solutions.

So I shouldn't switch languages. Explaining that to someone who isn't at ground zero is difficult, and sort of subjective in any case. In that concrete example I just offered up, I don't think it's fair to say that I chose the wrong languages. "Getting a job as a corporate programmer" was nowhere near my goal list when I started learning and, if anything, it's further away now.

It's also not really fair to say that the employer in this case made the wrong decision. Working on a web-app for a billing department isn't likely to run them up against fundamentally unsolved problems, they likely have a large number of small teams, the business guys (non-programmers) are in charge, and I have a hunch that their turnover is something above the industry average. Given the context, would you seriously recommend Haskell or Common Lisp to these people? They may be superior tools, but they're superior in precisely the way that corporate shops don't care about.

What were we talking about again?

Choosing languages. The fact is that so many factors play into what the correct answer is (if one even exists), from project goals, to company goals to the preferences your particular group. And all that is without even discussing things like technical features, platform availability, deployment strategies or performance. If you ask something like "Why choose Lisp for a project?" and expect an answer short enough to fit into a reasonably readable SO answer, your entire perspective of the problem could probably use some re-thinking.


Footnotes

1 - [back] - As opposed to a toy project.

2 - [back] - Where x is bound to a single programming language, regardless of what it is.

3 - [back] - And I don't even have kids yet.

4 - [back] - Or, as frequently happens in a larger company, several(hundred)? teams of 10.

5 - [back] - At the point that you need to maintain all the beginner code you'll be writing for the first little while.

6 - [back] - This has been my limited, subjective experience so far, it may not represent the Java community as a whole.

Wednesday, February 1, 2012

Smalltalk First Impressions

I've actually been meaning to get around to trying this out ever since the Dynamic Languages Smackdown[1].

So, I dusted off Pharo, which has had at least one major release since I last checked it out.

This time, I didn't pull punches, finding as many practical examples and tutorials to run through as I could. This includes two for Seaside[2], the couple for Pharo proper, and a built-in tutorial named ProfSteph which you can run from the greeting screen.

So here are my first impressions[3]; I'm sure they'll change as I learn more about the language (and I fully intend to learn more about it)

It Passes The Compaq Test

This thoroughly surprised me, because Smalltalk has a reputation for being brilliant and elegant but slow. I guess the people perpetuating this reputation mean "relative to C", because Seaside ran quite snappily off of a rather old machine with 256MB of ram. That was an "M". In fact, as I write this on that same ancient machine, I'm running Seaside in the background along with Slime and getting along perfectly well[4].

It Has "Source" Control

The word source is quoted because it's an image-based system, but a module called Monticello basically does for Smalltalk what git would do for other languages. I wouldn't mention this, except that I remember thinking about it last time, and several other people at the Smackdown expressed similar concerns. So if your main excuse for staying away from Smalltalk is "I don't want to give up source control", you no longer have an excuse.

Fantastic IDE

And this is coming from someone who usually hates IDEs. This one actually fails to get in my way at most opportunities, provides useful information and completions when I need them, is intuitive and well documented internally and externally, and (most importantly) does not take longer than Emacs to load up[5]. For those of you working cross-platform, it's also fully skinnable and comes with themes appropriate for the big three OSes (each of which it runs on beautifully).

Turtles All The Way Down

Everything is an object. Everything is an object. Signs of this show up in the way loops and conditionals are treated, as well as the complete construction of the system[7]. It's kind of an extension of the previous point, but I wanted to emphasize it. That fantastic environment I mentioned? It's built in Smalltalk. The main click-menu (called the World Menu) is actually represented in the image. You can head over to the class browser and find a class called TheWorldMenu. You can also Ctrl + right-click on any component of the menu to activate its halo and fuck with internal variables. You probably shouldn't, but you could. This level of introspection happens for almost[6] every component and sub-component you can see. I imagine this is what it would feel like to work on a full-out lisp machine.

Great GUI Toolkit

I reserve the right to change my mind since I've only gone through some very basic activities, but it looks like it would be very easy to put together desktop applications with Smalltalk. I'm not super clear on how you'd go about deploying them, but there seem to be ways.

That's the stuff that's attracted me. There's downsides too, of course, but they're not enough to give me pause. If you're just looking for an excuse not to try Smalltalk out, one of these should probably be enough.

No Respect for BEDMAS

All of the manuals are quite explicit about this too; the fact that everything is an object means that the expression 3 + 5 * 2 isn't actually an expression. It's two binary messages being sent to two SmallIntegers. That means that the only reasonable way to be consistent about it is to treat arithmetic strictly from the left; so that the expression above will actually evaluate to 16 rather than the expected 13 if you try it out.

Mouse-Centric

This may actually be a pro for some people, but it's not for me. The environment expects you to do most things with the mouse[8]. There's a greater than usual amount of time spent dealing with objects and widgets, so I guess that might be fair, but look. If your window system doesn't let me move between windows without reaching for the rat, you're doing something wrong. Being already used to a tiling WM just makes it that much more annoying[9]. A lot of things have keyboard shortcuts, but not everything, and those things that don't are quite annoying. Not exactly annoying enough to jump over to GNU Smalltalk, but still.

Odd Choice of String Delimiters

In Smalltalk "foo" is not the string foo. It's actually the comment foo. The string foo looks like 'foo'. How do you put an apostrophe in a string? You don''t. You either escape it with a second quote, or you use typographers’ quotes. Now you know. I'm still not entirely sure why this decision was made though. It seems like pretty much any other comment delimiters would have made more sense.

Wonky Keyboard Shortcuts

I'm putting this one at the bottom of the list because I'm convinced that there must be a way to change them that I just haven't discovered yet. By "wonky", I don't mean "it uses the wrong letter", I mean "who the fuck thought this was the correct behavior?". Things like not having Ctrl+backspace backward-word-kill (giving that honor to Shift+backspace for comical effect), or having Ctrl+x kill a line, but move forward doing it and keep the \n in place, or having Ctrl+Right move forward a word, but skip newlines so that moving your point to the last symbol of a line is just that little bit more annoying. Also in this category, things like having (, ' and " auto-close themselves, but only about half the time and with a noticeable delay. Like I said, this isn't that huge a deal because I'm convinced that

  • There must be options I'm missing that will let me fix this
  • Even if there is no explicit config option, there's a way to fix this through the object model, and it won't be complicated enough to drive me to drink

So there. That's first impressions after about half a week of poking at Pharo. Hopefully it came off as more positive than negative, because I really do like the language so far, but my internal censor goes a bit wonky at about 11:00, and I won't get a chance to proof this until tomorrow morning.


Footnotes

1 - [back] - And now I'm shocked because I could have sworn it wasn't more than a year ago, but here we are.

2 - [back] - Though the official Seaside tutorial has some issues with registering new handlers, in Pharo at least. They tell you to go the web-interface route, which consistently ignored my brilliant HelloWorld handler. Check the sidebar for links to working tutorials ("Seaside 3.0 in Pharo" actually gives you a working tour as of this writing).

3 - [back] - Which differ from Preliminary Impressions in that they're founded on something more than gut feeling.

4 - [back] - Though I will admit that squeak is at the top of top by using a whopping 6%-8% of my CPU and 10%-16% of my memory.

5 - [back] - I'm looking at you, Eclipse. Though, to be fair, it's been a while, I guess you may have lost weight since then.

6 - [back] - It does tell you to fuck off if you try to add a halo to a halo component. I'm assuming I have to edit that directly through the class editor rather than at the front end.

7 - [back] - It's not cumbersome, though, every command I've typed so far has been extremely elegant, if alien (though that's just because I'm not used to it).

8 - [back] - In fact, it advises you to go get a three-button mouse if you don't have one already.

9 - [back] - Though I'm sure it must be possible to build one for the VM in such a way that you can easily strip it from your final product; I may look into this once I get my bearings. Edit: Nevermind. Though it might still be a good learning exercise.