eForth on MUXLEQ

A Forth tutorial you can type into, running a real eForth on a two-instruction virtual machine compiled to WebAssembly.

Adapted from Easy Forth by Nick Morgan, with fixes by ruv.

What you are looking at

Forth is a language with almost no syntax. There are no expressions, no operator precedence, and barely any keywords. There is a stack, and there are words that act on it. That is nearly the whole language, which is why it fits on machines that have no business running a language at all.

The machine underneath this page is one of those. MUXLEQ is memory, two instruction forms, and one reserved escape. Memory is a flat array of 32-bit cells, and an instruction is three consecutive cells. The first form, SUBLEQ, subtracts one cell from another and branches if the result came out non-positive, which on its own is enough to compute anything. The second, MUX, copies bits from one cell to another through a mask, which makes a move a single instruction and shortens the subtract-and-branch sequences the boolean operations would otherwise need. One reserved mask address escapes to a native right shift, the one useful thing neither form can do cheaply. There are no registers, no call instruction, and no indirect addressing: code that needs a pointer writes the address into the operand field of the instruction about to run. The last chapter gives the whole instruction set in a dozen lines, and the reference manual documents the machine, its image format, and how the system is built.

eForth is what makes such a machine usable. It is a compact Forth designed to be brought up on unlikely targets: about two dozen primitives written in machine code, and everything above them, the interpreter, the compiler, the decompiler, a screen editor, more than 250 words in all, written in Forth itself. On MUXLEQ that comes to roughly 6,600 cells. The image also carries the cross compiler that produced it, so the system can rebuild itself from its own Forth sources, and the rebuilt image coming out byte-identical is how the project knows the compiler is correct.

What you are about to type into is that pair, unchanged: the same C interpreter that runs from a terminal, compiled to WebAssembly, running the same eForth image. This is not a Forth-flavored toy written in JavaScript; when a word misbehaves here it misbehaves the same way on the command line.

Every editor on this page gets its own machine. A word you define in one does not exist in the next, so you can experiment freely. The reset button gives you a fresh machine if you get one wedged.

The row of boxes across the top of each editor is the data stack, one box per cell, bottom of the stack on the left and the top marked. Three things about it are worth knowing before you start:

• Whatever your last line pushed comes up highlighted, so you can see what a word did rather than work it out.
• To the right, that change is reported as a stack effect: ( 3 4 -- 7 ). It is computed from the before and after states rather than written by anyone, so it is the real effect of what you ran.
• Click any box to see the other readings of those 32 bits: signed, unsigned, hex, binary, and the character if it is one. This is the quickest way to see why true is -1 here.

There is also a step tickbox. With it on, a line is fed to the interpreter one word at a time, with a pause between, so the stack walks through its intermediate states instead of jumping to the answer. It is the paper illustration from Starting Forth, run live on your own code. Lines containing a string, a comment, or a definition are run whole, because feeding those a word at a time would change what they mean.

The stack

Anything you type that looks like a number gets pushed onto the stack. Type these three lines into the editor below, pressing Enter after each one. (Type them, do not paste them; the point is to watch the stack.)

1
2
3

The stack viewer at the top should now read:

Now type a single + and press Enter. The top two values, 2 and 3, are replaced by 5, and the viewer reports the effect as ( 2 3 -- 5 ):

Type + again and you get 6. Type it a third time and there is only one value left for a word that wants two, so eForth complains:

That -4 is a throw code, and -4 means stack underflow. Real Forth systems report errors as numbers, not sentences. Four of them account for almost everything you will hit:

Code	Means
-4	stack underflow: a word wanted more than was there
-10	division by zero
-13	undefined word
-14	a compile-only word used outside a definition

The two you will see most are worth telling apart at a glance. -13 prints the word it could not find first, as in zzz? -13?, so a typo names itself. -14 prints no word, because the word exists and was simply used in the wrong place.

Worth noticing: after an underflow the stack viewer shows values you never put there. eForth does not clear the stack when a word fails, so what you see is the memory the stack pointer is now sitting over. This is not the tutorial being sloppy, it is what the system actually does. Press reset when you want a clean one.

You do not have to type one thing per line. Try this:

123 456 +

The operator comes after its operands, which is called reverse Polish notation. It means the order you write things in is the order they happen, so there is nothing for parentheses to disambiguate. To compute 10 * (5 + 2):

5 2 + 10 *

. (pronounced "dot") pops the top value and prints it. Try 5 2 + 10 * . and watch the stack end up empty.

Stack effects

Forth code is commented with stack effect diagrams of the form ( before -- after ), with the top of the stack on the right. This is the same notation the viewer uses to report what your line did, and the same order the boxes are drawn in. Here is +, whose effect is ( n1 n2 -- sum ), applied to a stack of three:

before

1 2 3

+

after

1 5

Two things are worth reading off that picture. The rightmost name in the notation is the top of the stack, so n2 is 3, not 1. And the notation mentions only what the word touches: the 1 at the bottom is absent from ( n1 n2 -- sum ) because + never sees it. A word with a two-item effect behaves the same whether the stack is two deep or two hundred.

The arithmetic words all follow this pattern:

Word	Effect	Does
+	( n1 n2 -- sum )	adds
-	( n1 n2 -- diff )	subtracts n2 from n1
*	( n1 n2 -- prod )	multiplies
/	( n1 n2 -- quot )	divides n1 by n2
mod	( n1 n2 -- rem )	remainder
/mod	( n1 n2 -- rem quot )	both at once
abs	( n -- u )	absolute value
min	( n1 n2 -- n )	smaller of the two
max	( n1 n2 -- n )	larger of the two

Anything in parentheses is a comment, and so is everything after \ to the end of the line. Note that ( is a word like any other, so it needs a space after it.

/mod is the row to look at twice. It takes two and leaves two, and which one ends up on top is the part everybody misremembers. 17 5 /mod gives a remainder of 2 and a quotient of 3, remainder underneath:

before

17 5

/mod

after

2 3

One thing the table cannot say in a single word: division here is floored, not truncated toward zero, and the sign of mod follows the divisor rather than the dividend. Coming from C that is a genuine trap. -7 2 / is -4, not the -3 you may be expecting, and -7 2 mod is 1, not -1. Dividing by zero throws -10.

Type these and watch the viewer report each effect back to you:

17 5 /mod
-7 2 /
-7 2 mod

Shuffling the stack

Since the stack is the only place to put things, Forth has words whose whole job is rearranging it.

Word	Effect
dup	( n -- n n )
drop	( n -- )
swap	( n1 n2 -- n2 n1 )
over	( n1 n2 -- n1 n2 n1 )
rot	( n1 n2 n3 -- n2 n3 n1 )
nip	( n1 n2 -- n2 )
tuck	( n1 n2 -- n2 n1 n2 )
2dup	( n1 n2 -- n1 n2 n1 n2 )
?dup	( n -- n n | 0 ) duplicates unless zero
depth	( -- n ) how many items are on the stack

Try each of them and watch the viewer. 1 2 3 rot is a good one to stare at, and a good one to turn step on for: fed a word at a time you see the three values go on before rot moves them.

.s prints the whole stack without disturbing it, which is what the viewer at the top of each editor is quietly calling for you.

Defining words

A new word is defined with :, a name, a body, and ;. This is the entire mechanism; there are no functions, procedures, or methods, only words.

: square dup * ;
5 square .

Definitions can use words you defined a moment ago, which is how Forth programs are usually built: a lot of very small words, each doing one thing, stacked into slightly larger ones.

: cube dup square * ;
3 cube .

A definition can span several lines. Nothing happens until you type the closing ;, and you will notice the stack viewer stays quiet in the meantime, because the words are being compiled rather than run:

: average
  + 2 /
;
10 20 average .

Redefining a name is allowed. The old definition is not deleted, and anything already compiled against it keeps using the old one; new code picks up the new one. Try defining square twice and calling cube.

Type words in any editor to see everything the system knows. There are more than 250, all of them built out of the same two machine instructions.

Printing

Printing a string uses .", which reads up to the closing quote. Note the space after .": it is a word, not punctuation.

: hello ." Hello, world!" cr ;
hello

." only works inside a definition. If you want to print something right now, at the interpreter, use .( instead:

.( printed immediately) cr

This split catches people out, so it is worth knowing the general rule: words that need to compile something into a definition are marked compile-only, and using one at the interpreter gets you throw code -14. The loop words in the next section are the same.

Word	Does
cr	start a new line
space	print one space
spaces	( n -- ) print n spaces
emit	( c -- ) print one character by code
.	( n -- ) print a number
.s	print the stack

: shout 33 emit 33 emit 33 emit cr ;
shout

Conditionals

A conditional pops a flag and runs one branch or the other. The shape is if ... then, or if ... else ... then. Read then as "and then continue", not as the then of other languages; it marks the end of the conditional.

Zero is false and any non-zero value is true. The comparison words leave 0 or -1:

Word	Effect
= <>	( n1 n2 -- flag ) equal, not equal
< > <= >=	( n1 n2 -- flag ) signed comparison
0= 0< 0>	( n -- flag ) compare against zero
and or xor invert	bitwise, which on 0/-1 flags is also logical

: sign ( n -- )
  dup 0< if ." negative" else
  0> if ." positive" else
  ." zero" then then cr ;
-3 sign
7 sign
0 sign

Note that -1 is used for true rather than 1, because -1 is all bits set, which makes and and or work as logical operators without any conversion.

Loops

All of these are compile-only, so they must live inside a definition.

Counted loops

do ... loop takes a limit and a starting index, and i gives the current index:

: count-up 10 0 do i . loop cr ;
count-up

The limit is exclusive, so 10 0 do runs with i from 0 to 9. +loop takes a step off the stack instead of adding one, and j gives the index of the enclosing loop:

: evens 10 0 do i . 2 +loop cr ;
evens
: times-table
  4 1 do
    4 1 do j i * . loop
    cr
  loop ;
times-table

Counting down

eForth also has for ... next, which is cheaper and counts down. n for runs the body n+1 times with r@ going from n down to 0:

: countdown 5 for r@ . next cr ;
countdown

Conditional loops

begin ... until repeats until the flag on top is true, and begin ... while ... repeat tests before each pass:

: double-up 1 begin 2* dup . dup 1000 > until drop cr ;
double-up

Variables and memory

variable creates a name that pushes an address. ! stores, @ fetches, and +! adds in place.

variable total
0 total !
5 total +!
7 total +!
total @ .

constant makes a name that pushes a fixed value, with no address involved:

42 constant answer
answer .

For a block of memory, create names an address and allot reserves space after it. Here is where the machine shows through: eForth counts addresses in bytes, but every cell is 32 bits wide, so cells converts a count of cells into the byte offset you need.

create scores 10 cells allot
100 scores !
200 scores 1 cells + !
scores @ .
scores 1 cells + @ .

here pushes the address of the next free byte, so here . tells you how much of the image the dictionary has used so far. Watch it move as you define words.

Drawing

The editor below has a 24 by 24 display next to it. The display is not a device: it is 576 consecutive cells of ordinary Forth memory, and this page paints whatever color numbers it finds in them. graphics pushes the address of the first cell. Cell 0 is the top left corner, and the rows run left to right.

Color 0 is the background and 1 through 15 are colors. Storing into a cell is all it takes:

: plot ( color x y -- ) 24 * + cells graphics + ! ;
3 5 5 plot

Everything else is ordinary Forth. A horizontal line is a loop over plot, filling the screen is a loop over that, and a color ramp is two nested loops:

: hline ( color y -- ) 24 0 do 2dup i swap plot loop 2drop ;
: flood ( color -- ) 24 0 do dup i hline loop drop ;
4 flood
: ramp 24 0 do 24 0 do j i + 15 and i j plot loop loop ;
ramp

Two extra words are set up for you in every editor, because a drawing program wants them and stock eForth has neither. random takes a limit and leaves a value below it, and ekey reads a keystroke without waiting: it gives you the character code, or 0 if nobody has pressed anything.

: sprinkle 200 0 do 15 random 1+ 24 random 24 random plot loop ;
sprinkle

While a program of yours is running, everything you type goes to it rather than to the interpreter. The arrow keys arrive as codes $80 through $83, left, up, right, down.

Numbers in hexadecimal are written with a $ prefix, and the digits above 9 must be capitals: $FF works, $ff does not.

A game

Everything above is enough to write a game. The editor below has already loaded snake.fth: type play and steer with the arrow keys.

The whole game is stores into that block of memory. There is no drawing API, no event loop, and no frame callback. play is a begin ... until loop that redraws, waits with ms, checks ekey, moves the snake, and asks whether the cell the head just moved into was already occupied:

: play ( -- )
  setup
  begin
    show-snake show-apple
    30 ms
    ekey ?dup if turn then
    shift-body move-head
    eat?
    crashed?
  until
  ." game over" cr ;

Read the rest of snake.fth, then change it. The snake's body is two parallel arrays of coordinates, so making the board wrap around instead of killing you is a change to one word. So is making the apple worth more than one segment.

Underneath: two instructions

Everything on this page, the interpreter, the compiler, the decompiler, the number formatter, runs on the machine sketched at the top: two instruction forms, one addressing mode, no indirection.

Memory is an array of 32-bit cells, addressed by cell number. An instruction is three consecutive cells, a, b and c, and executing it means:

Mem[b] = Mem[b] - Mem[a]
if Mem[b] <= 0 then pc = c else pc = pc + 3

That is SUBLEQ, and it is enough to compute anything, slowly. MUXLEQ adds one thing: if c has its top bit set, and is not the all-ones value that spells halt below, the instruction is instead a bitwise multiplex through a mask held at the address in the low bits of c:

Mem[b] = (Mem[a] & ~m) | (Mem[b] & m)

Two mask addresses are special. Cell 6 always holds zero, so a mask fetched from it selects all of Mem[a], making the instruction a plain move, which pure SUBLEQ needs a multi-instruction sequence for. The reserved address $7FFFFFFE means shift right by one, turning a bit-serial loop into one instruction. Input, output and halt are spelled with -1 in the a, b and c field respectively.

With no indirect addressing, a Forth built on this cannot fetch through a pointer the way you would expect. It gets there by writing the address into the operand field of the next instruction and then running it. The image modifies itself constantly, and that is the normal case here rather than a trick.

You can see the result. see decompiles a word back into the words it was built from:

: square dup * ;
: cube dup square * ;
see cube

which prints the address of each compiled cell alongside the word it calls:

A machine this simple asks nothing of its host but a byte in and a byte out, which is why the WebAssembly module running all of the above imports nothing at all from the browser. The reference manual has the rest: the image layout, the self-modifying-operand rules, and the bootstrap that rebuilds the image from the Forth sources in forth/.

Try here . to see how much of the image you have used, and words to see what you got for it.