a life of coding

Sunday, December 04, 2005

Lisp in Games: Naughty Dog's Jax and Daxter

Here is a brief clipping from a Gamasutra article that talks about Lisp used for writing console games.  The really really short version: lisp allows for awesomely simple cooperative threading (via continuations) and a short development cycle (using interactive mode on the console), if you can find a language that runs on your console, and programmers who know lisp.


GOAL rules! Practically all of the run-time code (approximately half a million lines of source code) was written in GOAL (Game Object Assembly Lisp), Naughty Dog's own internally developed language, which was based on the Lisp programming language. Before you dismiss us as crazy, consider the many advantages of having a custom compiler.

Lisp has a very consistent, small set of syntactic rules involving the construction and evaluation of lists. Lists that represent code are executed by evaluating the items that are in the list; if the head of the list is a function (or some other action), you could think of the other items in the list as being the parameters to that function. This simplicity of the Lisp syntax makes it trivial to create powerful macros that would be difficult or impossible to implement using C++.

Writing macros, however, is not enough justification for writing a compiler; there were features we felt we couldn't achieve without a custom compiler. GOAL code, for example, can be executed at a listener prompt while the game is running. Not only can numbers be viewed and tweaked, code itself can be compiled and downloaded without interrupting or restarting the game. This allowed the rapid tuning and debugging, since the effects of modifying functions and data structures could be viewed instantaneously.

We wanted creatures to use nonpreemptive cooperative multi-tasking, a fancy way of saying that we wanted a creature to be able to execute code for a while, then "suspend" and allow other code to execute. The advantage of implementing the multi-tasking scheme using our own language was that suspend instructions could be inserted within a creature's code, and state could be automatically preserved around the suspend. Consider the following small snippet of GOAL code:

(dotimes (ii (num-frames idle))
   (set! frame-num ii)

This code has been simplified to make a point, so pretend that it uses a counter called ii to loop over the number of frames in an animation called idle. Each time through the loop the animation frame is set to the value of ii, and the code is suspended. Note that the value of ii (as well as any other local variables) is automatically preserved across the suspend. In practice, the preceding code would have been encapsulated into a macro such as:

(play-anim idle
   ;; Put code executed for each time..
   ;; through the loop here.

There are other major compiler advantages: a unified set of assembly op-codes consistent across all five processors of the Playstation 2, register coloring when writing assembly code, and the ability to intermix assembly instructions seamlessly with higher-level code. Outer loops could be written as "slower" higher-level code, while inner loops could be optimized assembly.

GOAL sucks! While it's true that GOAL gave us many advantages, GOAL caused us a lot of grief. A single programmer (who could easily be one of the top ten Lisp programmers in the world) wrote GOAL. While he called his Lisp techniques and programming practices "revolutionary," others referred to them as "code encryption," since only he could understand them. Because of this, all of the support, bug fixes, feature enhancements, and optimizations had to come from one person, creating quite a bottleneck. Also, it took over a year to develop the compiler, during which time the other programmers had to make do with missing features, odd quirks, and numerous bugs.

Eventually GOAL became much more robust, but even now C++ has some advantages over GOAL, such as destructors, better constructors, and the ease of declaring inline methods.
A major difficulty was that we worked in such isolation from the rest of the world. We gave up third-party development tools such as profilers and debuggers, and we gave up existing libraries, including code previously developed internally. Compared to the thousands of programmers with many years of C++ experience, there are relatively few programmers with Lisp experience, and no programmers (outside of Naughty Dog) with GOAL experience, making hiring more difficult.

GOAL's ability both to execute code at the listener and to replace existing code in the game at run time introduced the problem of memory usage, and more specifically, garbage collection. As new code was compiled, older code (and other memory used by the compiler) was orphaned, eventually causing the PC to run low on free memory. A slow garbage collection process would automatically occur when available memory became sufficiently low, and the compiler would be unresponsive until the process had completed, sometimes taking as long as 15 minutes.


Post a Comment


Create a Link

<< Home