Implementation of Programming Languages
FMI 2022
Who are we?
- Martin Dobrev
- Dimitar Trendafilov
What we are going to talk about?
- programming languages
- compilers
- interpreters
- virtual machines
- garbage collectors
What are we not going to talk about?
- virtualization of computer systems
- The theory of regular expressions and context free grammars
- compiler optimizations
What are you going to learn about?
- how a programming language works
- how to implement
- a compiler
- an interpreter
- a virtual machine for a language
- how programs in dynamically typed and statically type languages are executed
- how to automatically reclaim memory
How are WE going to learn about VMs?
We are going to study and enhance a JavaScript interpreter.
Design goals for the JSImpl
- understandable
- working
- extendable
- embeddable
How you are going to be graded?
- 50% mid-term test
- 50% course project
Projects will be individual and there will be simpler and complex projects.
Projects
A few sample of projects are:
- create a Lua interpreter based on JSImpl with generational, incremental
garbage collector
- create an AOT compiler for JavaScript
- create a static analyzer or a code refactoring tool
Homework?
- There will be homework assignments that will give you points.
- The assignments will be similar to the final projects, but simpler
- You don’t have to do them, but if you do - you can choose a simpler project at
the end of the semester and still get 100%.
Homework
- Homeworks will be announced at the end of a lecture
- In two weeks on the lecture we will discuss the best homeworks
- You can submit the homework at any moment
- doing that after the two weeks, you will score less points
- Submitting your homework is done by issuing a pull request
Sample homeworks
- a minifier (with variable renaming, tree-shaking, etc)
- an obfuscator
- a beautifier
- a linter that detects usage of global variables, code complexity, etc
- code browser that allows for searching where a variable is defined and used
- transpiler
Pull Requests
You can make pull requests against the repository and get points based on their
contribution.
- you can fix typos
- you can extend the VM we are implementing in a meaningful way
- i.e. add source location information to the AST
Pull Requests
- Follow the pull request template
- Add your faculty number in the description
What are the requirements?
- Will to learn and time to experiment and write code
- Programming with C++, fluent in C++ will be better
- Programming with JavaScript or other dynamic language
- Data structures
- Languages, Finite Automata, Computability
- How computers work - CPU, memory hierarchy, etc
1. Introduction
- Course information
- Programming languages
- Architectures of
- compilers
- interpreters
- virtual machines
2. Lexers
How to recognize the words of a language?
- What is a lexer?
- How to write one?
- How to use flex
3. Parser
How to recognize the sentences of a language?
- What is a parser?
- How to write a parser?
- How to use bison
4. AST
Abstract Syntax Tree
- How to grow one?
- What to do with it?
- Evaluating the syntax tree
- Transforming the syntax tree
5. Bytecode
- Bytecode design
- Bytecode generation
- Bytecode interpretation
6. VMs
Virtual machines
- What is a virtual machine?
- Implementing the language features in the VM
- Library - arrays, hash maps, etc
- OOP
- Exception handling
- Communicating with the “real” machine
7. GC
Garbage collection
- How to manage the resources in a language
- Garbage Collection algorithms
- “conservative, generational and incremental” - will start to have meaning
for you
8. JIT & AOT code generation
- Machine code and generation
- Just in Time
- Ahead of Time
Plan
| Topic | Week |
|---|
| Introduction | 1 |
| Lexers | 2 |
| Parser | 2 |
| AST | 3, 4 |
| Bytecode | 5, 6 |
| VM | 7, 8, 9 |
| GC | 10, 11 |
| JIT & AOT | 11, 12, 13 |
Resources
Real world virtual machines:
- V8, SpiderMonkey, JavaScriptCore, ChakraCore
- duktape
- lua, luajit
- cPython, PyPy