75

I always wonder this, and perhaps I need a good history lesson on programming languages. But since most compilers nowadays are made in C, how were the very first compilers made (AKA before C) or were all the languages just interpreted?

With that being said, I still don't understand how even the first assembly language was done, I understand what assembly language is but I don't see how they got the VERY first assembly language working (like, how did they make the first commands (like mov R21) or w/e set to the binary equivalent?

Improve this question
8
  • 9
    There was a comically inept programmer on my team once, where all he did was complain about C#. We used to joke about a fictional language he invented called Crunk. A little known fact about Crunk, it is the first language where the compiler was ALSO written in Crunk. :)
    – maple_shaft ♦
    Commented Jun 30, 2011 at 12:19
  • 2
    Why would someone complain about C#? has he never used smalltalk or Lisp? lol
    – user6791
    Commented Jun 30, 2011 at 13:38
  • 2
    possible duplicate of C compiler and Dennis Ritchie
    – vartec
    Commented Jun 30, 2011 at 14:02
  • 4
    @maple_shaft: to be fair, the gcc compiler is written in C. That actually isn't a problem if you have a good cross compiler to compile the first version. The first C compiler, of course, had to be written in another language.
    – Scott Whitlock
    Commented Jun 30, 2011 at 15:03
  • 5
    possible duplicate of How was the first compiler written?
    – Greg Hewgill
    Commented Jun 30, 2011 at 19:35

9 Answers 9

Reset to default
92

Ha, I've done this. Many CPUs have simple, fixed-size instructions that are just a couple of bytes long. For a simple CPU like a Motorola 6800 for example, you could fit all of its instructions on a single sheet of paper. Each instruction would have a two-byte opcode associated with it, and arguments. You could hand-assemble a program by looking up each instruction's opcode. You'd then write your program on paper, annotating each instruction with its corresponding opcode. Once you had written out your program, you could could burn each opcode in sequence to an EPROM which would then store your program. Wire the EPROM up to the CPU with just the right instructions at the right addresses, and you have a simple working program. And to answer your next question, yes. It was painful (we did this in high school). But I have to say that wiring up every chip in an 8-bit computer and writing a program manually gave me a depth of understanding of computer architecture which I could probably not have achieved any other way.

More advanced chips (like x86) are far more difficult to hand-code, because they often have variable-length instructions. VLIW/EPIC processors like the Itanium are close to impossible to hand-code efficiently because they deal in packets of instructions which are optimized and assembled by advanced compilers. For new architectures, programs are almost always written and assembled on another computer first, then loaded into the new architecture. In fact, for firms like Intel who actually build CPUs, they can run actual programs on architectures which don't exist yet by running them on simulators. But I digress...

As for compilers, at their very simplest, they can be little more than "cut and paste" programs. You could write a very simple, non-optimizing, "high level language" that just clusters together simple assembly language instructions without a whole lot of effort.

If you want a history of compilers and programming languages, I suggest you GOTO a history of FORTRAN.

Improve this answer
10
  • 28
    . . . and shoudn't that be "... I suggest you JMP to a history ..."
    – Binary Worrier
    Commented Jun 30, 2011 at 12:33
  • 10
    @Dave: You realise you've doomed yourself to death by Velociraptor?
    – Binary Worrier
    Commented Jun 30, 2011 at 12:38
  • 7
    They "knew" because they were literally hard-wired to perform that operation when they saw a 101010100 signal for a given instruction. They actually have an on-chip unit responsible for instruction decoding instructions: en.wikipedia.org/wiki/Decoder
    – Dave Markle
    Commented Jun 30, 2011 at 12:54
  • 4
    @Michael: That's absolutely true, and the Itanium instruction set is a great example of that. It relies on the compiler to detect paterns in instruction-level parallelism that would enable it to execute more than one instruction per clock cycle. Even in x86, new instructions are being added which are meant to service common patterns found in compiled code, such as the FMA (fused multiply-add) instruction.
    – Dave Markle
    Commented Jun 30, 2011 at 13:25
  • 8
    Worth adding: the compiler for a new language, when written in that same new language, is sometimes compiled with a "proto-compiler" written in another language that produces demonstrably-correct, but horrifically-inefficient code. Once so compiled, it is then run on itself to produce a reasonably-fast compiler. Compare Von Neumann Machine. :D
    – BMDan
    Commented Jul 1, 2011 at 1:52
59

That's what compiler bootstrapping is about (since no one mentioned how it's called =).

the process of writing a compiler (or assembler) in the target programming language which it is intended to compile. Applying this technique leads to a self-hosting compiler.

Many compilers for many programming languages are bootstrapped, including compilers for BASIC, ALGOL, C, Pascal, PL/I, Factor, Haskell, Modula-2, Oberon, OCaml, Common Lisp, Scheme, Java, Python, Scala and more...

The chicken and egg problem

If one needs a compiler for language X to obtain a compiler for language X (which is written in language X), how did the first compiler get written? Possible methods to solving this chicken or the egg problem include:

  • Implementing an interpreter or compiler for language X in language Y. Niklaus Wirth reported that he wrote the first Pascal compiler in Fortran.
  • Another interpreter or compiler for X has already been written in another language Y; this is how Scheme is often bootstrapped.
  • Earlier versions of the compiler were written in a subset of X for which there existed some other compiler; this is how some supersets of Java, Haskell, and the initial Free Pascal compiler are bootstrapped.
  • The compiler for X is cross compiled from another architecture where there exists a compiler for X; this is how compilers for C are usually ported to other platforms. Also this is the method used for Free Pascal after the initial bootstrap.
  • Writing the compiler in X; then hand-compiling it from source (most likely in a non-optimized way) and running that on the code to get an optimized compiler. Donald Knuth used this for his WEB literate programming system...
Improve this answer
2
16

Ultimately all computers operate on binary codes, which are fed into the CPU. These binary codes are perfectly natural for a CPU, but also perfectly useless for human beings. One of the first ways to write a program was by punching holes into cards. The position of the holes represented a particular bit position within a word, and the presence or absence of the hole was interpreted as a zero or a one. These cards were put into the right sequence in a box, and then fed into a card reader, which effectively converted them into binary code for the CPU (and your life was effectively forfeit if you dropped the box).

Obviously the very first programmers worked out the binary codes one by one and had a machine to punch the cards. This is essentially assembly language programming on your hands and knees. Once you have that, you can create all the other stuff from it: a simple text editor, an assembly language compiler (to convert the text assembly statements into binary codes), a linker and a loader. And the rest, as they say, is history.

Improve this answer
3
  • 5
    Before cards you had a set of switches for the address, a set for the data word and a switch to load the data. You programmed each memory address individually by setting the address and data switches with the binary representation and flicked the load switch on then off. It took ages but the program was only a few words long - bytes had not been invented then.
    – uɐɪ
    Commented Jun 30, 2011 at 12:35
  • 5
    ...And before that, you had to rewire it. Funfunfun!
    – Michael K
    Commented Jun 30, 2011 at 13:23
  • 1
    Yes, but when you had to do that, it wasn't really what we'd think of as a modern computer, as the Von Neumann architecture hadn't been invented yet.
    – Dave Markle
    Commented Jul 4, 2011 at 13:22
9

It is possible (if tedious) to write direct machine code. Maybe you write the program down in assembler on a piece of paper, and then you translate it by hand into the numeric machine code instructions which you enter into the machine memory. You can even skip the assembler-on-paper step if you have memorized the numeric values of all the machine code instructions - not uncommon in those days, believe it or not!

The very first computers were directly programmed in binary by toggling physical switches. It was a great productivity improvement when hardware evolved to let the programmer (or the data entry assistant) enter code in hexdecimal numbers via a keypad!

A software assembler only became relevant when more memory became available (since assembler code takes up more space than raw machine code) and hardware evolved to allow alphanumeric input. So the first assemblers were written directly by people fluent in machine code.

When you have an assembler, you can write a compiler for a higher level language in assembler.

The story for C has multiple steps. The first C compiler was written in B (a predecessor to C) which in turn was written in BCPL. BCPL is a pretty simple language (for example it doesn't have types at all), but still a step up from raw assembler. So you see how gradually more complex languages is build in simpler languages all the way back to assembler. And itself C is a pretty small and simple language by todays standards.

Today, the first compiler for a new language is often written in C, but when the language reaches a certain maturity it is often rewritten "in itself". The first Java compiler was written in C, but later rewritten in Java. The first C# compiler were written in C++, but recently it has been rewritten in C#. The Python compiler/interpreter is written in C, but the PyPy project is an attempt to rewrite it in Python.

It is not always feasible to write a compiler/interpreter for a language in the language itself though. A JavaScript interpreter written in JavaScript exists, but the compilers/interpreters in current browsers are still written in C or C++ for performance reasons. JavaScript written in JavaScript is simply too slow.

But you don't have to use C as the "starting language" for a compiler. The first F# compiler was written in OCaml, which is the other language which is most closely related to F#. When the compiler was complete, it was rewritten in F#. The first compiler for Perl 6 was written in Haskell (a pure functional language very different from Perl) but now has a compiler written in C.

An interesting case is Rust, where the first compiler was written in OCaml (now it is rewritten in Rust). This is notable because OCaml is generally considered higher level than Rust, which is a closer-to-the-metal systems language. So it is not always higher-level languages implemented in lower-level languages, it might also be the other way around.

Improve this answer
8

A little googling turns up EDSAC Initial Orders from the late 40s. Since it was the first assembler, it was probably coded in machine language.

Later came assemblers for other machines, like SOAP I and II for the IBM 650. SOAP I was also probably coded in machine language, though I haven't found the definitive statement.

A little later came Fortran (formula translator), for the IBM 704. Presumably it was written in assembler for the 704. An early assembler for the 701 is credited to Nathan Rochester.

If you want to get an idea how to program a computer in machine language, check out one of my favorite sites, Harry Porter's relay computer.

Improve this answer
3
  • Holy crap, the Harry Porter (almost said harry potter lol) homebuilt computer is AWESOME. I wish I understood how something like that was built :(.
    – user6791
    Commented Jun 30, 2011 at 14:58
  • 1
    @Sauron: Harry Porter would like nothing better than to tell you. Off that page he's got a beautifully-crafted powerpoint explaining it all. It does assume some basic knowledge of circuitry, but that's not too hard to get.
    – Mike Dunlavey
    Commented Jun 30, 2011 at 16:14
  • I know Im just messin ^_^, regardless it's a very impressive machine and im sure many wizard hours were put into it :).
    – user6791
    Commented Jun 30, 2011 at 17:43
3

Assuming you're starting with a bare instruction set and nothing else, you'd start by creating a minimal, just-barely-functional assembler or compiler that can load a file, parse a minimal subset of the target language, and generate an executable file as output, by writing the raw machine code using a hex editor or similar.

You'd then use that just-barely-functional compiler or assembler to implement a slightly more capable compiler or assembler that can recognize a larger subset of the target language. Lather, rinse, repeat, until you have the final product.

Improve this answer
3

It is not so difficult, as it seems. In the childhood ;) I made some x86 disassembly in mind.

You even don't need to learn it especially. It just happen, when you're able to program in ASM and then trying to fix a third-party binary using interactive disassemblers. Or when writing your own protection with code encryption.

I.e. sometimes you're migrating even from language to codes with no wonder.

Improve this answer
1

The first compilers were implemented using assembly language. And the first assemblers were implemented by coding programs in binary ...

It is not THAT long ago that programming in binary was still a skill that people used.

When I was an undergraduate, I remember doing a programming exercise that entailed writing a tiny program in PDP-8 (I think) machine code, entering it via the front panel switches, and running it. I couple of years later, I bought myself a 6502 system development kit that had a hex keypad for entering programs ... and 4k bytes of RAM.

Improve this answer
-3

A VERY SIMPLE ANSWER Suppose that we write a hardwired program and store it in ROM. It can be considered as compiler. So I simply want to say is that the very first compiler was hardwired. As the technology improved these simple compilers were then used to write high level compilers.

Improve this answer