Would a C compiler for the Apollo Guidance Computer be plausible?

Question

The Apollo Guidance Computer was used to control the command/service module and lunar module on the missions to the moon. (Definitely a retrocomputer!) As noted in this answer, programs were written in assembly language. There are several emulators available today, including one which can be run in a web browser.

Even though the AGC was invented before the C programming language, is a C compiler possible for this architecture? If not, why?

For the purposes of this question, a satisfactory compiler would support all of the C operators (including arithmetic, boolean, structure, and pointer) the original purpose of the AGC: notably, real-time signal processing and control. It does not have to be a lunar mission; the AGC was also used in a Navy rescue submarine and in the first airplane with computer fly-by-wire control.

Less important but nice to have:

• Originally I included structure and pointer operations as a requirement. However, arrays with indices would probably suffice.
• Ability to act as a general-purpose platform.
• Compliance to one or more standards (including but not limited to K&R, ANSI, and Embedded C).
• Floating point. The original software used fixed-point numbers, with subroutines for subtraction, multiplication, and division. Such numbers can be declared with Embedded C's fixed type. We'll call that good enough, even if it is possible to implement IEEE floating point.
• Standard libraries or system calls (i.e. stdio should not be a concern).

The compiler would be hosted on another system, not on the AGC itself.

I hope these clarifications help!

(Photograph of Apollo Director of Software Engineering Margaret Hamilton, next to the source code of her team)

Answer 1

One of the biggest problems with C for this architecture is the fragmented address space.  You would almost want some extensions for C that direct the compiler where to locate (global) data so that the various data would be accessible in an easy and known way from the code that uses it.  Somewhat reminiscent of FORTRAN Common Blocks...

Consider for a minute the 8086 extended, 20-bit addressing.  Compilers for that architecture had to choose a memory layout model for program execution.   There are basically three options:

• Stick with 16-bit pointers — and forgo the larger memory for the program (i.e. everything fits in 64k), leaving that additional address space for running multiple programs (rather than for running larger programs).

• Use 32-bit pointers to store 20-bit addresses — that means that every pointer dereference or array indexing operation required multiple instructions, involving swapping of segment registers and the like.  So, a simple *p++ = *q++; becomes a dozen or more instructions, whereas it is ideally a single instruction.

• Use 16-bit spaces for each of code, global data, stack, and heap.  Thus programs of 256k are possible with 64k of each of the above.  This was a reasonable option for Pascal due to being a less pointer-oriented (by having reference parameters, for example), but not as much for C, which is much more pointer happy (e.g. using pointers instead of reference parameters).

Architectures with paged memory banks using segment-specifying registers are surprisingly easy to program by human in assembly but hard to work by a compiler.  These architectures typically use a common base page, perfect for some of the globals, but easy to overflow if you put all the globals there.  So, again, you would almost want some location directives in C to inform the compiler that these globals should go in the coveted base page, vs. elsewhere.

Apparently the AGC has two levels of memory segments, the second due to the expansion by the Block II (via the SBank/SuperBank bit).  These things tend to wreak havoc with models of code generation and C's expectation that a universal full-address-space-sized pointer can refer to anything: code, data, stack, heap...

That's not to say it couldn't be done, but you'd want a number of language extensions, or else you'd find it extremely difficult to reach the efficiency of hand-written assembly.

Answer 2

A full conforming compiler would be impractical, but it would probably be possible to write a compiler for a subset of the language which a couple of features removed:

1. While it would be possible for a compiler to emulate recursion, code that needs to support re-entrancy would likely be much less efficient that code which doesn't. Given that the Standard imposes no requirement that compilers support recursion usefully (there's no guarantee that it be possible to nest any particular function more than one deep without bombing the stack) simply refusing to support recursion would seem more practical than generating re-entrant code for functions, and more "honest" than accepting such code but behaving in goofy fashion if functions are invoked recursively.

2. The Standard would require that an implementation support floating-point math on values with a mantissa of greater than 32 bits. Limiting floating-point computations to a 32-bit or even 16-bit mantissa would allow them to be handled with smaller and faster code than would be possible with a standard-conforming "double".

Usable C compilers exist for microprocessors whose architecture is even less "C-friendly" such as the CDP1802 (interesting chip, but the code to accomplish something like "ptr[index] = 1234;" would take 21 instructions) so the Apollo computer, which has an INDEX instruction, doesn't look too bad by comparison, at least if code doesn't need to support re-entrant functions.

Answer 3

I'm aware this is an old thread, but I thought it would be worth a brief comment given the relevance of some work I've done.

Personally I hope the answer to this question is yes, since last year I started a personal project to implement an LLVM compiler for AGC (LLVM, Clang).

I found it took a lot of effort just to manipulate the existing framework of the compiler, designed for modern processors, to be able to represent the funky aspects of the AGC assembly and programming model. For example, the blurred lines between what is a register and what is 'memory' required quite a bit of thought.

There's also the question of searching through the entire pipeline of the compiler to track down places where numbers are assumed to be two's complement. Constant folding comes to mind as something that would completely mess up your code if it made this assumption.

I only have experience with LLVM, but I would imagine even to an expert, writing a GCC backend would throw up the same class of issues. I'd expect there would be more chance of success from writing a well designed compiler from scratch.

For those who are interested I gave a talk this year at FOSDEM on this: https://fosdem.org/2019/schedule/event/llvm_apollo/

Answer 4

Even though the AGC was invented before the C programming language, is a C compiler possible for this architecture?

To begin with it depends on the value of for :))

• If the question is about that a compiler can be writen (on some computer) to produce code for the AGS (aka a crosscompiler), the answer is a clear Yes.

• If it asks for a compiler running on the AGS it gets harder. Not so much for having a compiler in it's 30 kWords of program ROM, but for not so theoretical a way of inputing a source to be compiled. Here I would go for a theoretical yes, but, by all love for low level interfaces, in praxis the answer is No.

For the purposes of this question, a satisfactory compiler would support all of the C operators (including arithmetic, boolean, structure, and pointer). It would not need to support all of the standard libraries or system calls (i.e. stdio should not be a concern).

"Satisfactory" is a nice word - just not very clear. Is it satisfactionary that it for example the only data type available is a 15 bit word, or is floating point mandatory? Does it only need to follow basic K&R, or is C99 (or C11) a goal?

The compiler would be hosted on another system, not on the AGC itself.

Sounds good. So the answer is a clear Yes.

It is possible to do a C compiler (even on contemporary computer to the AGC) following K&R, even including FP, whose output can be loaded (well, wired) into the AGC. For doing FP it might have to carry a considerable large runtime (library), so C without FP and only a 15 bit integer datatype might be the prefered solution to keep as much as possible ROM for useful code.

And then there is the question asked in the title (emphasis by me) which somewhat got lost in the question text:

Would a C compiler for the Apollo Guidance Computer be plausible?

Here the answer is a clear No.

The result of a C compiler will alway be inferiour to what an Assembler programmer can squeeze out. Considering the small code space (36 kWords) and complex job to handle, Assembly might have been the only way to go.

If at all, a language more suited to system programming than C would have been used - most likely something similar to MOL-360 or PL/1 (or rather its specialized cousin PL/S).