-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathSlides.html
More file actions
379 lines (378 loc) · 25.3 KB
/
Copy pathSlides.html
File metadata and controls
379 lines (378 loc) · 25.3 KB
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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="generator" content="pandoc" />
<meta name="author" content="Daniel Feltey (@dfeltey)" />
<meta name="date" content="2013-07-10" />
<title>Compilers From Scratch</title>
<style type="text/css">code{white-space: pre;}</style>
<style type="text/css">
table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode {
margin: 0; padding: 0; vertical-align: baseline; border: none; }
table.sourceCode { width: 100%; line-height: 100%; }
td.lineNumbers { text-align: right; padding-right: 4px; padding-left: 4px; color: #aaaaaa; border-right: 1px solid #aaaaaa; }
td.sourceCode { padding-left: 5px; }
code > span.kw { color: #007020; font-weight: bold; }
code > span.dt { color: #902000; }
code > span.dv { color: #40a070; }
code > span.bn { color: #40a070; }
code > span.fl { color: #40a070; }
code > span.ch { color: #4070a0; }
code > span.st { color: #4070a0; }
code > span.co { color: #60a0b0; font-style: italic; }
code > span.ot { color: #007020; }
code > span.al { color: #ff0000; font-weight: bold; }
code > span.fu { color: #06287e; }
code > span.er { color: #ff0000; font-weight: bold; }
</style>
<link rel="stylesheet" type="text/css" media="screen, projection, print"
href="http://www.w3.org/Talks/Tools/Slidy2/styles/slidy.css" />
<script src="http://www.w3.org/Talks/Tools/Slidy2/scripts/slidy.js.gz"
charset="utf-8" type="text/javascript"></script>
</head>
<body>
<div class="slide titlepage">
<h1 class="title">Compilers From Scratch</h1>
<p class="author">
Daniel Feltey (@dfeltey)
</p>
<p class="date">July 10, 2013</p>
</div>
<div id="slides-code-and-exercises" class="slide section level1">
<h1>Slides, Code, and Exercises</h1>
<p>GitHub: https://github.com/dfeltey/CompilersFromScratch</p>
<p>School of Haskell: https://www.fpcomplete.com/user/dfeltey/compilers-from-scratch</p>
</div>
<div id="the-compilation-process" class="slide section level1">
<h1>The Compilation Process</h1>
<p>A typical workflow</p>
<p>Source Code -> Lexer -> Parser -> Code Generator -> Machine Code</p>
</div>
<div id="outline" class="slide section level1">
<h1>Outline</h1>
<ul>
<li>Regular Expressions</li>
<li>Lexing</li>
<li>Parsing</li>
<li>Desugaring</li>
<li>The CEK machine</li>
<li>Code Generation</li>
</ul>
</div>
<div id="regular-expressions" class="slide section level1">
<h1>Regular Expressions</h1>
<p>3 Basic operations</p>
<ul>
<li>Alternation</li>
<li>Concatenation or sequencing</li>
<li>Repetition or Kleene Star</li>
</ul>
<p>Additionally</p>
<ul>
<li>Symbols</li>
<li>Epsilon: The empty string</li>
<li>Null: The empty language</li>
</ul>
</div>
<div id="regular-expressions-in-haskell" class="slide section level1">
<h1>Regular Expressions in Haskell</h1>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">RegEx</span> c <span class="fu">=</span> <span class="dt">Null</span>
<span class="fu">|</span> <span class="dt">Eps</span>
<span class="fu">|</span> <span class="dt">Sym</span> c
<span class="fu">|</span> <span class="dt">Alt</span> (<span class="dt">RegEx</span> c) (<span class="dt">RegEx</span> c)
<span class="fu">|</span> <span class="dt">Seq</span> (<span class="dt">RegEx</span> c) (<span class="dt">RegEx</span> c)
<span class="fu">|</span> <span class="dt">Star</span> (<span class="dt">RegEx</span> c)</code></pre>
<ul class="incremental">
<li>This is fine, but how do we represent a regex that matches any number?</li>
</ul>
<ul class="incremental">
<li><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">Alt</span> (<span class="dt">Sym</span> <span class="ch">'1'</span>) (<span class="dt">Alt</span> (<span class="dt">Sym</span> <span class="ch">'2'</span>) (<span class="dt">Alt</span> (<span class="dt">Sym</span> <span class="ch">'3'</span>) (<span class="dt">Alt</span> (<span class="dt">Sym</span> <span class="ch">'4'</span>) (<span class="dt">Alt</span> (<span class="dt">Sym</span> <span class="ch">'5'</span>) <span class="fu">...</span>))))</code></pre></li>
</ul>
</div>
<div id="a-slight-modification" class="slide section level1">
<h1>A Slight Modification</h1>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">RegEx</span> c <span class="fu">=</span> <span class="dt">Null</span>
<span class="fu">|</span> <span class="dt">Eps</span>
<span class="fu">|</span> <span class="dt">Sym</span> (c <span class="ot">-></span> <span class="dt">Bool</span>)
<span class="fu">|</span> <span class="dt">Alt</span> (<span class="dt">RegEx</span> c) (<span class="dt">RegEx</span> c)
<span class="fu">|</span> <span class="dt">Seq</span> (<span class="dt">RegEx</span> c) (<span class="dt">RegEx</span> c)
<span class="fu">|</span> <span class="dt">Star</span> (<span class="dt">RegEx</span> c)</code></pre>
<ul class="incremental">
<li>We add boolean "weights" to the symbols.</li>
</ul>
<ul class="incremental">
<li>Now to represent a regex for any digit character</li>
</ul>
<ul class="incremental">
<li><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">import</span> Data.Char
<span class="dt">Sym</span> (<span class="fu">isDigit</span>)</code></pre></li>
</ul>
</div>
<div id="matching-strings" class="slide section level1">
<h1>Matching Strings</h1>
<p>Two approaches</p>
<ul>
<li><p>Destructure a string like a regex</p></li>
<li><p>Destructure a regex like a string</p></li>
</ul>
</div>
<div id="regex-derivatives" class="slide section level1">
<h1>RegEx Derivatives</h1>
<p>Decomposing a regex</p>
<ul>
<li>Match one character at a time like a list or Haskell String</li>
<li>Take derivatives</li>
</ul>
<pre><code> D_c
Null -- c --> Null
Eps -- c --> Null
Sym p -- c --> if p c then Eps else Null
Alt r1 r2 -- c --> Alt (D_c r1) (D_c r2)
Seq r1 r2 -- c --> Alt (Seq (D_c r1) r2) (Seq (empty r1) (D_c r2))
Star r -- c --> Eps</code></pre>
</div>
<div id="empty" class="slide section level1">
<h1>Empty</h1>
<p>What is empty?</p>
<pre><code>empty Null = Null
empty Eps = Eps
empty (Sym _) = Null
empty (Alt r1 r2) = Alt (empty r1) (empty r2)
empty (Seq r1 r2) = Seq (empty r1) (empty r2)
empty (Star _) = Eps</code></pre>
<ul>
<li>Not implemented like this, but close enough</li>
</ul>
</div>
<div id="matching" class="slide section level1">
<h1>Matching</h1>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot">match ::</span> <span class="dt">RegEx</span> <span class="dt">Char</span> <span class="ot">-></span> <span class="dt">String</span> <span class="ot">-></span> <span class="dt">Bool</span>
match r [] <span class="fu">=</span> empty r
match r (c<span class="fu">:</span>cs) <span class="fu">=</span> match (derivative c r) cs</code></pre>
<ul>
<li>Lex with a list of (regex,String->token) pairs</li>
<li>Take as many derivatives as possible then apply the function</li>
</ul>
</div>
<div id="an-enriched-lambda-calculus" class="slide section level1">
<h1>An Enriched Lambda Calculus</h1>
<p>The Language we are implementing</p>
<pre><code><SExpr> : ( <SExpr> <SExpr> )
| (lambda <Var> <SExpr> )
| (<Binop> <SExpr> <SExpr> )
| (if <SExpr> <SExpr> <SExpr> )
| (let ( <Var> <SExpr> ) <SExpr> )
| (print <SExpr> )
| <Var>
| <Int>
| <Bool>
<Var> : [a-zA-Z]+
<Int> : [0-9]+
<Bool> : True | False
<Binop> : + | - | * | / | = | < | > | <= | >=
| % | and | or</code></pre>
</div>
<div id="abstract-syntax-in-haskell" class="slide section level1">
<h1>Abstract Syntax in Haskell</h1>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">SExpr</span> <span class="fu">=</span> <span class="dt">AppS</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">LambdaS</span> <span class="dt">Name</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">BinopS</span> <span class="dt">Op</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">VarS</span> <span class="dt">Name</span>
<span class="fu">|</span> <span class="dt">ValS</span> <span class="dt">Integer</span>
<span class="fu">|</span> <span class="dt">BoolS</span> <span class="dt">Bool</span>
<span class="fu">|</span> <span class="dt">IFS</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">LetS</span> (<span class="dt">Name</span>,<span class="dt">SExpr</span>) <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">PrintS</span> <span class="dt">SExpr</span></code></pre>
</div>
<div id="challenge" class="slide section level1">
<h1>Challenge</h1>
<ul>
<li>Create a token data type for this language</li>
<li>Specify a lexer</li>
</ul>
<p>Exercises: https://www.fpcomplete.com/user/dfeltey/compilers-from-scratch</p>
</div>
<div id="desugaring" class="slide section level1">
<h1>Desugaring</h1>
<p>Recall:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">SExpr</span> <span class="fu">=</span> <span class="dt">AppS</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">LambdaS</span> <span class="dt">Name</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">BinopS</span> <span class="dt">Op</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">VarS</span> <span class="dt">Name</span>
<span class="fu">|</span> <span class="dt">ValS</span> <span class="dt">Integer</span>
<span class="fu">|</span> <span class="dt">BoolS</span> <span class="dt">Bool</span>
<span class="fu">|</span> <span class="dt">IFS</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span> <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">LetS</span> (<span class="dt">Name</span>,<span class="dt">SExpr</span>) <span class="dt">SExpr</span>
<span class="fu">|</span> <span class="dt">PrintS</span> <span class="dt">SExpr</span></code></pre>
<ul>
<li>Is this more than we need?</li>
</ul>
</div>
<div id="a-smaller-language" class="slide section level1">
<h1>A Smaller Language</h1>
<p>Consider:</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Expr</span> <span class="fu">=</span> <span class="dt">App</span> <span class="dt">Expr</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">Lambda</span> <span class="dt">Name</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">Binop</span> <span class="dt">Op</span> <span class="dt">Expr</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">Var</span> <span class="dt">Name</span>
<span class="fu">|</span> <span class="dt">Val</span> <span class="dt">Integer</span>
<span class="fu">|</span> <span class="dt">BoolE</span> <span class="dt">Bool</span>
<span class="fu">|</span> <span class="dt">IF</span> <span class="dt">Expr</span> <span class="dt">Expr</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">PrintE</span> <span class="dt">Expr</span>
<span class="kw">deriving</span>(<span class="kw">Show</span>)</code></pre>
<ul>
<li>Is this language as expressive as the old one?</li>
<li>Write a function to convert between SExprs and Exprs.</li>
</ul>
</div>
<div id="the-cek-machine" class="slide section level1">
<h1>The CEK Machine</h1>
<ul>
<li>A mechanical model of the lambda calculus</li>
<li>A "register" machine with 3 registers</li>
<li>(C)ontrol (E)nvironment (K)ontinuation</li>
</ul>
</div>
<div id="cek-explained" class="slide section level1">
<h1>CEK explained</h1>
<p>We will be writing byte code for a CEK machine</p>
<ul>
<li>The Control register holds a stack of bytecode to be executed</li>
<li>The Environment register associates names with their values</li>
<li>The Continuation register tells us what to do with a value</li>
</ul>
</div>
<div id="our-language-again" class="slide section level1">
<h1>Our Language again</h1>
<p>What are the core concepts in our language?</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Expr</span> <span class="fu">=</span> <span class="dt">App</span> <span class="dt">Expr</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">Lambda</span> <span class="dt">Name</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">Binop</span> <span class="dt">Op</span> <span class="dt">Expr</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">Var</span> <span class="dt">Name</span>
<span class="fu">|</span> <span class="dt">Val</span> <span class="dt">Integer</span>
<span class="fu">|</span> <span class="dt">BoolE</span> <span class="dt">Bool</span>
<span class="fu">|</span> <span class="dt">IF</span> <span class="dt">Expr</span> <span class="dt">Expr</span> <span class="dt">Expr</span>
<span class="fu">|</span> <span class="dt">PrintE</span> <span class="dt">Expr</span>
<span class="kw">deriving</span>(<span class="kw">Show</span>)</code></pre>
<ul class="incremental">
<li>Function application</li>
<li>Lambda abstraction</li>
<li>Binary operators</li>
<li>Variable access</li>
<li>Constants</li>
<li>If expressions</li>
<li>Printing</li>
</ul>
</div>
<div id="from-concepts-to-byte-code" class="slide section level1">
<h1>From Concepts to ("Byte") Code</h1>
<p>Designing an instruction set for our core language</p>
<ul>
<li>The easy cases</li>
</ul>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">Val</span> <span class="dv">53</span> <span class="fu">---></span> <span class="dt">PushI</span> <span class="dv">53</span> </code></pre>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">BoolE</span> <span class="kw">True</span> <span class="fu">---></span> <span class="dt">PushB</span> <span class="kw">True</span></code></pre>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">Var</span> <span class="st">"x"</span> <span class="fu">---></span> <span class="dt">Access</span> <span class="st">"x"</span></code></pre>
</div>
<div id="from-concepts-to-byte-code-1" class="slide section level1">
<h1>From Concepts to ("Byte") Code</h1>
<ul>
<li>The middle cases</li>
</ul>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">Lambda</span> <span class="st">"x"</span> e <span class="fu">---></span> <span class="dt">Close</span> <span class="st">"x"</span> [compile e]</code></pre>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">IF</span> e1 e2 e3 <span class="fu">---></span> <span class="dt">Branch</span> [compile e1] [compile e2] [compile e3]</code></pre>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">PrintE</span> e <span class="fu">---></span> <span class="dt">Print</span> <span class="fu">:</span> compile e </code></pre>
</div>
<div id="from-concepts-to-byte-code-2" class="slide section level1">
<h1>From Concepts to ("Byte") Code</h1>
<ul>
<li>The hard cases</li>
</ul>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">App</span> e1 e2 <span class="fu">---></span> <span class="dt">Push</span> (compile e2) <span class="fu">:</span> compile e1</code></pre>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="dt">Binop</span> op e1 e2 <span class="fu">---></span> [<span class="dt">OpC</span> op, <span class="dt">Load</span> (compile e1), <span class="dt">Load</span> (compile e2)]</code></pre>
</div>
<div id="recap" class="slide section level1">
<h1>Recap</h1>
<p>Our "Byte" code as a Haskell data type</p>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Code</span> <span class="fu">=</span> <span class="dt">Push</span> [<span class="dt">Code</span>]
<span class="fu">|</span> <span class="dt">PushI</span> <span class="dt">Integer</span>
<span class="fu">|</span> <span class="dt">PushB</span> <span class="dt">Bool</span>
<span class="fu">|</span> <span class="dt">Access</span> <span class="dt">Name</span>
<span class="fu">|</span> <span class="dt">Close</span> <span class="dt">Name</span> [<span class="dt">Code</span>]
<span class="fu">|</span> <span class="dt">OpC</span> <span class="dt">Op</span>
<span class="fu">|</span> <span class="dt">Load</span> [<span class="dt">Code</span>]
<span class="fu">|</span> <span class="dt">Branch</span> [<span class="dt">Code</span>] [<span class="dt">Code</span>] [<span class="dt">Code</span>]
<span class="fu">|</span> <span class="dt">Print</span> </code></pre>
</div>
<div id="values-in-the-cek-machine" class="slide section level1">
<h1>Values in the CEK Machine</h1>
<p>When we run a program on the CEK machine what is the result?</p>
<ul class="incremental">
<li>A closure</li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Clos</span> <span class="fu">=</span> <span class="dt">Clos</span> (<span class="dt">Val</span>,[<span class="dt">Code</span>],<span class="dt">Env</span>)
<span class="kw">data</span> <span class="dt">Val</span> <span class="fu">=</span> <span class="dt">VNum</span> <span class="dt">Integer</span>
<span class="fu">|</span> <span class="dt">VVar</span> <span class="dt">Name</span>
<span class="fu">|</span> <span class="dt">VBool</span> <span class="dt">Bool</span></code></pre></li>
</ul>
</div>
<div id="continuations" class="slide section level1">
<h1>Continuations</h1>
<p>Our CEK machine will build continuations for all "complex" expressions</p>
<ul>
<li>The (K)ontinuation register is a stack of continuations</li>
<li>It keeps track of the next step of evaluation</li>
</ul>
<ul class="incremental">
<li>So what do we consider a "complex" expression?</li>
<li>Expressions which are not immediate values.</li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Cont</span> <span class="fu">=</span> <span class="dt">MT</span>
<span class="fu">|</span> <span class="dt">FN</span> <span class="dt">Clos</span> <span class="dt">Cont</span>
<span class="fu">|</span> <span class="dt">AR</span> [<span class="dt">Code</span>] <span class="dt">Env</span> <span class="dt">Cont</span>
<span class="fu">|</span> <span class="dt">OP</span> <span class="dt">Op</span> [<span class="dt">Clos</span>] [<span class="dt">Code</span>] <span class="dt">Env</span> <span class="dt">Cont</span>
<span class="fu">|</span> <span class="dt">IFC</span> [<span class="dt">Code</span>] [<span class="dt">Code</span>] <span class="dt">Env</span> <span class="dt">Cont</span>
<span class="fu">|</span> <span class="dt">PrintC</span> <span class="dt">Cont</span>
<span class="kw">deriving</span>(<span class="kw">Show</span>)</code></pre></li>
</ul>
</div>
<div id="evaluation-on-the-cek-machine" class="slide section level1">
<h1>Evaluation on the CEK Machine</h1>
<ul>
<li><p>The CEK machine is a state machine with transition rules.</p></li>
<li><p>The transitions are driven by two mutually recursive functions.</p></li>
</ul>
</div>
<div id="eval3-on-the-cek-machine" class="slide section level1">
<h1>Eval3 on the CEK Machine</h1>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">type</span> <span class="dt">MachineState</span> <span class="fu">=</span> ([<span class="dt">Code</span>],<span class="dt">Env</span>,<span class="dt">Cont</span>,[<span class="dt">String</span>])</code></pre>
<ul class="incremental">
<li><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot">eval3 ::</span> <span class="dt">MachineState</span> <span class="ot">-></span> (<span class="dt">Clos</span>,[<span class="dt">String</span>])</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">Access</span> x<span class="fu">:</span>c,e,k,o) <span class="fu">=</span> eval2 (k,envLookup e x,o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">PushI</span> n<span class="fu">:</span>c,e,k,o) <span class="fu">=</span> eval2 (k,<span class="dt">Clos</span> (<span class="dt">VNum</span> n,[],[]),o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">PushB</span> b<span class="fu">:</span>c,e,k,o) <span class="fu">=</span> eval2 (k,<span class="dt">Clos</span>(<span class="dt">VBool</span> b,[],[]),o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">Close</span> x c'<span class="fu">:</span>c,e,k,o) <span class="fu">=</span> eval2 (k,<span class="dt">Clos</span> (<span class="dt">VVar</span> x,c',e),o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">Push</span> c'<span class="fu">:</span>c,e,k,o) <span class="fu">=</span> eval3 (c,e,<span class="dt">AR</span> c' e k,o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">OpC</span> op<span class="fu">:</span><span class="dt">Load</span> c<span class="fu">:</span>c',e,k,o) <span class="fu">=</span> eval3 (c,e,<span class="dt">OP</span> op [] c' e k,o) </code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">Branch</span> b c1 c2 <span class="fu">:</span>c,e,k,o) <span class="fu">=</span> eval3 (b,e,<span class="dt">IFC</span> c1 c2 e k,o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval3 (<span class="dt">Print</span><span class="fu">:</span>c,e,k,o) <span class="fu">=</span> eval3 (c,e,<span class="dt">PrintC</span> k,o)</code></pre></li>
</ul>
</div>
<div id="eval2-on-the-cek-machine" class="slide section level1">
<h1>Eval2 on the CEK Machine</h1>
<pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">type</span> <span class="dt">ContState</span> <span class="fu">=</span> (<span class="dt">Cont</span>,<span class="dt">Clos</span>,[<span class="dt">String</span>])</code></pre>
<ul class="incremental">
<li><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot">eval2 ::</span> <span class="dt">ContState</span> <span class="ot">-></span> (<span class="dt">Clos</span>,[<span class="dt">String</span>])</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval2 (<span class="dt">AR</span> c e k,v,o) <span class="fu">=</span> eval3 (c,e,<span class="dt">FN</span> v k,o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval2 (<span class="dt">FN</span> (<span class="dt">Clos</span> (<span class="dt">VVar</span> x,c,e)) k,v,o) <span class="fu">=</span> eval3 (c,update e x v,k,o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval2 (<span class="dt">OP</span> op vs (<span class="dt">Load</span> c<span class="fu">:</span>c') e k, v,o) <span class="fu">=</span> eval3 (c,e,<span class="dt">OP</span> op (v<span class="fu">:</span>vs) c' e k,o) </code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval2 (<span class="dt">OP</span> op vs c e k,v,o) <span class="fu">=</span> eval2 (k,<span class="dt">Clos</span> (applyOp op (getVal (<span class="fu">head</span> vs)) (getVal v),[],[]),o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval2 (<span class="dt">IFC</span> c1 c2 e k,v,o) <span class="fu">=</span> eval3 (<span class="kw">if</span> truthy v <span class="kw">then</span> c1 <span class="kw">else</span> c2,e,k,o)</code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval2 (<span class="dt">PrintC</span> k,v,o) <span class="fu">=</span> eval2 (k,v, printClos v o) </code></pre></li>
<li><pre class="sourceCode haskell"><code class="sourceCode haskell">eval2 (<span class="dt">MT</span>,v,o) <span class="fu">=</span> (v,o)</code></pre></li>
</ul>
</div>
</body>
</html>