Monday, June 16, 2014

The Legacy of GOAL

GOAL was a programming environment created by the incredibly smart co-founder of Naughty Dog -- Andy Gavin -- for the PlayStation 2 generation. It was never released to the public, hence only rumors of its greatness has trickled into the general game development scene.

Why was GOAL so awesome?


There is no doubt about it, GOAL was simply awesome. But why?

In my opinion it was due to one single idea: Interactivity. Think about it: These days we revel in the idea of hot-loading assets, changing shaders on the fly, and interacting via scripting languages such as Lua and advanced level editors. What if your whole engine was interactive. Not just parts of it, but all of it.

The Listener


Let us think about what interactivity for your entire (run-time) code-base entails. First, we need a method for adding/removing code and data on our target machine where the game is currently running. That means that the game will have to run code at a dedicated safe-point that can patch the memory that holds code and static data. It also needs a mechanism to make use of the new code/data, so it needs to patch calls to functions and reads of global data. Now, the target (the game) is often resource constrained, so it is vital that the target code for this is compact. We don't want to implement a linker or a JIT-compiler on the target. But what we will need is a listener on the target that can receive code, execute allocation and deletion of code and patch in calls to new code. Since this will also be part of the debugging infrastructure, it will also be convenient to be able to inspect data, i.e. be able to respond to debugging commands sent from outside the game. So, the listener is a (thin) server that runs on the target. 

The Linker


Given that the listener is supposed to be a thin server, something else needs to know where code and static data is on the target. This is typically done by a linker, but a linker is not a server. It also does not know how to change code on the fly. So, what is needed is a linker service. We could certainly do that, but it turns out that the linker has an almost trivial task. Most of the complexity for a linker is due to things like linker scripts and arcane file formats. If you distill the essence of a linker it is almost trivial. It is a data-base of names to real addresses. It takes "object files" that contain code and static data (along with some meta-information) and produces and actual executable where all names have been resolved into final addresses. We are going to need this information at a higher level, so it makes sense to make the linker an integrated component of the system.

The Debugger


Most debuggers (like e.g. gdb) are written as a stand-alone system. The big flaw with it is that the debugger needs to execute code. If I have an array of 10,000 structures, I don't want to inspect it by clicking on the array and manually search for the structure that has the name 'crate-b-01'. Instead, I'd like to execute some kind of code to find it for me. Some debuggers support scripting languages for these tasks, but that just introduces yet another language to our system. Why not implement the debugger as an extension of the language itself? After all, we are creating the one-and-only language we need. An we have everything we need, we have a listener on the target that can execute any commands that we send it. For more advanced queries, we can do it in two ways. We either compile the debugging code (our search function) on the host, boiling down the result into commands to be executed on the listener, or we compile the debugging code into code that is to be executed on the target. We might need both, for the cases where the game or the listener crashes on the target.

The Dependency Manager


When programmers talk about interactivity, they often refer to the "REPL". The REPL is basically a command line system where you can write code and have the compiler interpret (or compile) the code, execute it and then give back control to the command line. 

While this is powerful, that's not really what we want. We want to be able to create or change some code in our project, hit a key (or click button) in our favorite editor and have the system magically compile all changed code, send the deltas to the listener and let it update the code on the target to reflect our changes. In order for this to be possible, we need detailed knowledge of dependencies within the entire code base.

This means that "make" won't be enough, instead it has to be a crucial component of our system.

The Language


It is interesting that syntax of the actual language that we use is not that important. However, given our environment there are some rather important restrictions that has to be considered.

First, in order to have an interactive experience we must avoid anything like C/C++'s #include system. Instead, the compiler will need to support a module system. Each source file corresponds to a module, so that every function (and static data) name at the source file level is scoped uniquely. Type information, exported names and dependencies needs to be cached by the compiler in order to facilitate code patches as quickly as possible. The Go language definitely has the right approach here.

Second, since we want to be able to use the language as part of the debugger, we probably want to be able to reason about types and other meta-data. It might also be useful to execute code on the host during compilation, in other words - macros. If we do support macros and a debugger language, the language should be very similar to the target language. Lisp languages do this automatically, but there are other solutions in languages with syntax.

GOAL


What I have described above isn't just possible, it has already been done. Andy's system was not just a compiler. It was also a linker, a debugger, a dependency manager and a macro expander, but more importantly -- it was a server. This is so fundamentally important. If you are going to change code on the fly, something needs to know "everything", and the compiler knew everything. It was live, so you could get access to everything, results of macros, memory on the target. 

GOAL's source language was very simple. Much simpler than Lisp, C/C++, Rust etc. There was not a lot of features, not much of functional programming (it was imperative). As a matter of fact, it was basically an assembly language compiler with register coloring. It used Lisp macro system to make things easier for the developer, and it had little of type-checking. But even without the more advanced features of other languages it was a beautiful system, because it was interactive and immediate. It still happens to be the best programming environment for games programming I have ever seen.