loading...

Coding challenge: Implement a simplified 💻 Virtual Machine in JavaScript

codeguppy profile image Adrian ・3 min read

Implement a simplified virtual machine in JavaScript

In this coding challenge I'm proposing you to implement a very simple virtual machine and use it to execute the following bytecode program.

The array contains a real program! You have to discover yourself what it does once you build the machine to execute it.

var program = [11,0,10,42,6,255,30,0,11,0,0,11,1,1,11,3,1,60,1,10,2,0,20,
                2,1,60,2,10,0,1,10,1,2,11,2,1,20,3,2,31,2,30,2,41,3,2,19,31,0,50];

run(program);

function run(program)
{
    ...
}

Don't worry, we don't ask you to implement a VM to run a Linux system in the clouds... just a small VM (in about 100 lines of code) that only executes programs using a limited set of instructions such as the one above.

Why is this important?

  • by implementing this simplified VM you'll learn how a CPU works
  • you can use this knowledge to develop real machines emulators
  • you can use this knowledge to implement VMs that run the output of custom compilers / interpreters

Machine specs

The machine you're about to build is a fantasy one. It doesn't exist in the real world, but it mimics very closely how a real CPU works. The machine is partially insired by this article.

The machine has 4 general purpose number registers: R0, R1, R2, R3 (Think of this registers as variables that can store a number). Besides these registers, the machine has also a stack with ability to push or pop values on and out of the stack.

The machine operates by instructions. Since it is a simplified machine it has only the following instructions. Some of the instructions don't have operands, while other instructions have several operands.

A series of instructions, make our VM program. Instructions are encoded in the program as this:

INSTRUCTION [OPERAND1] [OPERAND2] [OPERAND3]

Each instruction has a unique number associated with it. For simplicity, instruction codes, operands and even addresses are regular numbers. Therefore no bytes, or any other data types are needed. Everything is a number!

Our program is therefore a series of numbers. Each number occupies a single cell of memory. For example an instruction with 3 operands will take 4 cells of program memory (1 for the instruction code and 3 for operands).

And now let's see the set of the instructions that our VM accepts:

Loads the value from reg_src into reg_dst. E.g. reg_dst = reg_src
MOVR reg_dst, reg_src
MOVR = 10

Loads the numeric value into register reg_dst. E.g. reg_dst = value
MOVV reg_dst, value
MOVV = 11

Adds the value from reg_src to the value of reg_dst and store the result in reg_dst
ADD reg_dst, reg_src
ADD = 20

Substracts the value of reg_src from the value of reg_dst and store the result in reg_dst
SUB reg_dst, reg_src
SUB = 21

Pushes the value of reg_src on the stack
PUSH reg_src
PUSH = 30

Pops the last value from stack and loads it into register reg_dst
POP reg_dst
POP = 31

Jumps the execution to address addr. Similar to a GOTO!
JP addr
JP = 40

Jump to the address addr only if the value from reg_1 < reg_2 (IF reg_1 < reg_2 THEN JP addr)
JL reg_1, reg_2, addr
JL = 41

Pushes onto the stack the address of instruction that follows CALL and then jumps to address addr
CALL addr
CALL = 42

Pops from the stack the last number, assumes is an address and jump to that address
RET
RET = 50

Print on the screen the value contained in the register reg
PRINT reg
PRINT = 60

Stops our VM. The virtual CPU doesn't execute instructions once HALT is encountered.
HALT
HALT = 255

Bonus

After you complete the challenge, please do this for extra fun:

  • disassemble (specify its instructions) the program presented at the beginning of the article. Please include your comments to make the program readable by a human
  • create additional programs for this VM and share them in the comments

Solution

Please first try to solve the challenge on your own and share your solution in the comments! Do not open the following link.

However, you can consult the official solution.

Alt Text

Have fun!

Posted on May 23 by:

codeguppy profile

Adrian

@codeguppy

Teaching coding to kids, teens and creative adults at https://codeguppy.com

Discussion

markdown guide