1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
|
---
title: "Introduction to Implementation of Programming Languages"
date: 2022-09-15T17:45:53+03:00
draft: false
outputs:
- Reveal
---
# Implementation of Programming Languages
FMI 2022
---
# Who are we?
- Martin Dobrev
- Dimitar Trendafilov
---
# What is this?
- An university course.
- A group of people that find it interesting how computers work and how they are
programmed.
- https://sofiacpp.github.io/IPL
---
## 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.
- JSImpl
---
## 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
---
## Homework
- Make a folder inside the *homework* folder with your faculty number and a
folder inside that for each homework
- Sample - https://github.com/SofiaCPP/IPL/tree/master/homework/80095/js2html
---
## 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?
1. Will to learn and time to experiment and write code
2. Programming with C++, fluent in C++ will be better
2. Programming with JavaScript or other dynamic language
3. Data structures
4. Languages, Finite Automata, Computability
5. How computers work - CPU, memory hierarchy, etc
---
# Contents of the course
---
## 1. Introduction
0. Course information
1. Programming languages
2. Architectures of
- compilers
- interpreters
- virtual machines
---
## 2. Lexers
How to recognize the words of a language?
1. What is a lexer?
2. How to write one?
3. How to use [flex](https://github.com/westes/flex)
---
## 3. Parser
How to recognize the sentences of a language?
1. What is a parser?
2. How to write a parser?
3. How to use [bison](https://www.gnu.org/software/bison/)
---
## 4. AST
Abstract Syntax Tree
1. How to grow one?
2. What to do with it?
3. Evaluating the syntax tree
4. Transforming the syntax tree
{{% note %}}
- language transformation at syntax level
- code formatting
- code minification
- syntactic macros
{{% /note %}}
---
## 5. Bytecode
1. Bytecode design
2. Bytecode generation
3. Bytecode interpretation
---
## 6. VMs
Virtual machines
1. What is a virtual machine?
2. Implementing the language features in the VM
- Library - arrays, hash maps, etc
- OOP
- Exception handling
3. Communicating with the "real" machine
---
## 7. GC
Garbage collection
1. How to manage the resources in a language
- manual
- automatic
2. Garbage Collection algorithms
- "conservative, generational and incremental" - will start to have meaning
for you
---
## 8. JIT & AOT code generation
1. Machine code and generation
2. Just in Time
3. 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
- https://github.com/SofiaCPP/IPL
- https://sofiacpp.github.io/IPL
- https://sofiacpp.github.io/IPL/resources/
---
## Resources
Real world virtual machines:
- V8, SpiderMonkey, JavaScriptCore, ChakraCore
- duktape
- lua, luajit
- cPython, PyPy
---
# ?
|
