Ir al contenido principal

Mariano Guerra's Log

This is my blog, more about me at marianoguerra.github.io

🦋 @marianoguerra.org 🐘 @marianoguerra@hachyderm.io 🐦 @warianoguerra

Bootstrapping OOP Part 3: Who Parses the Parser?

In Bootstrap post-collapse OOP technology with Wasm GC (Part 2) we implemented the minimum viable runtime in raw WebAssembly to run our prelude and bootstrap a basic OOP language.

But the prelude was provided to our runtime as text, and our runtime has no parser (yet), how do we feed the prelude it?

In Part 1 I embedded the following video:

The video description says:

Demonstration of the convoluted process of booting an Altair floppy disk using a Teletype and paper tape. This was required when the Disk Boot Loader PROM was not available in an Altair 8800

I'm pretty sure a paper tape reader and a floppy disk drive aren't going to be easy to find. Since the bootstrapping process is probably going to enter the Wasm implementation by hand, we can expect the capability to initialize its memory to some binary representation that our runtime can interpret.

The choice is between a data serialization format or bytecode for a small VM.

🤷‍♀️ Why not both?

You may have noticed that our language follows the idea of "code as data", a "program" is just a data structure that is evaluated according to some semantics specified in an environment.

Since code is data and data is code, loading a program into memory is the same as loading a data structure. Our data serialization format can also be used as the representation of a program.

VM Instructions

Our little VM is going to have 12 basic instructions:

  • PUSH_NIL
  • PUSH_1
  • PUSH_INT
  • PUSH_FLOAT
  • PUSH_STR
  • POP_NAME
  • POP_LATER
  • POP_PAIR
  • POP_SEND
  • POP_MSG
  • POP_ARRAY
  • POP_BLOCK

Let's explore them one by one:

PUSH_NIL: pushes the nil value onto the stack

PUSH_1: pushes the integer 1 onto the stack

Since 1 is going to be used as the value for true and a common value in itself it gets its own instruction.

PUSH_INT: push an integer

The value to push is in the next 8 bytes / 64 bits in the bytecode stream.

PUSH_FLOAT: push a float

Like PUSH_INT the value to push comes after the instruction, the value is encoded using the IEEE-754 Floating Point binary representation.

PUSH_STR: push a string

The immediate 64 bit value is split in two:

  • The top 32 bits represent the length of the string to read
  • The bottom 32 bits represent the byte offset where the string starts in memory

POP_PAIR: pops the two top values from the stack and pushes a pair with them back to the stack

The order in which the two items are encoded allows to load a cons list in the order the values are read in the bytecode stream, for example:

1 : 2 : 3

Is encoded as:

  • PUSH_INT 3
  • PUSH_INT 2
  • POP_PAIR
  • PUSH_1
  • POP_PAIR

POP_ARRAY: pops N items from the top of the stack and pushes an array with the items in reverse order.

This operation builds the array in reverse to allow the brave humans encoding programs by hand to enter the array items in order.

The instruction first pops the array length from the top of the stack, allocates an array of that size and then pops N items setting them in the array from back to front.

To create an array with the values 10, 20, 30 the instructions are:

  • PUSH_INT 10
  • PUSH_INT 20
  • PUSH_INT 30
  • PUSH_INT 3
  • POP_ARRAY

POP_BLOCK: same as POP_ARRAY but pushes a block back instead

POP_LATER: pops the top of the stack and pushes a Later wrapping the value back onto it

POP_NAME: pops a string from the top and pushes a name using the string back

POP_MSG: pops a value (obj) and a string (verb) and pushes a message back

POP_SEND: pops a value (obj) a string (verb) and another value (subj) and pushes a send back

Notice that all "composite" types except Pair encode the values in the byte stream in the natural order they are entered from left to right.

VM Implementation

With this design we can implement a set of functions that evaluate the instructions and operate on a stack, if the instructions are set up correctly the end result is a stack with a single item that represents the program or data structure we wanted to build.

The most basic function to implement is a function that takes a stack, an instruction and an optional immediate value and returns a new stack with the result of executing the instruction on the input stack.

Let's call it $vmEvalInstr, we can implement it using the br_table instruction which let's us implement a pretty basic and verbose switch statement.

On top of it we can implement a function that takes a stack and a program counter, reads the next instruction at the memory location pointed by the program counter, if the instruction needs an immediate value it loads it from the next memory position, calls $vmEvalInstr and returns the new stack and the new position for the program counter (since depending on the instruction it may advance one or more bytes).

Let's call it $vmEvalNextInstr. This function uses the multiple return feature of Webassembly to return both values.

If the instruction is not in the valid range of instructions the function returns the stack and program counter as they were passed, this means that any instruction outside the range of valid instructions works as the halt instruction.

Finally we want to run a complete program, for that we can define a function that takes a stack, a program counter where the program should start and runs the next instruction until the returned program counter is equal to the previous one.

This means the program encountered a bad/halt instruction, for consistency let's define a standard HALT instruction with the value 255, it has no special meaning or implementation, just a standard invalid instruction that marks the end of a program.

Let's call that function $vmEvalRun.

To make sure our program terminates we should append an invalid instruction at the end, just in case the remaining memory accidentally contains valid instructions (a memory initialized all with 0s is a valid program that pushes nils forever).

With these three functions and one for the implementation of each instruction we are ready to load our binary encoded prelude, but we haven't defined how the stack is implemented.

To take advantage of the code we already have we can implement it as a cons list using the Pair data type.

Encoding the Prelude

Now it's time to encode our prelude in binary.

Since I still have computers around I adapted the existing parser to generate an AST that can emit its binary representation: fatt.ast.js

It also does the string layout in memory for the PUSH_STR instruction for us.

With this adapted parser we can parse the prelude and get the binary bytecode back, the implementation above generates a bytecode stream 4676 bytes long.

Optimizing the Encoding for Input Happiness

Thinking about the person that may have to read and write the bytes manually we can do some small optimizations.

The first is to notice that the prelude is full of repeated symbols, the most common ones are it and that. If we define instructions for PUSH_SYM_IT and PUSH_SYM_THAT then the prelude takes 4140 bytes.

The next observation is that many integers are really small, using 8 bytes to write an integer or the length of something small is 7 bytes too many, the second optimization I implemented is to check if the instruction has the 8th bit set, if it does then the immediate read from memory is only one byte long.

I could have used a variable length encoding for numbers like Wasm does, but it would take more code to implement and more effort to encode by hand.

With this optimization the prelude takes 3811 bytes.

We could continue optimizing but you get the idea :)