Teach you how to implement a virtual machine with JS

What is a virtual machine ？

Virtual machine is to create a virtual computer by programming . What is a computer ？ I remember when I was in grade two , First computer class , The computer teacher explained it to me like this ： The essence of a computer is a computing machine . this sentence , Left a big question mark in my little head . Until I grow up , I knew that. , This is clearly ： Listen to your words , If you listen to a piece of nonsense . Why? ？ The teacher is right , A computer is essentially a computing machine . however , The computers we come into contact with everyday , Such as ： The notebook 、 Desktop computer 、 mobile phone 、 Raspberry pie, etc. , But they are all lively 、 Vivid . Be able to design and build airplanes , I can fish and play games . It looks like buying food with us 、 The commonly used two digit addition, subtraction, multiplication and division calculation, such as taking a bus, does not have a dime relationship . This is because modern computers have been developed for 70 or 80 years , Countless great scientists and outstanding engineers , Give computer performance 、 The function and appearance have brought earth shaking changes . The function of the original electronic computer was really used for trajectory calculation . Given the specified trajectory equation , Then the initial velocity of the shell 、 The firing angle parameter is substituted into , The landing point of the shell can be accurately calculated . conversely , It can also be based on the measured final velocity and angle of the shell , Calculate the firing point and velocity of the shell . These are dedicated computers . Insert a sentence , In the process , Computers have input and display devices . It's just that the display device makes modern people feel a little crude , It uses only a few light bulbs or paper tapes to output the results for people to read . The input device is also very simple , Not a keyboard , Also use paper tape . Its program memory is unimaginable , The polarity of magnetic beads is directly used to represent binary 0 and 1, An instruction has eight bits , It is represented by a string of eight magnetic beads . later , With the technology upgrading , Computers have become more powerful and cheaper , Scientists and engineers began adding graphic displays to computers 、 Mouse and other devices . Again , Engineers have also developed more powerful software , To solve problems in more fields . Such as ： Bank accounting software , Supermarket cashier software , Office software . As software becomes more complex and diverse , What comes with it is software that needs management software to manage them . This is the operating system .
Back to the calculation itself , Let's give a simple calculation example ： Suppose we are now in the first grade of primary school , Having a math class , The math teacher arranged for the students to calculate “ 3 + 9 = ”. then , The students began to take out their notebooks , Finally, tell the teacher the answer . Think about this scenario , Each of us is like a computer , Try to work out the mathematical formula given by the teacher , And report the results to the teacher . Is the teacher like a programmer ？ He will program “ 3 + 9 = ” Input “ Computer ”, And then wait “ Computer ” Give feedback . Of course , There may be something wrong with some computers in the process , Figure out some ironic answers . Then the programmer will catch the computer , Start hand in hand with him debug, Until he calculates the correct answer . Of course, some computers may need to stay in the classroom after school to continue to calculate , Until the parents find the school , Take him back .
Analyze the process , A normal computer needs several key components . We need program memory - It's usually your arithmetic book , Because we have to copy down what the teacher has entered , Easy to calculate . We also need an acting herb , You can't write the calculation process directly into the arithmetic book . This book can be understood as RAM. We also need an arithmetic unit with normal computing power – This is our brain .

Arithmetic book

Acting herb

Our brains , From program memory （ Arithmetic book ） Read characters one by one . The first thing to read is 3, We drew three dots on the performance . Then I read a plus sign , We know that we have to add . And then I read 9, Also, nine dots are drawn on the performance herb . Combined with the previous judgment, it is an addition operation , Let's draw three dots on the next line , Draw nine more dots , The last count is 12 A little bit . So we get “3 + 9 = 12”. You run to the teacher , Tell the teacher your answer with a proud face . Then the teacher praised you for your intelligence , I will give you a little red flower , And declare you the prettiest kid in the class .
A typical computer should consist of an arithmetic unit 、 Memory 、 controller 、 Input device and output device are composed of five basic components . Corresponding to the scene above , Arithmetic units and controllers are our brains , Memory is our arithmetic book and algorithm 、 Input devices are our eyes , The output device is our mouth .
A virtual machine is a virtual computer , Therefore, it also needs to include the above five components .

Use JS Implement a simple virtual machine that supports binocular operation

Memory

Our virtual machine architecture also needs to meet the requirements of computers . But for ease of understanding , Let's first implement the arithmetic unit 、 Controller and memory functions . Input and output , We will support . Arithmetic unit we use js With its own computing power . Memory is divided into program memory and operation memory , Used to store program code or operations , We use arrays to implement . The function of the controller is to control the reading of the program and the reading and writing of the operation result data , We also use js Code to simulate .

Memory can be understood as ： A large cabinet composed of drawers , If you don't understand, you can look at the express cabinet above , It is also composed of small drawers . Only one express box can be placed in each drawer . Multiple drawers hold your double 11 Buy all the express （ Maybe just a small part ）. The difference between our storage and express cabinet is , All the drawers are arranged in a straight line , Instead of dividing into multiple sub cabinets .

Program memory

Program memory stores code . Code can be divided into opcodes and operands . Back to the example above , The opcode is in the formula “+”, Two of the operands are ：3 and 9. In the example above , We use mathematical language to describe a calculation . If expressed in the form of operands plus opcodes , So the above formula , It's written as ： Operands (3) + opcode (+) + Operands (9) . When our computer describes a calculation , In a slightly different way . Usually ： opcode + Operands perhaps A single opcode The way . that , What is stored in our program memory is ： One or more opcode + Operands or opcode The orderly arrangement of .
Hard to understand ？ Put a picture and see .

Our program is running , You need to load the code in memory step by step . The first thing to load is the opcode . If the operation code corresponds to a data that needs to be operated , This is usually followed by an operand . At this time , We need to load subsequent operands . After loading , According to the operation code , Perform the corresponding calculation . Take the example above , The operation code in the formula is “+”, This means that we need to compare two operands 3 and 9 To add .

Data storage

The program is in the process of calculation , There may be some intermediate results , We need to save these intermediate results , For later calculations . This requires a data memory , Store these intermediate data .

controller

While the program is running , We need to load the operands and opcodes from the program memory step by step , There can be no mistake at all . therefore , We use a variable to record the location of the next code to be read . This variable is called PC, Its full name is Program Counter.
The data storage and reading during the program running cannot be irregular . Why? ？ for instance , Some children calculate math problems , Often because in calculus , The carry symbol is not carefully marked , Finally, add the extra time , Forget to add , Cause calculation error . This is a typical case where intermediate data is not stored according to the rules, resulting in an error in reading intermediate results , To get the wrong answer . So you need a rule to manage this data . We have defined a thing called stack to store these data . Simple understanding , Stack is a memory structure stored in data storage . It is a large cabinet composed of a series of small memory drawers . Why are there so many small drawers ？ Because complex programs may have multiple intermediate results , Therefore, it is necessary to keep multiple small drawers separately . Hard to understand ？ such as , We calculated ：12 + 23 * (123 / (12+1)) - 6 . This formula is a little complicated , Segment calculation is required . So how to ensure that these intermediate data are stored in the correct location ？ This requires a variable to point to the location of the current data store . This variable is called SP, The full name is Stack Pointer. in addition , This stack is a little special , When it stores data , Always start with the high address , Then store down in turn . When reading data , First read from the low address , Then read up . Be careful ： It's important to understand the above sentence . If you can't understand , Let's give you an example ： There was a courier with obsessive-compulsive disorder who deposited the express to the express cabinet , He first put the express in the highest drawer , Then put the express down one by one . When you pick up the express , There is also obsessive-compulsive disorder , First open the drawer from the lowest place , Then go up until the top express .

Arithmetic unit

Speaking of arithmetic , We said before , Our virtual machine supports binary computing . What is binomial operation ？ The simple understanding is that binomial operation is the operation of two numbers . Since it is two numbers , Then you must need two memories to store these two numbers respectively . Why? ？ Let's look at the example above , In the second screenshot , When we calculate , Three points and nine points respectively , This is not saved in two separate places ？ actually , In the calculation of the above example , We used three positions , Store two operands and the result of the operation respectively . This is a bit of a waste of memory . In fact, you can use only two memories to complete the calculation . To achieve this goal , Added a variable , This variable is called AX, Generally, the calculation results are stored .
Then there is how to realize the operation function . Operation function we use js Code operation function to simulate , Support separately ： Logical operations 、 Boolean operation 、 Shift operation and arithmetic operation .
Once again remind , We support binomial operations , You need to manipulate two operands with an opcode to get the result .
How to realize the operation function ？ Take addition as an example , We first put an operand on the stack , Then put the second operand in AX in , And then use js The operation function of , Operate on these two numbers , Finally, put the operation result into AX in . Other calculation processes are similar , It also uses the data at the top of the stack and AX Data operation in , Then deposit the results in AX in .

opcode

As mentioned earlier , We have designed the memory 、 Functions of controller and arithmetic unit . But how to use them to complete the calculation function ？ Or the example above , We know that a program is composed of opcodes and operands . Opcode is the function of commanding controller and arithmetic unit to complete the operation of operands .
So what opcodes are needed to implement basic computing functions ？

Data storage and loading

Through the functions of the arithmetic unit described above , We know , The function of the arithmetic unit is to AX And the data at the top of the stack . therefore , We need some instructions , Load the operands in the program into AX And the top of the stack .
First , Let's define a IMM Instructions , Load an immediate into AX in ;
then , Let's define a PUSH Instructions , take AX The value in , Load into stack ;
such , We have the ability to put an operand on the top of the stack . Just use IMM Put an immediate number in AX in , And then use PUSH Instructions , You can put the data on the top of the stack .
The problem is coming. , We want to store a certain value in a specified location on the stack （ Address ） What to do ？
Simple , Design a new instruction , be called SI, Its function is to take the value at the top of the stack as the destination address , take AX The value of is added to the destination address of the stack . Be careful , In this step , We need to move this address off the stack . Why? ？ Because it is useless for this operation . If you use , Just use IMM+PUSH Just put the address back on the stack .
But there is another problem , How do we access the values we store ？
By defining a LI Instructions , Load values from the stack into AX in . But the stack is a piece of memory , What we need to load is the data of a certain address in the stack , What do I do ？ We will LI This design ：LI Instruction to AX The value stored in is the address , From the stack AX The value of the memory pointed to by the address stored in is loaded into AX in .
Above , We used IMM,PUSH,SI and LI These four instructions put the immediate number into AX、 Put the immediate at the top of the stack 、 Put the immediate into the specified position on the stack , Load data from the specified address of the specified stack to AX.

Data operation

Use the above instructions , We can put the two operands in the binomial operation on the top of the stack and AX. How to calculate it ？ According to the four types of operations we need to support , Need to design 16 Instructions , Namely ：

• Logical operations
  • OR or
  • XOR Exclusive or
  • AND And
• Boolean operation
  • EQ equal
  • NE It's not equal
  • LT Less than less than
  • GT Greater than greater than
  • LE Less than or equal to
  • GE Greater than or equal to
• Shift operation
  • SHL shift left
  • SHR shift right
• Arithmetic operations
  • ADD Add
  • SUB reduce
  • MUL ride
  • DIV except
  • MOD Remainder
    It needs to be explained , The arithmetic unit needs to read the data at the top of the stack every time , This step is also accompanied by the data out of the stack . Well understood. , The data at the top of each stack is only involved in one data operation , After the data is involved in the calculation , There is no point in keeping it , Directly out of the stack . It's a bit like used calculators can't escape the fate of being discarded .
    Program exit
    After our program runs, we need to specify an exit instruction , To tell the virtual machine to stop running .
• EXIT
  • The virtual machine executes to this instruction , Will stop moving PC Read next instruction

To sum up , We ordered one by one CPU, It currently supports 23 Orders . thus , We just need to use code to implement our above instructions , So we realized a super simple but usable virtual machine .

Realization CPU Code and CPU Test of

Close the door and let it go ！！！

  //only support minimum function 
  class CPU {
  
    constructor(stackSize) {
      this.stackSize = stackSize
      this.pc = 0
      this.sp = this.stackSize - 1
      this.bp = this.sp
      this.ax = 0
      this.stack = new Array(this.stackSize)
      const opcodes = [
        "IMM", "LI", "LC", "SI", "SC", "PUSH",
        "OR", "XOR", "AND", "EQ", "NE", "LT", "GT", "LE", "GE", "SHL", "SHR", "ADD", "SUB", "MUL", "DIV", "MOD",
        "EXIT"
      ]
      this.OPCodes = {}
      let i = 0
      opcodes.forEach(prop => {
        this.OPCodes[prop] = i++;
      })
    }

    loadProgram(code) {
      this.code = code
    }

    run() {
      this.pc = 0
      this.sp = this.stackSize - 1
      this.bp = this.sp
      this.ax = 0
      let exit = false
      while (!exit) {
        let opcode = this.code[this.pc++]
        switch (opcode) {
          //  Data manipulation 
          case this.OPCodes.IMM:
            // load immediate number to ax
            this.ax = this.code[this.pc++]
            break
          case this.OPCodes.LI:
            // load a int value to ax, the value stored in stack while it's address stored in ax 
            this.ax = this.stack[this.ax]
            break
          case this.OPCodes.LC:
            // the same as above, but load a char value
            this.ax = (byte)(this.stack[this.ax])
            break
          case this.OPCodes.SI:
            {
              // store a value to stack at the specified address, the value contained by ax, the specified address stored in the top of stack
              let address = this.stack[this.sp++]
              this.stack[address] = this.ax
            }
            break
          case this.OPCodes.SC:
            {
              // the same as above, but store a char value
              let address = this.stack[this.sp++]
              this.stack[address] = (byte)(this.ax)
            }
            break
          case this.OPCodes.PUSH:
            {
              // push ax's value to the top of stack
              this.stack[--this.sp] = this.ax
            }
            break

          //  Data calculation 
          case this.OPCodes.OR:
            // 
            this.ax = this.stack[this.sp++] | this.ax
            break

          case this.OPCodes.XOR:
            // 
            this.ax = this.stack[this.sp++] ^ this.ax
            break

          case this.OPCodes.AND:
            // 
            this.ax = this.stack[this.sp++] & this.ax
            break

          case this.OPCodes.EQ:
            // 
            this.ax = this.stack[this.sp++] == this.ax ? 1 : 0
            break

          case this.OPCodes.NE:
            // 
            this.ax = this.stack[this.sp++] != this.ax ? 1 : 0
            break

          case this.OPCodes.LT:
            // 
            this.ax = this.stack[this.sp++] < this.ax ? 1 : 0
            break

          case this.OPCodes.LE:
            // 
            this.ax = this.stack[this.sp++] <= this.ax ? 1 : 0
            break

          case this.OPCodes.GT:
            // 
            this.ax = this.stack[this.sp++] > this.ax ? 1 : 0
            break

          case this.OPCodes.GE:
            // 
            this.ax = this.stack[this.sp++] > this.ax ? 1 : 0
            break

          case this.OPCodes.SHL:
            // 
            this.ax = this.stack[this.sp++] << this.ax
            break

          case this.OPCodes.SHR:
            // 
            this.ax = this.stack[this.sp++] >> this.ax
            break

          case this.OPCodes.ADD:
            // 
            this.ax = this.stack[this.sp++] + this.ax
            break

          case this.OPCodes.SUB:
            // 
            this.ax = this.stack[this.sp++] - this.ax
            break

          case this.OPCodes.MUL:
            // 
            this.ax = this.stack[this.sp++] * this.ax
            break

          case this.OPCodes.DIV:
            // 
            this.ax = this.stack[this.sp++] / this.ax
            break

          case this.OPCodes.MOD:
            // 
            this.ax = this.stack[this.sp++] % this.ax
            break

          //  Built in functions 
          case this.OPCodes.EXIT:
            // print ax
            exit = true
            console.log(this)
            break
        }
      }
    }
  }

How to test this CPU Well ？ You can use the following code

  // make a cpu which is so poor,only has a 16 length stack
  let cpu16 = new CPU(16)
  // write 2 case for test
  // case 1 : calculate 3 + 9
  let count = 0;
  let code1 = [];
  code1[count++] = cpu16.OPCodes.IMM
  code1[count++] = 3
  code1[count++] = cpu16.OPCodes.PUSH
  code1[count++] = cpu16.OPCodes.IMM
  code1[count++] = 9
  code1[count++] = cpu16.OPCodes.ADD
  code1[count++] = cpu16.OPCodes.EXIT
  cpu16.loadProgram(code1)
  cpu16.run()

  // case 2 :a litte complexed case, calculate 12 * 8 * 6
  cpu16 = new CPU(16)
  count = 0;
  let code2 = [];
  code2[count++] = cpu16.OPCodes.IMM
  code2[count++] = 12
  code2[count++] = cpu16.OPCodes.PUSH
  code2[count++] = cpu16.OPCodes.IMM
  code2[count++] = 8
  code2[count++] = cpu16.OPCodes.PUSH
  code2[count++] = cpu16.OPCodes.IMM
  code2[count++] = 6
  code2[count++] = cpu16.OPCodes.MUL
  code2[count++] = cpu16.OPCodes.MUL
  code2[count++] = cpu16.OPCodes.EXIT
  cpu16.loadProgram(code2)
  cpu16.run()

  // case 3 :a slightly more complexed case, calculate 12 * 8 + 6 / 2 
  // (as you see, in order to example LI、SI opcode,i make this calculate a litter more complexed)
  cpu16 = new CPU(16)
  count = 0;
  let code3 = [];

  // store 12 * 8 in stack address 0
  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 0
  code3[count++] = cpu16.OPCodes.PUSH

  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 12
  code3[count++] = cpu16.OPCodes.PUSH
  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 8
  code3[count++] = cpu16.OPCodes.MUL
  // code3[count++] = cpu16.OPCodes.PUSH

  code3[count++] = cpu16.OPCodes.SI

  // store 6 / 2 in stack address 1
  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 1
  code3[count++] = cpu16.OPCodes.PUSH

  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 6
  code3[count++] = cpu16.OPCodes.PUSH
  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 2
  code3[count++] = cpu16.OPCodes.DIV

  code3[count++] = cpu16.OPCodes.SI

  // code3[count++] = cpu16.OPCodes.ADD

  // load result 1 to stack top 
  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 0
  code3[count++] = cpu16.OPCodes.LI
  code3[count++] = cpu16.OPCodes.PUSH

  // load result 1 to ax 
  code3[count++] = cpu16.OPCodes.IMM
  code3[count++] = 1
  code3[count++] = cpu16.OPCodes.LI

  code3[count++] = cpu16.OPCodes.ADD

  code3[count++] = cpu16.OPCodes.EXIT

  cpu16.loadProgram(code3)
  cpu16.run()

From the front CPU In the code of , We can see in the EXIT In the instruction , We printed the whole CPU The state of . You can also see from the code , Every time we calculate the result, there is ax in . stay chrome Running in the browser , It will print the results shown in the following figure .