Hi and welcome to the first session of the Essentials of Interpretations class
where we discuss semantics of the programming languages
My name is Dmitry Soshnikov and I'll be teaching this class, and just to give a
brief overview of what we'll be studying: this class has two parts. The first part
will be crash course on the compilers. Will be discussing different parsing
pipelines, see the difference between Interpreters and Compilers, talk about
what is Abstract Syntax Tree, Ahead-of-time compilers, JIT-compilers, etc, and
in the second part we're going to implement an actual interpreter for a
programming language similar to Python or JavaScript. So in this class we study
specifically a runtime semantics that is the meaning of the program execution as
we will see shortly. So with this being said, let's start with the first part and
we'll talk about the parsing pipeline. Now, any compiler book starts from the
parsing pipeline specifically, going deeper into lexers, parsers, etc. Now I
believe that parsing topic is complex by itself
and requires a full separate class talking about formal grammars languages
and how it can generate automatic parsers. So in this class will be just
briefly touching the parsing topic and I will show you a trick how we can skip
the parsing stage altogether and come directly to the code evaluation. But
let's just briefly talk about what happens when your program is met by the
parser and how we obtain the first intermediate representation. So let's say
we have an abstract program which prints the word "hello". And the first module
which means your program is known as Tokenizer or a Lexical analysis.
Sometimes it's called a "Lexer" or "Scanner", and the purpose of the Tokenizer is to
obtain the first intermediate representation known as a stream of
tokens. Now a "token" is first indivisible unit which consists of token type
and the value associated with this type -- in this case as you can see we
obtained two tokens: identifier with a value "print"
and the string token with the value "hello". So the tokens are just higher
abstract entities than single characters, so we group those single
characters to form the tokens. Now we should also say that tokenizer doesn't
make any commitment whether our program is syntactically valid. It might be
completely syntactically invalid, for example: if we have program like this:
"if" and open paren, then for us this is clearly an invalid program, but tokenizer
will be able to obtain two tokens: one is a keyword with the value "if", and the
second one is open parenthesis with its value. So the tokenizer again doesn't
validate whether your program is syntactically valid. The module which
actually validates whether our program is valid is known as parser or syntactic
analysis. Now this module already takes the formal grammar of your language and
tries to match to what you entered in the source text. Again in theory the
purpose of the parser is exactly validation, however on practice parser
produces the next intermediate representation known as Abstract Syntax Tree
This form is already suitable for a program to work with
If the source text here was suitable mainly for us
then the AST already is something we can feed to interpreter or compiler and
obtain the result. OK, so this was the AST. We should also say that this
happens at Static time or a Compile time. That is by this moment we haven't
actually started executing our program all we did is just translated it to
several intermediate representations and validated whether it's syntactically
valid that's it there is no actual execution yet and the actual execution
will happen at runtime. Let's give one more example of an AST: x = 10 * 5 + y
x = 10 * 5 + y. Then the AST for this code might be an assignment operator
which has left-hand side and right-hand side. And the right-hand side here is a
complex expression itself so it's an
addition with the left-hand side which is multiplication, also left-hand
side and right-hand side, and the right-hand side for the addition -- y
So this is an example of the AST. Again just to reiterate in this class we do not
study parsers. There will be a separate class known as essentials of parsing
where we specifically will be focusing on the parsing techniques however just
briefly mentioning here, when we talk about parsers we differentiate
handwritten parsers and automatically generated. And for the handwritten
parsers we mainly have implementation known as Recursive descent, which is
widely used on practice since you get full control of the parser implementation
however the parsing process can be actually automated and we can build some
machinery which can take your grammar, grammar of your language as a
specification and generate fully working parsing module based on different
algorithms. You can take a look at the tool called Syntax, which is a language
agnostic parser generator, and which can generate parsers for multiple languages
such as JavaScript, Python, Rust, C#, Java, etc. Again all this we'll be
studying in a separate class called Essentials of Parsing. So what do we
study in this class then? As we said it's Runtime semantics, that is the meaning of
your program. Let's take a look at a small example to see what specifically
it is so let's say we have these two small pieces of code: one is written in
JavaScript, and the other one is written in PHP. And this code might have the same
AST structure at static semantics, right as we can see we have an AST node for a
variable, for function declaration, and for function call. Right exactly the same
however when it comes to Runtime, executing this code in JavaScript gives
us predictable result, printing "JS is cool". However when we try execute the same
in PHP we actually get an error here: the variable "data" is not defined. Now the
problem here is that PHP and JavaScript has different scoping rules for function
declarations as well see shortly all functions in JavaScript are known to be
Closures, that is they capture all the bindings from the parent environment and
the function has access to this free variable "data", however simple functions
in PHP do not capture any bindings so it doesn't see the variable "data". PHP by now
has concept of the closure but to defining closure you need to have a
different syntax. So that is exactly the purpose of our class that is what we
study and answer questions such as "What it means to define a variable?"
"What it means to define a function?", "How a function is called?", and "What is call stack?"
"How we pass parameters?", etc. And when we talk about
languages we also distinguish Interpreters and Compilers. And pretty
often we can hear that "interpreters execute line by line" while compilers
"do it all at once". Well the fact is, compilers do not execute code at all
right only interpreters execute the code -- that's exactly the difference. That is
interpreters implement semantics themselves. Exactly the interpreters
answer the questions "What it means to create a variable?", "Wow a function is called?", etc
Now compilers instead just delegate semantics to some target
language hoping that there is an interpreter for that target language
right so compilers only translate from one language to another and this is
pretty much similar to natural languages for example
Если я сейчас переключусь на русский язык, то, возможно, меня сейчас не все поймут
What I said is: "If I switch to Russian
language, then probably not everyone will understand me", and you'll need to have a
translator from Russian to English. And then when you have translated to English
and don't understand a meaning of some word, you'll need an interpreter which
will help you understand semantics that is the meaning
of that world. So let's take a look at this picture: let's say we have some
program P1 written in some language. Then if you want to obtain an output of this
program we always need an interpreter: there is no other way to get the output
of this program. However if we don't have interpreter for this program, we might
choose to implement a compiler which will just translate to equivalent
program P2, and hoping that there is an interpreter for that program. So at
the very low level such interpreter really exists and it's called the CPU itself
So if you translate your code directly to the machine
instructions you might be sure that CPU will be able to execute them.
And interpreters will have two main types, these are: AST-based or recursive
interpreters, and Bytecode-interpreters, also known as Virtual machines. Now the
only difference here is in the format of the program itself. In case of the AST
based interpreter it's a tree-like data structure, and in Bytecode interpreter is
a plain array of encoded instructions which are closer to real machines that's
why these interpreters are known as virtual machines. And for compilers we
have three main types, these are: Ahead-of-time compiler, that is when all the
source code is translated to another language before the execution. Now the
classic example is a C++ compiler which translates the code before execution
By the way, the C++ is interesting compiler since it may call interpreter directly
at compilation stage to pre-evaluate some parts, for example for optimization
so this is very important point: compiler may call interpreter during the
compilation. And we also have Just-in-time compilers or JIT-compilers
this is where the code generation might be executed at runtime and we'll see
details of this in the next lecture. And also we have so-called
AST-transformers or Transpilers. Now "Transpiler" stands for high-level
compiler. This is mainly transformation at the AST level: add node, remove node, etc
and usually most of the syntactic sugar and optimizations are
done at the AST level. OK, so this is the brief overview of the course and what
specifically we'll be studying in this class. In the next lecture we'll talk in
detail about all this interpretation and compilation pipelines
and as was mentioned in the second part will be actually building an interpreter
from scratch: a fully working language similar in semantics to JavaScript or
Python. Once you have implemented an interpreter
for this language your practical level for example of Python or JavaScript or
any other language will become more professional. And besides implementing
interpreters is just an interesting engineering tasks and of course what
will make you a better engineer. Okay, that's it for today, thanks and see you
in the class