MakoVM is an extremely simple stack-based virtual machine intended for the creation of video games. This tutorial will explain the workings of Mako, and at the same time introduce Maker, a Forth-inspired compiled language targeting Mako. While it is entirely possible to compile existing languages to MakoVM instructions, Maker code has a very tight relationship with Mako and makes it easy to explain the "hardware" on a low level.
Let's begin with a simple "Hello, World" program:
:include "Print.fs"
: main
"Hello, World!" typeln
;
Forth programs are made out of whitespace delimited tokens called words. Tokens can contain any combination of characters. Strings are a special exception, and include any text enclosed within double quotes. When a word's name is encountered, it is executed. Some special words are carried out at compilation time, while most are carried out at runtime.
The first word in this program is :include. By convention, words beginning with a colon are related to the compiler and have compile-time semantics. :include instructs the compiler to load the source file specified by the following string, in this case Print.fs, a library for console output.
We then reach the word :, which defines a word. The next token is used as a name. The name main is special, and will always be used as the entrypoint to a program. : should always be paired with a ;, which terminates a definition.
The string "Hello, World!" will compile an inline string constant and leave the address of this string on the stack, to be used by the typeln word to print a sequence of characters to stdout.
To run this example, place your code in the examples directory in a file called Hello.fs, and type the following:
./maker examples/Hello.fs --run
We see a whole bunch of output- a disassembly of our compiled program followed by the text "Hello, World!":
00000: (PC) 117
00001: (DP) 140
00002: (RP) 190
-- snip --
00112: (typeln) CALL 94 (type)
00114: CALL 20 (cr)
00116: RET
00117: (main) JUMP 133
00119: "Hello, World!"
00133: CONST 119
00135: CALL 112 (typeln)
00137: JUMP -1
00139: RET
00140: (data-stack) <<< 50 words >>>
00190: (return-stack) <<< 50 words >>>
00240: (grid) <<< 1271 words >>>
01511: (grid-tiles) <<< 64 words >>>
01575: (sprites) <<< 1024 words >>>
02599: (sprite-tiles) <<< 64 words >>>
2663 words, 10.402 kb.
Hello, World!
The only definintion here we're really interested in is that of our main word. We can instruct Maker to only print a disassembly of a specific word by using the --word flag and specifying the word we want to see:
java Maker examples/Hello.fs --word main
00117: (main) JUMP 133
00119: "Hello, World!"
00133: CONST 119
00135: CALL 112 (typeln)
00137: JUMP -1
00139: RET
2671 words, 10.434 kb.
Even though "Hello, World!" programs are a common starting point for teaching programming languages, this one has a fair amount of subtlety to it. Let's start over with the basics.
Mako is a stack-oriented architecture. Instead of storing intermediate values in registers, we push values onto a stack. Operators consume operands from the top of the stack and leave their results behind. Consider the following expression:
2 3 +
The first two tokens are numbers, so they push their values onto the stack. The word + consumes the top two elements of the stack, adds them, and leaves the result on the stack. If you've ever used an RPN calculator, this kind of postfix math will seem pretty familiar.
Maker provides the following words without the use of any library, and all but the last two map directly to a single MakoVM instruction:
+(addition)-(subtraction)*(multiplication)/(integer division)mod(modulus)and(bitwise AND)or(bitwise OR)xor(bitwise XOR)not(bitwise NOT)<(less-than)>(greater-than)<=(less-than or equal to)>=(greater-than or equal to)
Given a definition like the following:
: operation 2 * 5 + not ;
The resulting disassembly might look like this:
00126: (operation) CONST 2
00128: MUL
00129: CONST 5
00131: ADD
00132: NOT
00133: RET
CONST is a single instruction that is followed by a parameter whose value will be pushed onto the stack. MUL, ADD and NOT are the assembly mnemonics corresponding to *, + and not, respectively. RET returns from a subroutine call.
Each element of the stack (a cell) is a 32-bit two's complement signed integer. The comparison operations (greater-than, less-than and so on) result in 0 (all bits 0) for false, and -1 (all bits 1) for true, making it possible to perform a variety of useful bitwise operations on the results. These boolean flags are used by convention to represent logical true and false, and the words true and false can be used in place of the numeric constants.
Numeric constants can be given as signed decimal integers (as above) or as hexadecimal or binary values. Hexadecimal values are prefixed with 0x, and binary values are prefixed with 0b:
0 -31 45 # decimal constants
0xC0FFEE 0xA 0x34 # hexadecimal constants
0b110001 0b0 0b01 # binary constants
Finally, note that in the above example we've used # to delimit single-line comments. The paretheses, ( and ), are used to delimit multiline comments. Multiline comments may not be nested.
Simple expressions are not always sufficient for programming- sometimes we need multiple copies of an operand, or we need to discard 'junk'. Fortunately, Forth has a number of operators for manipulating the top of the stack.
drop and dup discard or duplicate the topmost element of the stack, respectively. swap exchanges the top two stack elements. over is similar to dup but instead pushes a copy of the second element of the stack. 2drop discards the top two elements of the stack, and 2dup makes a copy of the top two elements of the stack. (Equivalent to the sequence over over.) All of these except 2dup and 2drop are primitives.
In addition to the main "parameter stack", Mako has a second "return stack". The return stack is primarily used to store the return addresses of subroutine calls, but it can be freely manipulated. >r (to-r) and r> (r-to) move a value from the parameter stack to the return stack and vice versa. These operators are represented with the assembly opcodes STR and RTS, respectively. These words are commonly used to provide an intermediate storage location during a complex set of stack manipulations, but if used skillfully they can also provide very flexible new flow-control capabilities. For convinience, Maker also provides the mnemonic rdrop, which is equivalent to the sequence r> drop.
Forth programmers commonly use stack effect diagrams to illustrate the signature of their words. They consist of a block comment with a list of "before" and "after" stack elements separated by a --. The rightmost element of these lists is meant to be read as the topmost element of the stack.
: sum-cubed ( a b -- c )
+ dup dup * *
;
The stack diagram for this example shows at a glance that the word takes two arguments and yields a single result. For complex word definitions it may be helpful to place stack comments throughout your code to remind yourself of what is on the stack.
Here's a summary of the stack manipulation operations we've learned and their stack effect diagrams:
dup( a -- a a )drop( a -- )swap( a b -- b a )2drop( a b -- )2dup( a b -- a b a b )
If we use a pipe (|) to separate a view of the data stack from the return stack, we can illustrate the return stack words as well:
>r( a | -- | a )r>( | a -- a | )rdrop( | a -- | )
Pure functions and combinators are all well and good, but to do much of interest we're going to need some flow control structures.
if...else...then
This is your basic bread and butter if statement. The word if consumes a value from the stack and carries out some operations until a matching then statement if this value is not zero. An else is optional.
: double-if-two ( a -- b )
dup 2 = if dup + then
;
: odd? ( n -- flag )
2 mod if true else false then
;
Sometimes it's convenient to be able to check if something is zero- Maker also provides a negated if statement called -if which can be used identically with else and then:
: = ( a b -- flag )
xor -if true else false then
;
(Incidentally this is the most common idiom for confirming that two values are equal in Maker. The = definition is a handy utility routine.)
loop...while/until/again
The loop words are the Forth equivalent of C's do { ... } while(); construct. loop is always paired with while, until or again. while and until consume a value from the stack and cause execution to jump back to the matching loop if this value is zero or nonzero, respectively. again is used for infinite loops and jumps back to the matching loop unconditionally.
: palindrome? ( n -- flag )
dup >r 0
loop
base * over base mod + swap
base / swap
over
while
swap drop r>
xor -if true else false then
;
: stack-overflow ( -- )
loop
42
again
;
If you want to exit a loop early, the break word is what you're looking for- it will jump past the current loop's matching while, until or again.
: count-to-five ( -- 0 1 2 3 4 5 )
0 loop
dup 1 +
dup 4 > if break then
again
;
for...next
The Forth for loop is an easy way to repeat an operation several times. for reads a value from the stack, storing it as an index counter on the return stack. Every time next is encountered, this counter is examined. If the counter is greater than or equal to zero, execution resumes after the matching for.
: five-copies ( a -- a a a a a )
3 for
dup
next
;
If you need to access the loop index, r> and >r can do the trick, but Maker also provides the words i and j, which will push a copy the top or second elements of the return stack to the parameter stack. You can thus easily nest two for loops while still accessing loop indices.
: multiplication-table ( -- )
10 for
10 for
i j *
. # a word from Print.fs for printing a number to stdout
next
cr # another routine for printing a carriage return
next
;
Finally, exit can be used to return immediately from the current definition. If you use exit in the middle of a for loop be sure you first remove the loop index from the return stack!
Defining words are words that create other words, much like :. Some Forth implementations allow you to create your own defining words, which can be a very powerful metaprogramming facility. Maker does not provide this functionality, but it does come packed with a rich set of built-in defining words.
:const is used to declare constants. It requires a name and a numerical value, which can be based on other constants, variables or word definitions. When the name of a constant is refrenced, the value of the constant will be inlined.
:const byte-size 255
:const hexconst 0xDEADBEEF
:var declares a single-cell (one 32-bit int) variable. It requires only a name, and will be initialized to a value of zero. When the name of a var is refrenced, the address at which this variable is stored will be inlined. The word @ can be used to fetch the value stored at an address, while the word ! can be used to store a value to an address. @ and ! form the basis of all memory operations in Forth.
:var storage
: toggle ( -- )
storage @ # load the value in storage
not # negate the value from storage
storage ! # store the negated value to the var again
;
:array is much like :var, except it is used to allocate a group of several cells at once. It requires a name, a number of cells and a value with which to initialize the array.
:array buffer 256 0 # 256-element array filled with 0
:array tile 64 -1 # 64-element array filled with -1
:data is the most freeform approach to describing data. It requires only a name. When numbers or word names (including code or constants) are encountered outside a word definition, it is simply appended literally into the MakoVM memory image.
# initializing an array
:data data-array 0 1 2 45 23 12 11
# building a lookup table of function pointers
: func1 + ;
: func2 - ;
: func3 * ;
:data ftable
43 func1
45 func2
42 func3
:table is another way to create lookup tables. The most common application of this command is the creation of an array of strings. Strings will be laid out as they are encountered, and a list of pointers will be added to the rom after a ; is encountered. In addition to building the list of pointers, :table makes a constant available indicating the 1-indexed size of the table in cells by appending a -size suffix to the table name.
:table colors
"Red"
"Orange"
"Green"
"Blue"
"Indigo"
"Violet"
;
: color-name RN @ colors-size mod colors + @ ;
:image is used for including image data from external files. It requires a name, a quoted filename and a horizontal and vertical size (in pixels) of the tiles of the image. The pixels of the image will be stored one 32-bit color pixel to a cell in, one tile after another. Images will be discussed in more detail later on.
# load a sheet of 16 pixel wide by 32 pixel tall tiles
:image sprite-tiles "Scrubby.png" 16 32
:binary can be used to include a raw binary file in a Mako rom, optionally unpacking 8-, 16- or 32-bit words into mako cells and padding the binary to some fixed number of cells.
# include a binary file, storing 1 byte per cell, padded to 4096 cells:
:binary some-bin "File.bin" 1 4096
Mako uses a single, contiguous addressing space for memory. The first dozen or so memory locations contain registers which control I/O devices and dictate the layout of important memory regions. Maker exposes constants which allow you to treat registers as Forth variables. In this section we will deal with the most basic of these registers, and later we will discuss the specialized graphics registers controlling the Grid and Sprites.
PC contains Mako's program counter. Maker initializes this register to point to the first cell of a word called main, our entrypoint.
DP contains the address of the top element of the parameter stack, and RP does likewise for the return stack. Both stacks grow downwards- that is, the stack pointers are incremented as elements are pushed onto the stack. Maker allocates 50 cells for each by default, but this behavior can be overridden if you create your own array definitions with the names data-stack or return-stack.
: pick ( index -- element )
DP @ 2 - swap - @
;
RN is a memory-mapped random number generator. Loading from this register will return a random 32-bit integer. Storing to this register will have no effect.
: random ( max -- n )
RN @ swap mod
;
KY is similar to RN- a memory-mapped peripheral. Loading from this register will return a bit-vector representing the state of Mako's keypad. Maker provides the following masking constants for extracting individual keys: key-up, key-dn, key-lf, key-rt, key-a and key-b. The keys associated with these bits may vary from implementation to implementation, but the first four should generally be some sort of directional pad. Maker also offers the convenient word keys which is equivalent to KY @.
: left-key-pressed?
KY @ key-lf and if true else false then
;
CO is a (possibly) bidirectional debug port. Writing a value to this address should print the corresponding ASCII character to stdout. Some implementations may also support reading from this register to grab input from stdin. The Print.fs and String.fs standard library files contain useful definitions for printing values and reading values with the debug port, respectively. When it doesn't make sense, or for simplicity, MakoVM implementations may choose to do nothing when this register is manipulated- as the name would suggest, it's mainly for debugging.
AU is an 8-bit, unsigned, mono, 8khz pipeline to the DSP, facilitating crude music and sound effects. Writing to this address will enqueue a sample which will be played at the VM's nearest convenience. Implementations may (and really probably should) supply their own buffering. Implementations are free to ignore the AU register if sound cannot be conveniently provided. Game/Blip.fs has several helpful code examples and utility routines for dealing with sound.
KB provides access to typed keyboard input. As the VM runs, keyboard characters are buffered in a FIFO queue. Reading from KB will pop the next ASCII character out of this queue, or return a -1 if no more characters are buffered. Characters will always reflect the modifiers depressed when the key is typed- for example, shift+A will result in a capital A (ASCII 65) and ctrl+C will result in ASCII 3. Implementations which cannot provide keyboard input capabilities should always return -1 when reading from this address.
Mako has a series of registers related to general-purpose IO. Currently, the reference implementation defines support for basic reading and writing of local files. This centers around three registers:
XO is a bidirectional IO port, similar to CO. If a stream is selected and open, reading from XO will return a character of data. -1 will be returned at the end of a file or if the selected stream id is closed.
XA is used to select streams for XO. Mako will transparently maintain multiple stream handles for you, distinguished by ids. When files are first opened, an id will be assigned and stored to XA. If for any reason a file cannot be opened, -1 will be stored in XA- this id can be considered "always invalid". Subsequent changes to XA can select between open streams.
XS is the IO status register. Reading XS will return 0 for implementations which do not support external IO, and otherwise will return a bit vector representing supported features. Currently the lowest bit indicates support for reading local files and the second bit indicates support for writing to local files. Writing to XS delivers a command:
- 0 (
x-close) will close and flush the stream indicated byXA. - 1 (
x-open-read) will open a new stream to read based on a path indicated byXA. - 2 (
x-open-write) will open a new stream to write base don a path indicated byXA.
More commands may be added in the future.
Paths indicated by XA are a pointer to the head of a null-terminated string in Mako address space. Out of bounds or unterminated strings should result in silent failure when opening a file. Path formats are not currently defined in detail, so the only kind of path which should be used is a raw filename, interpreted as a file relative to the Mako executable.
Mako has a 320x240 pixel display. Every time the sync instruction is executed, the VM pauses execution and the display is refreshed. First, the screen buffer is cleared with the background color, then the grid is drawn, then sprites are drawn and the completed image is made visible. It's worth noting that the bit vector provided by querying KY is only updated when sync is called.
The clear color is stored in the CL register, and by default is 0xFF000000. Like all Mako color values, the clear color is stored as an ARGB packed integer, with 8 bits per color channel. If the alpha channel has a value other than 0xFF, a pixel is considered transparent.
The Grid itself consists of a matrix of 8x8 pixel tiles. Given a 320x240 display, this means 40x30 tiles are visible on-screen at once. The GP register points to a block of memory containing a sequential list of tile indices, counting from left to right and top to bottom. These indices indicate an offset added to the contents of the GT register, which should point to a set of sequential 64 word blocks, each representing the pixels of a tile. Tile indices count from zero, and tiles with a negative index are not drawn. Tiles can also contain transparent pixels. If the 31st bit of a tile index is set, (the z-bit) it will be drawn after any sprites. A mask constant called grid-z is available for manipulating the z-bit.
The Grid can also be scrolled. The SX and SY registers contain offsets added to the screen coordinates of tiles before they are drawn. Mako actually renders a 41x31-tile area based on the position of GP. By shifting GP every time the screen is scrolled 8 pixels with the scroll registers it is possible to produce a free-scrolling grid of arbitrary size- take a look at the OpenWorld.fs example to see how this technique works.
The GS register is also key for scrolling displays. When the grid is rendered, 41 cells making up a row of the display are fetched at a time, and then 41 plus the value of the GS register is added to a counter. If the horizontal rows of a tilemap in memory are wider than a single display, GS can be used to compensate for this so that the next row of tile data is read from the correct position.
# look up a tile in the current grid
# by its x and y coordinates.
: tile-grid@ ( x y -- tile-address )
GS @ 41 + * swap + GP @ +
;
Much like the return stack and data stack, if a grid and grid tileset are not defined explicitly, Maker will automatically allocate space for them. You can define your own grid and choose the initial configuration of the scroll and skip registers by defining arrays and constants with the names 'grid', 'grid-tiles', 'grid-skip', 'scroll-x', 'scroll-y' or 'clear-color'.
The standard library file Grid.fs contains a number of useful words for manipulating the grid.
In addition to the Grid, Mako can have 256 sprites on the screen at once. Sprites are drawn in the order of their indices, from back to front. Also like the grid, sprite data is stored in a special block of memory- here indicated by the SP register. The sprite table consists of 256 entries which are 4 cells long, for a total of 1024 cells. The meaning of the fields of an entry are as follows:
- Status flags. If the least significant bit is 0, the sprite is not drawn. Bits 15-12 and 10-8 indicate the height and width of the sprite, respectively, in increments of 8 pixels, with a minimum size of 8 on either axis. This means the maximum size of a sprite is 64x64 pixels. Maker provides constants for sprite sizes of the form "NxM" for every valid combination of sizes- for example
8x8,16x32and48x64. Bits 16 and 17 indicate that a sprite should be mirrored horizontally and/or vertically, respectively. Maker provides bitmasks for these fields calledsprite-mirror-horizandsprite-mirror-vert.
# given the status field, compute
# the width and height of a sprite in pixels:
: sprite-w 0x0F00 and 256 / 1 + 8 * ;
: sprite-h 0xF000 and 4096 / 1 + 8 * ;
-
Tile index. An offset from the Sprite Tile register,
ST. Tiles are zero-indexed and indexed based on the size of the current sprite, so tile 2 for an 8x8 sprite begins at SP+128, while tile 2 for an 8x16 sprite begins at SP+256. -
X position. The value of
SXandSYare subtracted from the X and Y position of a sprite to determine the final screen coordinates of a sprite. -
Y position. See above.
# configure sprite 9 as a 24x32 sprite,
# flipped horizontally and showing tile 37
# in the bottom right corner of the screen.
: showNine ( -- )
9 4 * SP @ +
24x32 sprite-mirror-horiz or over !
37 over 1 + !
296 over 2 + !
208 swap 3 + !
;
Also like the stacks and grid, Maker allocates memory for the sprite table if it is not explicitly allocated by the programmer. If you want to do it manually, use the names sprites and sprite-tiles for the sprite table and sprite tileset.
The standard library file Sprite.fs contains many useful words for manipulating sprites, including collision detection facilities.
Maker has a few more spiffy capabilities that deserve brief mention.
Whenever Mako attempts to jump to the address -1, the VM will halt. Maker provides the word halt as a convenient way to do this.
Anonymous inline words can be defined by enclosing code in curly braces. Like a string constant (enclosed in double quotes), these inline definitions will leave the address of the resulting chunk of memory on the stack:
: exec2 dup exec exec ;
: { "Hello" type } exec2 cr ;
' (pronounced "tick"), followed by a word name will, instead of compiling a CALL to the word definition, push the address of the first cell of the word definition. You can then call a dynamic address with exec. These instructions are useful for function pointer style tricks and supplying words with predicates.
: print-A 65 CO ! ;
: deferred-print ( -- )
print-A # the normal approach
' print-A exec # again with indirection
;
Maker is a single-pass compiler, so everything must be defined before it can be used. In general, this just means your source files should be arranged in a logical reading order, but for mutually-recursive functions this is a problem. The :proto word defines a prototype for a word that will be defined later. It only makes sense to do this for code definitions, and in all cases :proto should be used sparingly for purposes of readability. Maker will complain if you use :proto but fail to supply an implementation for the prototype.
:proto defined-later
: defined-first defined-later 2 - ;
: defined-later 42 78 + ;
Data may also require forward references. :ref works just like :proto, but is used to refer to and is satisfied by variables and variable-like definitions such as :array, :data or :table.
Finally, :vector is identical to : but starts a word definition with a preamble that makes it possible to revector the word later, dynamically changing the behavior of calls to the word. See the standard library file Vector.fs for support code, examples and a more detailed explanation.
Forth is as much an engineering approach as it is a programming language. When you're writing Forth programs, keep these ideas in mind:
-
Factor. Avoid long word definitions. Break complex words down into simple words which can be reused. Subroutine calls are cheap in Forth- use them freely.
-
Keep the stack shallow. If a word takes more than 3 arguments, consider breaking it down into smaller definitions. If you're having trouble remembering what's on the stack, it may be another sign you're doing too much in one place. You may be able to replace some arguments with constants by writing a less general word or simplify flow by introducing global variables.
-
Solve only the problem at hand. Don't overgeneralize your solutions or leave hooks for future expansion. If you don't need it now, there's a good chance you don't need it at all. Focused solutions lead to simpler code.
-
Change the problem. Sometimes the key to simplicity is realizing a problem doesn't need to be solved at all. Examine your underlying assumptions. Are there details of your model that can be left out? Features that are unnecessary? Can you use a different data structure or algorithm to accomplish a similar goal?
Now go out there and write some code!