ExpDesc Concept

Before introducing the reading and writing of tables, this section first introduces ExpDesc, the core data structure of syntax analysis.

Problems with Table Construction

There is a performance issue with the construction of the table implemented in the previous section. For example, for the general type [ exp ] = exp, the expression corresponding to the key and value will be loaded to the top of the stack through the load_exp() function in turn as a temporary variable; then SetTable bytecode will be generated, including The indices of the two temporary variables on top of the stack. code show as below:

     Token::SqurL => { // `[` exp `]` `=` exp
         nmap += 1;
         self. lex. next();

         self.load_exp(sp); // load key to the top of the stack
         self.lex.expect(Token::SqurR); // `]`
         self.lex.expect(Token::Assign); // `=`
         self.load_exp(sp + 1); // load value to the top of the stack

         self.byte_codes.push(ByteCode::SetTable(table, sp as u8, sp as u8 + 1));
     },

This is wasteful because certain expression types, such as local variables, temporary variables, and constants, can be referenced directly without being loaded on the stack. For example, the following Lua code:

local k = 'kkk'
local v = 'vvv'
local t = { [k] = v }

According to the current implementation, the runtime stack and bytecode sequence are as follows:

    +---------+
  0 |  "kkk"  |---\[1] Move 3 0
    +---------+   |
  1 |  "vvv"  |---|-\[2] Move 4 1
    +---------+   | |
  2 |   { }   |<--|-|---------\
    +---------+   | |         |
  3 |  "kkk"  |<--/ |   --\   |
    +---------+     |      >--/[3] SetTable 2 3 4
  4 |  "vvv"  |<----/   --/
    +---------+
    |         |

In fact, neither of these two temporary variables is needed, but only one bytecode is needed: SetTable 2 0 1, where the three parameters are the indexes of the table, key, and value on the stack. This is also the way Lua is officially implemented, that is, to directly refer to the index as much as possible, and avoid unnecessary temporary variables. The runtime stack and bytecode sequences are as follows:

    +---------+
  0 |  "kkk"  |---\
    +---------+    >--\[1] SetTable 2 0 1
  1 |  "vvv"  |---/   |
    +---------+       |
  2 |   { }   |<------/
    +---------+
    |         |

These two methods (whether to introduce temporary variables) correspond to two types of virtual machines: stack-based and register-based.

Stack-based and Register-based

First list the bytecode of the current implementation in the above example:

Move 3 0    # Load k to position 3. Now 3 is the top of the stack
Move 4 1    # Load v to position 4. Now 4 is the top of the stack
SetTable 2 3 4

In the current implementation, we can be sure that the key and value are to be loaded to the top of the stack, so the first parameter (that is, the target address) in the two Move bytecodes can be omitted; in addition, we can also be sure when setting the table, the key and value must be at the top of the stack, so the last two parameters of SetTable bytecode can also be omitted. So the bytecode sequence can be simplified as follows:

Push 0     # load k to the top of the stack
Push 1     # load v to the top of the stack
SetTable 2 # Use the two values at the top of the stack as key and value,
           # and set them to the table at position 2

This method of operating parameters through the top of the stack is called a stack-based virtual machine. The virtual machines of many scripting languages such as Java and Python are based on stacks. The method of directly indexing parameters in the bytecode (such as SetTable 2 0 1) is called register-based virtual machine. The "register" here is not a register in the computer CPU, but a virtual concept. For example, in our Lua interpreter, it is a register implemented by a stack and a constant table. Lua was the first (official virtual machine) register-based mainstream language.

The above is the write statement through the table as an example. Let's introduce another example that is easier to understand, the addition statement (although we have not implemented addition yet, it is indeed easier to understand). For the following Lua code:

local
local a = 1
local b = 2
r = a + b

The bytecode generated by a stack-based virtual machine might look like this:

Push 1    # load a to the top of the stack
Push 2    # load b to the top of the stack
Add       # Pop and add the 2 numbers at the top of the stack, and push the result to the top of the stack
Pop 0     # Pop the result at the top of the stack and assign it to r

The bytecode generated by a register-based virtual machine might look like this:

Add 0 1 2

It can be seen intuitively that the number of bytecode sequences based on the register virtual machine is small, but each bytecode is longer. It is generally believed that the performance of register-based bytecode is slightly better, but the implementation is more complicated. A more detailed description and comparison of these two types is beyond the scope of this article, and I have no ability to introduce them. The reason why I chose register-based in this project is simply because that's what the official Lua implementation does. I didn't know these two ways until I even wrote part of the project. Next, just continue to follow the register-based method instead of entangled with the stack-based method.

One thing to note is that the register-based method is just trying to avoid using the temporary variable on the top of the stack. It is also needed when necessary. How to choose a register or a temporary variable will be described in detail later.

Intermediary ExpDesc

Since we want to follow the register-based method, why do we need to load both key and value to the top of the stack and use the stack-based method in the construction of the table in the previous section? It's because we can't implement a register-based approach yet. Now load_exp() function directly generates bytecode and loads it to the specified position of the stack after encountering Token. code show as below:

     fn load_exp(&mut self, dst: usize) {
         let code = match self. lex. next() {
             Token::Nil => ByteCode::LoadNil(dst as u8),
             Token::True => ByteCode::LoadBool(dst as u8, true),
             Token::False => ByteCode::LoadBool(dst as u8, false),
             Token::Float(f) => self. load_const(dst, f),
             Token::String(s) => self. load_const(dst, s),
             // omit other tokens
         };
         self.byte_codes.push(code);
     }

Therefore, when parsing the general-purpose writing statement of the above table, when the expression of key and value is encountered, it is immediately loaded to the top of the stack, and it becomes a stack-based method.

And if we want to realize the register-based method to generate bytecodes such as SetTable 2 0 1, when encountering key or value expressions, we cannot generate bytecodes immediately, but need to save them temporarily and wait for the opportunity When it is mature, deal with it according to the situation. Or use the Lua code at the beginning of this section as an example:

local k = 'kkk'
local v = 'vvv'
local t = { [k] = v }

The table construction statement in line 3 is parsed as follows:

[, determined as a general formula;
k, as a Name, first determine that it is a local variable, the index is 0, and then save it as a key;
] and =, as expected;
v, as a Name, is also determined to be a local variable, the index is 1, and then saved as a value;
At this point, an initialization statement is completed, and the indexes of the key and value saved before are 0 and 1 respectively, so the bytecode SetTable 2 0 1 can be generated.

The key here is "save the key/value". We are going to add this staging mechanism now. A solution is to directly save the read Token. For example, in this example, the key and value are saved as Token::Name("k") and Token::Name("v") respectively. But doing so has several problems:

A small problem is that Name may be a local variable or a global variable. We will see later that the handling of these two variables is different, and Token::Name cannot distinguish between these two types.
The slightly bigger problem is that some expressions are more complex and contain more than one Token, such as t.k, a+1, foo(), etc., which cannot be represented by a Token. To support tables in this chapter, we must support expression statements such as t.k or even t.k.x.y.
The bigger problem is that table reads t.k can at least be implemented in a stack-based way, but table writes cannot. For example, t.k = 1 is the left part of the assignment statement. When parsing, it must be saved first, then parse the rvalue expression, and finally execute the assignment. To support the write statement of the table, it is necessary to add this temporary storage mechanism first. This is why this section must be inserted before supporting the read and write functions of the table.

So, we need a new type to hold intermediate results. To this end we introduce ExpDesc (the name comes from the official Lua implementation code):

#[derive(Debug, PartialEq)]
enum ExpDesc {
     Nil,
     Boolean(bool),
     Integer(i64),
     Float(f64),
     String(Vec<u8>),
     Local(usize), // on stack, including local and temporary variables
     Global(usize), // global variable
}

Now it seems that its type is the type currently supported by the expression, but Token::Name is split into Local and Global, so introducing this type is a bit of a fuss. But in the next section to support the reading and writing of tables, as well as subsequent statements such as calculation expressions and conditional jumps, ExpDesc will show its talents!

The original parsing process is to directly generate bytecode from Token:

     Token::Integer -> ByteCode::LoadInt
     Token::String -> ByteCode::LoadConst
     Token::Name -> ByteCode::Move | ByteCode::GetGlobal
     ...

Now that the ExpDesc layer is added in the middle, the parsing process becomes:

     Token::Integer -> ExpDesc::Integer -> ByteCode::LoadInt
     Token::String -> ExpDesc::String -> ByteCode::LoadConst
     Token::Name -> ExpDesc::Local -> ByteCode::Move
     Token::Name -> ExpDesc::Global -> ByteCode::GetGlobal
     ...

Syntax Analysis and ExpDesc

ExpDesc is very important, and I will introduce it from another angle here.

Section 1.1 The general compilation process is introduced in the basic compilation principle:

              Lexical Analysis      Syntax Analysis      Semantic Analysis
Character Stream --------> Token Stream --------> Syntax Tree --------> Intermediate Code ...

We still use the above addition code as an example:

local
local a = 1
local b = 2
r = a + b

According to the above general compilation process, for the addition statement in the last line, the syntax analysis will get the syntax tree:

Then during semantic analysis, first see +, and know that this is an addition statement, so you can directly generate bytecode: Add ? 1 2. Among them, ? is the target address of the addition, which is handled by the assignment statement and is ignored here; 1 and 2 are the stack indexes of the two addends respectively.

But our current approach, which is also the official implementation of Lua, omits the "semantic analysis" step, directly generates intermediate code from syntax analysis, and generates code while analyzing. Then when syntactic analysis, you can't have a global perspective like the above-mentioned semantic analysis. For example, for the addition statement a+b, when a is read, it is not known that it is an addition statement, so it can only be saved first. When + is read, it is determined that it is an addition statement, and then the second addend is read, and then bytecode is generated. We introduce an intermediate layer ExpDesc for this purpose. So ExpDesc is equivalent to the role of the "syntax tree" in the general process. It's just that the syntax tree is global, and ExpDesc is local, and it is the smallest granularity.

             Lexical Analysis            Syntax Analysis
Character stream --------> Token stream ----(ExpDesc)---> intermediate code ...

It can be seen intuitively that this method of Lua omits the semantic analysis step, and the speed should be slightly faster, but because there is no global perspective, the implementation is relatively complicated. A more detailed description and comparison of these two approaches is beyond the scope of this article. We choose to follow Lua's official implementation method and choose the method of syntactic analysis to directly generate bytecode.

Summary

This section introduces the concept of ExpDesc and describes its role. In the next section, the existing code will be modified based on ExpDesc.

Build a Lua Interpreter in Rust