1 \documentclass[dvipsnames,14pt,t]{beamer} |
1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{xcolor} |
2 \usepackage{../slides} |
3 \usepackage{../slides} |
3 \usepackage{../langs} |
4 \usepackage{../langs} |
4 \usepackage{../data} |
5 \usepackage{../data} |
5 \usepackage{../graphics} |
6 \usepackage{../graphics} |
6 \usepackage{../grammar} |
7 \usepackage{../grammar} |
7 |
8 |
8 % beamer stuff |
9 \usepackage[most]{tcolorbox} |
9 \renewcommand{\slidecaption}{CFL 07, King's College London} |
10 |
|
11 \newtcbox{\hl}[1][]{% |
|
12 size=fbox, |
|
13 tcbox raise base, nobeforeafter, |
|
14 enhanced, colframe=gray, |
|
15 colback=gray!30, boxrule=1pt, |
|
16 fontupper=\ttfamily, |
|
17 #1} |
|
18 |
|
19 \lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries} |
|
20 |
|
21 % beamer stuff |
|
22 \renewcommand{\slidecaption}{CFL 09, King's College London} |
10 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
23 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
24 |
11 |
25 |
12 \begin{document} |
26 \begin{document} |
13 |
27 |
14 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
28 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
15 \begin{frame}[t] |
29 \begin{frame}[t] |
16 \frametitle{% |
30 \frametitle{% |
17 \begin{tabular}{@ {}c@ {}} |
31 \begin{tabular}{@ {}c@ {}} |
18 \\[-3mm] |
32 \\[-3mm] |
19 \LARGE Compilers and \\[-2mm] |
33 \LARGE Compilers and \\[-2mm] |
20 \LARGE Formal Languages (7)\\[3mm] |
34 \LARGE Formal Languages (8)\\[3mm] |
21 \end{tabular}} |
35 \end{tabular}} |
22 |
36 |
23 \normalsize |
37 \normalsize |
24 \begin{center} |
38 \begin{center} |
25 \begin{tabular}{ll} |
39 \begin{tabular}{ll} |
26 Email: & christian.urban at kcl.ac.uk\\ |
40 Email: & christian.urban at kcl.ac.uk\\ |
27 Office: & N\liningnums{7.07} (North Wing, Bush House)\\ |
41 Office: & N7.07 (North Wing, Bush House)\\ |
28 Slides: & KEATS (also homework is there)\\ |
42 Slides: & KEATS (also home work is there)\\ |
29 \end{tabular} |
43 \end{tabular} |
30 \end{center} |
44 \end{center} |
31 |
45 |
32 \end{frame} |
46 \end{frame} |
33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
47 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
34 |
48 |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
49 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
36 \begin{frame}[c] |
50 \begin{frame}[c] |
37 \frametitle{Bird's Eye View} |
|
38 |
|
39 \begin{center} |
|
40 \begin{tikzpicture} |
|
41 \node (rexp) {\bl{\bf Lexer}}; |
|
42 \node (nfa) [right=of rexp] {\bl{\bf Parser}}; |
|
43 \node (dfa) [right=of nfa] |
|
44 {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Java Byte Code\end{tabular}}}; |
|
45 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm] |
|
46 sequence\end{tabular}} (nfa); |
|
47 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree\end{tabular}}(dfa); |
|
48 \end{tikzpicture}\\ |
|
49 \end{center} |
|
50 |
|
51 \end{frame} |
|
52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
53 |
|
54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
55 \begin{frame}[c] |
|
56 \begin{textblock}{10}(0.5,0.5) |
|
57 \LARGE |
|
58 \fontspec{Hoefler Text Black} |
|
59 \textcolor{ProcessBlue}{JVM\\ Code} |
|
60 \\[12mm] |
|
61 |
|
62 \normalsize |
|
63 Jasmin\\ |
|
64 Krakatau\\ |
|
65 ASM lib |
|
66 \end{textblock} |
|
67 |
|
68 |
|
69 \fontsize{8}{10}\selectfont |
|
70 %\footnotesize |
|
71 \mbox{}\\[-8mm]\mbox{} |
|
72 |
|
73 \begin{columns} |
|
74 \begin{column}{2cm} |
|
75 \lstinputlisting[numbers=none]{../progs/appHa.j} |
|
76 \end{column} |
|
77 |
|
78 \begin{column}{2cm} |
|
79 \lstinputlisting[numbers=none]{../progs/appHb.j} |
|
80 \end{column} |
|
81 |
|
82 \end{columns} |
|
83 |
|
84 \end{frame} |
|
85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
86 |
|
87 |
|
88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
89 \begin{frame}[t] |
|
90 |
51 |
91 \begin{center} |
52 \begin{center} |
92 \bl{\begin{tabular}{@{}lcl@{}} |
53 \bl{\begin{tabular}{@{}lcl@{}} |
93 \\[-12mm] |
|
94 \meta{Stmt} & $::=$ & $\texttt{skip}$\\ |
54 \meta{Stmt} & $::=$ & $\texttt{skip}$\\ |
95 & $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\ |
55 & $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\ |
96 & $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\ |
56 & $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\ |
97 & $|$ & \texttt{while}\; \meta{BExp} \;\texttt{do}\; \meta{Block}\\ |
57 & $|$ & \texttt{while}\; \meta{BExp} \;\texttt{do}\; \meta{Block}\\ |
98 & $|$ & \texttt{read}\;\textit{Id}\\ |
58 & $|$ & \texttt{read}\;\textit{Id}\\ |
107 \end{tabular}} |
67 \end{tabular}} |
108 \end{center} |
68 \end{center} |
109 \end{frame} |
69 \end{frame} |
110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
70 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
111 |
71 |
112 |
|
113 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
114 \begin{frame}[c] |
|
115 \frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}} |
|
116 |
|
117 \mbox{}\\[-18mm]\mbox{} |
|
118 |
|
119 {\lstset{language=While}\fontsize{10}{12}\selectfont |
|
120 \texttt{\lstinputlisting{../progs/fib.while}}} |
|
121 |
|
122 \end{frame} |
|
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
124 |
|
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
126 \begin{frame}[c] |
|
127 \frametitle{Interpreter} |
|
128 |
|
129 \begin{center} |
|
130 \bl{\begin{tabular}{@{}lcl@{}} |
|
131 $\text{eval}(n, E)$ & $\dn$ & $n$\\ |
|
132 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\ |
|
133 $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\ |
|
134 $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\ |
|
135 $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\ |
|
136 $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\ |
|
137 $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\ |
|
138 $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\ |
|
139 \end{tabular}} |
|
140 \end{center} |
|
141 |
|
142 \end{frame} |
|
143 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
144 |
|
145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
146 \begin{frame}[c] |
|
147 \frametitle{Interpreter (2)} |
|
148 |
|
149 \begin{center} |
|
150 \bl{\begin{tabular}{@{}lcl@{}} |
|
151 $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\ |
|
152 $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\ |
|
153 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\ |
|
154 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\; |
|
155 \text{eval}(cs_1,E)$}\\ |
|
156 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\ |
|
157 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\ |
|
158 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\ |
|
159 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\; |
|
160 \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\ |
|
161 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\ |
|
162 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\ |
|
163 \end{tabular}} |
|
164 \end{center} |
|
165 |
|
166 \end{frame} |
|
167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
168 |
|
169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
170 \begin{frame}[c] |
|
171 \frametitle{Test Program} |
|
172 |
|
173 \mbox{}\\[-18mm]\mbox{} |
|
174 |
|
175 {\lstset{language=While}\fontsize{10}{12}\selectfont |
|
176 \texttt{\lstinputlisting{../progs/loops.while}}} |
|
177 |
|
178 \end{frame} |
|
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
180 |
|
181 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
182 \begin{frame}[c] |
|
183 \fontsize{7}{9}\selectfont |
|
184 |
|
185 |
|
186 \begin{columns} |
|
187 \begin{column}{7cm} |
|
188 \lstinputlisting[numbers=none]{../progs/appHa.j} |
|
189 \end{column} |
|
190 |
|
191 \begin{column}{7cm} |
|
192 \lstinputlisting[numbers=none]{../progs/appHb.j} |
|
193 \end{column} |
|
194 \end{columns} |
|
195 |
|
196 \end{frame} |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 |
|
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
200 \begin{frame}[t] |
|
201 \frametitle{Interpreted Code} |
|
202 |
|
203 \begin{center} |
|
204 \begin{tikzpicture} |
|
205 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
|
206 \addplot+[smooth] file {interpreted.data}; |
|
207 \end{axis} |
|
208 \end{tikzpicture} |
|
209 \end{center} |
|
210 |
|
211 \end{frame} |
|
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
213 |
|
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
215 \begin{frame}[c] |
|
216 \frametitle{Java Virtual Machine} |
|
217 |
|
218 \begin{itemize} |
|
219 \item introduced in 1995 |
|
220 \item is a stack-based VM (like Postscript, CLR of .Net) |
|
221 \item contains a JIT compiler |
|
222 \item many languages take advantage of JVM's infrastructure (JRE) |
|
223 \item is garbage collected $\Rightarrow$ no buffer overflows |
|
224 \item some languages compiled to the JVM: Scala, Clojure\ldots |
|
225 \end{itemize} |
|
226 |
|
227 \end{frame} |
|
228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
229 |
|
230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
72 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
231 \begin{frame}[t,fragile] |
73 \begin{frame}[t,fragile] |
232 \frametitle{Compiling AExps} |
74 \frametitle{Compiling AExps} |
233 |
75 |
234 For example \liningnums{\bl{$1 + ((2 * 3) + (4 - 3))$}}:\medskip |
76 For example \bl{$1 + ((2 * 3) + (4 - 3))$}:\medskip |
235 |
77 |
236 \begin{columns}[T] |
78 \begin{columns}[T] |
237 \begin{column}{.3\textwidth} |
79 \begin{column}{.3\textwidth} |
238 \begin{center} |
80 \begin{center} |
239 \bl{\begin{tikzpicture} |
81 \bl{\begin{tikzpicture} |
240 \tikzset{level distance=12mm,sibling distance=4mm} |
82 \tikzset{level distance=12mm,sibling distance=4mm} |
241 \tikzset{edge from parent/.style={draw,very thick}} |
83 \tikzset{edge from parent/.style={draw,very thick}} |
242 \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]] |
84 \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]] |
243 \end{tikzpicture}} |
85 \end{tikzpicture}} |
244 \end{center} |
86 \end{center} |
245 \end{column} |
87 \end{column} |
246 \begin{column}{.3\textwidth} |
88 \begin{column}{.3\textwidth} |
247 \begin{lstlisting}[language=JVMIS,numbers=none] |
89 \begin{lstlisting}[language=JVMIS,numbers=none] |
248 ldc 1 |
90 ldc 1 |
249 ldc 2 |
91 ldc 2 |
250 ldc 3 |
92 ldc 3 |
251 imul |
93 imul |
261 \small |
103 \small |
262 Traverse tree in post-order \bl{$\Rightarrow$} code for |
104 Traverse tree in post-order \bl{$\Rightarrow$} code for |
263 stack-machine |
105 stack-machine |
264 |
106 |
265 \end{frame} |
107 \end{frame} |
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
267 |
109 |
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
269 \begin{frame}[t,fragile] |
111 \begin{frame}[c,fragile] |
270 \frametitle{Compiling AExps} |
112 \frametitle{Compiling AExps} |
271 |
113 |
272 \liningnums{\textbf{\Large\bl{1 + 2 + 3}}} |
114 \bl{ |
273 |
|
274 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
275 ldc 1 |
|
276 ldc 2 |
|
277 iadd |
|
278 ldc 3 |
|
279 iadd |
|
280 \end{lstlisting} |
|
281 |
|
282 |
|
283 \end{frame} |
|
284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
285 |
|
286 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
287 \begin{frame}[t,fragile] |
|
288 \frametitle{Compiling AExps} |
|
289 |
|
290 \liningnums{\textbf{\Large\bl{1 + (2 + 3)}}} |
|
291 |
|
292 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
293 ldc 1 |
|
294 ldc 2 |
|
295 ldc 3 |
|
296 iadd |
|
297 iadd |
|
298 \end{lstlisting} |
|
299 \bigskip\pause |
|
300 \vfill |
|
301 |
|
302 \textcolor{codepurple}{\textbf{\texttt{dadd}}}, |
|
303 \textcolor{codepurple}{\textbf{\texttt{fadd}}}, |
|
304 \textcolor{codepurple}{\textbf{\texttt{ladd}}}, \ldots |
|
305 |
|
306 \end{frame} |
|
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
308 |
|
309 |
|
310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
311 \begin{frame}[t] |
|
312 \frametitle{Compiling AExps} |
|
313 |
|
314 \begin{center} |
|
315 \bl{\begin{tabular}{@{}lcl@{}} |
|
316 $\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\ |
|
317 $\text{compile}(a_1 + a_2)$ & $\dn$\\ |
|
318 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\ |
|
319 $\text{compile}(a_1 - a_2)$ & $\dn$\\ |
|
320 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\ |
|
321 $\text{compile}(a_1 * a_2)$ & $\dn$\\ |
|
322 \multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\ |
|
323 \end{tabular}} |
|
324 \end{center} |
|
325 |
|
326 \end{frame} |
|
327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
328 |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 \begin{frame}[t,fragile] |
|
331 \frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}} |
|
332 |
|
333 \liningnums{\textbf{\Large\bl{1 $+$ 2 $*$ 3 $+$ (4 $-$ 3)}}} |
|
334 |
|
335 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
336 ldc 1 |
|
337 ldc 2 |
|
338 ldc 3 |
|
339 imul |
|
340 ldc 4 |
|
341 ldc 3 |
|
342 isub |
|
343 iadd |
|
344 iadd |
|
345 \end{lstlisting} |
|
346 |
|
347 \end{frame} |
|
348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
349 |
|
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
351 \begin{frame}[c] |
|
352 \frametitle{Variables} |
|
353 \liningnums{\textbf{\Large\bl{x $:=$ 5 $+$ y $*$ 2}}}\bigskip\pause |
|
354 |
|
355 \begin{itemize} |
|
356 \item lookup: \bl{$\textcolor{codepurple}{\textbf{\texttt{iload}}}\; index$} |
|
357 \item store: \bl{$\textcolor{codepurple}{\textbf{\texttt{istore}}}\; index$} |
|
358 \end{itemize}\bigskip\pause |
|
359 |
|
360 while compilating we have to maintain a map between our identifiers and the |
|
361 Java bytecode indices |
|
362 |
|
363 \begin{center} |
|
364 \bl{$\text{compile}(a, E)$} |
|
365 \end{center} |
|
366 |
|
367 \end{frame} |
|
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
369 |
|
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
371 \begin{frame}[t] |
|
372 \frametitle{Compiling AExps} |
|
373 |
|
374 \begin{center} |
|
375 \bl{\begin{tabular}{@{}lcl@{}} |
|
376 $\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\ |
|
377 $\text{compile}(a_1 + a_2, E)$ & $\dn$\\ |
|
378 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{iadd}$}\smallskip\\ |
|
379 $\text{compile}(a_1 - a_2, E)$ & $\dn$\\ |
|
380 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\ |
|
381 $\text{compile}(a_1 * a_2, E)$ & $\dn$\\ |
|
382 \multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\ |
|
383 $\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\ |
|
384 \end{tabular}} |
|
385 \end{center} |
|
386 |
|
387 \end{frame} |
|
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
389 |
|
390 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
391 \begin{frame}[c, fragile] |
|
392 \frametitle{Mathematical Functions} |
|
393 |
|
394 Compilation of some mathematical functions: |
|
395 |
|
396 \begin{center} |
115 \begin{center} |
397 \begin{tabular}{lcl} |
116 \begin{tabular}{lcl} |
398 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ |
117 $\textit{compile}(n, E)$ & $\dn$ & $\pcode{ldc}\;n$\smallskip\\ |
399 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ |
118 $\textit{compile}(a_1 + a_2, E)$ & $\dn$ \\ |
400 \texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\ |
119 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{iadd}$}\smallskip\\ |
401 \texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\ |
120 $\textit{compile}(a_1 - a_2, E)$ & $\dn$ \\ |
402 \texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\ |
121 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{isub}$}\smallskip\\ |
|
122 $\textit{compile}(a_1 * a_2, E)$ & $\dn$ \\ |
|
123 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{imul}$}\smallskip\\ |
|
124 $\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$\\ |
|
125 \multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{idiv}$}\smallskip\\ |
|
126 $\textit{compile}(x, E)$ & $\dn$ & $\pcode{iload}\;E(x)$\\ |
403 \end{tabular} |
127 \end{tabular} |
404 \end{center} |
128 \end{center}} |
405 |
129 |
406 \end{frame} |
130 \end{frame} |
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
408 |
|
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
410 \begin{frame}[c] |
|
411 \frametitle{Compiling Statements} |
|
412 |
|
413 We return a list of instructions and an environment for the |
|
414 variables |
|
415 |
|
416 \begin{center} |
|
417 \bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
|
418 $\text{compile}(\text{skip}, E)$ & $\dn$ & $(\textit{Nil}, E)$\bigskip\\ |
|
419 $\text{compile}(x := a, E)$ & $\dn$\\ |
|
420 \multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\ |
|
421 \end{tabular}} |
|
422 \end{center}\medskip |
|
423 |
|
424 where \bl{$index$} is \bl{$E(x)$} if it is already defined, |
|
425 or if it is not, then the largest index not yet seen |
|
426 |
|
427 \end{frame} |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 |
|
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
431 \begin{frame}[c,fragile] |
|
432 \frametitle{Compiling Assignments} |
|
433 |
|
434 \liningnums{\textbf{\Large\bl{x $:=$ x $+$ 1}}} |
|
435 |
|
436 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm] |
|
437 iload /*@\bl{$n_x$}@*/ |
|
438 ldc 1 |
|
439 iadd |
|
440 istore /*@\bl{$n_x$}@*/ |
|
441 \end{lstlisting}\medskip |
|
442 |
|
443 where \bl{$n_x$} is the index corresponding to the variable~\bl{$x$} |
|
444 |
|
445 \end{frame} |
|
446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
447 |
|
448 |
|
449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
450 \begin{frame}[t] |
|
451 \frametitle{Compiling Ifs} |
|
452 |
|
453 {\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip |
|
454 |
|
455 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} |
|
456 |
|
457 \begin{center} |
|
458 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
459 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
460 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
461 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
462 \node (A1) [point] {}; |
|
463 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
464 \node (A2) [point, right=of b] {}; |
|
465 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; |
|
466 \node (A3) [point, right=of cs1] {}; |
|
467 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; |
|
468 \node (A4) [point, right=of cs2] {}; |
|
469 |
|
470 \only<2>{ |
|
471 \draw (A1) edge [->, red, line width=1mm] (b); |
|
472 \draw (b) edge [->, red, line width=1mm] (cs1); |
|
473 \draw (cs1) edge [->, red, line width=1mm] (A3); |
|
474 \draw (A3) edge [->,skip loop] (A4); |
|
475 \node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};} |
|
476 \only<3>{ |
|
477 \draw (A1) edge [->, red, line width=1mm] (b); |
|
478 \draw (b) edge [->, red, line width=1mm] (A2); |
|
479 \draw (A2) edge [skip loop] (A3); |
|
480 \draw (A3) edge [->, red, line width=1mm] (cs2); |
|
481 \draw (cs2) edge [->,red, line width=1mm] (A4); |
|
482 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} |
|
483 \end{tikzpicture} |
|
484 \end{center} |
|
485 |
|
486 \end{frame} |
|
487 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
488 |
|
489 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
490 \begin{frame}[t,fragile] |
|
491 \frametitle{Conditional Jumps} |
|
492 |
|
493 \begin{minipage}{1.1\textwidth} |
|
494 \begin{itemize} |
|
495 \item \textcolor{codepurple}{\textbf{\texttt{if\_icmpeq}}} \bl{$label$} |
|
496 if two ints are equal, then jump\medskip |
|
497 \item \textcolor{codepurple}{\textbf{\texttt{if\_icmpne}}} \bl{$label$} |
|
498 if two ints aren't equal, then jump\medskip |
|
499 \item \textcolor{codepurple}{\textbf{\texttt{if\_icmpge}}} \bl{$label$} |
|
500 if one int is greater or equal then another, then jump |
|
501 \item[]\ldots |
|
502 \end{itemize} |
|
503 \end{minipage}\pause |
|
504 |
|
505 \begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=2cm] |
|
506 /*@\bl{$L_1$:}@*/ |
|
507 if_icmpeq /*@\bl{$L_2$}@*/ |
|
508 iload 1 |
|
509 ldc 1 |
|
510 iadd |
|
511 if_icmpeq /*@\bl{$L_1$}@*/ |
|
512 /*@\bl{$L_2$:}@*/ |
|
513 \end{lstlisting} |
|
514 |
|
515 |
|
516 \begin{textblock}{3.5}(11,12) |
|
517 \only<3>{labels must be unique} |
|
518 \end{textblock} |
|
519 \end{frame} |
|
520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
521 |
132 |
522 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
523 \begin{frame}[c,fragile] |
134 \begin{frame}[c,fragile] |
524 \frametitle{Compiling Ifs} |
135 \frametitle{Compiling Ifs} |
525 |
136 |
553 \end{tikzpicture} |
164 \end{tikzpicture} |
554 |
165 |
555 \end{frame} |
166 \end{frame} |
556 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
557 |
168 |
558 |
|
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
560 \begin{frame}[t] |
|
561 \frametitle{Compiling BExps} |
|
562 |
|
563 {\Large\bl{$a_1 = a_2$}} |
|
564 |
|
565 \begin{center} |
|
566 \bl{\begin{tabular}{lcl} |
|
567 $\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ |
|
568 \multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$} |
|
569 \end{tabular}} |
|
570 \end{center} |
|
571 |
|
572 \end{frame} |
|
573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
574 |
|
575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
576 \begin{frame}[c, fragile] |
|
577 \frametitle{Boolean Expressions} |
|
578 |
|
579 Compilation of boolean expressions: |
|
580 |
|
581 \begin{center} |
|
582 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
583 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
584 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
585 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
586 \node (A1) [point] {}; |
|
587 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
588 \node (A2) [point, right=of b] {}; |
|
589 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; |
|
590 \node (A3) [point, right=of cs1] {}; |
|
591 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; |
|
592 \node (A4) [point, right=of cs2] {}; |
|
593 |
|
594 \only<1>{ |
|
595 \draw (A1) edge [->, red, line width=1mm] (b); |
|
596 \draw (b) edge [->, red, line width=1mm] (A2); |
|
597 \draw (A2) edge [skip loop] (A3); |
|
598 \draw (A3) edge [->, red, line width=1mm] (cs2); |
|
599 \draw (cs2) edge [->,red, line width=1mm] (A4); |
|
600 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} |
|
601 \end{tikzpicture} |
|
602 \end{center} |
|
603 |
|
604 \begin{center} |
|
605 \begin{tabular}{lcl} |
|
606 \texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\ |
|
607 \texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\ |
|
608 \texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\ |
|
609 \texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\ |
|
610 \end{tabular} |
|
611 \end{center} |
|
612 |
|
613 \end{frame} |
|
614 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
615 |
|
616 |
|
617 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
618 \begin{frame}[t] |
|
619 \frametitle{Compiling Ifs} |
|
620 |
|
621 {\Large\bl{if $b$ then $cs_1$ else $cs_2$}} |
|
622 |
|
623 \begin{center} |
|
624 \bl{\begin{tabular}{lcl} |
|
625 $\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\ |
|
626 \multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\ |
|
627 \multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\ |
|
628 \multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\ |
|
629 \multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\ |
|
630 \multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\ |
|
631 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\ |
|
632 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\ |
|
633 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\ |
|
634 \multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\ |
|
635 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\ |
|
636 \end{tabular}} |
|
637 \end{center} |
|
638 |
|
639 \end{frame} |
|
640 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
641 |
|
642 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
643 \begin{frame}[t] |
|
644 \frametitle{Compiling Whiles} |
|
645 |
|
646 {\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip |
|
647 |
|
648 \onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:} |
|
649 |
|
650 \begin{center} |
|
651 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
652 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
653 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
654 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
655 \node (A0) [point, left=of A1] {}; |
|
656 \node (A1) [point] {}; |
|
657 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
658 \node (A2) [point, right=of b] {}; |
|
659 \node (cs1) [block, right=of A2] {code of \bl{$cs$}}; |
|
660 \node (A3) [point, right=of cs1] {}; |
|
661 \node (A4) [point, right=of A3] {}; |
|
662 |
|
663 \only<2>{ |
|
664 \draw (A0) edge [->, red, line width=1mm] (b); |
|
665 \draw (b) edge [->, red, line width=1mm] (cs1); |
|
666 \draw (cs1) edge [->, red, line width=1mm] (A3); |
|
667 \draw (A3) edge [->,skip loop] (A1);} |
|
668 \only<3>{ |
|
669 \draw (A0) edge [->, red, line width=1mm] (b); |
|
670 \draw (b) edge [->, red, line width=1mm] (A2); |
|
671 \draw (A2) edge [skip loop] (A3); |
|
672 \draw (A3) edge [->, red, line width=1mm] (A4);} |
|
673 \end{tikzpicture} |
|
674 \end{center} |
|
675 |
|
676 \end{frame} |
|
677 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
678 |
|
679 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
680 \begin{frame}[t] |
|
681 \frametitle{Compiling Whiles} |
|
682 |
|
683 {\Large\bl{while $b$ do $cs$}} |
|
684 |
|
685 \begin{center} |
|
686 \bl{\begin{tabular}{lcl} |
|
687 $\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\ |
|
688 \multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\ |
|
689 \multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\ |
|
690 \multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\ |
|
691 \multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\ |
|
692 \multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\ |
|
693 \multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\ |
|
694 \multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\ |
|
695 \multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\ |
|
696 \end{tabular}} |
|
697 \end{center} |
|
698 |
|
699 \end{frame} |
|
700 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
701 |
|
702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
703 \begin{frame}[c,fragile] |
170 \begin{frame}[c,fragile] |
704 \frametitle{Compiling Whiles} |
171 \frametitle{Compiling Whiles} |
705 |
172 |
706 For example |
173 For example |
791 \end{frame} |
257 \end{frame} |
792 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
793 |
259 |
794 |
260 |
795 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
796 \mode<presentation>{ |
262 \begin{frame}[c,fragile] |
|
263 \frametitle{Functional Programming} |
|
264 |
|
265 \footnotesize |
|
266 \begin{textblock}{13}(0.9,3) |
|
267 \begin{lstlisting}[]numbers=none] |
|
268 def fib(n) = if n == 0 then 0 |
|
269 else if n == 1 then 1 |
|
270 else fib(n - 1) + fib(n - 2); |
|
271 |
|
272 def fact(n) = if n == 0 then 1 else n * fact(n - 1); |
|
273 |
|
274 def ack(m, n) = if m == 0 then n + 1 |
|
275 else if n == 0 then ack(m - 1, 1) |
|
276 else ack(m - 1, ack(m, n - 1)); |
|
277 |
|
278 def gcd(a, b) = if b == 0 then a else gcd(b, a % b); |
|
279 \end{lstlisting} |
|
280 \end{textblock} |
|
281 |
|
282 \end{frame} |
|
283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
284 |
|
285 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
797 \begin{frame}[c] |
286 \begin{frame}[c] |
798 \frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}} |
287 \frametitle{Fun Grammar} |
|
288 \bl{ |
|
289 \begin{plstx}[rhs style=] |
|
290 : \meta{Exp} ::= \meta{Var} | \meta{Num}{\hspace{3cm}} |
|
291 | \meta{Exp} + \meta{Exp} | ... | (\meta{Exp}) |
|
292 | \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp} |
|
293 | \code{write} \meta{Exp} {\hspace{3cm}} |
|
294 | \meta{Exp} ; \meta{Exp} |
|
295 | \textit{FunName} (\meta{Exp}, ... , \meta{Exp})\\ |
|
296 : \meta{BExp} ::= ...\\ |
|
297 : \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ... , $x_n$) = \meta{Exp}\\ |
|
298 : \meta{Prog} ::= \meta{Def} ; \meta{Prog} |
|
299 | \meta{Exp} ; \meta{Prog} |
|
300 | \meta{Exp}\\ |
|
301 \end{plstx}} |
|
302 |
|
303 % Almost what is implemented - Exp ; Exp is left-recursive |
|
304 % |
|
305 \end{frame} |
|
306 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
307 |
|
308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
309 \begin{frame}[c, fragile] |
|
310 \frametitle{Abstract Syntax Trees} |
|
311 |
|
312 \footnotesize |
|
313 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] |
|
314 abstract class Exp |
|
315 abstract class BExp |
|
316 abstract class Decl |
|
317 |
|
318 case class Var(s: String) extends Exp |
|
319 case class Num(i: Int) extends Exp |
|
320 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
|
321 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
|
322 case class Write(e: Exp) extends Exp |
|
323 case class Sequ(e1: Exp, e2: Exp) extends Exp |
|
324 case class Call(name: String, args: List[Exp]) extends Exp |
|
325 |
|
326 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
|
327 |
|
328 case class Def(name: String, |
|
329 args: List[String], |
|
330 body: Exp) extends Decl |
|
331 case class Main(e: Exp) extends Decl |
|
332 \end{lstlisting} |
|
333 |
|
334 \end{frame} |
|
335 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
336 |
|
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
338 \begin{frame}[c, fragile] |
|
339 \frametitle{Idea} |
|
340 |
|
341 Compile \texttt{exp} such that the result of the expression |
|
342 is on top of the stack.\bigskip |
799 |
343 |
800 \begin{itemize} |
344 \begin{itemize} |
801 \item assembly $\Rightarrow$ byte code (class file) |
345 \item \texttt{\color{codepurple}{write}}\texttt{(1 + 2)} |
802 \item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip |
346 \item \texttt{1 + 2; 3 + 4} |
803 \item \texttt{javap} is a disassembler for class files |
|
804 \end{itemize} |
347 \end{itemize} |
805 |
348 |
806 \end{frame}} |
349 \end{frame} |
|
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
351 |
|
352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
353 \begin{frame}[c, fragile] |
|
354 \frametitle{Sequences} |
|
355 |
|
356 Compiling \texttt{exp1 ; exp2}:\bigskip |
|
357 |
|
358 |
|
359 \begin{lstlisting}[mathescape,language=JVMIS, numbers=none] |
|
360 $\textit{compile}$(exp1) |
|
361 pop |
|
362 $\textit{compile}$(exp2) |
|
363 \end{lstlisting} |
|
364 |
|
365 \end{frame} |
|
366 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
367 |
|
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
369 \begin{frame}[t, fragile] |
|
370 \frametitle{Write} |
|
371 |
|
372 Compiling call to \texttt{write(1+2)}:\bigskip |
|
373 |
|
374 |
|
375 \begin{lstlisting}[mathescape,language=JVMIS, numbers=none] |
|
376 $\textit{compile}$(1+2) |
|
377 dup |
|
378 invokestatic XXX/XXX/write(I)V |
|
379 \end{lstlisting}\bigskip |
|
380 |
|
381 \small |
|
382 needs the helper method |
|
383 |
|
384 \footnotesize |
|
385 \begin{lstlisting}[language=JVMIS, |
|
386 xleftmargin=2mm, |
|
387 numbers=none] |
|
388 .method public static write(I)V |
|
389 .limit locals 1 |
|
390 .limit stack 2 |
|
391 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
392 iload 0 |
|
393 invokevirtual java/io/PrintStream/println(I)V |
|
394 return |
|
395 .end method |
|
396 \end{lstlisting} |
|
397 \end{frame} |
|
398 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
399 |
|
400 |
|
401 |
|
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
403 \begin{frame}[t, fragile] |
|
404 \frametitle{Function Definitions} |
|
405 |
|
406 \footnotesize |
|
407 \begin{lstlisting}[language=JVMIS, |
|
408 xleftmargin=2mm, |
|
409 numbers=none] |
|
410 .method public static write(I)V |
|
411 .limit locals 1 |
|
412 .limit stack 2 |
|
413 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
414 iload 0 |
|
415 invokevirtual java/io/PrintStream/println(I)V |
|
416 return |
|
417 .end method |
|
418 \end{lstlisting}\bigskip |
|
419 |
|
420 \small We will need for definitions, like\footnotesize\medskip |
|
421 |
|
422 \begin{lstlisting}[language=JVMIS, |
|
423 xleftmargin=2mm, |
|
424 numbers=none] |
|
425 def fname (x1, ... , xn) = ... |
|
426 |
|
427 .method public static fname (I...I)I |
|
428 .limit locals ?? |
|
429 .limit stack ?? |
|
430 ?? |
|
431 .end method |
|
432 \end{lstlisting} |
|
433 |
|
434 \end{frame} |
|
435 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
436 |
|
437 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
438 \begin{frame}[c, fragile] |
|
439 \frametitle{Stack Estimation} |
|
440 \small |
|
441 \mbox{}\\[-15mm] |
|
442 |
|
443 \bl{\begin{center} |
|
444 \begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} |
|
445 $\textit{estimate}(n)$ & $\dn$ & $1$\\ |
|
446 $\textit{estimate}(x)$ & $\dn$ & $1$\\ |
|
447 $\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ & |
|
448 $\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\ |
|
449 $\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & |
|
450 $\textit{estimate}(b) +$\\ |
|
451 & & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\ |
|
452 $\textit{estimate}(\pcode{write}(e))$ & $\dn$ & |
|
453 $\textit{estimate}(e) + 1$\\ |
|
454 $\textit{estimate}(e_1 ; e_2)$ & $\dn$ & |
|
455 $max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\ |
|
456 $\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & |
|
457 $\sum_{i = 1..n}\;estimate(e_i)$\medskip\\ |
|
458 $\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ & |
|
459 $\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\ |
|
460 \end{tabular} |
|
461 \end{center}} |
|
462 |
|
463 \end{frame} |
|
464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
465 |
|
466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
467 \begin{frame}[fragile] |
|
468 \frametitle{Successor Function} |
|
469 |
|
470 \begin{textblock}{7}(1,2.5)\footnotesize |
|
471 \begin{minipage}{6cm} |
|
472 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
473 .method public static suc(I)I |
|
474 .limit locals 1 |
|
475 .limit stack 2 |
|
476 iload 0 |
|
477 ldc 1 |
|
478 iadd |
|
479 ireturn |
|
480 .end method |
|
481 \end{lstlisting} |
|
482 \end{minipage} |
|
483 \end{textblock} |
|
484 |
|
485 \begin{textblock}{7}(6,8) |
|
486 \begin{bubble}[5cm]\small |
|
487 \begin{lstlisting}[language=Lisp, |
|
488 basicstyle=\ttfamily, |
|
489 numbers=none, |
|
490 xleftmargin=1mm,linebackgroundcolor=\color{cream}] |
|
491 def suc(x) = x + 1; |
|
492 \end{lstlisting} |
|
493 \end{bubble} |
|
494 \end{textblock} |
|
495 |
|
496 \end{frame} |
|
497 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
498 |
|
499 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
500 \begin{frame}[fragile] |
|
501 \frametitle{Addition Function} |
|
502 |
|
503 \begin{textblock}{7}(1,1.9)\footnotesize |
|
504 \begin{minipage}{6cm} |
|
505 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
506 .method public static add(II)I |
|
507 .limit locals 2 |
|
508 .limit stack 5 |
|
509 iload 0 |
|
510 ldc 0 |
|
511 if_icmpne If_else |
|
512 iload 1 |
|
513 goto If_end |
|
514 If_else: |
|
515 iload 0 |
|
516 ldc 1 |
|
517 isub |
|
518 iload 1 |
|
519 invokestatic XXX/XXX/add(II)I |
|
520 invokestatic XXX/XXX/suc(I)I |
|
521 If_end: |
|
522 ireturn |
|
523 .end method |
|
524 \end{lstlisting} |
|
525 \end{minipage} |
|
526 \end{textblock} |
|
527 |
|
528 \begin{textblock}{7}(6,6.6) |
|
529 \begin{bubble}[7cm]\small |
|
530 \begin{lstlisting}[language=Lisp, |
|
531 basicstyle=\ttfamily, |
|
532 numbers=none, |
|
533 xleftmargin=1mm,linebackgroundcolor=\color{cream}] |
|
534 def add(x, y) = |
|
535 if x == 0 then y |
|
536 else suc(add(x - 1, y)); |
|
537 \end{lstlisting} |
|
538 \end{bubble} |
|
539 \end{textblock} |
|
540 |
|
541 \end{frame} |
|
542 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
543 |
|
544 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
545 \begin{frame}[c,fragile] |
|
546 \frametitle{Factorial} |
|
547 |
|
548 \begin{textblock}{7}(1,1.8)\footnotesize |
|
549 \begin{minipage}{6cm} |
|
550 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
551 .method public static facT(II)I |
|
552 .limit locals 2 |
|
553 .limit stack 6 |
|
554 iload 0 |
|
555 ldc 0 |
|
556 if_icmpne If_else_2 |
|
557 iload 1 |
|
558 goto If_end_3 |
|
559 If_else_2: |
|
560 iload 0 |
|
561 ldc 1 |
|
562 isub |
|
563 iload 0 |
|
564 iload 1 |
|
565 imul |
|
566 invokestatic fact/fact/facT(II)I |
|
567 If_end_3: |
|
568 ireturn |
|
569 .end method |
|
570 \end{lstlisting} |
|
571 \end{minipage} |
|
572 \end{textblock} |
|
573 |
|
574 \begin{textblock}{7}(6,7) |
|
575 \begin{bubble}[7cm]\small |
|
576 \begin{lstlisting}[language=Lisp, |
|
577 basicstyle=\ttfamily, |
|
578 numbers=none, |
|
579 xleftmargin=1mm,linebackgroundcolor=\color{cream}] |
|
580 def facT(n, acc) = |
|
581 if n == 0 then acc |
|
582 else facT(n - 1, n * acc); |
|
583 \end{lstlisting} |
|
584 \end{bubble} |
|
585 \end{textblock} |
|
586 |
|
587 \end{frame} |
|
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
589 |
|
590 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
591 \begin{frame}[fragile] |
|
592 |
|
593 \begin{textblock}{7}(1,-0.2)\footnotesize |
|
594 \begin{minipage}{6cm} |
|
595 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}] |
|
596 .method public static facT(II)I |
|
597 .limit locals 2 |
|
598 .limit stack 6 |
|
599 (*@\hl{facT\_Start:} @*) |
|
600 iload 0 |
|
601 ldc 0 |
|
602 if_icmpne If_else_2 |
|
603 iload 1 |
|
604 goto If_end_3 |
|
605 If_else_2: |
|
606 iload 0 |
|
607 ldc 1 |
|
608 isub |
|
609 iload 0 |
|
610 iload 1 |
|
611 imul |
|
612 (*@\hl{istore 1} @*) |
|
613 (*@\hl{istore 0} @*) |
|
614 (*@\hl{goto facT\_Start} @*) |
|
615 If_end_3: |
|
616 ireturn |
|
617 .end method |
|
618 \end{lstlisting} |
|
619 \end{minipage} |
|
620 \end{textblock} |
|
621 |
|
622 \begin{textblock}{7}(6,7) |
|
623 \begin{bubble}[7cm]\small |
|
624 \begin{lstlisting}[language=Lisp, |
|
625 basicstyle=\ttfamily, |
|
626 numbers=none, |
|
627 xleftmargin=1mm,linebackgroundcolor=\color{cream}] |
|
628 def facT(n, acc) = |
|
629 if n == 0 then acc |
|
630 else facT(n - 1, n * acc); |
|
631 \end{lstlisting} |
|
632 \end{bubble} |
|
633 \end{textblock} |
|
634 |
|
635 \end{frame} |
|
636 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
637 |
|
638 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
639 \begin{frame}[t, fragile] |
|
640 \frametitle{Tail Recursion} |
|
641 |
|
642 A call to \texttt{f(args)} is usually compiled as\medskip |
|
643 |
|
644 {\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
|
645 args onto stack |
|
646 invokestatic .../f |
|
647 \end{lstlisting}}\pause |
|
648 |
|
649 |
|
650 A call is in tail position provided:\medskip |
|
651 |
|
652 {\small\begin{itemize} |
|
653 \item \texttt{if Bexp then \hl{Exp} else \hl{Exp}} |
|
654 \item \texttt{Exp ; \hl{Exp}} |
|
655 \item \texttt{Exp op Exp} |
|
656 \end{itemize}}\medskip |
|
657 |
|
658 then a call \texttt{f(args)} can be compiled as\medskip\small |
|
659 |
|
660 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
|
661 prepare environment |
|
662 jump to start of function |
|
663 \end{lstlisting} |
|
664 |
|
665 \end{frame} |
|
666 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
667 |
|
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
669 \begin{frame}[c, fragile] |
|
670 \frametitle{Tail Recursive Call} |
|
671 \footnotesize |
|
672 |
|
673 \begin{textblock}{13}(-0.3,2) |
|
674 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
675 def compile_expT(a: Exp, env: Mem, name: String): Instrs = |
|
676 ... |
|
677 case Call(n, args) => if (name == n) |
|
678 { |
|
679 val stores = args.zipWithIndex.map |
|
680 { case (x, y) => "istore " + y.toString + "\n" } |
|
681 args.flatMap(a => compile_expT(a, env, "")) ++ |
|
682 stores.reverse ++ |
|
683 List ("goto " + n + "_Start\n") |
|
684 } |
|
685 else |
|
686 { |
|
687 val is = "I" * args.length |
|
688 args.flatMap(a => compile_expT(a, env, "")) ++ |
|
689 List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") |
|
690 } |
|
691 \end{lstlisting} |
|
692 \end{textblock} |
|
693 |
|
694 \end{frame} |
|
695 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
696 |
|
697 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
698 \begin{frame}[c] |
|
699 \frametitle{Dijkstra on Testing} |
|
700 |
|
701 \begin{bubble}[10cm] |
|
702 ``Program testing can be a very effective way to show the |
|
703 presence of bugs, but it is hopelessly inadequate for showing |
|
704 their absence.'' |
|
705 \end{bubble}\bigskip |
|
706 |
|
707 \small |
|
708 What is good about compilers: the either seem to work, |
|
709 or go horribly wrong (most of the time). |
|
710 |
|
711 \end{frame} |
|
712 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
713 |
|
714 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
715 \begin{frame}[c] |
|
716 \frametitle{\Large Proving Programs to be Correct} |
|
717 |
|
718 \begin{bubble}[10cm] |
|
719 \small |
|
720 {\bf Theorem:} There are infinitely many prime |
|
721 numbers.\medskip\\ |
|
722 |
|
723 {\bf Proof} \ldots\\ |
|
724 \end{bubble}\bigskip |
|
725 |
|
726 |
|
727 similarly\bigskip |
|
728 |
|
729 \begin{bubble}[10cm] |
|
730 \small |
|
731 {\bf Theorem:} The program is doing what |
|
732 it is supposed to be doing.\medskip |
|
733 |
|
734 {\bf Long, long proof} \ldots\\ |
|
735 \end{bubble}\bigskip\medskip |
|
736 |
|
737 \small This can be a gigantic proof. The only hope is to have |
|
738 help from the computer. `Program' is here to be understood to be |
|
739 quite general (compiler, OS, \ldots). |
|
740 |
|
741 \end{frame} |
807 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
742 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
808 |
743 |
809 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
744 |
810 \mode<presentation>{ |
745 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
811 \begin{frame}[t] |
746 |
812 \frametitle{\begin{tabular}{c}Compiled Code\end{tabular}} |
747 \begin{frame}[c] |
|
748 \frametitle{Can This Be Done?} |
|
749 |
|
750 \begin{itemize} |
|
751 \item in 2008, verification of a small C-compiler |
|
752 \begin{itemize} |
|
753 \item ``if my input program has a certain behaviour, then the compiled machine code has the same behaviour'' |
|
754 \item is as good as \texttt{gcc -O1}, but much, much less buggy |
|
755 \end{itemize} |
|
756 \end{itemize} |
813 |
757 |
814 \begin{center} |
758 \begin{center} |
815 \begin{tikzpicture} |
759 \includegraphics[scale=0.12]{../pics/compcert.png} |
816 \begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small] |
|
817 \addplot+[smooth] file {compiled.data}; |
|
818 \end{axis} |
|
819 \end{tikzpicture} |
|
820 \end{center} |
760 \end{center} |
821 |
761 |
822 \end{frame}} |
762 \end{frame} |
823 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
824 |
764 |
825 |
765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
826 |
|
827 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
828 \mode<presentation>{ |
|
829 \begin{frame}[t] |
|
830 \frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}} |
|
831 |
|
832 \begin{center} |
|
833 \begin{tikzpicture} |
|
834 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
|
835 xlabel=n, |
|
836 enlargelimits=0.05, |
|
837 ybar interval=0.7, legend style=small] |
|
838 \addplot file {interpreted2.data}; |
|
839 \addplot file {compiled2.data}; |
|
840 %\legend{interpreted, compiled} |
|
841 \end{axis} |
|
842 \end{tikzpicture} |
|
843 \end{center} |
|
844 |
|
845 \end{frame}} |
|
846 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
847 |
|
848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
849 \mode<presentation>{ |
|
850 \begin{frame}[c] |
766 \begin{frame}[c] |
851 \frametitle{Backend} |
767 \frametitle{Fuzzy Testing C-Compilers} |
852 |
|
853 \begin{center} |
|
854 \begin{tikzpicture} |
|
855 \node (rexp) {\bl{\bf Lexer}}; |
|
856 \node (nfa) [right=of rexp] {\bl{\bf Parser}}; |
|
857 \node (dfa) [right=of nfa] {\bl{\begin{tabular}{c}\bf Optimizations\end{tabular}}}; |
|
858 \path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm] |
|
859 sequence\end{tabular}} (nfa); |
|
860 \node (final) [below=of dfa] {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Byte Code\end{tabular}}}; |
|
861 \path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree |
|
862 \end{tabular}}(dfa); |
|
863 \path[->, red, line width=2mm] (dfa) edge (final); |
|
864 \end{tikzpicture}\\ |
|
865 \end{center} |
|
866 |
|
867 \end{frame}} |
|
868 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
869 |
|
870 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
871 \mode<presentation>{ |
|
872 \begin{frame}[t] |
|
873 \frametitle{\begin{tabular}{c}What is Next\end{tabular}} |
|
874 |
768 |
875 \begin{itemize} |
769 \begin{itemize} |
876 \item register spilling |
770 \item tested GCC, LLVM and others by randomly generating |
877 \item dead code removal |
771 C-programs |
878 \item loop optimisations |
772 \item found more than 300 bugs in GCC and also |
879 \item instruction selection |
773 many in LLVM (some of them highest-level critical)\bigskip |
880 \item type checking |
774 \item about CompCert: |
881 \item concurrency |
775 |
882 \item fuzzy testing |
776 \begin{bubble}[10cm]\small ``The striking thing about our CompCert |
883 \item verification\bigskip\\ |
777 results is that the middle-end bugs we found in all other |
884 |
778 compilers are absent. As of early 2011, the under-development |
885 \item GCC, LLVM, tracing JITs |
779 version of CompCert is the only compiler we have tested for |
|
780 which Csmith cannot find wrong-code errors. This is not for |
|
781 lack of trying: we have devoted about six CPU-years to the |
|
782 task.'' |
|
783 \end{bubble} |
886 \end{itemize} |
784 \end{itemize} |
887 |
785 |
888 \end{frame}} |
786 \end{frame} |
889 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
787 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
890 |
|
891 |
788 |
892 \end{document} |
789 \end{document} |
893 |
790 |
894 %%% Local Variables: |
791 %%% Local Variables: |
895 %%% mode: latex |
792 %%% mode: latex |