/
index.html
260 lines (257 loc) · 9.81 KB
/
index.html
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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>dbp.io :: Verified Compilers and Multi-Language Software</title>
<link rel="stylesheet" type="text/css" href="../../css/default.css" />
<link rel="stylesheet" type="text/css" href="../../css/syntax.css" />
<style type="text/css">
a {
text-decoration: underline;
}
</style>
</head>
<body>
<h2>Verified Compilers and Multi-Language Software</h2>
<table>
<tbody>
<tr class="odd">
<td style="text-align: left;">Course</td>
<td>CS4910 (CRN 17946): Verified Compilers and Multi-Language Software</td>
</tr>
<tr class="even">
<td style="text-align: left;">Semester</td>
<td>Fall 2019</td>
</tr>
<tr class="odd">
<td style="text-align: left;">Meeting</td>
<td>Monday/Thursday, 11:45AM-1:25PM</td>
</tr>
<tr class="even">
<td style="text-align: left;">Instructor</td>
<td>Daniel Patterson (<a href="mailto:dbp@dbpmail.net">dbp@dbpmail.net</a>)</td>
</tr>
<tr class="odd">
<td style="text-align: left;">Office</td>
<td>WVH 308</td>
</tr>
</tbody>
</table>
<h3 id="why-this-course"><strong>Why this course?</strong></h3>
<blockquote>
<p>“Can you trust your compiler?” — Xavier Leroy, developer of the Compcert verified C compiler</p>
</blockquote>
<p>Software is written in a variety of languages, and in most cases, in order to run, it must be compiled down to some lower-level target. <strong>But what if that compiler isn’t correct?</strong> Compilers are some of the trickier pieces of software we build, and yet bugs in them are insidious: bugs in compilers mean that one of our most basic debugging strategies, reading source code, may not be helpful, since what actually ran may not correspond to that source code!</p>
<p>In the presence of buggy compilers, we must worry about what the compiler does and how our programs are translated to the target, possibly looking at compiler output or stepping through with low-level debuggers. Much better if the compiler were, essentially, invisible — if the source code fully specified what would happen. But a compiler can only truly be invisible if we can be sure that it does exactly what we expect: if we are sure it is correct. To be absolutely sure, we must prove it correct, and build a <em>verified</em> compiler.</p>
<p>Colliding with the field of verified compilation is the question of how different languages should be able to interact — that interaction, or linking, happens after compilation, in the lower-level target of compilation. But when using a variety of source languages, we would like to think in terms of those source languages, not worry about how our various languages compile, and so again, we are left wanting an invisible compiler, a verified compiler.</p>
<p>These are our high-level motivations. The course itself, while motivated with these problems, will be very grounded: we will be <strong>building languages, compilers, and proving them correct</strong>.</p>
<h3 id="how-will-the-course-be-structured"><strong>How will the course be structured?</strong></h3>
<p><strong>Part 1.</strong> We want to produce verified compilers, and so we will use one of the state-of-the-art tools used for this: the <a href="https://coq.inria.fr/">Coq proof assistant</a>. This is a general purpose tool — in addition to being used to build a verified <a href="http://compcert.inria.fr/">optimizing C compiler</a>, in work towards <a href="http://flint.cs.yale.edu/certikos/">certified operating systems</a> and <a href="http://verasco.imag.fr/wiki/Main_Page">other</a> <a href="https://github.com/mit-plv/fiat-crypto">verification</a> <a href="https://jasmin-lang.github.io/">projects</a>. It has also been used in various efforts of formalizing mathematics (most notably, the <a href="https://en.wikipedia.org/wiki/Four_color_theorem">Four Color Theorem</a>). For our purpose, Coq allows us to write functional programs, like compilers, and prove properties about them, like correctness. The first section of the course will be dedicated to learning Coq and becoming familiar with the process of <em>mechanized</em> proof — that is, proofs that are checked by a machine. The text that we will use for this section of the course is <a href="https://ilyasergey.net/pnp">“Programs and Proofs” by Ilya Sergey</a>.</p>
<p><strong>Part 2.</strong> This part of the course will involve designing, in groups, different source languages. These will all likely be simple functional languages, and we will do plenty of design review to ensure that the language design you pick will not cause too much difficulty later on.</p>
<p><strong>Part 3.</strong> The final part will involve building and proving correct compilers from your language to a common low-level target language. All the languages will compile to the same target language, and so once we have compilers, and concurrent with the verification effort, you will experiment building small programs that use a mixture of different student languages.</p>
<h3 id="a-note-on-collaboration"><strong>A note on collaboration</strong></h3>
<p>This will be a highly collaborative course. For the first section, the actual assignments will be done individually, to ensure that you get sufficient practice with theorem-proving, as proof assistants like Coq are not something you can learn without using. Even so, we <em>expect and encourage people to work together throughout the course</em>, beyond just the teams you are working in, provided that the actual work you submit is your own. Once the first section ends, the course will truly become a large collaboration. All of our compilers will be in a shared repository, and while you will be assessed on and be responsible for understanding your own compiler, all are welcome to help any of your classmates. We will also do group reviews or reviews of one group by another.</p>
<h3 id="requirements"><strong>Requirements</strong></h3>
<p>Intended for advanced undergraduates, you would be well prepared by either having taken CS4400 (programming languages) or CS4410 (compilers). However, if you are interested and haven’t taken either, <strong>please reach out to the instructor</strong>. I’m happy to talk to you about your background, or give you additional information about the type of stuff we’ll be working on to see if it seems like it’ll be a good fit. While not required, familiarity with typed functional languages (e.g., Scala, Haskell, or OCaml) would be helpful, since Coq is related to that class of language, as would any exposure to formal proof in mathematics.</p>
<h3 id="schedule">Schedule</h3>
<table>
<thead>
<tr class="header">
<th>Week</th>
<th>Date</th>
<th>Topic</th>
<th style="text-align: left;">Reading</th>
<th>Assignment</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>0</td>
<td>9/5</td>
<td>Course structure, intro to Coq / mechanized mathematics, Coq setup.</td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>1</td>
<td>9/9</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>9/12</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>2</td>
<td>9/16</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>9/19</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>3</td>
<td>9/23</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>9/26</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>4</td>
<td>9/30</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>10/3</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>5</td>
<td>10/7</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>10/10</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>6</td>
<td>10/14</td>
<td>NO CLASS</td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>10/17</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>7</td>
<td>10/21</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>10/24</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>8</td>
<td>10/28</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>10/31</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>9</td>
<td>11/4</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>11/7</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>10</td>
<td>11/11</td>
<td>NO CLASS</td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>11/14</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>11</td>
<td>11/18</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>11/21</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>12</td>
<td>11/25</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="odd">
<td></td>
<td>11/28</td>
<td>NO CLASS</td>
<td style="text-align: left;"></td>
<td></td>
</tr>
<tr class="even">
<td>13</td>
<td>12/2</td>
<td></td>
<td style="text-align: left;"></td>
<td></td>
</tr>
</tbody>
</table>
<h3 id="other-question-something-not-clear"><strong>Other question? Something not clear?</strong></h3>
<p>Please reach out to the instructor: Daniel Patterson (<a href="mailto:dbp@dbpmail.net">dbp@dbpmail.net</a>)</p>
<p><br /><br /></p>
</body>
</html>