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.
Interesting write-up. How did you guys deal with changing data layouts? If I were to add/remove a data member to some structure, is this something the system was able to fix-up, or were there some changes like this that required full restarts?
ReplyDeleteGOAL was not that smart, but you could change data layouts - though manually. First, you would ask the compiler what dependencies there was on a type. Then you would update the new type (but still no code would use the information). After that you would update code and data that used the new layout. Then finally you would update the function or file that would make use of the new data.
DeleteNeedless to say, this was a little error-prone and could probably have been implemented automatically. Having said that, it usually worked fine.
When you talk about code dependencies, was this useful so that you could inline functions? So if I were to update some function Foo(), the system would trace dependencies to know every function that inlined Foo(), and recompile it?
ReplyDeleteAlso was there much in the way of compile-time checking? So the whole system could pause if it detected some compile error, until it was resolved?
As mentioned above, it was mostly to facilitate help for the programmer - but we believed that it was also possible to update code and data automatically, and for that you need detailed dependencies.
DeleteThere was some type checking, but quite minimal. GOAL supported both static types as well as dynamic types, and would check for trivial errors on static types. Obviously, errors would be detected by the compiler and it would not update target code if that happened. The target would never pause due to the compiler, except through explicit "break" commands sent over the debugging channel.
Hey Pal,
ReplyDeleteSo I open Facebook and someone's talking about GOAL! Ah, good times! :)
So for J&D 2 and 3 did Andy extend GOAL? I don't remember there being a dependency manager, but I remember we talked about needing one :) The original GOAL only had its "named globals" table, including functions, but it didn't do a lookup for every call because that would be too slow. On J&D if you recompiled a function, any function that already called the old code still called the old code. I thought a simple "JMP NEW_CODE" patch would fix this but a broader solution sounds great - did you have that, then?
Global variable lookups *were* indirected and never hard-linked, so recreating those was trivial and instant, except for the table maintenance when loading an object file, which took *ages* to streamline enough for "no load time". There was a small hit for every global reference but I don't think they ever mattered to performance. A proper dependency manager could move that hit to load-time at best, couldn't it, since a new object file can overwrite an old global name or an old function name?
BTW you don't mention here one of GOAL's most awesomest features - the integrated inline assembler. It made it very easy to slip a bit of SIMD code in here and there.
Have you done any Lisp coding since those days?
Hi Pal,
ReplyDeleteI have a few questions.
So if I understood your post correctly, GOAL was not a "real Lisp" in any sense of the word, but a language somewhere between assembly and C with a Lisp syntax and macros. Were there things such as eval or closures? Were the macros hygienic like Scheme's or unhygienic like Common Lisp's?
Finally, I remember reading somewhere that Andy Gavin was going to release the documentation for GOAL, but never got around to it. Do you know anything about this?
Thanks,
Long