A Glimpse into the Apollo Guidance Computer
The other day, I posted the following snippet of code on Facebook and Twitter:
This code is from the original Apollo Guidance Computer (AGC) source code, available on ibiblio.org as well as on an (easier to browse) GitHub repo.
I was already aware that the AGC source code was available online, but someone reminded me of it recently, and my post was mostly a “ha ha, look at this code comment” post.
However, then I became curious about what FLAGORGY actually does, which led me down the rabbit hole of reading a lot of online documentation and some 1960’s manuals (specially this one). The result, in the end, was actually a bit anti-climactic: contrary to what I had hoped, FLAGORGY does not trigger a jingoistic ejection of tiny American flags on the surface of the moon (you’ll have to wait until the end of this article to find out what FLAGORGY actually does). However, reading about the AGC architecture in more detail was pretty fascinating, not to mention very humbling. I am in awe of programmers back then; programming computers nowadays seems almost trivial by comparison.
Anyway, I decided to write this article to provide a summary of what I found. It is not intended as a comprehensive summary of the AGC architecture, but it should provide a decent glimpse into what the AGC was like (and what FLAGORGY does). By necessity, I’m assuming you are familiar with basic computer architecture concepts (instruction sets, memory addressing, etc.) I’m also by no means an AGC expert (or an expert on 1960’s architectures), so I’m more than happy to be corrected on anything I say here.
AGC Architecture 101
First of all, let’s see what the AGC architecture looks like. It is actually your run-of-the-mill Von Neumann architecture: it has a processor with an instruction set, registers, memory, and input/output devices. The devil is in the details, and each of these components gets pretty complicated once you dig into them, so I’ll focus only on the aspects that relate to understanding FLAGORGY. If you want to read more on the AGC architecture, the Wikipedia article on the Apollo Guidance Computer provides a pretty decent summary.
In the AGC architecture, words were 16 bits long, although only 15 bits are actually usable (the 16th bit is a parity bit for error checking). A word in memory can be used to represent either data (integers and real numbers up to a certain precision) or instructions. We will only need to understand how instructions are represented, so I’ll focus on that (for a description of how data is represented in AGC memory, see this page).
A word containing an instruction uses the first three bits to store an operation code (or “opcode”), and the remaining 12 bits to store an address.
Ok, let that sink in for a bit: three bits for the opcode. This means the AGC only had eight opcodes. This didn’t, however, mean that you only had eight instructions: several of the opcodes would behave differently depending on whether the address was a special address (like the all-zeroes address), or whether it contained an actual address in memory. Additionally, the AGC included a mechanism to use the fourth bit as part of the op code as well (this required calling an EXTEND instruction first, so the computer would know the following instruction had a special four-bit opcode).
Amusing side note: Apparently, the three bits for the opcode originated in the first version of the AGC (“Block I”), which legitimately needed only a three-bit opcode. The next version of the AGC (“Block II”, the one that actually had to fly to the moon, and the one I’m describing in this article) was stuck with this design decision, and the AGC developers had to creatively work around it. This is a situation that I’m sure many software developers out there are painfully familiar with (“three bits for the opcode ought to be enough for anybody!”)
In any case, even with the expanded instruction set, this was a pretty limited instruction set compared to modern processors. The instructions themselves are actually not relevant to our quest for the meaning of FLAGORGY, although they include the usual suspects: instructions to add register values, instructions to store/load values from/to memory, instructions to branch depending on a value, etc. If you’re curious, you can see the entire instruction set here.
Another interesting aspect of the instruction words is that the 12 bits for the address field were not enough to address the entire memory space, so the architecture uses bank switching to access the full range of addresses. But, again, we don’t need to know all the gory details (which you can find in pages 1–7 to 1–14 of this manual).
But how much memory did the AGC have? It actually had only 36,864 words of read-only memory (“fixed” memory in AGC lingo), and 2,048 words of read-write memory (or “erasable” memory). The actual amount of memory available to programmers was actually a bit less, since there were special addresses and ranges that could not be used by programmers.
Once again, take a moment to let this sink in: all the software required to fly a massively complex spacecraft to the moon and back had to fit in 36K words of memory. Not just that, the AGC didn’t support dynamically loading programs from secondary storage; instead the software for the AGC was literally hardwired into rope memory and, once this was done, it could not be modified.
On top of that, you only had 2K words to store “variables” in, with some of the “erasable” memory used by the astronauts and mission control to specify new pieces of code to run.
So, that’s the AGC architecture in a nutshell (and, again, I’m leaving out tons of details; see some of the links peppered throughout this section if you want to learn more).
Now, you might think that, since this was a custom-built architecture, it would’ve met all requirements of the lunar missions. However, you have to remember that, during the space race, everyone (from the rocket scientists to the software developers) was in uncharted territory and having to improvise a lot along the way, with some design decisions turning out to be less than ideal in hindsight (like the three-bit opcode). And, as it turns out, the AGC architecture still had another major issue…
The AGC Instruction Set: Still Too Limited
Even with the creative workarounds to the three-bit opcode, the instruction set was still too limited to meet the requirements of the Apollo missions. To quote the AGC4 Basic Training Manual (Section 2.1):
The Apollo Guidance Computer was designed with the idea that its weight, size, and power supply were costly items. Mission requirements warrant a hardware compromise of a word-length with a minimum of 15 bits and an instruction repertoire of 33 instructions with which to work. The result. therefore, is a small, fairly simple machine with limited abilities. While the AGC hardware provided for manipulation of single- and double-precision quantities, frequent need arose to handle multi-precision quantities, trigonometric operations, vector and matrix operations, and extensive scalar operations.
Faced with this problem, you could reasonably think of two possible solutions:
Design a new instruction set for the AGC: This is a solution that sounds ideal on paper, but is completely infeasible in practice, specially when you’re in the middle of a high-stakes race to beat the Soviets to the moon. Heck, it’s just plain infeasible, period. Why do you think we’re still stuck with x86 processors that have to be backwards-compatible with processors from the 70’s, and with banks that still run COBOL programs on ancient mainframes?
Build a library of software subroutines for the programmers: Ok, this is actually a more reasonable solution that relies on a bedrock of software development: abstraction. Just create subroutines that abstract away the limited instruction set, and provide higher-level operations for the developers (e.g., vector and matrix subroutines, so that developers don’t have to write these operations from scratch every time).
In fact, the AGC team recognized that a software-based solution was the way to go. The previous quote from their manual actually ends with this:
Thus. to fulfill the system requirements planned for the lunar missions within the constraints of hardware limitations, it is necessary to employ software to expand the capabilities of the AGC.
Unfortunately, the AGC team found that building a library of software subroutines was not doable (see pages 2–1 and 2–2 of the AGC4 Basic Training Manual for their rationale). In a nutshell, the cost of setting up the calls to the subroutines would result in too much wasted memory.
So, the AGC team had to come up with a more efficient solution…
Enter The Interpreter
To address the limited instruction set, the AGC team wrote a software virtual machine (or p-code machine) for the AGC to interpret an entirely new instruction set called the “interpretive language”. While this virtual machine (called “the interpreter”) used up precious memory space, it used a set of common resources to allow new instructions to be run, resulting in a more efficient memory footprint than a collection of subroutines.
In particular, the interpretive language used 7-bit opcodes and 15-bit address fields, using the following packed instruction format:
In other words, they packed two instructions in three words. Hackish? Sure, but when memory is very limited, this is a pretty darn good solution.
Of course, the AGC itself does not understand this format, so any time a developer wanted to run code in the interpretive language, they had to call an interpreter subroutine. In the AGC assembly language, this looked like this:
TC INTPRET“TC” is a native AGC instruction to “Transfer Control” to a subroutine (in this case, the interpreter). Once this is done, the AGC will interpret the subsequent instructions in memory as interpreter instructions, not as native AGC instructions. The source code for the INTPRET subroutine can be found here.
At this point, you may be wondering what all this has to do with the FLAGORGY subroutine (or you may have even forgotten that’s what we were building up to). Well, remember this is the FLAGORGY code:
FLAGORGY TC INTPRET # DIONYSIAN FLAG WAVING
CLEAR CLEAR
NOTHROTL
REDFLAG
CLEAR SET
LRBYPASS
MUNFLAG
CLEAR CLEAR
P25FLAG # TERMINATE P25 IF IT IS RUNNING.
RNDVZFLG # TERMINATE P20 IF IT IS RUNNING.i.e., FLAGORGY is written in interpretive language!
FLAGORGY explained, at last
So, what does FLAGORGY do? In the AGC assembly language, interpretive language instructions are written similar to the way they’re laid out in memory: two opcodes, followed by two addresses (the first one for the first opcode, and the second one for the second opcode).
So, we actually have only two instructions: CLEAR and SET. These instructions manipulate single-bit flags stored in memory, called “switches” in AGC lingo (it is not clear from the AGC documentation whether these flags mapped to visible indicators that the astronauts could see, or whether they were just internal flags).
The address fields are actually used to specify the switch numbers, and the meaning of each switch is described in the FLAGWORD_ASSIGNMENTS.agc file of the AGC source code:
- CLEAR NOTHROTL: “Permit full throttle”
- CLEAR REDFLAG: “Landing site redesignation not permitted”
- CLEAR LRBYPASS: “Do not bypass landing radar updates”
- SET MUNFLAG: “Servicer calls MUNRVG” (MUNRVG is a subroutine that performs some computations needed by the thrusting program)
- CLEAR P25FLAG: “P25 not operating”
CLEAR RNDVZFLG: “P20 not running”
P20 and P25 are programs used during the rendezvous between the command module and the lunar module.
Given that the FLAGORGY subroutine is located in file THE_LUNAR_LANDING.agc, and that it seems to belong to this program:
# *************************************
# P63: THE LUNAR LANDING, BRAKING PHASE
# *************************************All the above switch operations seem to make sense during the braking phase (for example, not allowing the landing site to be redesignated).
But why is it called FLAGORGY and why the “DIONYSIAN FLAG WAVING” comment? Before I understood what the code was doing exactly, but knowing that it was part of the braking phase, I thought it was just a self-congratulatory “WE’RE ABOUT TO LAND ON THE MOON! USA! USA! USA!”. However, now I think this was just a programmer basically saying “JUST UPDATING A WHOLE BUNCH OF FLAGS HERE”. In a modern program, you might encounter something like this (with less colorful language):
def update_braking_phase_flags(self):
# Lots of flags to update!
self.no_throttle = False
self.landing_site_redesignation = False
self.landing_radar_bypass = False
self.call_munrvg = True
self.p25 = False
self.p20 = FalseSo, there you have it. FLAGORGY updates a whole bunch of flags and/or possibly patriotically rejoices in the program’s upcoming landing on the moon.
Coda: Margaret Hamilton
As you read this article, it’s possible you were imagining the “AGC team” as a bunch of white-shirted, horn-rimmed-glasses-wearing NASA dudes. While it’s likely that many of them fit that stereotype, the lead Apollo flight software engineer was Margaret Hamilton, an oft-overlooked woman in the history of computing, seen here in an iconic photo with a printout of the AGC code:
If you had never heard about Margaret Hamilton, take a moment to read her Wikipedia page. You may also want to check out this recent interview and the article “Meet Margaret Hamilton, the badass ’60s programmer who saved the moon landing”.
