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.