preface
In the previous article, “The Entire Programming Language in typescript (Pseudo),” we defined an abstract syntax tree with TS. The job after that is the whole back end, generating object code.
But what about compiling to that environment? Next comes the entire virtual machine as the target of compilation
Type and value
The values were defined in the previous section, designing abstract syntax trees. However, for virtual machines, the processing methods and concerns are not the same, so it needs to be processed separately.
Start by defining an enumeration that represents all the types that need to be processed.
export enum LxType {
nil, int, func
}
Copy the codeThere are three types — null, integer, and function. While a value is a tuple, the two-element distribution represents the value’s type and parameters.
One value for an empty type.
type Nil = [LxType.nil, null]
Copy the codeFor integers, the argument is a numeric value.
type Int = [LxType.int, number]
Copy the codeIn the case of a function, the argument is a prototype of the function.
type Func = [LxType.func, Proto]
Copy the codeFunction, including the following properties.
export class Proto {
numParams: number = 0 // Fixed number of parameters
code: number[] = [] / / instruction sheet
slotSize: number = 0 [] // The number of registers
maxStackSize: number = 0/ / stack space
constants: LxValue[] = [] / / often scale
protos: Proto[] = [] // Subfunction prototype table
}
Copy the codeFixed number of arguments records how many arguments this function passes;
Statements in the body function are compiled into instructions for the virtual machine. The instruction table is a list of these instructions.
The operation of the instruction is carried out on the stack. The stack space indicates the total size of the stack required by the function, facilitating the initialization of the stack.
Values such as int(1) are not included in instructions, which have a finite length. There’s a constant scale;
For a single function, there can be multiple inner functions, and the subfunction prototype table holds the prototypes of these inner functions.
Then all the types that our virtual machine can process can be defined.
type LxValue = Nil | Int | Func
Copy the codeRegisters and stacks
In more low-level languages such as C/C ++ or Rust, we often think about whether to put certain data on the heap or on the stack. The heap capacity is large, while the stack access speed is relatively fast. And this stack is the basic structure for processing computation in our virtual machine.
This “virtual stack” is needed to implement both functions, local/temporary variables storage, and operations. This is actually a function of the simulated CPU.
We logically split the stack into two parts. The first part is used to store local/temporary variables, namely registers. The latter part implements the computation part.
So when c = a + b is calculated, the stack changes as follows.
- The initial state
In this case, we implement the stack with an array.
export class Stack {
#slots: LxValue[] = []
// The top index of the stack. -1 indicates the empty stack
#top: number = -1
constructor(size: number) {
this.#slots = new Array(size).fill(null)
this.#top = -1
}
// Convert relative index to absolute index
absIndex(idx: number) {
return idx >= 0 ? idx : (idx + this.#top + 1)}/ / into the stack
push(val: LxValue) {
if (this.#top + 1> =this.#slots.length)
throw new Error('stack: stackoverflow! ')
this.#top++
this.#slots[this.#top] = val
}
/ / out of the stack
pop() {
if (this.#top < 0)
throw new Error('stack: stack is empty! ')
const val = this.#slots[this.#top]
if(! val)throw new Error(a)this.#slots[this.#top] = nil()
this.#top --
return val
}
// Get the value corresponding to the index
get(idx: number) {
const absIdx = this.absIndex(idx)
const val = absIdx >= 0 && absIdx <= this.#top
? this.#slots[absIdx]
: null
if(! val)throw new Error('out of range! ')
return val
}
// Set the corresponding index value
set(idx: number, val: LxValue) {
const absIdx = this.absIndex(idx)
if (absIdx >= 0 && absIdx <= this.#top)
this.#slots[absIdx] = val
else
throw new Error('stack: invalid index')}// Get the top of the stack
top() {
return this.#top
}
// Set the top of the stack
setTop(n:number){
if (n + 1> =this.#slots.length)
throw new Error('stack: stackoverflow! ')
this.#top = n
}
// Push the top value of the stack and write it to the corresponding index
replace(idx: number) {
const val = this.pop()
this.set(idx, val)
}
}
Copy the codeCall frame and stack
Aside from the “stack” of the stack, on the other hand, we often use the concept of “stack” — the call stack. When a function call is executed, a new call frame is pushed onto the call stack. When the function is finished, the call frame is pushed off the stack and continues with the previous function.
First we define a call stack that records the call frames at the top of the stack.
And then to implement the stack operation. If it is already the bottom stack, continuing out of the stack will terminate the program.
The Terminate method is not yet easy to implement, so define it as an abstract method for now. So the LxCallStack is an abstract class.
export abstract class LxCallStack {
#top: LxCallFrame
constructor(top:LxCallFrame){
this.#top = top
}
push(frame:LxCallFrame){
frame.prev = this.#top
this.#top = frame
}
pop(){
const top = this.#top
if(top.prev){
this.#top = top.prev
return top
}else{
this.terminate()
}
}
abstract terminate(): void
}
Copy the codeAnd in our call frame, we record its last call frame.
The call frame is directly related to the function, and naturally it needs to record the prototype of the current function.
Function instructions are executed on the call frame, so it is also necessary to record the call stack for exit and push.
export class LxCallFrame {
prev: LxCallStack | null = null
resultSlot :number
#proto: Proto
#stack: LxCallStack
constructor(proto:Proto,stack: LxCallStack){
this.#prev = prev
this.#stack = stack
}
}
Copy the codeCall frame
In the previous section, we combined call frames with call stacks and designed a prototype call frame.
But we also need to combine the call frame with the stack so that the call frame has the ability to execute instructions.
How to combine? Inheritance!
Since the maximum required stack space is recorded on proto, it happens to be passed to the stack via super().
Also by setTop(), the space reserved for the register is slotSize.
ResIdx records where the results of the call frame need to be written after execution has finished
export class LxCallFrame extends Stack {
prev: LxCallFrame | null = null
#stack: LxCallStack
#resIdx: number
#proto: Proto
constructor(proto: Proto, stack: LxCallStack) {
super(proto.maxStackSize)
this.setTop(proto.slotSize - 1)
this.#proto = proto
this.#stack = stack
this.#resIdx = resultIdx
}
}
Copy the codeSince the call frame records the prototype of the corresponding function, it is natural to extend more methods to the stack.
- Record the current instruction position, and instruction jump, get the method of the next instruction.
export class LxCallFrame extends Stack {
// ...
// Instruction index
#pc = 0
// Instruction jump
addPC(n: number) { this.#pc = this.#pc + n }
// Get the next instruction
fetch() {
const ins = this.#proto.code[this.#pc]
this.#pc = this.#pc + 1
return ins
}
}
Copy the code- To obtain a constant
export class LxCallFrame extends Stack {
// ...
pushConst(idx: number) {
const s = this.#proto.constants[idx]
this.push(s)
}
}
Copy the code- Let’s expand on the stack
export class LxCallFrame extends Stack {
// ...
// Pushes the value at the specified index to the top of the stack
pushValue(idx: number) {
const val = this.get(idx)
this.push(val)
}
// Copy values from one location to another location
copy(fromIdx: number, toIdx: number) {
this.pushValue(fromIdx)
this.replace(toIdx)
}
}
Copy the code- Extend the operation for function calls
Start by pushing the function onto the stack
export class LxCallFrame extends Stack {
// ...
// Push the subfunction at the specified index to the top of the stack
loadProto(idx: number) {
const proto = this.#proto.protos[idx]
this.push(func(proto))
}
}
Copy the codeTo execute a function call, before the call is executed, the executing function and the call parameters need to be arranged at the top of the stack. So I need to pass in the number of parameters.
After execution, arguments and functions are off the stack. Function is used to generate new call frames. Parameter is placed on the top of the stack for the new call frame. According to the number of fixed parameters described in the function prototype, if it is insufficient, it will fill in nil, if it is too much, it will drop out.
export class LxCallFrame extends Stack {
// ...
// Push the subfunction at the specified index to the top of the stack
call(arguLength: number) {
let argus: LxValue[] = []
while (arguLength-- > 0) {
argus.push(this.pop())
}
argus.reverse()
const fn = this.pop()
if (fn[0] !== LxType.func) throw new Error(a)const proto = fn[1]
const stack = this.#stack
const nframe = new LxCallFrame(proto,stack)
for (let i = 0; i < proto.numParams; i++) {
nframe.set(i,argus[i] ?? [LxType.nil, null])}this.#stack.push(nframe)
}
}
Copy the codeReturns the result of a function call, pushing it into the corresponding resIdx register of the previous call frame.
export class LxCallFrame extends Stack {
// ...
// Push the result at the specified index to the top of the stack
return(idx: number) {
const val = this.get(idx)
if(! val)throw new Error(a)if (this.#prev) {
this.prev.push(val)
this.#stack.pop()
}
}
}
Copy the codeAfterword.
We’ve defined a prototype virtual machine above, but this virtual machine has only one shelf for its most important function — executing code.
The next article will add this functionality to the virtual machine.