Why I wrote a book about interpreters

It can even be source code: source-to-source compiler.

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.

What, then, is the difference between a compiler and an interpreter? Just that the compiler saves its output rather than executing it?

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.

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.

That's a pity: the lecture videos were worthwhile, and I got all the unit tests by dissecting the auto-checking scripts that the class supplied :-/

Oh I overlooked that. Guessed that the others were older. My bad on that.

Here's the one I always drop for people like you:

http://lambda-the-ultimate.org/node/1752

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:

https://en.wikipedia.org/wiki/Ten15

On a total tangent, I'd love to get that metacircular interpreter poster, any chance you'd like to sell a print-quality copy? :)

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.

I've tried to submit before, and it's stopped me by detecting it's a dupe before accepting it.

How did this submission get through that check within an hour of the previous one?

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.