Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

The first compiler was written by Grace Hopper in 1952 while the Lisp interpreter was written in 1958 by John McCarthy's student Steve Russell. Writing a compiler seems like a much harder problem than an interpreter. If that is so, why was the first compiler written six-years before the first interpreter?

share|improve this question
58  
because there was more need for a compiler than a interpreter at the time –  ratchet freak Jul 28 at 13:27
18  
To compile the first interpreter? :P (only partially tongue in cheek, an interpreter is complex (more so than a simple compiler) and it would be nasty to write an efficient one in machine code) –  Vality Jul 28 at 14:07
4  
If you take your CPU executing instructions as interpreting them, which is the way I see it (however implemented via hardware), then the claim that the first interpreter was written after the first compiler doesn't hold. Btw, I know this doesn't help with the question/answer. It's just meant to be an interesting comment on a different point of view. –  Pedro Henrique A. Oliveira Jul 28 at 14:31
11  
McCarthy did not write the LISP interpreter. McCarthy invented a mathematical formalism. Steve Russell, one of the students in the MIT AI Lab at the time, realized he could write an interpreter to execute McCarthy's flights of fancy, and the rest is history. –  John R. Strohm Jul 28 at 15:01
5  
In fact, I heard that McCarthy believed LISP to be unimplementable. It was Russell who realized that McCarthy's universal function from the LISP manual a) was an interpreter and b) was implementable. –  Jörg W Mittag Jul 28 at 16:10

9 Answers 9

up vote 75 down vote accepted

Writing a compiler seems like a much harder problem than an interpreter.

That might be true now, but I would argue that it was not the case some 60 years ago. The reasons why I think so are:

  • With interpreter, you have to keep both it and the program in memory. In an age where 1kb of memory was a massive luxury, keeping the running memory footprint low was the key. And interpreting requires a bit more memory than running a compiled program.
  • Modern CPUs are extremely complex with a huge catalogs of instructions. So writing a good compiler is truly a challenge. Old CPUs were much simpler, so even compilation was simpler.
  • Modern languages are much more complex than old ones, so even compilers are much more complex. Old languages would thus have simpler compilers.
share|improve this answer
50  
and without a compiler you'd have to write the interpreter in assembly –  ratchet freak Jul 28 at 13:29
28  
The first compilers where people. (When people are interpreters we don't need computers). Then someone must have considered writing a compiler in a compiled language (the only ones they had, but as the time compiled my humans). –  richard Jul 28 at 13:37
1  
Actually.... I recently read that the Apollo Guidance Computer used in the 60s moon flights had an interpreter: wiki entry "...the interpreter provided many more instructions than AGC natively supported..." I suppose this "interpreter" was more like the "Sweet 16" interpreter embedded in old Apple II computers than something like LISP. –  Joe Rounceville Jul 28 at 15:17
2  
@ratchetfreak And it was. As were the first compilers. –  RBarryYoung Jul 28 at 17:07
2  
@richard: When people were interpreters/calculators their job title was called "computer". So when people were interpreters they were the computers, literally. The Manhattan project employed thousands of "computers" (actual job title, seriously) to which the nuclear physicists sent their calculations by mail to be executed. Actually, the project also employed mathematicians who broke down the calculations from the engineers who formulated the calculations from the theories of the physicists to be sent the the "computers". –  slebetman Jul 30 at 9:04

Others have mentioned parts, but I think the fundamental point is that the computing hardware environment of the 1950s, meant that only a compiler was feasible, or desirable, given the batch-oriented processing of computers in the 1950s.

At the time the better user-interfaces were primarily limited to punch cards, and teletype printers. The first Cathode-Ray Tube (CRT) display on a computer was I believe the SAGE system which was first operational in 1961. So the interactive nature of an interpreter was not preferable or natural until much later.

Numerous computers in the 1950s used front panel switches to load instructions, and the output was simply rows of lamps/LEDs, and hobbyists even used front-panel switches & LEDs into the 1970s, such as the infamous Altair 8800.

Other hardware limitations: the extreme limited availability of primary memory (e.g. RAM) in computers in the 1950s (prior to the semiconductor integrated circuit, which wasn't until 1958) was limited to magnetic core memory or delay line memory which was measured in bits or words, no prefix, and combined with the slowness of secondary, storage memory (e.g. disk or tape) meant that it would be considered wasteful, if not unfeasible to have much of the memory used for the interpreter, even before the program being interpreted was loaded.

The limitations of memory was still a factor for concern and criticism when the team lead by John Backus at IBM created the FORTRAN compiler in 1954-57. It only achieved success because it was an optimizing compiler.

Most of the computers in the 1950s barely had any Operating System, let alone modern features such as dynamic linking and virtual memory management so the idea of an interpreter was too radical and impractical at that time.

Addendum

The languages of the 1950s were primitive. They consistent of a small handful of operations, many times the influenced by either the underlying hardware's instructions or the problem definition of their targeted use.

At that time, computers were rarely general purpose computers in the sense we think today. They were reprogrammable without having to be rebuilt was considered a revolutionary concept compared to the limitations of electromechanical machines (typically calculators) people had been using previously to compute or calculate answers (the majority of applications in the 1950s were numeric in nature).

From a Computer Science point of view, compilers and interpreters are both translators, and roughly equal in complexity to implement.

share|improve this answer
    
Did computers use teletypes prior to the advent of time sharing? I would have expected them to either use line printers or spool to tape. Otherwise, the 1-8 seconds the computer would have to wait after each line of text would represent a 1-8 seconds that the computer could have been--but wasn't--doing something useful. –  supercat Jul 28 at 21:10
2  
@supercat - yes, teletypes were used, but they were far from "interactive". The first computer I programmed had a memory consisting of 18 bit words - 1K of them. The memory itself was a rotating drum, so when you turned the computer on you had to wait until the memory came up to speed. It had a teletype attached and you could A) read a character typed in from either the keyboard or read by the paper tape reader (from the point of view of the computer both were the same), B) write a character to the "printer" of the teletype. Ah, great days - GREAT days..! IS MY GRUEL WARM YET?!?!? :-) –  Bob Jarvis Jul 29 at 2:31
    
@BobJarvis: What year would that have been? –  supercat Jul 29 at 2:49
1  
@supercat - 1973 - but the computer in question (an EDP-18, by Educational Data Products) was relatively elderly even then. Still, it was what we had (and having any computer to mess with in high school in the early-mid-70s was unusual) so as we thought it was pretty amazing. :-) –  Bob Jarvis Jul 29 at 10:53
2  
This is a much better and complete answer than the accepted one. –  Jim Garrison Jul 29 at 19:37

The first programming languages were quite simple (no recursion for example) and close to machine architecture which was itself simple. The translation was then a straightforward process.

A compiler was simpler as a program than an interpreter that would have to keep together both the data for program execution and the tables to interpret the source code. And the interpreter would take more space, for itself, for program source code and for symbolic tables.

Memory could be so scarce (for both cost and architectural reasons) that compilers could be stand-alone programs that overwrote the operating system (I did use one of these). The OS had to be reloaded after compiling in order to run the compiled program. ... which does make it clear that running an interpreter for real work was simply not an option.

To be true, the simplicity required of compilers was such that compilers were not very good (code optimization was still in infancy, when considered at all). Hand written machine code had, at least until the late sixties in some places, the reputation of being significantly more efficient than compiler generated code. There was even a concept of code expansion ratio, that compared the size of compiled code to the work of a very good programmer. It was usually greater than 1 for most (all?) compilers, which meant slower programs, and, much more importantly, larger programs requiring more memory. This was still an issue in the sixties.

The interest of compiler was in programming ease, especially for users who were not computing specialists, such as scientists in various fields. This interest was not code performance. But still, programmer time was then considered a cheap resource. The cost was in computer time, until 1975-1980, when the cost switched from hardware to software. Which means that even compiler were not taken seriously by some professionals.

The very high cost of computer time was yet another reason for disqualifying interpreters, to the point that the very idea would have been laughable for most people.

The case of Lisp is very special, because it was an extremely simple language which made it feasable (and the computer had become a bit bigger in 58). More importantly, the Lisp interpreter was a proof of concept regarding the self definability of Lisp (meta-circularity), independently of any issue of usability.

Lisp success is due largely to the fact that this self definibility made it an excellent testbed for studying programming structures and design new languages (and also for its convenience for symbolic computation).

share|improve this answer
2  
My, how bold. –  Pharap Jul 30 at 6:12
    
@Pharap Is that improper style? My purpose is to make key information easier to find, while allowing for a freer style than simple enumeration of facts. I must confess that it does not really seem very effective on this SE site. –  babou Jul 30 at 6:19
    
@anonymous-downvoter Downvoting without an explanatory comment shows that someone may be stupid. However, it does not say who. –  babou Jul 30 at 6:23

The other part of the equation is that compilers were a step abstraction above an assembler. First we had hard-coded machine code. "We" were the assembler. Every jump and offset, etc. was hand-calculated into hex (or octal) and then punched into paper tape or cards. So when assemblers came on the scene, it was a huge time-saver. The next step was macro assemblers. That gave the capability to write a macro that would expand into a set of machine instructions. So Fortran and Cobol were a huge step forward. The lack of resources (storage, memory, and cpu cycles) meant that general purpose interpreters had to wait for technology to grow. Most early interpreters were byte-code engines (like Java or CLR of today, but with much less capability). UCSD Pascal was a very popular (and fast) language. MS Basic was a byte-code engine under the hood. So the "compile" was really to generate a byte-code stream that was actually executed by the runtime.

In terms of instruction overhead, it totally depended on what processor was being run. The industry went through a big RISC vs CISC turmoil for a while. I personally wrote assembler for IBM, Data General, Motorola, Intel (when they showed up), TI, and several others. There was a fairly significant difference in instruction sets, registers, etc. that would influence what was required to "interpret" a p-code.

As a time reference, I started programming in the phone company around 1972.

share|improve this answer

If you are not holding everything in memory, compiled code is much more quick. Don't forget, that in these times functions were joined to the compiled code. If you are not compiling, you do not know what functions you'll need. So, you are calling functions from... Oh, not from disk yet, we are in early 50-ties, but from cards! In runtime!

Of course, it is possible to find a workarounds, but they were not found yet, for languages were very simple and not so far from machine code. And compiling was easy and enough.

share|improve this answer

Before a looping program can be interpreted, it must be stored in a medium which can be read repeatedly. In most cases, the only suitable medium would be RAM. Since code will typically be entered on punched cards which--for human readable languages--are likely to be largely empty, some sort of processing must be performed upon the code before it is stored in RAM. In many cases, processing the punched-card text into a form which is suitable for direct execution by the processor is not really any more difficult than processing it into a form which could be efficiently handled via an interpreter.

Note that the goal of the early compilers was not to produce an assembly-language or object-code file on disk, but rather to end up code in RAM that was ready to execute. This is actually surprisingly easy when there's no operating system to get in the way. A compiler can generate code starting at one end of memory and allocate variables and branch targets starting at the other. If a statement is marked with label "1234", the compiler will store in variable called "1234" an instruction to jump to the current code generation address, creating that variable if it doesn't exist. A statement "goto 1234" will create a variable "1234" if it doesn't exist, and then jump to that variable [which will hopefully have a jump to the proper location stored in it before that statement executes]. Note that the compiler doesn't have to do anything special to allow code to goto a label which hasn't been defined yet, since it knows when the goto compiles where it's going to jump--to a variable. That may not be the most efficient way to generate code, but it's adequate for the sizes of programs that computers were expected to handle.

share|improve this answer
1  
Disk? Ummmm...no. Tape. Big, slow, reel-to-reel tapes. And lots of them. I remember going to a lecture given by Grace Murray Hopper (doubly interesting to me because I was a systems analysis major AND a midshipman in the Navy ROTC detachment on campus, and CAPT Hopper was a serving naval officer). She related a story where, she said, she came up with the idea of writing unused parts of a program to tape - she called it "using auxiliary storage". "But", she said, "the idea didn't catch on until IBM did the same thing and called it Virtual Memory". CAPT Hopper really disliked IBM... :-) –  Bob Jarvis Jul 29 at 2:42
    
@BobJarvis: I hadn't considered that aspect, but the same general one-pass design that would be used for compiling ready-to-run code to RAM could work well with a tape drive; the output from the compiler would go to tape, then the tape would be rewound and read into sequential memory addresses and run directly, without needing to have any part of the compiler in memory at the same time. –  supercat Jul 31 at 2:50

Before the first compiler was written, people wrote assembler code which was a huge progress compared to plain binary code. At the time, there was a strong argument that code compiled by a compiler would be less efficient than assembler code - at that time the relation of (cost of computer) to (cost of programmer) was much, much different than today. So there was strong resistance against compilers from that point of view.

But compilers are an awful lot more efficient than interpreters. If you had suggested writing an interpreter at that point in time, people would have thought you are crazy. Can you imagine buying a million dollar computer and then wasting 90% of its power to interpret code?

share|improve this answer
    
I don't know much about 1950s computers, but at least for the simple von Neumann machines of later decades, interpreter overhead would be two to five instructions (maybe four to ten cycles total) per interpreted instruction: Decode, indirect jump, maybe decode additional arguments. If you make the interpreted instruction set sufficiently high-level (so you execute several machine instructions per interpreter instruction) this would be less than 90% and perhaps even acceptable. See also: Forth. –  delnan Jul 28 at 14:57
3  
Before the first compiler was written, the majority of programs were actually written in actual machine code, not assembly language (op-codes mnemonics). –  mctylr Jul 28 at 15:40
2  
@delnan Those systems ran with clocks in the kiloHertz, so wasting a 3-5 time reduction in performance would likely be the difference between the program completing successfully before the system fails due to hardware failure (i.e. vacuum tube blown) or not. Hardware failures were a daily occurrence in the 1950s if I recall correctly. –  mctylr Jul 28 at 15:45
    
delnan: Show me an interpreter that can interpret with a five instruction overhead. And Forth is not an interpreted language, it is an abomination :-). Sorry, I mean a threaded language. Something like BASIC takes gazillions of instructions to interpret one statement. –  gnasher729 Jul 28 at 16:18
    
@gnasher: In 1974, I built a high-performance BASIC interpreter for Keronix (ahem, Data General Nova clones) that used a byte-oriented P-code to encode the BASIC statement. It took about 25-50 machine instructions to "interpret" a pCode, 10 of them for the byte fetch itself. (I did a token based one back in 1969 that took more because it had to in effect re-parse the expressions). But it wasnt and isnt "gazillions". –  Ira Baxter Jul 28 at 19:28

Another factor: When the first compilers were written the cost of machine time was a lot higher than it is now. Interpreters use a lot more machine time.

share|improve this answer

Because interpreters need compilers in order to work.

The above statement isn't really true. Strictly speaking, you can make an interpreter without ever using or otherwise interacting with a compiler. But the results of doing this wouldn't wouldn't look very much like what I think you mean by those terms.

In the strict sense, compilers and interpreters do entirely different things. A compiler reads text from some source, and transforms it into some other format: assembly language, machine code, another high-level language, a data structure, or whatever else. An interpreter, meanwhile, takes in a data structure of some kind, and performs instructions based on it.

What we tend to think of as a "compiler" nowadays is actually a compiler that has been paired with a code generator: a program that takes in data from some source, and outputs code in some format based on what it sees. That's a fairly intuitive use for compilers, and it was one of the first things compilers were created for. But if you look at it another way, this seems very similar to what an interpreter does. It always outputs code instead of performing more general operations, but the principle is the same.

If we look at it from the other side, an interpreter needs to get its data from somewhere. This is just data, so you can build it up in the same ways you'd build up any other kind of data. Since we're talking about interpretation, it seems natural that you could build your data based on instructions in a text file. But to do that, you'd need something to read in the text and create your data structure, and that's a compiler. It's hooked up to the interpreter instead of to a code generator, but it's a compiler all the same.

That's why compilers were written first. The idea of interpreting data structures wasn't new even when compilers were conceived, but compilers were the "missing link" that let programmers build those structures out of text.

share|improve this answer
    
The original Basic interpreter for the Apple ][ was, from what I understand, hand-translated into machine code and never existed in machine-readable source-code format. I'm not sure what "compiler" you would say was used to produce it. –  supercat Jul 30 at 1:00
    
@supercat: I don't know how the Basic interpreter you mention was produced, but I'm not talking about compilers used to produce interpreters. I'm talking about the compilers that are part of interpreters. As part of its code, the Apple ][ BASIC interpreter needs some way to read in the text files containing BASIC code and create a syntax tree from that text, which it then executes. The code that does this is a compiler; it doesn't generate machine code, but it still performs the tasks of reading in the code and translating it to another form. –  The Spooniest Jul 30 at 12:29
    
Typical microcomputer BASIC interpreters do not produce anything even remotely resembling a syntax tree. I'm not familiar with the original Apple BASIC interpreter (called "integer BASIC") but the BASIC interpreter implemented by Microsoft for Apple ("Applesoft BASIC"), Commodore, and various other companies stored program text as-is except for two things: (1) each line was preceded by a 16-bit line number and the 16-bit address of the next line, and followed by a zero byte; (2) each keyword was replaced with a single byte that had the high bit set. Other than that, expressions were parsed... –  supercat Jul 30 at 15:04
    
...character by character, left to right; a statement like A=1234" would convert the digits 1, 2, 3, and 4 into a floating-point number at run-time. –  supercat Jul 30 at 15:05
    
@supercat: That sounds closer to a bytecode than a syntax tree, then, so I'm in error on that particular. But the main point still stands: the pseudo-bytecode must still be constructed from text, and the code which does this is a compiler. –  The Spooniest Jul 30 at 16:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.