When was the relocatable object module invented?

Question

During the time when programming was done in machine codes, there was no need for object modules; it just wouldn't make sense. People would write the whole program they needed to run in "zeroes and ones", put it on a computer medium, and introduce it into the computer.

It is natural to assume that when assembly languages started to appear, their initial functionality was only to provide the ability to write machine code using opcode mnemonics and symbolic addresses to facilitate the familiar development process.

The notion of separate compilation which would require linking, allow libraries of pre-compiled modules, and necessitate a binary format combining relocatable code and a table of external symbols would likely come somewhat later, but, one would think, sometime between the first assembler (SOAP for IBM 650, 1955) and the prominently mentioned IBM/360 linkage editor (1964).

Unfortunately, none of the referred wiki pages focuses on that aspect of the history. When was the first relocatable object file format invented, then, and by what company, if not IBM?

Answer 1

Grace Hopper invented a kind of linking loader in 1951 for the Univac, as part of the A-0 "compiler" (not a compiler like we understand it today).

One must keep in mind that memory was extremely limited on those very early computers, so what today would be an object module with many routines was equivalent to handling a single subroutine at that time. Also, the result of a linked program couldn't be stored in memory (again because there was not enough of it), so it would be stored on tape in a first pass, and then this tape would be executed in a second pass.

In the paper Automatic Coding for Digital Computers, Grace Hopper describes it this way:

Compiling routines [i.e., a linker/loader in modern terms], which also read a pseudo-code, but which withdraw subroutines from a library and operate upon them, finally linking the pieces together to deliver, as output, a complete specific program for future running: [For example] UNIVAC A-compilers, BIOR, and the NYU Compiler System.

So just like a relocatable object module loader would operate on an executable and read in a pre-compiled modules from a library, resolve relocations and load the whole thing into memory, Grace Hopper's compiling routines would take a pre-compiled subroutine in a specific format, make changes to it (e.g. substitute fixed parameters for formal arguments if apropriate, and probably also "call/return" jumps similar to the relocation), and then "compile" (arrange) the modified subroutines together with the main program.

A similar idea seems to have appeared even a bit earlier, in David Wheeler's Programme Organization and Initial Orders for the EDSAC (1950), but I can't find an accessible version of that paper.

Edit

I wouldn't say that the development of the idea of a linker preceeded symbolic coding. There's a fascinating collection of sessions presented at the MIT Summer Session 1954 called Advanced Coding Techniques. Among other things it contains a bit more details about the A-2 "linker" (p.30), and various forms of "Automatic Coding Systems" (p. 55) like the IBM 701 Speedcoding System (a sort of interpreted, more complex ISA) by John Backus (p. 41).

But earlier on in the collection, it becomes quite clear that various forms of symbolic coding were already in widespread use, and practice was far removed from "zeroes and ones".

Page 7 (Whirlwind I was designed 1947):

• Mnemonic coding: it is convenient for humans to use suggestive letter pairs or triples to denote the operation sections of instructions, or to identify subroutines. Machines usually ultimately require a digital representation. This is a simple change of type 1b. Whirlwind I has always performed this change on the operation sections of instructions.

• Identification of words: the control unit of a machine can operate on words only if it is given the absolute addrssses. Humans find it more convenient when coding to use relative or symbolic addresses. The necessary change is of type 2 and can be performed by the machine, usually before execution of the routine.

• Representation of numbers: these may originate as, say, .023, 47.10^-5, or 7/45. The conversion to the standard machine form can be performed by the machine, though the routine required to do this is often lengthy. Type 1b.

And page 21:

Stanley Gill described a technique used on the Illiac which makes it unnecessary to list constants separately and refer to them in the program; instead, the constants may be written directly in the instruction which use them; thus, instead of writing

ccf al
al, +123

one might write simply

ccf +123

And:

Donn Combelic gave, as an example of mnemonic coding, the way in which input and output editing is requested in the M.I.T. Comprehensive System. Three letters specify respectively the medium, whether input or output, and the notational form; this may be followed by a sample number.

There's also a webpage which claims that the "Initial Orders" system I mentioned above should be called the first assembler. That would have been 1951, way before SOAP.

Edit:

And here is Grace Hopper talking about how subroutines were "invented" by borrowing notebooks during her work on the Aiken Mark 1 in World War 2, and she already hints at the necessity of "relocating" them ("when you integrate a piece of code into another program, you frequently have to add addresses, and programmers can't add").