Friday, May 16, 2014

(Ab)Using Language Features: The Common Lisp Condition System

One of the recommendations in The Pragmatic Programmer is to learn at least one new programming language every year.  According to the book:
Different languages solve the same problems in different ways. By learning several different approaches, you can help broaden your thinking and avoid getting stuck in a rut.
Over the years, I've taken that advice to heart.  I guess you could say that I'm an expert language learner at this point.  There are many languages that I'm proficient in (C, C++, Lua, Common Lisp, Python), and many more that I've at least written some non-trivial code in (Perl, JavaScript, LabVIEW, Java, Prolog, Haskell, Erlang, Ruby, Scheme, and more...).

A programming language is more than a tool for writing programs.  It forms a mental framework for solving problems.  When faced with a problem, a dyed-in-the-wool C++ programmer will start mentally formulating an object-oriented solution with virtual functions, overloading, templates, etc.  A "functional" solution to the same problem may never occur to them.

The hardest thing about learning a new programming language is that there are usually at least one or two novel features that break the mold of our current mental framework.  If not, the language may not be worth learning in the first place.

So, given that learning new languages can be challenging, I would like to share a tip that has served me well over the years.

One of the best ways to really understand a new or novel language feature is to think of ways to twist and abuse it.


I know it sounds odd, but I like doing this for several reasons.

  • It gives me an interesting mini-project to work on which usually leaves me with a better understanding of how the feature works.
  • I'm likely to run into the limitations and corner cases of the language (which is something I enjoy exploring)
  • Thinking of ways to abuse a feature is a creative exercise that allows my brain to leave the confines of its normal working space.  This puts me in a good frame-of-mind for breaking my existing mental molds.

So, enough with justifications, let's jump right into today's victim, the Common Lisp condition system.

Intro to Conditions


At a very high level, Common Lisp's conditions are analogous to exceptions in other languages.  They can be used to interrupt the control flow of an application and pass error information up the call stack.

Here's a simple example comparing C++ exceptions and Lisp conditions so you can compare the basic usage.

// C++
try {
   LogData d = parseLog(log);
   doSomethingWithData(d);
}
catch (const LogParseError& e) {
   fprintf(stderr, "Failed to parse data out of log");
}
;; Common Lisp
(handler-case
    (let ((d (parse-log log)))
      (do-something-with-data d))
  (log-parse-error (e) 
    (format *error-output* "Failed to parse data out of log")))

As you can see, these examples are very similar.  However, Lisp conditions are more than just exceptions by a different name.

Enter the Restart and the Condition Handler


One of the biggest differences between Lisp conditions and traditional exceptions are features of the condition system called restarts and condition handlers.

These features, used in conjunction, can be used to invoke custom logic when a particular exceptional situation is encountered.  If a given condition type has a handler "bound" to it, when this condition is signaled, the corresponding condition handler is run.  This handler has the opportunity to examine the condition signaled and invoke a restart (if provided by the lower level code).  A key thing to note is that the condition handler is run before unwinding the stack, and by invoking a restart can handle the error right where it occurred.

That last part is an important distinction.  Condition handlers and restarts allow you to handle exceptional situations right where they happen, as opposed to higher up the call stack.

Separating Mechanism from Policy


Before getting into the specifics of why someone would want to use a restart, let's digress for a minute and talk about something more philosophical.

In general, well-designed software should clearly separate the high-level rules and requirements from the low-level mechanics of what is being done.  A common way to refer to this is separating mechanism from policy.

By allowing for high-level code to dictate how lower-level code recovers from errors, condition handlers and restarts can provide a better separation between the mechanism and policy of your code.

Anyway, enough talk about what condition handlers and restarts are, let's see some abuse!

Abuse: C-Style Hex Literals in Common Lisp


Given the age and lineage of Lisp, there are some things that seem odd when viewed through the lense of newer languages.  One such thing is how hexadecimal literals are specified.

Rather than using something like 0x100, which you could use in just about any other language.  In Common Lisp, you have to type #x100.  Once you get used to it, it's not terrible, but it would be nicer if I could specify hex literals using the more common c-style notation.

In this first example, I will use restarts to allow for c-style hex literals in Lisp code.

(Note: All of my examples are using GNU Clisp.  The default restarts provided by each Common Lisp implementation will unfortunately be different so this may not work exactly as-is in different implementations.)

In GNU Clisp, when the evaluator encounters a variable it doesn't recognize, it signals the unbound-variable condition.  When running code in the interpreter, Clisp provides a restart called use-value.  This restart allows you to provide a value to substitute for the unknown variable.  We can take advantage of this mechanism in this case because when the evaluator encounters something like 0x100, it will try to interpret it as a variable name.

First, let's create a helper function that will convert a c-style hex string into a number.

(defun hex-val (str)
  (multiple-value-bind (match regs)
      (cl-ppcre:scan-to-strings "^0[xX]([0-9a-fA-F]+)$" str)
    (if match
      (parse-integer (aref regs 0) :radix 16)
      nil)))

Next, we need a condition handler function that can take an "unbound-variable" condition and invoke the "use-value" restart with the appropriate value if this looks like a hex literal.

(defun c-like-hex-literal-handler (condition)
  (let* ((var-name (symbol-name (cell-error-name condition)))
         (val (hex-val var-name)))
    (when val
      (invoke-restart 'use-value val))))

With these 2 functions in place, we can now do things like this:
(handler-bind ((unbound-variable #'c-like-hex-literal-handler))
  (format t "Answer is ~A~%" (+ 0x01 0x100 10)))
;; --> "Answer is 267"

This being lisp though, we can also create a macro that does this.
(defmacro with-hex-literals (&body body)
  `(handler-bind ((unbound-variable #'c-like-hex-literal-handler))
     ,@body))

Now we can just do:
(with-hex-literals
  (format t "Answer is ~A~%" (+ 0x01 0x100 10)))
;; --> "Answer is 267"

Note that this would work in more than just the trivial cases described above.  To use some Lisp terminology, the condition handler binding exists in the dynamic environment (as opposed to the lexical one).  This means that the c-style hex literals can be used at any point between when the handler binding is made and when the handler-bind form completes.

Abuse: Limited Infix Notation


As you've surely grasped by now, Lisp uses what is called prefix notation.  This just means that rather than expressing things like "1 + 1", Lisp puts the function first, like "+ 1 1".

In a similar vein to our c-style hex literal code, let's add support for simple infix literals, just for fun.  This code will take advantage of the infix library by Mark Kantrowitz.

First, let's write a function that will evaluate a string as infix notation (or return nil if it doesn't look like an infix expression).

(defun infix-val (str)
  (let ((infix-form (handler-case (infix:string->prefix str)
                      (condition () nil))))
    (when infix-form
      (eval infix-form))))

Note that we're using handler-case here to convert any conditions signaled by the prefix conversion to nil.

Next, we'll write a condition handler function that takes an unbound-variable condition and invokes the use-value restart with the appropriate value (if this is infix).  Notice that this looks very similar to the c-like-hex-literal-handler.

(defun infix-literal-handler (condition)
  (let* ((var-name (symbol-name (cell-error-name condition)))
         (val (infix-val var-name)))
    (when val
      (invoke-restart 'use-value val))))

Finally, we'll create a macro that establishes an environment in which we can use infix notation.

(defmacro with-infix-literals (&body body)
  `(handler-bind ((unbound-variable #'infix-literal-handler))
     ,@body))

Now we can do things like this:

(with-infix-literals
  (format t "Answer is ~A~%" (+ 1 10*10)))
;; --> "Answer is 101"

Note that this particular use has many limitations.
  • There cannot be any spaces in the infix notation since the evaluator must treat the whole thing like a variable name.
  • We cannot use parenthesis for grouping since the lisp reader breaks up tokens at parens.

As an interesting aside, we can actually use lisp's pipe ('|') notation to work around both of these limitations...but that somewhat defeats the purpose of having a simple in-line notation without special syntax.
(with-infix-literals
  (format t "Answer is ~A~%" (+ 1 |10 * 10 * (1 + 1)|)))
;; --> "Answer is 201"

Supreme Abuse: Putting it all together


Let's create one macro that combines these things to show how these 2 examples can actually work together.
(defmacro with-crazy-stuff (&body body)
  `(with-hex-literals
     (with-infix-literals
       ,@body)))

This lets us use c-style hex literals in infix expressions
(with-crazy-stuff
  (format t "Answer is ~A~%" (+ 1 10+0x3*0xa)))
;; --> "Answer is 41"

Let's go over what's going on behind the scenes here.
  1. During evaluation, the unbound-variable condition is signaled for the 10+0x3*0xa "variable".
  2. The infix-literal-handler transforms this into
    (+ 10 (* 0x3 0xa))
    by invoking the use-value restart
  3. This triggers another unbound-variable condition to be signaled for the 0x3 and 0xa "variables" (each in turn).
  4. The outer c-like-hex-literal-handler transforms these into the numeric versions of these hex values (again by invoking the use-value restart)

Conclusion


I hope that this leads some people to a little better of an understanding of conditions, condition handlers, and restarts.  However, please don't do this in production code :).  This was purely intended as a vehicle for learning and nothing more.

That being said, if you'd like to try this code for yourself, I've packaged it as a GitHub Gist.  Are there other language features you would like me to abuse?  Let me know in the comments.

Monday, April 21, 2014

Pyroscaphe: Adding a Touch Screen to PC Gaming

I have a confession to make.  I am a big fan of PC gaming.  Ok, that's not too controversial, but let me take this a step further.  I am a big fan of PC gaming...with a controller.

For all too long, the controller has been a second-class citizen in PC-land, with the mouse and keyboard reigning supreme.  This is why I was so excited when I heard news of the Steam controller that Valve is developing.  For those of you that don't know, this is a controller, currently under development, which is designed from the ground-up to work well with PC games, even those that traditionally could only be played with a keyboard and mouse.

Originally announced Steam controller design
The initial prototypes of the controller were impressive.  Obviously the dual trackpads are integral, but the part that excited me the most was the touch screen display at the center of the controller.  This touch screen was to be a multi-purpose input/output mechanism for games to utilize for auxiliary tasks or just as "soft buttons".

There are so many possibilities for a mechanism like this.
  • on-screen maps
  • inventory management
  • quick save/load buttons
  • ammo status for "realistic" shooter games
  • any auxiliary function that may not map well to existing controller inputs
To my disappointment, a few months ago Valve announced that the touch screen had been dropped from the steam controller design.  I'm sure they had good reasons to do this, but as an engineer excited by this concept, I just couldn't let this die.

Steam controller with touch screen removed

The Premise


Most of us already have powerful touchscreen devices in our pockets.  Rather than design a new controller with a built-in touch-screen, we could leverage the devices that we already have to enable these new types of game interactions.

That was my general line of thinking, and it's how Pyroscaphe was born.

Prototype Controller


Pyroscaphe


At its core, Pyroscaphe is a web server that allows you to interact with your gaming machine on a local network from a web-enabled device (like a phone or ipod touch).  This server serves web page UIs for a given game and also receives WebSocket requests which lets the player interact with the game in a real-time, low-latency manner.

In its current state, Pyroscaphe is mainly useful for sending keypress events to games, so through the UI on your mobile browser, you can essentially press keys on your keyboard.

In the future, I would like to make this more of a 2-way interaction, with the touch interface receiving more data about the running game.

Demo


(I apologize for the blair witch photography)



Why Web-Based?


There have been many articles recently that have declared the mobile web dead...or dieing, with the App being king.  However, for this particular application, I believe web-based UIs are best.

If something like this is to succeed, it depends heavily on the community generating content in an incremental, and distributed way.

This would be very challenging for a traditional mobile app.  With an app, we would have to have a central location for UIs to be reviewed and vetted, and they would have to go through the long Apple review process.  This process discourages frequent updates and also means that there must be a central authority that spends a lot of time hand-holding the process and vetting these touch UIs.

Since Pyroscaphe is essentially a locally-hosted web-app, it doesn't have these particular issues.  All of the content lives on the user's PC, where they have full control over what's installed and can update it incrementally with UIs created by the community.  There doesn't have to be any central authority.  UIs can be freely downloaded from ftp sites, discussion forums, or traded on floppy disk :)

Also, though inter-browser compatibility can be challenging at times, it's not too difficult to write HTML that works across most mobile browsers (as opposed to writing one interface in ObjectiveC, another in Java, etc..).

Finally, by using HTML, it greatly reduces the barrier to entry for creating one of these UIs.  HTML is a universal language that just about anyone can pick up fairly easily.

Client web page creation


Like I said previously, if Pyroscaphe is to have any chance to succeed, it must leverage the power of the community.  There are just so many talented and creative gamers out there.  If someone feels the itch to create a touch UI for their favorite game, I want it to be as easy as possible to do so.

One of the things I'm doing to accomplish this is to leverage HTML5 "data-" attributes.  Here is what my prototype "Duke Nukem 3D" page looks like:




<html>
  <head>
    <title>Duke Nukem 3D</title>
    <script src="/pyroscaphe.js"></script>
    <script> $(document).ready(function(){ initPyroscaphe(); });    </script>
    <style>
      <!-- CSS omitted for expository purposes -->
    </style>
  </head>
  <body>
    <table id="gunTbl">
      <tr>
        <td><img class="dukeGun" data-key="2" src="pistolIcon.png"></img></td>
        <td><img class="dukeGun" data-key="3" src="shotgunIcon.png"></img></td>
      </tr>
      <tr>
        <td><img class="dukeGun" data-key="4" src="chaingunIcon.png"></img></td>
        <td><img class="dukeGun" data-key="5" src="rpgIcon.png"></img></td>
      </tr>
    </table>
  </body>
</html>
As you can see, this HTML is extremely simple.  The bootstrapping mechanism is fairly lightweight as well.  Pages must pull in "pyroscaphe.js" and initialize Pyroscaphe when the document is loaded.

With that in place, pages can use the "data-key" attribute on an element to specify which key they want to press when a given element is touched.  In this case, weapons are selected with the number keys, so we bind the pistol image with key "2", shotgun with key "3", etc.

Behind the scenes Pyroscaphe uses jQuery to add the appropriate event handlers to send the right WebSocket commands to the server.

The prototype UI for Mortal Kombat is even simpler:



<html>
  <head>
    <title>Mortal Kombat</title>
    <script src="/pyroscaphe.js"></script>
    <script> $(document).ready(function(){ initPyroscaphe(); }); </script>
    <style>
      <!-- CSS omitted for expository purposes -->
    </style>
  </head>
  <body>
    <img id="finishHim" data-seq="V;A;L;V;E;" src="finishHim.png"></img>
  </body>
</html>
In this example, Pyroscaphe is bootstrapped just like before.  However, we just have a single image on the page with a "data-seq" attribute (as opposed to the "data-key" attribute that the previous page used).  As you've surely guessed, this tells Pyroscaphe to send a sequence of key presses to the game when this UI element is touched.

These are just 2 examples of very simple UIs that can be created.  Again, this is about leveraging the creativity of the gaming community to create these UIs.  The easier I can make it to create this content, the more likely it is that someone will do so.

Latency


Web apps have a bad rap for being slow and unresponsive, at least compared to native applications.  However, Pyroscaphe has several things going for it on this front.

It's designed to be used in a local network, so very few hops are required to get from client to server.  This also means interaction is more deterministic since we're not just sending data out into "the cloud", it's only going out on a small, controlled network.

We're also using WebSockets for all time-critical game interactions.  This means we don't have to deal with the overhead of creating a new socket connection for each server call (which itself involves a few round-trips).  We also don't have to deal with the overhead of the HTTP protocol.  As such Pyroscaphe has a very simple bare-bones command protocol that keeps performance snappy.

To validate that the latency wasn't too bad, I wrote a fairly simple test.


By round-trip time, I mean that this is the time it took for the UI to send a command to the server and for the server to send a simple response back.  So in reality, the lag between interacting with the touch UI and seeing a key press is roughly half of this time.  As you can see, in my tests the vast majority of calls had a round-trip time of 3-4 ms, which is more than sufficient for most game applications (and in-line with standard wireless controller latency).

A secondary benefit of using a single WebSocket (as opposed to many web-service calls with their own sockets) is that the data is serialized and we don't have to worry about data arriving at the server in a non-deterministic order.

FAQ


Won't the mobile web browser UI get in the way?


This can happen with some browsers.  I personally recommend using browsers that have a good fullscreen mode (like Atomic Web Browser Lite).

A touch screen on the controller diverts attention away from the action on-screen.  Won't that hurt the overall experience?


Touch screens are probably not the best input mechanism for really fast-paced action games.  However, there are a large number of games out there that don't require absolute non-blinking focus.  Those are the games that Pyroscaphe is intended for.

Can Pyroscaphe UIs send xbox 360 controller (XInput) button presses?


Not at the moment.  Currently, you have to use a program like Joy2Key to have your controller send key presses (and configure your game for keyboard input).

I would certainly like to get this working at some point.  However, I couldn't find an easy way to do this.  I could probably create a driver for this purpose (I personally work a lot with drivers by trade), but that's more trouble than I wanted to go through for the initial 0.1 version of Pyroscaphe.

Why are your demo UIs so ugly?


Sorry, UI design isn't my strength.  I'd be thrilled if someone wanted to help make these demos look better (or create new UIs).

So this can only send keypresses to a game?  So what.


It's not much right now, but I would like this to be the start of something better.  It's much easier to get keypresses to a game than to get data from a game (like showing an interactive map with your current location).  I suspect that doing the latter will require some game modding which isn't something I've done before.  Again, any help is welcomed.

Future Direction


There are a lot of possibilities for Pyroscaphe in the future.  Here are a few ideas I've had.

  • Auto-detect the game that has been launched and instruct the touch-screen to change UIs.
  • Simulate controller key presses via XInput and/or DirectInput
  • Simulate a mouse touchpad for navigating complex game menus
  • Detect key bindings or otherwise make it easier for users to map a given touch UI to their key bindings.

Conclusion


It's not much right now, but my hope is that if there are others like me out there, Pyroscaphe might gain some momentum and eventually lead to some really interesting and engaging gaming experiences.

Give It a Try!

Pyroscaphe's code is open source and freely available on GitHub.

https://github.com/justindvs/pyroscaphe

Don't want to build it from source?  You can download a binary distribution for Windows x64 here:

https://github.com/justindvs/pyroscaphe/releases