Why was the first compiler written before the first interpreter?

Question

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?

because there was more need for a compiler than a interpreter at the time — ratchet freak, Jul 28 '14 at 13:27
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 '14 at 14:07
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 '14 at 14:31
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 '14 at 15:01
Edited to give credit to the unsung heroes of academia- the graduate student — anguyen, Jul 28 '14 at 15:37
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 '14 at 16:10
Source that these were the first compiler and interpreter? Seems like a big assumption if you can't back it up. — jpmc26, Jul 28 '14 at 16:39
Point: What Hooper wrote in 1952 (A-0) was called a "compiler" by her, but would not be considered a compiler by todays standards (nor even the standards of 1960s). Even then, it was more accuratley called an "Assembly Link Loader". By most accounts, the first true completed compiler was FORTRAN in 1957 by John Backus. — RBarryYoung, Jul 28 '14 at 17:03
@JörgWMittag - Clarke's First Law - "When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong". (Although I don't think you could say that McCarthy was "elderly", being only about 32 at the time - but given that it was very early days and he'd been at it for over 10 years I suppose that he was pretty much the "old man" wherever he went, so... :-). — Bob Jarvis - Слава Україні, Jul 29 '14 at 02:22
I suspect there were interpreters prior to Lisp, but perhaps not Turing complete. — Daniel R Hicks, Jul 29 '14 at 03:15
I always assumed that, since the very concept of assemblers and compilers and interpreters didn't exist at first, it all had to be invented from the ground up. So the first idea was to take human-readable text and have that translate into machine code (i.e. assemblers and compilers), which was only natural, since computers can only run machine code! And the idea of "take human readable text and do what it says" came later. — Mr Lister, Jul 29 '14 at 12:09
The story of Grace Hopper as the first compiler author is well known: http://www.cs.yale.edu/homes/tap/Files/hopper-story.html The lisp interpreter was initially intended to be compiled until Russell realized instructions could be translated directly http://www-formal.stanford.edu/jmc/history/lisp/node3.html#SECTION00030000000000000000 — anguyen, Jul 29 '14 at 13:23
Grace Hopper and FLOW-MATIC are no earlier than 1955/56, public release 1957. Fortran is the first major compiled language, in around 1957. There were at least 10 compilers in the works around that time. Lisp was very much the odd one out. — david.pfx, Jul 29 '14 at 14:24
Arguably the first interpreter were microcodes - which translated bits of 1s and 0s arranged in a logical format that engineers can easily understand to a rats' nest of signals that needed to be timed correctly in order for the CPU to execute an instruction. In which case, the interpreter came before the compiler ;-) — slebetman, Jul 30 '14 at 10:15
@MrLister sorta a case of "cutting out the middle man" you mean? Sounds perfectly reasonable. — jwenting, Jul 30 '14 at 12:51
@slebetman Um, microcode came long after 1958. We're talking vacuum tubes and discrete transistors in those days. — Ross Patterson, Jul 31 '14 at 23:44
@RossPatterson: The first microcoded machine was built in 1947 at MIT. The microcode was written as an array of diodes — slebetman, Aug 01 '14 at 00:07
What am I talking about? I forgot why I said the interpreter came first! The first microcoded machine/interpreter was Charles Babbage's Analytical Engine first described in 1837. He wroted a small interpreter implemented as pegs in a drum (normal programs were written in punch cards) driving one or more Difference Engines to implement the Analytical Engine which has higher level instructions which would be difficult to implement purely as gears and catchment mechanisms. Though technically it was never built but it was designed (the interpreter written) — slebetman, Aug 01 '14 at 00:23
@slebetman Ah ... the Whirlwind. I guess you're right about that. As to Babbage, gedankenexperimenten don't count - you've got to build the thing to win :-) — Ross Patterson, Aug 01 '14 at 22:16
The Analytical Engine wasn't a thought experiment, just a failed Kickstarter project :) Enough was built for Babbage's son to use to calculate (buggy) digits of PI. They built a somewhat complete CPU (mill) which can run hardcoded programs they just didn't have the resources to build the RAM (store). — slebetman, Aug 03 '14 at 00:05

score 99 · Accepted Answer · edited Nov 08 '14 at 02:50

99

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

That might be true today, but I would argue that it was not the case some 60 years ago. A few reasons why:

With an 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 key. And interpreting requires a bit more memory than running a compiled program.
Modern CPUs are extremely complex with 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 languages, so even compilers are much more complex. Old languages would thus have simpler compilers.

edited Nov 08 '14 at 02:50

samthebrand

368
2
12
27

answered Jul 28 '14 at 13:27

Euphoric

36,735
6
78
110

65

and without a compiler you'd have to write the interpreter in assembly – ratchet freak Jul 28 '14 at 13:29
34

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). – ctrl-alt-delor Jul 28 '14 at 13:37
@richard I thought about that too, but forgot to mention. – Euphoric Jul 28 '14 at 15:03
1

Actually.... I recently read that the Apollo Guidance Computer used in the 60s moon flights had an interpreter: [wiki entry](http://en.wikipedia.org/wiki/Apollo_Guidance_Computer) "...the interpreter provided many more instructions than AGC natively supported..." I suppose this "interpreter" was more like the ["Sweet 16"](http://www.6502.org/source/interpreters/sweet16.htm) interpreter embedded in old Apple II computers than something like LISP. – Calphool Jul 28 '14 at 15:17
Just remembered. A friend of mine told be how he wrote an special purpose interpreter, because there was not enough memory for a compiled program. – ctrl-alt-delor Jul 28 '14 at 16:18
6

@ratchetfreak And it was. As were the first compilers. – RBarryYoung Jul 28 '14 at 17:07
@richard like this one http://fabiensanglard.net/anotherWorld_code_review/? Note that this was a VM/interpreter with a very specific purpose. Also of note http://fabiensanglard.net/prince_of_persia/pop_boot.php, which allowed loading a big binary in pieces. – SJuan76 Jul 28 '14 at 22:10
1

Writing a compiler is easier even now. Linking is the complicated part, and when you're writing an interpreter, you're just avoiding the problem by letting the compiler you write the interpreter in do most of the work. Other than that, the compiler simply puts data and instructions for the CPU to execute. That's a lot easier than handling a complete virtual machine in software :) – Luaan Jul 29 '14 at 13:33
@richard People *are* interpreters. Have you never stepped through code in your head? That's interpretation. We're simply an **extremely** slow interpreter. – Cruncher Jul 29 '14 at 15:30
@Luaan: Not only that, but the relative cost between memory and gates used to be such that circuitry to perform a function could often be cheaper than the quantity of memory needed to hold the code which would otherwise be necessary to perform it. – supercat Jul 29 '14 at 20:04
1

Give the bit about the [1401 Fortran compiler](http://ibm-1401.info/1401-IBM-Systems-Journal-FORTRAN.html) for IBM a read. We think of 1 pass, 2 pass, or maybe 3 pass complication steps - each step doing tens of thousands of operations. Back then, one couldn't keep that much in memory - so more passes, with each pass being much smaller. "The 1401 FORTRAN compiler has 63 phases, an average of 150 instructions per phase, and a maximum of 300 instructions in any phase." For comparison, Pascal was designed so that it could be implemented with a one pass compiler. – Jul 30 '14 at 02:22
@MichaelT That's hard-core - and Fortran was quite a simple language, compared even to C. And Turbo Pascal, oh god, that was just so awesome. Incredibly fast, low memory requirements and so easy to work with (except those annoying strings! :D) – Luaan Jul 30 '14 at 06:54
3

@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 '14 at 09:04
1

@Luaan as an aside... it *was* a compiler, but there's more to the story. From [Wikipedia](http://en.wikipedia.org/wiki/Fortran#IBM_1401_FORTRAN) "FORTRAN was provided for the IBM 1401 by an innovative 63-pass compiler that ran in only 8k of core. It kept the program in memory and loaded overlays that gradually transformed it, in place, into executable form, as described by Haines et al. The executable form was not machine language; **rather it was interpreted**, anticipating UCSD Pascal P-code by two decades." – Jul 30 '14 at 22:28

score 43 · Answer 2 · edited Nov 08 '14 at 02:49

The fundamental point is that the computing hardware environment of the 1950s made it such that only a compiler was feasible given the batch-oriented processing of computers back then.

At the time the better user interfaces were primarily limited to punch cards and teletype printers. In 1961 the SAGE system became the first Cathode-Ray Tube (CRT) display on a computer. 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. Maybe you're familiar with the infamous Altair 8800.

Other hardware limitations also made interpreters unfeasible. There was the extreme limited availability of primary memory (e.g. RAM) in computers in the 1950s. Prior to the semiconductor integrated circuit (which didn't come until 1958) memory was limited to magnetic core memory or delay line memory which was measured in bits or words, no prefix. Combined with the slowness of secondary storage memory (e.g. disk or tape), 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.

Memory limitations were still a major factor when the team lead by John Backus at IBM created the FORTRAN compiler in 1954-57. This innovative compiler was successful only 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 included only a small handful of operations, often influenced either by 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 that we think of computers today. That they were reprogrammable without having to be rebuilt was considered a revolutionary concept -- previously people had been using electromechanical machines (typically calculators) 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.

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 '14 at 21:10
@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 '14 at 02:31
@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 '14 at 10:53
This is a much better and complete answer than the accepted one. — Jim Garrison, Jul 29 '14 at 19:37

score 14 · Answer 3 · edited Jun 16 '20 at 10:01

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).

@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 '14 at 06:19
@anonymous-downvoter Downvoting without an explanatory comment shows that someone may be stupid. However, it does not say who. — babou, Jul 30 '14 at 06:23

score 5 · Answer 4 · edited May 23 '17 at 12:40

I disagree with the premise of the question.

Adm. Hopper's first compiler (the A-0) was more like a linker or a macro language. She stored subroutines on a tape (each one assigned a number) and her programs would be written as a list of subroutines and arguments. The compiler would copy the requested subroutines from tape and re-order them into a complete program.

She used the word "compile" in the same sense that one compiles an anthology of poems: collecting various items together into one volume.

That first compiler did not have a lexer or parser, as far as I can tell, which makes it a distant ancestor of a modern compiler. She later created another compiler (the B-0, a.k.a. FLOW-MATIC) with the goal of a more English-like syntax, but it wasn't completed until 1958 or 1959 -- around the same time as the Lisp interpreter.

Therefore, I think the question itself is a bit mistaken. It seems that compilers and interpreters co-evolved almost exactly at the same time, no doubt due to the sharing of ideas that would have had many scientists thinking along the same lines in those days.

A better answer with citations here: https://stackoverflow.com/a/7719098/122763.

Bill Brothers · Answer 5 · 2014-07-29T04:00:49.747

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.

score 2 · Answer 6 · answered Jul 28 '14 at 13:49

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.

score 1 · Answer 7 · answered Jul 28 '14 at 14:35

1

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?

answered Jul 28 '14 at 14:35

gnasher729

42,090
4
59
119

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. – Jul 28 '14 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 '14 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 '14 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 '14 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 '14 at 19:28
@delnan: The big difficulty with interpreters is that if you start with programs on punched cards, getting the program into RAM in a form which can be interpreted efficiently isn't hugely different from putting it into a form which would match real instructions. For larger programs, interpreted byte code might be more compact than machine code, but only if a program was large would savings would likely outweigh the cost of the interpreter. – supercat Jul 28 '14 at 21:13
@gnasher729 Well, Forth ;-) The VM, and to some extent the language, needs to be designed for this. For example dynamic typing would take its toll, a statically typed or untyped language makes things easier. You make the first byte signify the opcode, store the code for opcode i at `BASE+(i< – Jul 28 '14 at 21:26
@supercat Yes, that's a good point. – Jul 28 '14 at 21:26

score 1 · Answer 8 · answered Jul 28 '14 at 18:21

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.

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 '14 at 02: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 '14 at 02:50

score 0 · Answer 9 · answered Jul 29 '14 at 17:16

0

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.

answered Jul 29 '14 at 17:16

The Spooniest

2,160
12
9

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 '14 at 01: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 '14 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 '14 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 '14 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 '14 at 16:22
One wouldn't refer to a text editor that loaded a UTF-8-formatted input file into a list of UTF-16 strings as a "compiler"; the transformations done by MS-BASIC when a program is typed in aren't really any more substantial than that. – supercat Jul 30 '14 at 16:48
A converter between text encodings doing a character-by-character transformation of raw data, rather than performing any kind of semantic analysis of the text. The transformations done by a BASIC interpreter (MS or Apple or C64 or whatever) are less complex than those done by, say, a JavaScript interpreter, but they are considerably more sophisticated than an encoding conversion, or even those done by an assembler. This is what kicks it up into compiler-land. – The Spooniest Jul 30 '14 at 17:58
The character sequence "END" gets converted to 128; "FOR", 129; "NEXT", 130; "DATA", 131; etc. Such conversions are done with "greedy" matching, in context-free fashion. If one typed "1 TENDER SUPREME", it would get parsed as [T][END][E][R][space][S][U][P][REM][E]. When executed, it would see the "T", match any additional letters or digits, look up "T" as a variable name, look for an equals sign, not see one, and flag a syntax error. The fact that `END` makes no sense as anything other than the first token in a statement would be irrelevant to the tokenizer. – supercat Jul 30 '14 at 18:24
@supercat: what you're describing is more like an assembler than a BASIC interpreter. Assemblers are not compilers, it's true, but BASIC is not assembly language: it seems primitive by today's standards, but it's still a considerable step up from the metal. – The Spooniest Jul 30 '14 at 19:50

score -1 · Answer 10 · answered Jul 29 '14 at 04:47

-1

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.

answered Jul 29 '14 at 04:47

Loren Pechtel

3,371
24
19

Why was the first compiler written before the first interpreter?

10 Answers10