Hi and welcome to the first session of the Building a Virtual Machine class.
My name is Dmitry Soshnikov and I'll be teaching this class and just to set the
agenda this is purely practical class we will discuss just few amount of theory however
most of the lectures will be actual practical exercises right building a virtual machine from
scratch and for those of you who have taken the Essentials of Interpretation class this will be
natural next step and from the AST interpreter which we have implemented in the previous class
now we will be moving down to the low level and will implement a Stack-based virtual machine.
As you can see this class has almost twice as many lectures as the previous class
and it also has the prerequisites. First of all we need to have the basic C++ experience
however we will not be using two specific C++ constructs so if you don't have any C++ experience
you still may follow the lectures and the first thing we need to say this is not a class about C++
right we will not be using two specific C++ features and we'll be operating with a very simple
constructs for example this for loop which is pretty much the same in any programming language
this is exactly what we'll be using in contrAST for example with the for_each
from the algorithm in the C++ so you may port this implementation to any other language.
The most complex construct from C++ probably will be just pointers if you're not familiar a pointer
just keeps an address and the reason why we need pointers because virtual machines operate with
different types of pointers for example Stack pointer (sp), Instruction pointer (ip), Frame
pointer (fp), etc. So if you have a variable using the & operator in C++ you can get it address
and the pointer is nothing but the address of the variable
where the value is stored and for those of you who are not familiar with the memory concept
you may treat it as just the giant array of bytes right where indices of this array are
called addresses and we can store values those addresses and those indices so simple array
and there's also inverse operation to get value from the pointer using the * operator
right so if we apply the star (*) on `px` we get 10 that is the value stored at this address
now we will not be even using any build system right not the Make, CMake, etc,
we'll be using just plain header (.h) files not even splitting implementation from the declaration
and there will be just one single .cpp file again this is not a class about C++ rather about virtual
machine concepts so we try to make build and the code very simple in fact that's the only command
we'll be using standard clang++ utility passing the main .cpp file and specifying the output
and then we can execute the output passing either the direct expression or the pass to a file
but of course we may use some specific flags for clang for example standard C++17,
enabling warnings and enabling the debugger support now since we have a lot of lectures here
in this class we will not be using the test driven development (TDD) as we did in previous courses
just to save time so if we encounter some problems some bugs or issue we will be debugging them as we
go but please as you follow consider implementing the unit tests for specific modules you may use
simple asserts from C++ or GTest (Google Test) or any other framework and also as we said we want to
make this transferable for example to Rust or any other low level language and for example you may
just mimic the heap the memory by leveraging the typed arrays right using the byte array this is
exactly represents the storing value at memory and getting it by its pointer so in this case
we really see the pointer just the index in this array but C++ makes it the most convenient working
with memory it provides direct raw access to memory and also it will be more convenient
to implement JIT-compiler however again you may implement everything here in any other language
now the second requirement is the Essentials of Interpretation class, unless you're familiar
already with concepts of closures, scope chain, identifier resolution, how eval works, etc,
that is how the runtime works at AST level you have to take Essentials of Interpretation class
where we built a full interpreter for a programming language at AST level at
high level and then come back to this class as the natural extension so these are two
prerequisites and so let's get started. In the previous class we mentioned that we distinguish
languages on Interpreted and Compiled and in fact it's not the languages but the implementations
and we also said that the runtime semantics is defined exactly by interpreters right specifically
interpreters tell and answer the questions what it means to define a variable, what it means to
define a function, how function is called, etc, and the compilers they do not execute any programs
they just translate from one language to another right hoping that there is an interpreter for that
target language in fact they delegate semantics to the target language so just to demonstrate it
let's say we have the program P1 written in some language then in order to get the output of this
program we always need an interpreter and there is no other way we can get the output for the program
P1 however let's say we don't have interpreter for this program let's say it's just a new language in
this case you may choose to implement a compiler from P1 to the semantically equivalent program P2
again hoping that there is an interpreter for that P2 program and to get the same result
and at the very low level such interpreter really exists and it's called the CPU itself
right so if you have the code in your programming language and you translate it that is compile
to native code you can be sure that the CPU will be able to execute it so in this class we'll be
working specifically with the interpreters that is the virtual machines and will have
both implementations we'll will have the compiler from the source code to the bytecode right pretty
much from the P1 to P2 and then implementing the interpreter that is the virtual machine itself
and just to remind previous implementation let's quickly see how the AST interpreter works
as we said it defines the high level semantics and here's the classic parsing pipeline which
we have been discussing in the previous lectures let's say we have the simple program "print hello"
and the first module which meets our program is known as Tokenizer that is the lexical
analysis and the idea here is to group individual characters into stream of tokens
just for more convenient work instead of working with single characters we work with words in this
case we have two tokens identifier with the value "print" and the string with the value "hello"
now the tokenizer doesn't make any commitment whether our program is syntactically valid
for this we have parser however besides the validation parser produces the next
intermediate representation known as Abstract Syntax Tree or the AST and this representation
is already suitable to pass to the compiler or to the interpreter and to obtain the result
now when we discuss runtime semantics we don't work much with parsers now the topic of parsing
might be completely separate from the runtime implementation for the same runtime you may
have multiple syntaxes so if you're interested in parsing specifically you may consider taking
two classes Building a Parser from scratch where we build a manual recursive-descent
parser or you may even take the Essentials of Parsing class more theoretical when we talk
about syntactic analysis theory and implement automated parser using parser generator tool
at the AST the way we implemented we just directly passed the AST to the interpreter
and by traversing it we obtained the correct result plain simple again you may implement full
programming language at this level potentially there is no need to go to the low level
implementation for example you may have simple DSL please choose to implement it at the AST
here's the example when we have the source code and obtain the AST after parsing which is directly
passed to the interpreter and also we said there might be multiple AST formats for example in the
parsers class we used the explicit JSON format with the explicit type property for each node
now let's see what we have in the bytecode interpreter so the bytecode interpreter also known
as virtual machine has couple of more extra steps during the compilation and it also fundamentally
changes the runtime data structures so here after obtaining the AST we pass it at the static time
at the compile time to the module which is called Bytecode Emitter or simply a Compiler
and this emitter produces the next intermediate representation known as the Bytecode and in this
case it looks like it's a bytecode for the stack machine as we'll see shortly in this class so here
we have two instructions pushing the value "hello" onto the stack and calling the print function and
then this bytecode is passed to the interpreter again to the virtual machine and we obtain exactly
the same result now why do we need this again why not just interpret the AST as we did previously
well when you have a production-level very generic programming language you need to make it fast,
at the AST level the structure of a program was represented exactly as a tree which already takes
a lot of space and might be slower in the evaluation loop and while in the bytecode
we have just plain array of bytes which is much faster to interpret and takes less space
so let's take a look at this example we have the source code in the S-expression format
for those of you who are not familiar with S-expression it's a syntax of languages
such as Scheme, Lisp and many others and it's pretty naturally represent the AST
in fact in the previous interpreter class we've just used simple JavaScript arrays which map 1:1
to the S-expression right we have just more quotes commas here but these arrays represent
exactly the AST structure of the program so we were able to skip the parsing stage altogether
and start writing the interpreter however as we said it takes too much memory right
allocation of this arrays strings etc makes a larger program to consume much more memory
in addition everything is evaluated at runtime right everything for example if we need to
resolve variable x we have to traverse the full environment chain until we find it and when we
access x second time we do this over and over again so the evaluation loop becomes very slow
now let's see what the bytecode proposes so in contrast with all this arrays location etc this
equivalent program in the bytecode is much smaller we do store extra data structures but still once
it's pre-compiled to the bytecode it takes less memory now in addition we pre-compile as much as
possible at the compilation time right instead of evaluating the variable x say in the environment
chain we know exactly in which environment it exists and know exactly the index in that
environment so we can directly jump and get this value so the evaluation becomes much fASTer this
is why all the production level virtual machines today use exactly the bytecode implementation
and pre-compilation and optimizations before we hit the runtime now one problem
this representation becomes much harder to read for humans since this is optimized for the machine
so that's why to understand what's happening inside of this bytecode we will need to have
a Disassembler so here we see the memory addresses where the bytecode is located
we see the bytecode itself still the same bytes and then textual representation known
as the Assembly, Assembly language as you can see disassembler was able to deconstruct
these bytes into specific instructions for example CONST with the index 0 for value 15
getting the variable x etc and as you can see it has pre-calculated index 0, so it knows exactly
without any runtime resolution where the variable x lives and we should also say
in this class we use custom bytecode which we invented and what is the case for many
virtual machines today they all provide custom bytecode and also this class is exactly about the
virtual machine so we need to understand how the actual bytecode interpretation works however there
is also a way to reuse existing production-level bytecode which is provided by the LLVM framework
however for the LLVM we'll have a separate class called Programming language with LLVM and again
in this class we focus on the custom bytecode which looks very similar to the Python bytecode.
Okay so with this being said please meet Eva or meet again for those who have taken the
interpreter's class again Eva is a dynamic programming language similar to Python or
JavaScript it supports functional programming and object-oriented, closures, lambda functions
and for syntax as we said we're going to use again S-expression
here's the examples in this case it's + operator, set instruction or if for the if expression as you
can see the if is also a complex expression inside it has other sub-expressions and here's one more
example for the function declaration as you can see we use the def keyword borrowed from Python
we're also going to support lambda functions or anonymous functions and also we'll be able
to call lambda right after the declaration right we create the function and immediately
apply it so called Immediately-invoked Lambda Expressions (IILE) so this is pretty much it
without further introduction let's jump directly to the implementation. So I'm creating the
directory for our project eva-vm and let's start from the virtual machine class EvaVM.h as we said
we'll be using just header (.h) files with direct implementation in the header files right for
actual C++ it's not the best way of implementing everything in the header files usually you split
declaration in the header and implementation in .cpp but again we don't focus on C++ much here
now we'll be using standard guards for the header files so this header is included only once
so we represent a virtual machine as a class where the main API method is the exec
right we accept the program as the string and for this we include the string header and here's
what should happen inside the exec well first of all we need to parse this program into AST
as we said we don't focus on parsers too much so we'll just have a simple parser for S-expressions
and this will be happening later in the course then we have to compile
the parse AST into the bytecode right and then start executing the
evaluation loop for the bytecode for now we'll just be creating the code directly and manually
just to see the process from inside and later we will implement the parser and the compiler
so what is bytecode now the bytecode is just a set of bytes that exactly what we have an
array or vector which contains unsigned integers (uint8_t) and we need to know which exact byte we
analyze at the moment so virtual machines and actual real machines have the pointer
known as Instruction pointer which points exactly to the currently evaluated instruction
so the standard name for this pointer is `ip` (instruction pointer) sometimes it's called `pc`
(program counter) but we'll use the ip here as it's called for example an Intel architecture
and to start evaluating we need to set the ip to the first byte of the bytecode
right so we take the first byte and as we said we apply the ampersand & operator to get the address
remember the pointers store the addresses and we define this pointer inside our class
is exactly a pointer pointing into a byte and then as previously we just have the eval
function pretty much the core of any interpreter in contrast with the AST interpreter the eval is
not recursive here it's just the infinite loop right let's write it as the infinite for loop
which should analyze the current byte and behave accordingly right for specific instruction it
executes specific handling procedure pretty much the same as we did at the AST interpreter
now the set of the bytecode instructions is known as the Instruction Set Architecture (ISA)
and today we're going to have only one instruction which is called HALT
and we encode it with the first byte let's say number 0 the encoding might be completely
arbitrary but we'll be just using the increasing numbers so the HALT instruction has the bytecode 0
and then let's manually create the current bytecode which contains only one instruction
the HALT instruction now the HALT instruction as we said should stop the program and inside
the interpretation loop we need to read the next byte so let's introduce this function read byte
and then we check if it's the HALT instruction we just return right we're done
okay that should be it for the first instruction let's create the main virtual machine executable
the only .cpp file we're going to have right let's create the instance
and for this we need to include the header and then just call the exec method
and we will be passing the actual program to the exec and today we have only the HALT instruction
but going forward the actual program will go here as we said to compile we're going to use clang++
I have version 11 for Apple please address documentation for your version you may use gcc
or clang or Windows version again we'll be using very plain C++ constructions so it should work
for any type of compiler again we use the C++ 17 standard here enable all warnings
and enable the debugger support then we specify the path to the C++ file and tell that output
should be ./eva-vm executable let's compile okay the first problem now first of all we're going
to have a lot of such compilation errors this is not a problem we need to follow them and fix
this also might be good exercise for those of you who are not familiar with C++ just how to debug to
see the errors and in this case we actually forgot to define the READ_BYTE macro so let's do this
so the READ_BYTE function or the macro in this case should read the current byte in
the instruction pointer right and then increase the instruction pointer to point to the next byte
this is exactly what we do we read the value using the * operator remember if we apply
the * to a pointer we get the value and then we increase it with ++ all right that should be it
let's execute and it works we don't see any output but it's exactly the correct evaluation because
we didn't stack in the infinite loop of the eval for example try changing the HALT opcode from 0 to
say 0xFF value and in this case you should stuck in the for loop
so that's it for today that's the introduction lecture we have started building the virtual
machine, talked about the bytes, the bytecode, instruction pointer, instruction set,
and in the next lectures we'll start talking about numbers, mathematical operations going
further to strings, to objects, functions, etc. Okay, thanks and see you in the class