The way I would sum up interpreters and compilers, trying to put it as concisely as possible:
Step 1. Write a program that reads the input program into a data structure that exactly represents the language. You just wrote a parser.
Step 2. Write a program that operates on the data structure from (1) to execute the program. You just wrote an interpreter.
Step 3 (Optional): Write a program that converts the data structure from (1) into a different data structure that you can interpret more efficiently. You just wrote an optimizer.
Step 4 (Optional): Keep iterating on (3) until the output of your optimizer is machine code. You just wrote a compiler.
Not saying the above obviates the need for a book like this one (at all), I just had never thought of it in quite this way and wanted to write it down. :)
I think in everyday usage, the most common thing that distinguishes the two is that a compiler saves its output in some standard format that some other piece of software is expected to understand.
So for example, something like Babel for JS is considered a compiler, because its output is JavaScript, which is a standardized language.
On the other hand, Python is not usually considered a compiler, even though it writes .pyc files to disk, because its output is bytecode that only Python itself is expected to understand.
Even this is a little bit grey though, because we would say that Python contains a bytecode compiler as one of its components, but I don't think that most people would say that the Python binary is a compiler.
> Python is not usually considered a compiler, even though it writes .pyc files to disk, because its output is bytecode that only Python itself is expected to understand.
I'd disagree, simply because this is exactly what javac does too.
Python bytecode on the other hand is not standardized: its bytecode is considered an implementation detail of CPython and can vary from version to version.
But javac doesn't run it. It's run by "java". Therefore javac is called the compiler.
If things were such that "java" runs all .java files and creates those .class files as bytecode cache, then java won't have been called a compiler.
And similarly, if python had two different programs, one to create *.pyc files and the other runs it, the former one would have been called a python compiler.
Colloquial usage really diverges strongly from technical usage.
For example, CPython could be considered to technically be a virtual machine because it does garbage collection on dead objects since v 2.4 at least, rather than being pure reference counting.
Yet most people would call CPython a straight interpreter.
Yes, it took me a while to "realise" (or perhaps "accept") this as well. What is machine code? Code that a machine can execute natively? What if I built a machine that had primitive instructions for JavaScript? Then JavaScript would be machine code, and an X->JavaScript "transpiler" could be considered a "compiler".
Now what if before building such a machine, I wanted to simulate one? I could write a "virtual" machine, which is really just a program that acts like a physical machine with native JavaScript instructions. Also known as a JavaScript interpreter.
Yeah, plus even when you get down to machine code, those instructions can be implemented as microcode in the CPU. Then you have things like the lisp machines. Or V8 compiling bits of javascript to machine code while it "interprets". What exactly defines a compiler gets pretty fuzzy.
You could write something that compiles down to JavaScript opcodes then run them in your JavaScript virtual machine. This is actually pretty similar to what Perl5 does. You wouldn't have to do that to have an interpreter, though. So your implementation of your "interpreter" fuzzes the line moreso because it indeed technically contains a compiler.
They have very different outputs. Compilers produce programs, while interpreters produce answers. More specifically, compilers produce programs in another language (stereotypically machine code), while interpreters run your program to get an answer.
If all you have are compilers, you can never run a program. All you can do is convert it between different languages. Fortunately your computer comes with an interpreter built in: you can think of your cpu as an interpreter for machine code, implemented in hardware.
It can be but needn't be. You can evaluate straight from walking your AST. You can also transform from your AST into an output then run the output. Either one is commonly called an interpreter but the former is further to that end of a spectrum.
I would define it as: when a compiler operates on its own source code, the resultant compiled compiler executes as fast as the original. When an interpreter evaluates its own source code, the resultant interpreted interpreter is an order of magnitude slower. This definition allows for things like "just in time" compilation, and rules out silly tricks like bundling an interpreter and some source code into an executable image.
The speed differential. Your basically making a list of jumps into machine code and then jumping in a loop. The interpreter takes your input and turns it into a jump list which it pumps into the loop. You can reuse a jump list by defining it as a new word.
For me, the compiler takes input program in language A and spits out the same program in language B. An interpreter goes (more or less) line by line and executes what it reads.
In theory, compilation is reversible, execution is not.
Minor nit-pick: an interpreter need not work line-by-line, but rather (more commonly?) AST-node-by-AST-node. This isn't necessarily true for BASIC interpreters or something resembling assembly, but in general the code is represented as a tree of parsed values by the time the interpreter starts running your code.
That's technically true. Those are also known as translators, although they are technically no different from compilers.
Something that compiles to an executable format for your environment is most likely to be actually called a compiler. Some "interpreters" are actually compiling to opcodes for a virtual machine then running on the virtual machine.
There's a lot of mystique and prestige around the idea of compilers. It doesn't help that parsing is a fairly untidy, complex process. You're definitely right in trying to present the overall functions in a much, much simpler way.
My personal recommendation in this field is nanopass compiler architecture. It's a more manageable approach to the task of implementing a compiler, through the use of lots of incremental passes rather than a few heroic ones.
NB "When a paper on the first nanopass framework was accepted for ICFP 2004, however, the program committee required the authors to refocus the paper on education because they did not believe the nanopass methodology was suitable for commercial compilers. They were principally concerned with the compile-time overhead of repeated traversals. This concern was impossible to refute at the time because the prototype infrastructure and implementation were not mature enough to put to the test."
Interesting. My first compiler experience, 40 years ago, could reasonably be considered nanopass. This was the IBM Fortran IV compiler on an 11/30 clone. IIRC, the code to compile was kept in the minuscule memory, while dozens of passes were pulled in from disk to move slowly from source to machine code. As a bonus, you could usually gauge how far you'd progressed by watching the pattern of the blinkenlights.
Definitely. This wasn't meant to be an actual guide as much as a way of concisely explaining the terms. You'll almost always want byte-code of some kind if you want good performance.
I highly recommend the Coursera compilers class: you don't have to work though it in synch with a class; just sign up and work at your own pace. If you have to watch the same video two or three times, you can. None of this stuff actually turns out to be that complicated: it just takes a little while to get the lingo and concepts.
it's possible they are available in the internet archive backup, but I don't have idea how to inspect those without downloading tens of gigabytes of stuff.
[Ignoring the dupes since they got no attention. Good reason to resubmit if material is worthwhile.]
The author seems to be doing a good thing. Like he said, most of the write-ups on this subject are either ultra-heavy with theory or basically nothing with code examples. Doing interpreters piece-by-piece like in SICP or The Little Schemer series in an accessible language gradually giving them the code and theory they need is a good idea.
It could also help in my verifiable builds scheme where people show no subversion exist by building from ASM to small language (or interpreter) then to bigger one then whole compiler. I was debating p-code, Oberon, Scheme, MiniML... Biggest problem is that the best stuff, eg Scheme's or ML's, is least likely for imperative programmers to try to understand. Something like this could help if I use an imperative base.
At the time I pointed out that this is a dupe the previous submission had been less than an hour earlier, scarcely giving it enough time to get any attention.
But screw that, let's just submit things every 10 minutes until they get upvotes.
Personal story only, I never liked Imp, nor OO that much (all my OO code tried to be lisp or caml without knowing it). I learned lisp eval, then lc, typed lc.. recently prolog; where the machine vanishes quite a lot. Yet the very high abstraction view that path led to makes the understanding of systems and languages very coherent even if thinking in an imperative POV. But I can't suggest doing that to anybody since it may fail miserably for them.
It stays low-level and builds the components of a Scheme at same time. Piece by piece with ability to understand and verify. The resulting language could be used to build better LISP's, ML's, Prolog's, etc. sklogic's DSL toolkit illustrates that nicely where he mix and matches on top of a foundation of a LISP custom-designed for it.
Taking it further, you might like FLEX and Ten15 VM that unified higher-level languages:
Except the dupe story, does anyone gave the book a closer look and can say if it's suitable for beginning programmers? By that I mean if it's suitable to study and implement an interpreter in other language without a degree in computer sience?
Programming is one of my hobbies and my dream is to do an interpreter on my own, but most books are so heavy to understand if you know what I mean.
My suggestion to you is simple: go read about the brainfuck language, and implement an interpreter for it.
You'll probably get to the end and find that your first implementation "cheats", whatever that means. That's fine, improve it.
Write the memory model as a contained module, and have the interpreter core call into it.
Build an internal representation of a program, then make reading the source code a separate step from running it. Once you have that representation, some opportunities arise: e.g. represent increment and decrement as "add 1" and "add -1" instead.
Then you can write your first optimiser: turn long runs of increment and decrement instructions in the source code into a single "add n" instruction.
At this point, you have modules that turn source code into an internal representation, optimise the internal repr, and execute it. Start thinking of commands you can add to the language. Start thinking of how to handle data in the source code, rather than just instructions. How to build functions.
When you get to this point, you'll realise that you're no longer thinking "I wonder how an interpreter works", but rather "I wonder how you implement this particular part of an interpreter", and that is a much easier question to find answers for.
Disclaimer: I'm the author of the book and thus pretty biased.
As a matter of fact, I wrote this book specifically for people like you and me: no CS degree, highly interested in interpreters and compilers, but intimidated by the existing literature. (If you studied compilers in college, this book will probably teach you nothing new.) There's a sample on the landingpage that should give you an impression of the difficulty - my guess is, that if you already know how to program and know the basics of Go, you'll get along just fine.
You can read The Little Schemer and The Seasoned Schemer which are deceptively easy to work through but teach you concepts some CS grad students are ignorant of. Following it up with Structure and Interpretation of Computer Programs will make you a much stronger programmer.
You can work through Sedgewick's Algorithms course on Coursera to get a stronger foundation for the more technical aspects of compiler writing.
I haven't given the book a look, but in general, if you pick a small enough language, you can absolutely build an interpreter without needing a CS degree.
A couple of years ago, I wrote https://github.com/steveklabnik/mojikun , which is an implementation of Brainfuck. I specifically over-engineered it to be more like a real interpreter than the smallest possible code, so it's actually split into parser/lexer/runtime/interpreter. I also made it have a more strongly-typed AST, which in retrospect is a little silly, at least the way that I did it. A bunch of those files have empty classes for this purpose.
Anyway, my overall point is, this project has the same structure as a "real" interpreter, and it's like 160 lines of code for the core functionality, no complex algorithms. And you can move on to harder languages fairly easily, and learn as you go.
(Somewhat of a repost, but I'm a fan of these things.)
I had the same feeling, so I tried it out myself. Inspired by Jonesforth (highly recommended), I wrote an arguably complete Lisp interpreter in a single, heavily commented ARM assembly language file.
Lisp is an obvious target, with its minimal syntax and simple concepts. The first Lisp was written in assembly on a machine with comparable capacity to your laptop keyboard's microcontroller, after all.
Sure, I think I wrote my first interpreter when I was about 15. It's not hard at all. The trick is finding the right resources. IIRC I studied http://javascript.crockford.com/tdop/tdop.html for lexing + parsing (I wouldn't understand LL or LR parsing for years… you really don't need to) and wrote a very naïve AST-walking interpreter (the idea of compiling to bytecode and interpreting that did not occur to me).
Now I'm sort of a serial language designer/implementor and pump out virtual machines on a regular basis. This stuff is really easy until you want to make it fast, then it gets really hard. ;-)
Just for starting out, I think you should basically make parsing as simple as you can. It's probably the most confusingly computer-sciency part of language implementation… and also probably the least important. So just avoid it. Maybe write a Lisp or Forth if you want. I actually advocate just using a very small simple (pascal-like) syntax though, and writing an operator-precedence parser. You'll learn more that way.
I suggest http://web.archive.org/web/20160413005246/http://www.norvig..... It's extremely easy to understand. Once you start adding features to your Lisp interpreter and extending it, you'll eventually realize that the naive recursive descent approach is getting in the way of your more complicated ideas, but you'll be ready to try more sophisticated approaches to writing an interpreter. Nothing beats Norvig to me for learning how to write an interpreter as a beginner. Lisp isn't as complex as the Monkey programming language from https://interpreterbook.com, but I argue that that's a good thing. Once you get the basic principles, writing an interpreter for a language like Monkey seems like a much more easily surmountable task.
I like these kinds of books a lot. I'm not at all interested in Go, so I'll probably convert the code to C# for my own amusement...but I dig it. I've mucked with lexers for text editing purposes and have always wanted to build my own compiler. It's somewhere down on the bucket list.
Edit: To those who downvoted me, let me just point out that this was submitted less than an hour after the previous submission, hence my pointing at that (barely) earlier item.
So let me ask a serious question here. Suppose someone submits a story. The following day it has few points, and no comments. If someone then submits the same story, fair enough.
Now suppose the story is submitted, has few points, no comments, and then 30 seconds later someone submit the same story. Is it fair to point at the one that's only 30 seconds old? I would say yes, you might disagree, I would be interested to know what you think.
If it's reasonable to point at a submission that's only 30 seconds older, then we have a question:
How old should a previous submission be to declare that it's fair enough to give it a second chance?
I would say that an hour isn't long enough, so if something is submitted a second time within an hour then it's perfectly reasonable to point at the previous submission.
If you disagree, fine, say so. If you think it's reasonable that something is submitted within seconds of a previous submission, say so.
I'd be interested to know what you think is reasonable. It's plausible that we have different opinions about what is reasonable in this context. If so, I'd like to know what you think.
So it's OK for you to tell me what to do, and what not to do:
> Please don't post previous
> submissions without comments,
> they are worthless.
... and yet you decline to answer my question, or to tell me your opinion on these matters.
That's a pity. I'd've liked to have known your thoughts as to whether it's reasonable to have multiple submissions within minutes without indicating the duplication.
A fun and fairly simple project, with a surprisingly high ratio of usefullness to effort, is to write an interpreter for a concatenative language. Concatenative languages, like FORTH, can do a lot with very limited resources, making them good candidates for embedded systems.
If you want to play around with making your own concatenative language, it is actually surprisingly simple. Here is an overview of a step-by-step approach that can take you from a simple calculator to a full language with some optimization that would actually be quite reasonable to use in an embedded system.
So let's start with the calculator. We are going to have a data stack, and all operations will operate on the stack. We make a "dictionary" whose entries are "words" (basically names of functions). For each word in the dictionary, the dictionary contains a pointer to the function implementing that word.
We'll need six functions for the calculator: add, sub, mul, div, clr, and print. The words for these will be "+", "-", "x", "/", "clr", and "print". So our dictionary looks like this in C:
We need a main loop, which will be something like this (pseudocode):
while true
token = NextToken()
if token is in dictionary
call function from that dict entry
else if token is a number
push that number onto the data stack
Write NextToken, making it read from your terminal and parse into whitespace separated strings, implement add, sub, mul, div, clr, and print, with print printing the top item on the data stack on your terminal, and you've got yourself an RPN calculator. Type "2 3 + 4 5 + x print" and you'll get 45.
OK, that's fine, but we want something we can program. To get to that, we first extend the dictionary a bit. We add a flag to each entry allowing us to mark the entry as either a C code entry or an interpreted entry, and we add a pointer to an array of integers, and we add a count telling the length of that array of integers. When an entry is marked as C code, it means that the function implementing it is written in C, and the "func" field in the dictionary points to the implementing function. When an entry is marked as interpreted, it means that the pointer to an array of integers points to a list of dictionary offsets, and the function is implemented by invoking the functions of the referenced dictionary entries, in order.
A dictionary entry now looks something like this:
struct DictEntry {
char * word;
bool c_flag;
void (*func)(void);
int * def;
int deflen;
}
Now the main loop has to look something like this:
while true
token = NextToken()
if token is in dictionary
if dict entry is marked as C code
call function from that dict entry
else
InterpWords(def, deflen)
else if token is a number
push that number onto the data stack
and InterpWords looks something like this
void InterpWords(int * def, int deflen)
while (deflen-- > 0)
InterpOneWord(&dict[*def++])
void InterpOneWord(dict * dp)
if (dp->c_flag)
(*dp->func)()
else
InterpWords(dp->def, dp->deflen)
With this, we can add new built-in functions defined in terms of already defined functions. Before we do any of that, though, we should add some more stack manipulation functions. Add at least "dup", "drop", and "swap", which, respectively, push a copy of the current top of stack onto the stack, pop an entry from the stack, and exchange the top two items on the stack.
For reference, after adding those, the dictionary offsets of the 9 words we've defined are:
0 +
1 -
2 x
3 /
4 clr
5 print
6 dup
7 drop
8 swap
and they are all marked as C code. Now let us add a built-in function "sq", which squares the top item on the stack. To do that, add a new dictionary entry initialized like this:
{"sq", false, 0, sq_def, 2}
where sq_def looks like this:
int sq_def[] = {6, 2}
That's marked as being interpreted rather the C code, so when the main loop finds it it will call InterpWords, passing it sqdef and 2, and InterpWords will end up invoking dup and x, with the result being the top of the stack is squared.
OK, that's all fine and dandy, but we want to be able to define functions in our language from our language. So far, we can define functions in our language, like sq, but we have to do it by editing a C data structure and recompiling.
To do this, we'll need some changes to both InterpWords and/or InterpWord, and to the main loop. The basic idea is that we add a "compiling" mode. When we are in compiling mode the main loop does not execute the tokens it gets. Instead it just makes a list of the dictionary offsets of the words it would have executed. So in compiling mode, if you type "dup x", the main loop doesn't actually call dup and x, it just makes the list {6, 2}. That is used to make the function we are compiling. We'll have to find some way to tell the interpreter what we want to call the new function. The interpreter can than make a new dictionary entry for it, referencing that list of dictionary offsets.
The above only covers words in compiling mode...what do we do when the main loop sees a number in compiling mode? That's where we need to extend InterpWords. We need to change the list of dictionary offsets it receives to be able to also specify numbers. Maybe something like this (taking advantage of the fact that dictionary offsets are always non-negative):
void InterpWords(int * def, int deflen)
while (deflen-- > 0)
if (*def >= 0)
InterpOneWord(&dict[*def++])
else if (*def == -1)
push def[1] onto data stack
def += 2; deflen--;
else error
A -1 in the word offset stream now means that the next item in the stream is a number to push onto the stack rather than a word offset. So now we can support functions like "dup x 10 +" that squares the top of the stack and adds 10, which would compile to {6, 2, -1, 10, 0}
We still aren't there, though, because we don't yet have a way to enter or leave compiling mode. That's easy. We'll add a new built-in function, ":". We'll write this in C. What ":" does is read the next token, see if it is a legal word name and not already in use. If it is (legal) and isn't (in use), it creates a new dictionary entry for it, allocates space for the definition, and flips on the global compiling flag.
Great! Now we can start defining new words from in our language. Just one problem...how do we terminate compilation? The main loop is compiling everything, so how do we get it to execute the command to stop compiling and finish making the dictionary entry?
For that, we need yet another flag in the dictionary: the immediate flag.
struct DictEntry {
char * word;
bool c_flag;
void (*func)(void);
int * def;
int deflen;
bool immediate;
}
Change the main loop so that when it sees a word with the immediate flag set, it executes it even if it is in compiling mode. With that, we can add a word ";", with the immediate flag set, that turns off compiling mode and finalizes the compilation of the word that was being compiled. When we get these changes in, then we would be able to define "sq" from within the language instead of making it a built-in like we did earlier: ": sq dup x ;"
Of course, we probably want our language to support some kind of if/else construct and some kind of looping construct.
I bet you can see how this will be done. Most of the work is done in InterpWords. Much like we used -1 to indicate that the next entry is a number for the stack, we'll use -2 to indicate a goto. The entry after -2 will be the offset to go to. (Should it be an absolute offset or relative? Your choice). We'll use -3 to indicate a conditional goto. It works like -2, except that it only goes if the top of the stack is non-zero, and it pops the top of the stack. If the top of the stack is zero, it pops it, and then skips over the offset.
Here's how we could use this to implement a do...while kind of loop. First think of how we want it to look in our programs. It might be something like this "do <body of loop> <loop condition> while". So we want the compiled code to look like this:
<dict offset list for body of loop>
<dict offset list for loop condition>
-3
offset of body of loop above
To make "do" and "while" work, we need to flag their dictionary entries as immediate words. So when we are compiling and hit "do" the code for "do" is executed. For now, let's make this C code. What the "do" code does is simply save the offset of where the next word will be compiled to. What the "while" code does is put the -3 in the compiled code, and then put the offset that was saved by the "do" into the compiled code.
You can do similar things for if/else constructs, for loops, and any other control flow you want: make the low level operations you need in InterpWords, and then make immediate words for use during compilation that gather and use the necessary information to write that control flow.
Now let's talk a bit about optimization. One thing you can do is some inlining. Consider this function ": cube dup sq x ;". When compiling this, we could notice that "sq" is not C code, and put its definition inline, so we end up compiling cube as if it were written like this: ": cube dup dup x x ;".
(BTW, remember earlier when I said it was up to you whether you use absolute or relative offsets in the low level control flow? Relative will make inlining easier if the inlined function has any branches).
Now if you are going to implement entirely in C or similar, that's about the end of the simple optimizations (at least as far as my feeble mind can handle). However, if you are willing to work in assembly language some, you can get much fancier.
You can make the lowest level built-ins, such as add, mul, dup, and similar assembly language. (In the following I'm going to continue to say C function, for consistency with the earlier stuff, but what it now means is a function that is not defined in our language). We can change the way non-C functions are defined from being a list of dictionary offsets to a pointer to actual code. So for ": sq dup x ;" instead of compiling that as a pointer to the list {6, 2}, we compile it as a pointer to a list of call instructions, followed by a return. For sq, that would look like this:
call dup
call mul
ret
Cube would look like this (without optimization)
call dup
call sq
call mul
ret
and with sq inlined at the high level, it would become
call dup
call dup
call mul
call mul
ret
For built-ins that are position independent assembly code, we can do another level of inlining and replace calls to them with their body.
Depending on the addressing modes your processor supports, this could end up with cube being as simple as four instructions (not counting the return), with all the calls eliminated!
You can go farther and do things like cache the top few stack items in registers, and add peephole optimizers that go over the compiled code to eliminate redundant operations.
The really cool thing is how easy bootstrapping this kind of thing is. You only need a small number of built-in assembly functions to give you enough to write the rest of the language in itself, and these systems tend to be small and perform reasonably well. These kind of languages can be great in embedded systems, and indeed that is where the granddaddy of this kind of language, FORTH, got its start.
I agree with your approach! I built a non-Turing-complete Forth-like interpreter in Go a few years ago with words similar to the set you've defined above:
Awesome! As someone interested in compilers and interpreters who has not completed a degree in computer science it was quite hard to get any of the background. This post is spot on: you'll either read a 1000 page book about it or you're stuck reading tiny blog posts. Notation also sucks for beginners, few books ever bother explaining it at all. My favorite/most helpful text I've found so far is Essentials of Programming Languages, which covers a wide variety of topics and introduces them as parts of (complete) interpreters. The code is written in very readable Scheme (so much so that I was able to understand everything despite not knowing Scheme or Lisp at the time I began reading it).
Step 1. Write a program that reads the input program into a data structure that exactly represents the language. You just wrote a parser.
Step 2. Write a program that operates on the data structure from (1) to execute the program. You just wrote an interpreter.
Step 3 (Optional): Write a program that converts the data structure from (1) into a different data structure that you can interpret more efficiently. You just wrote an optimizer.
Step 4 (Optional): Keep iterating on (3) until the output of your optimizer is machine code. You just wrote a compiler.
Not saying the above obviates the need for a book like this one (at all), I just had never thought of it in quite this way and wanted to write it down. :)