|
1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{../slides} |
|
3 \usepackage{../langs} |
|
4 \usepackage{../data} |
|
5 \usepackage{../graphics} |
|
6 \usepackage{../grammar} |
|
7 \usepackage{soul} |
|
8 |
|
9 \tikzset{onslide/.code args={<#1>#2}{% |
|
10 \only<#1>{\pgfkeysalso{#2}} % \pgfkeysalso doesn't change the path |
|
11 }} |
|
12 |
|
13 \makeatletter |
|
14 \newenvironment<>{btHighlight}[1][] |
|
15 {\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}} |
|
16 {\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}} |
|
17 |
|
18 \newcommand<>\btHL[1][]{% |
|
19 \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}% |
|
20 } |
|
21 \def\bt@HL@endenv{%b jm |
|
22 \end{btHighlight}% |
|
23 \egroup |
|
24 } |
|
25 \newcommand{\bt@HL@box}[2][]{% |
|
26 \tikz[#1]{% |
|
27 \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}% |
|
28 \pgfusepath{use as bounding box}% |
|
29 \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}}; |
|
30 }% |
|
31 } |
|
32 \makeatother |
|
33 |
|
34 \lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries} |
|
35 |
|
36 % beamer stuff |
|
37 \renewcommand{\slidecaption}{CFL 09, King's College London} |
|
38 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
39 |
|
40 |
|
41 \begin{document} |
|
42 |
|
43 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
44 \begin{frame}[t] |
|
45 \frametitle{% |
|
46 \begin{tabular}{@ {}c@ {}} |
|
47 \\[-3mm] |
|
48 \LARGE Compilers and \\[-2mm] |
|
49 \LARGE Formal Languages (8)\\[3mm] |
|
50 \end{tabular}} |
|
51 |
|
52 \normalsize |
|
53 \begin{center} |
|
54 \begin{tabular}{ll} |
|
55 Email: & christian.urban at kcl.ac.uk\\ |
|
56 Office: & N7.07 (North Wing, Bush House)\\ |
|
57 Slides: & KEATS (also home work is there)\\ |
|
58 \end{tabular} |
|
59 \end{center} |
|
60 |
|
61 \end{frame} |
|
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
63 |
|
64 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
65 \begin{frame}[t,fragile] |
|
66 \frametitle{Compiling AExps} |
|
67 |
|
68 For example \bl{$1 + ((2 * 3) + (4 - 3))$}:\medskip |
|
69 |
|
70 \begin{columns}[T] |
|
71 \begin{column}{.3\textwidth} |
|
72 \begin{center} |
|
73 \bl{\begin{tikzpicture} |
|
74 \tikzset{level distance=12mm,sibling distance=4mm} |
|
75 \tikzset{edge from parent/.style={draw,very thick}} |
|
76 \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]] |
|
77 \end{tikzpicture}} |
|
78 \end{center} |
|
79 \end{column} |
|
80 \begin{column}{.3\textwidth} |
|
81 \begin{lstlisting}[language=JVMIS,numbers=none] |
|
82 ldc 1 |
|
83 ldc 2 |
|
84 ldc 3 |
|
85 imul |
|
86 ldc 4 |
|
87 ldc 3 |
|
88 isub |
|
89 iadd |
|
90 iadd |
|
91 \end{lstlisting} |
|
92 \end{column} |
|
93 \end{columns}\bigskip |
|
94 |
|
95 \small |
|
96 Traverse tree in post-order \bl{$\Rightarrow$} code for |
|
97 stack-machine |
|
98 |
|
99 \end{frame} |
|
100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
101 |
|
102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
103 \begin{frame}[c,fragile] |
|
104 \frametitle{Compiling AExps} |
|
105 |
|
106 \bl{ |
|
107 \begin{center} |
|
108 \begin{tabular}{lcl} |
|
109 $\textit{compile}(n, E)$ & $\dn$ & $\pcode{ldc}\;n$\smallskip\\ |
|
110 $\textit{compile}(a_1 + a_2, E)$ & $\dn$ \\ |
|
111 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{iadd}$}\smallskip\\ |
|
112 $\textit{compile}(a_1 - a_2, E)$ & $\dn$ \\ |
|
113 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{isub}$}\smallskip\\ |
|
114 $\textit{compile}(a_1 * a_2, E)$ & $\dn$ \\ |
|
115 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{imul}$}\smallskip\\ |
|
116 $\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$\\ |
|
117 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{idiv}$}\smallskip\\ |
|
118 $\textit{compile}(x, E)$ & $\dn$ & $\pcode{iload}\;E(x)$\\ |
|
119 \end{tabular} |
|
120 \end{center}} |
|
121 |
|
122 \end{frame} |
|
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
124 |
|
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
126 \begin{frame}[c,fragile] |
|
127 \frametitle{Compiling Ifs} |
|
128 |
|
129 For example |
|
130 |
|
131 \begin{lstlisting}[mathescape,numbers=none,language=While] |
|
132 if 1 = 1 then x := 2 else y := 3 |
|
133 \end{lstlisting} |
|
134 |
|
135 |
|
136 \begin{center} |
|
137 \begin{lstlisting}[mathescape,language=JVMIS,numbers=none] |
|
138 ldc 1 |
|
139 ldc 1 |
|
140 if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$ |
|
141 ldc 2 |
|
142 istore 0 |
|
143 goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$ |
|
144 L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$ |
|
145 ldc 3 |
|
146 istore 1 |
|
147 L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$ |
|
148 \end{lstlisting} |
|
149 \end{center} |
|
150 |
|
151 \begin{tikzpicture}[remember picture,overlay] |
|
152 \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) |
|
153 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east); |
|
154 \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm) |
|
155 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east); |
|
156 \end{tikzpicture} |
|
157 |
|
158 \end{frame} |
|
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
160 |
|
161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
162 \begin{frame}[c,fragile] |
|
163 \frametitle{Compiling Whiles} |
|
164 |
|
165 For example |
|
166 |
|
167 \begin{lstlisting}[mathescape,numbers=none,language=While] |
|
168 while x <= 10 do x := x + 1 |
|
169 \end{lstlisting} |
|
170 |
|
171 |
|
172 \begin{center} |
|
173 \begin{lstlisting}[mathescape,language=JVMIS,numbers=none] |
|
174 L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$ |
|
175 iload 0 |
|
176 ldc 10 |
|
177 if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$ |
|
178 iload 0 |
|
179 ldc 1 |
|
180 iadd |
|
181 istore 0 |
|
182 goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$ |
|
183 L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$ |
|
184 \end{lstlisting} |
|
185 \end{center} |
|
186 |
|
187 \begin{tikzpicture}[remember picture,overlay] |
|
188 \draw[->,very thick] (LA) edge [->,to path={-- ++(12mm,0mm) |
|
189 -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east); |
|
190 \draw[->,very thick] (LC) edge [->,to path={-- ++(12mm,0mm) |
|
191 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east); |
|
192 \end{tikzpicture} |
|
193 |
|
194 \end{frame} |
|
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
196 |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 \begin{frame}[c,fragile] |
|
199 \frametitle{Compiling Writes} |
|
200 |
|
201 \small |
|
202 \begin{lstlisting}[language=JVMIS,mathescape, |
|
203 numbers=none,xleftmargin=-6mm] |
|
204 .method public static write(I)V |
|
205 .limit locals 1 |
|
206 .limit stack 2 |
|
207 getstatic java/lang/System/out |
|
208 Ljava/io/PrintStream; |
|
209 iload 0 |
|
210 invokevirtual java/io/PrintStream/println(I)V |
|
211 return |
|
212 .end method |
|
213 |
|
214 |
|
215 |
|
216 iload $E(x)$ |
|
217 invokestatic XXX/XXX/write(I)V |
|
218 \end{lstlisting} |
|
219 |
|
220 \end{frame} |
|
221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
222 |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 \begin{frame}[c,fragile] |
|
225 \frametitle{Compiling Main} |
|
226 |
|
227 \footnotesize |
|
228 \begin{lstlisting}[language=JVMIS,mathescape, |
|
229 numbers=none,xleftmargin=-6mm] |
|
230 .class public XXX.XXX |
|
231 .super java/lang/Object |
|
232 |
|
233 .method public <init>()V |
|
234 aload_0 |
|
235 invokenonvirtual java/lang/Object/<init>()V |
|
236 return |
|
237 .end method |
|
238 |
|
239 .method public static main([Ljava/lang/String;)V |
|
240 .limit locals 200 |
|
241 .limit stack 200 |
|
242 |
|
243 $\textit{\ldots{}here comes the compiled code\ldots}$ |
|
244 |
|
245 return |
|
246 .end method |
|
247 \end{lstlisting} |
|
248 |
|
249 \end{frame} |
|
250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
251 |
|
252 |
|
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
254 \begin{frame}[c,fragile] |
|
255 \frametitle{Functional Programming} |
|
256 |
|
257 \footnotesize |
|
258 \begin{textblock}{13}(0.9,3) |
|
259 \begin{lstlisting}[]numbers=none] |
|
260 def fib(n) = if n == 0 then 0 |
|
261 else if n == 1 then 1 |
|
262 else fib(n - 1) + fib(n - 2); |
|
263 |
|
264 def fact(n) = if n == 0 then 1 else n * fact(n - 1); |
|
265 |
|
266 def ack(m, n) = if m == 0 then n + 1 |
|
267 else if n == 0 then ack(m - 1, 1) |
|
268 else ack(m - 1, ack(m, n - 1)); |
|
269 |
|
270 def gcd(a, b) = if b == 0 then a else gcd(b, a % b); |
|
271 \end{lstlisting} |
|
272 \end{textblock} |
|
273 |
|
274 \end{frame} |
|
275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
276 |
|
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
278 \begin{frame}[c] |
|
279 \frametitle{Fun Grammar} |
|
280 \bl{ |
|
281 \begin{plstx}[rhs style=] |
|
282 : \meta{Exp} ::= \meta{Var} | \meta{Num}{\hspace{3cm}} |
|
283 | \meta{Exp} + \meta{Exp} | ... | (\meta{Exp}) |
|
284 | \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp} |
|
285 | \code{write} \meta{Exp} {\hspace{3cm}} |
|
286 | \meta{Exp} ; \meta{Exp} |
|
287 | \textit{FunName} (\meta{Exp}, ... , \meta{Exp})\\ |
|
288 : \meta{BExp} ::= ...\\ |
|
289 : \meta{Decl} ::= \meta{Def} ; \meta{Decl} |
|
290 | \meta{Exp}\\ |
|
291 : \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ... , $x_n$) = \meta{Exp}\\ |
|
292 \end{plstx}} |
|
293 |
|
294 |
|
295 |
|
296 \end{frame} |
|
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
298 |
|
299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
300 \begin{frame}[c, fragile] |
|
301 \frametitle{Abstract Syntax Trees} |
|
302 |
|
303 \footnotesize |
|
304 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] |
|
305 abstract class Exp |
|
306 abstract class BExp |
|
307 abstract class Decl |
|
308 |
|
309 case class Var(s: String) extends Exp |
|
310 case class Num(i: Int) extends Exp |
|
311 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
|
312 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
|
313 case class Write(e: Exp) extends Exp |
|
314 case class Sequ(e1: Exp, e2: Exp) extends Exp |
|
315 case class Call(name: String, args: List[Exp]) extends Exp |
|
316 |
|
317 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
|
318 |
|
319 case class Def(name: String, |
|
320 args: List[String], |
|
321 body: Exp) extends Decl |
|
322 case class Main(e: Exp) extends Decl |
|
323 \end{lstlisting} |
|
324 |
|
325 \end{frame} |
|
326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
327 |
|
328 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
329 \begin{frame}[c, fragile] |
|
330 \frametitle{Sequences} |
|
331 |
|
332 Compiling \texttt{exp1 ; exp2}:\bigskip |
|
333 |
|
334 |
|
335 \begin{lstlisting}[mathescape,language=JVMIS, numbers=none] |
|
336 $\textit{compile}$(exp1) |
|
337 pop |
|
338 $\textit{compile}$(exp2) |
|
339 \end{lstlisting} |
|
340 |
|
341 \end{frame} |
|
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
343 |
|
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
345 \begin{frame}[c, fragile] |
|
346 \frametitle{Write} |
|
347 |
|
348 Compiling call to \texttt{write(1+2)}:\bigskip |
|
349 |
|
350 |
|
351 \begin{lstlisting}[mathescape,language=JVMIS, numbers=none] |
|
352 $\textit{compile}$(1+2) |
|
353 dup |
|
354 invokestatic XXX/XXX/write(I)V |
|
355 \end{lstlisting}\bigskip |
|
356 |
|
357 \small |
|
358 needs the helper method |
|
359 |
|
360 \footnotesize |
|
361 \begin{lstlisting}[language=JVMIS, |
|
362 xleftmargin=2mm, |
|
363 numbers=none] |
|
364 .method public static write(I)V |
|
365 .limit locals 1 |
|
366 .limit stack 2 |
|
367 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
368 iload 0 |
|
369 invokevirtual java/io/PrintStream/println(I)V |
|
370 return |
|
371 .end method |
|
372 \end{lstlisting} |
|
373 \end{frame} |
|
374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
375 |
|
376 |
|
377 |
|
378 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
379 \begin{frame}[t, fragile] |
|
380 \frametitle{Function Definitions} |
|
381 |
|
382 \footnotesize |
|
383 \begin{lstlisting}[language=JVMIS, |
|
384 xleftmargin=2mm, |
|
385 numbers=none] |
|
386 .method public static write(I)V |
|
387 .limit locals 1 |
|
388 .limit stack 2 |
|
389 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
390 iload 0 |
|
391 invokevirtual java/io/PrintStream/println(I)V |
|
392 return |
|
393 .end method |
|
394 \end{lstlisting}\bigskip |
|
395 |
|
396 \small We will need for definitions, like\footnotesize\medskip |
|
397 |
|
398 \begin{lstlisting}[language=JVMIS, |
|
399 xleftmargin=2mm, |
|
400 numbers=none] |
|
401 def fname (x1, ... , xn) = ... |
|
402 |
|
403 .method public static fname (I...I)I |
|
404 .limit locals ?? |
|
405 .limit stack ?? |
|
406 ?? |
|
407 .end method |
|
408 \end{lstlisting} |
|
409 |
|
410 \end{frame} |
|
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
412 |
|
413 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
414 \begin{frame}[c, fragile] |
|
415 \frametitle{Stack Estimation} |
|
416 \small |
|
417 \mbox{}\\[-15mm] |
|
418 |
|
419 \bl{\begin{center} |
|
420 \begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} |
|
421 $\textit{estimate}(n)$ & $\dn$ & $1$\\ |
|
422 $\textit{estimate}(x)$ & $\dn$ & $1$\\ |
|
423 $\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ & |
|
424 $\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\ |
|
425 $\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & |
|
426 $\textit{estimate}(b) +$\\ |
|
427 & & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\ |
|
428 $\textit{estimate}(\pcode{write}(e))$ & $\dn$ & |
|
429 $\textit{estimate}(e) + 1$\\ |
|
430 $\textit{estimate}(e_1 ; e_2)$ & $\dn$ & |
|
431 $max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\ |
|
432 $\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & |
|
433 $\sum_{i = 1..n}\;estimate(e_i)$\medskip\\ |
|
434 $\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ & |
|
435 $\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\ |
|
436 \end{tabular} |
|
437 \end{center}} |
|
438 |
|
439 \end{frame} |
|
440 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
441 |
|
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
443 \begin{frame}[fragile] |
|
444 \frametitle{Successor Function} |
|
445 |
|
446 \begin{textblock}{7}(1,2.5)\footnotesize |
|
447 \begin{minipage}{6cm} |
|
448 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
449 .method public static suc(I)I |
|
450 .limit locals 1 |
|
451 .limit stack 2 |
|
452 iload 0 |
|
453 ldc 1 |
|
454 iadd |
|
455 ireturn |
|
456 .end method |
|
457 \end{lstlisting} |
|
458 \end{minipage} |
|
459 \end{textblock} |
|
460 |
|
461 \begin{textblock}{7}(6,8) |
|
462 \begin{bubble}[5cm]\small |
|
463 \begin{lstlisting}[language=Lisp, |
|
464 basicstyle=\ttfamily, |
|
465 numbers=none, |
|
466 xleftmargin=1mm] |
|
467 def suc(x) = x + 1; |
|
468 \end{lstlisting} |
|
469 \end{bubble} |
|
470 \end{textblock} |
|
471 |
|
472 \end{frame} |
|
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
474 |
|
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
476 \begin{frame}[fragile] |
|
477 \frametitle{Addition Function} |
|
478 |
|
479 \begin{textblock}{7}(1,1.9)\footnotesize |
|
480 \begin{minipage}{6cm} |
|
481 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
482 .method public static add(II)I |
|
483 .limit locals 2 |
|
484 .limit stack 5 |
|
485 iload 0 |
|
486 ldc 0 |
|
487 if_icmpne If_else |
|
488 iload 1 |
|
489 goto If_end |
|
490 If_else: |
|
491 iload 0 |
|
492 ldc 1 |
|
493 isub |
|
494 iload 1 |
|
495 invokestatic XXX/XXX/add(II)I |
|
496 invokestatic XXX/XXX/suc(I)I |
|
497 If_end: |
|
498 ireturn |
|
499 .end method |
|
500 \end{lstlisting} |
|
501 \end{minipage} |
|
502 \end{textblock} |
|
503 |
|
504 \begin{textblock}{7}(6,6.6) |
|
505 \begin{bubble}[7cm]\small |
|
506 \begin{lstlisting}[language=Lisp, |
|
507 basicstyle=\ttfamily, |
|
508 numbers=none, |
|
509 xleftmargin=1mm] |
|
510 def add(x, y) = |
|
511 if x == 0 then y |
|
512 else suc(add(x - 1, y)); |
|
513 \end{lstlisting} |
|
514 \end{bubble} |
|
515 \end{textblock} |
|
516 |
|
517 \end{frame} |
|
518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
519 |
|
520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
521 \begin{frame}[fragile] |
|
522 \frametitle{Factorial} |
|
523 |
|
524 \begin{textblock}{7}(1,1.5)\footnotesize |
|
525 \begin{minipage}{6cm} |
|
526 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
527 .method public static facT(II)I |
|
528 .limit locals 2 |
|
529 .limit stack 6 |
|
530 iload 0 |
|
531 ldc 0 |
|
532 if_icmpne If_else_2 |
|
533 iload 1 |
|
534 goto If_end_3 |
|
535 If_else_2: |
|
536 iload 0 |
|
537 ldc 1 |
|
538 isub |
|
539 iload 0 |
|
540 iload 1 |
|
541 imul |
|
542 invokestatic fact/fact/facT(II)I |
|
543 If_end_3: |
|
544 ireturn |
|
545 .end method |
|
546 \end{lstlisting} |
|
547 \end{minipage} |
|
548 \end{textblock} |
|
549 |
|
550 \begin{textblock}{7}(6,7) |
|
551 \begin{bubble}[7cm]\small |
|
552 \begin{lstlisting}[language=Lisp, |
|
553 basicstyle=\ttfamily, |
|
554 numbers=none, |
|
555 xleftmargin=1mm] |
|
556 def facT(n, acc) = |
|
557 if n == 0 then acc |
|
558 else facT(n - 1, n * acc); |
|
559 \end{lstlisting} |
|
560 \end{bubble} |
|
561 \end{textblock} |
|
562 |
|
563 \end{frame} |
|
564 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
565 |
|
566 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
567 \begin{frame}[fragile] |
|
568 |
|
569 \begin{textblock}{7}(1,-0.2)\footnotesize |
|
570 \begin{minipage}{6cm} |
|
571 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}] |
|
572 .method public static facT(II)I |
|
573 .limit locals 2 |
|
574 .limit stack 6 |
|
575 (*@\hl{facT\_Start:} @*) |
|
576 iload 0 |
|
577 ldc 0 |
|
578 if_icmpne If_else_2 |
|
579 iload 1 |
|
580 goto If_end_3 |
|
581 If_else_2: |
|
582 iload 0 |
|
583 ldc 1 |
|
584 isub |
|
585 iload 0 |
|
586 iload 1 |
|
587 imul |
|
588 (*@\hl{istore 1} @*) |
|
589 (*@\hl{istore 0} @*) |
|
590 (*@\hl{goto facT\_Start} @*) |
|
591 If_end_3: |
|
592 ireturn |
|
593 .end method |
|
594 \end{lstlisting} |
|
595 \end{minipage} |
|
596 \end{textblock} |
|
597 |
|
598 \begin{textblock}{7}(6,7) |
|
599 \begin{bubble}[7cm]\small |
|
600 \begin{lstlisting}[language=Lisp, |
|
601 basicstyle=\ttfamily, |
|
602 numbers=none, |
|
603 xleftmargin=1mm] |
|
604 def facT(n, acc) = |
|
605 if n == 0 then acc |
|
606 else facT(n - 1, n * acc); |
|
607 \end{lstlisting} |
|
608 \end{bubble} |
|
609 \end{textblock} |
|
610 |
|
611 \end{frame} |
|
612 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
613 |
|
614 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
615 \begin{frame}[c, fragile] |
|
616 \frametitle{Tail Recursion} |
|
617 |
|
618 A call to \texttt{f(args)} is usually compiled as\medskip |
|
619 |
|
620 {\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
|
621 args onto stack |
|
622 invokestatic .../f |
|
623 \end{lstlisting}}\pause |
|
624 |
|
625 |
|
626 A call is in tail position provided:\medskip |
|
627 |
|
628 {\small\begin{itemize} |
|
629 \item \texttt{if Bexp then \hl{Exp} else \hl{Exp}} |
|
630 \item \texttt{Exp ; \hl{Exp}} |
|
631 \item \texttt{Exp op Exp} |
|
632 \end{itemize}}\medskip |
|
633 |
|
634 then a call \texttt{f(args)} can be compiled as\medskip\small |
|
635 |
|
636 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
|
637 prepare environment |
|
638 jump to start of function |
|
639 \end{lstlisting} |
|
640 |
|
641 \end{frame} |
|
642 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
643 |
|
644 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
645 \begin{frame}[c, fragile] |
|
646 \frametitle{Tail Recursive Call} |
|
647 \footnotesize |
|
648 |
|
649 \begin{textblock}{13}(-0.3,2) |
|
650 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
651 def compile_expT(a: Exp, env: Mem, name: String): Instrs = |
|
652 ... |
|
653 case Call(n, args) => if (name == n) |
|
654 { |
|
655 val stores = args.zipWithIndex.map |
|
656 { case (x, y) => "istore " + y.toString + "\n" } |
|
657 args.flatMap(a => compile_expT(a, env, "")) ++ |
|
658 stores.reverse ++ |
|
659 List ("goto " + n + "_Start\n") |
|
660 } |
|
661 else |
|
662 { |
|
663 val is = "I" * args.length |
|
664 args.flatMap(a => compile_expT(a, env, "")) ++ |
|
665 List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") |
|
666 } |
|
667 \end{lstlisting} |
|
668 \end{textblock} |
|
669 |
|
670 \end{frame} |
|
671 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
672 |
|
673 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
674 \begin{frame}[c] |
|
675 \frametitle{Dijkstra on Testing} |
|
676 |
|
677 \begin{bubble}[10cm] |
|
678 ``Program testing can be a very effective way to show the |
|
679 presence of bugs, but it is hopelessly inadequate for showing |
|
680 their absence.'' |
|
681 \end{bubble}\bigskip |
|
682 |
|
683 \small |
|
684 What is good about compilers: the either seem to work, |
|
685 or go horribly wrong (most of the time). |
|
686 |
|
687 \end{frame} |
|
688 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
689 |
|
690 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
691 \begin{frame}[c] |
|
692 \frametitle{\Large Proving Programs to be Correct} |
|
693 |
|
694 \begin{bubble}[10cm] |
|
695 \small |
|
696 {\bf Theorem:} There are infinitely many prime |
|
697 numbers.\medskip\\ |
|
698 |
|
699 {\bf Proof} \ldots\\ |
|
700 \end{bubble}\bigskip |
|
701 |
|
702 |
|
703 similarly\bigskip |
|
704 |
|
705 \begin{bubble}[10cm] |
|
706 \small |
|
707 {\bf Theorem:} The program is doing what |
|
708 it is supposed to be doing.\medskip |
|
709 |
|
710 {\bf Long, long proof} \ldots\\ |
|
711 \end{bubble}\bigskip\medskip |
|
712 |
|
713 \small This can be a gigantic proof. The only hope is to have |
|
714 help from the computer. `Program' is here to be understood to be |
|
715 quite general (compiler, OS, \ldots). |
|
716 |
|
717 \end{frame} |
|
718 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
719 |
|
720 |
|
721 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
722 |
|
723 \begin{frame}[c] |
|
724 \frametitle{Can This Be Done?} |
|
725 |
|
726 \begin{itemize} |
|
727 \item in 2008, verification of a small C-compiler |
|
728 \begin{itemize} |
|
729 \item ``if my input program has a certain behaviour, then the compiled machine code has the same behaviour'' |
|
730 \item is as good as \texttt{gcc -O1}, but much, much less buggy |
|
731 \end{itemize} |
|
732 \end{itemize} |
|
733 |
|
734 \begin{center} |
|
735 \includegraphics[scale=0.12]{../pics/compcert.png} |
|
736 \end{center} |
|
737 |
|
738 \end{frame} |
|
739 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
740 |
|
741 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
742 \begin{frame}[c] |
|
743 \frametitle{Fuzzy Testing C-Compilers} |
|
744 |
|
745 \begin{itemize} |
|
746 \item tested GCC, LLVM and others by randomly generating |
|
747 C-programs |
|
748 \item found more than 300 bugs in GCC and also |
|
749 many in LLVM (some of them highest-level critical)\bigskip |
|
750 \item about CompCert: |
|
751 |
|
752 \begin{bubble}[10cm]\small ``The striking thing about our CompCert |
|
753 results is that the middle-end bugs we found in all other |
|
754 compilers are absent. As of early 2011, the under-development |
|
755 version of CompCert is the only compiler we have tested for |
|
756 which Csmith cannot find wrong-code errors. This is not for |
|
757 lack of trying: we have devoted about six CPU-years to the |
|
758 task.'' |
|
759 \end{bubble} |
|
760 \end{itemize} |
|
761 |
|
762 \end{frame} |
|
763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
764 |
|
765 \end{document} |
|
766 |
|
767 %%% Local Variables: |
|
768 %%% mode: latex |
|
769 %%% TeX-master: t |
|
770 %%% End: |
|
771 |