29 \end{tabular} |
56 \end{tabular} |
30 \end{center} |
57 \end{center} |
31 |
58 |
32 \end{frame} |
59 \end{frame} |
33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
61 |
|
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
63 \begin{frame}[c,fragile] |
|
64 \frametitle{Functional Programming} |
|
65 |
|
66 \footnotesize |
|
67 \begin{textblock}{13}(0.9,3) |
|
68 \lstset{emph={def,if,then,else},emphstyle=\color{codepurple}} |
|
69 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
|
70 def fib(n) = if n == 0 then 0 |
|
71 else if n == 1 then 1 |
|
72 else fib(n - 1) + fib(n - 2); |
|
73 |
|
74 def fact(n) = if n == 0 then 1 else n * fact(n - 1); |
|
75 |
|
76 def ack(m, n) = if m == 0 then n + 1 |
|
77 else if n == 0 then ack(m - 1, 1) |
|
78 else ack(m - 1, ack(m, n - 1)); |
|
79 |
|
80 def gcd(a, b) = if b == 0 then a else gcd(b, a % b); |
|
81 \end{lstlisting} |
|
82 \end{textblock} |
|
83 |
|
84 \end{frame} |
|
85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
86 |
|
87 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
88 \mode<presentation>{ |
|
89 \begin{frame}[c] |
|
90 |
|
91 \begin{center} |
|
92 \bl{\begin{tabular}{@{}lcl@{}} |
|
93 \textit{Exp} & $\rightarrow$ & \textit{Var} $|$ \textit{Num}\\ |
|
94 & $|$ & \textit{Exp} \texttt{+} \textit{Exp} $|$ ... $|$ ( \textit{Exp} )\\ |
|
95 & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Exp} \;\texttt{else}\; \textit{Exp}\\ |
|
96 & $|$ & \texttt{write}\;\textit{Exp}\\ |
|
97 & $|$ & \textit{Exp}\;\texttt{;}\;\textit{Exp}\\ |
|
98 & $|$ & \textit{FunName} \texttt{(}\textit{Exp},...,\textit{Exp}\texttt{)}\medskip\\ |
|
99 \textit{BExp} & $\rightarrow$ & \ldots\medskip\\ |
|
100 \textit{Decl} & $\rightarrow$ & \textit{Def} \;\texttt{;}\; \textit{Decl}\\ |
|
101 & $|$ & \textit{Exp}\medskip\\ |
|
102 \textit{Def} & |
|
103 $\rightarrow$ & \texttt{def} \textit{FunName}\texttt{(}\textit{x}$_1$,..., \textit{x}$_n$\texttt{)} \texttt{=} \textit{Exp}\\ |
|
104 \end{tabular}} |
|
105 \end{center} |
|
106 |
|
107 |
|
108 \end{frame}} |
|
109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
110 |
|
111 |
|
112 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
113 \begin{frame}[c, fragile] |
|
114 \frametitle{Abstract Syntax Tree} |
|
115 |
|
116 \footnotesize |
|
117 \begin{textblock}{13}(0.3,2) |
|
118 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
119 abstract class Exp |
|
120 abstract class BExp |
|
121 abstract class Decl |
|
122 |
|
123 case class |
|
124 Def(name: String, args: List[String], body: Exp) |
|
125 extends Decl |
|
126 case class Main(e: Exp) extends Decl |
|
127 |
|
128 case class Call(name: String, args: List[Exp]) extends Exp |
|
129 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
|
130 case class Write(e: Exp) extends Exp |
|
131 case class Var(s: String) extends Exp |
|
132 case class Num(i: Int) extends Exp |
|
133 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
|
134 case class Sequ(e1: Exp, e2: Exp) extends Exp |
|
135 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
|
136 \end{lstlisting} |
|
137 \end{textblock} |
|
138 |
|
139 \end{frame} |
|
140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
141 |
|
142 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
143 \begin{frame}[c, fragile] |
|
144 \frametitle{Mathematical Functions} |
|
145 |
|
146 Compilation of some mathematical functions: |
|
147 |
|
148 \begin{center} |
|
149 \begin{tabular}{lcl} |
|
150 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ |
|
151 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ |
|
152 \texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\ |
|
153 \texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\ |
|
154 \texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\ |
|
155 \end{tabular} |
|
156 \end{center} |
|
157 |
|
158 \end{frame} |
|
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
160 |
|
161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
162 \begin{frame}[c, fragile] |
|
163 \frametitle{Boolean Expressions} |
|
164 |
|
165 Compilation of boolean expressions: |
|
166 |
|
167 \begin{center} |
|
168 \begin{tikzpicture}[node distance=2mm and 4mm, |
|
169 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
|
170 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
|
171 skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] |
|
172 \node (A1) [point] {}; |
|
173 \node (b) [block, right=of A1] {code of \bl{$b$}}; |
|
174 \node (A2) [point, right=of b] {}; |
|
175 \node (cs1) [block, right=of A2] {code of \bl{$cs_1$}}; |
|
176 \node (A3) [point, right=of cs1] {}; |
|
177 \node (cs2) [block, right=of A3] {code of \bl{$cs_2$}}; |
|
178 \node (A4) [point, right=of cs2] {}; |
|
179 |
|
180 \only<1>{ |
|
181 \draw (A1) edge [->, red, line width=1mm] (b); |
|
182 \draw (b) edge [->, red, line width=1mm] (A2); |
|
183 \draw (A2) edge [skip loop] (A3); |
|
184 \draw (A3) edge [->, red, line width=1mm] (cs2); |
|
185 \draw (cs2) edge [->,red, line width=1mm] (A4); |
|
186 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};} |
|
187 \end{tikzpicture} |
|
188 \end{center} |
|
189 |
|
190 \begin{center} |
|
191 \begin{tabular}{lcl} |
|
192 \texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\ |
|
193 \texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\ |
|
194 \texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\ |
|
195 \texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\ |
|
196 \end{tabular} |
|
197 \end{center} |
|
198 |
|
199 \end{frame} |
|
200 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
201 |
|
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
203 \begin{frame}[t, fragile] |
|
204 \frametitle{Sequences} |
|
205 |
|
206 Compiling \texttt{arg1 ; arg2}: |
|
207 |
|
208 |
|
209 \begin{textblock}{7}(2,5)\footnotesize |
|
210 \begin{minipage}{6cm} |
|
211 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
212 ...arg1... |
|
213 pop |
|
214 ...arg1... |
|
215 \end{lstlisting} |
|
216 \end{minipage} |
|
217 \end{textblock} |
|
218 |
|
219 |
|
220 \end{frame} |
|
221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
222 |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 \begin{frame}[t, fragile] |
|
225 \frametitle{Write} |
|
226 |
|
227 Compiling \texttt{write(arg)}: |
|
228 |
|
229 |
|
230 \begin{textblock}{7}(2,4)\footnotesize |
|
231 \begin{minipage}{6cm} |
|
232 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
233 ...arg... |
|
234 dup |
|
235 invokestatic XXX/XXX/write(I)V |
|
236 \end{lstlisting} |
|
237 \end{minipage} |
|
238 \end{textblock} |
|
239 |
|
240 |
|
241 |
|
242 \begin{textblock}{7}(2,8)\footnotesize |
|
243 \begin{minipage}{6cm} |
|
244 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
245 case Write(a1) => { |
|
246 compile_exp(a1, env) ++ |
|
247 List("dup\n", |
|
248 "invokestatic XXX/XXX/write(I)V\n") |
|
249 } |
|
250 \end{lstlisting} |
|
251 \end{minipage} |
|
252 \end{textblock} |
|
253 |
|
254 \end{frame} |
|
255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
256 |
|
257 |
|
258 |
|
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
260 \begin{frame}[c, fragile] |
|
261 \frametitle{Functions} |
|
262 |
|
263 \begin{textblock}{7}(1,2)\footnotesize |
|
264 \begin{minipage}{6cm} |
|
265 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
266 .method public static write(I)V |
|
267 .limit locals 5 |
|
268 .limit stack 5 |
|
269 iload 0 |
|
270 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
271 swap |
|
272 invokevirtual java/io/PrintStream/println(I)V |
|
273 return |
|
274 .end method |
|
275 \end{lstlisting} |
|
276 \end{minipage} |
|
277 \end{textblock} |
|
278 |
|
279 |
|
280 \begin{textblock}{10}(1,9.8) |
|
281 \small We will need for definitions\\[-8mm]\mbox{}\footnotesize |
|
282 \begin{center} |
|
283 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
284 .method public static f (I...I)I |
|
285 .limit locals ?? |
|
286 .limit stack ?? |
|
287 ?? |
|
288 .end method |
|
289 \end{lstlisting} |
|
290 \end{center} |
|
291 \end{textblock} |
|
292 |
|
293 \end{frame} |
|
294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
295 |
|
296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
297 \begin{frame}[c, fragile] |
|
298 \frametitle{Stack Estimation} |
|
299 \footnotesize |
|
300 \begin{center} |
|
301 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
302 def max_stack_exp(e: Exp): Int = e match { |
|
303 case Call(_, args) => args.map(max_stack_exp).sum |
|
304 case If(a, e1, e2) => max_stack_bexp(a) + |
|
305 (List(max_stack_exp(e1), max_stack_exp(e1)).max) |
|
306 case Write(e) => max_stack_exp(e) + 1 |
|
307 case Var(_) => 1 |
|
308 case Num(_) => 1 |
|
309 case Aop(_, a1, a2) => |
|
310 max_stack_exp(a1) + max_stack_exp(a2) |
|
311 case Sequ(e1, e2) => |
|
312 List(max_stack_exp(e1), max_stack_exp(e2)).max |
|
313 } |
|
314 |
|
315 def max_stack_bexp(e: BExp): Int = e match { |
|
316 case Bop(_, a1, a2) => |
|
317 max_stack_exp(a1) + max_stack_exp(a2) |
|
318 } |
|
319 \end{lstlisting} |
|
320 \end{center} |
|
321 |
|
322 \end{frame} |
|
323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
324 |
|
325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
326 \begin{frame}[fragile] |
|
327 \frametitle{Successor} |
|
328 |
|
329 \begin{textblock}{7}(1,2.5)\footnotesize |
|
330 \begin{minipage}{6cm} |
|
331 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
332 .method public static suc(I)I |
|
333 .limit locals 1 |
|
334 .limit stack |
|
335 iload 0 |
|
336 ldc 1 |
|
337 iadd |
|
338 ireturn |
|
339 .end method |
|
340 \end{lstlisting} |
|
341 \end{minipage} |
|
342 \end{textblock} |
|
343 |
|
344 \begin{textblock}{7}(6,8) |
|
345 \begin{bubble}[5cm]\small |
|
346 \begin{lstlisting}[language=Lisp, |
|
347 basicstyle=\ttfamily, |
|
348 numbers=none, |
|
349 xleftmargin=1mm] |
|
350 def suc(x) = x + 1; |
|
351 \end{lstlisting} |
|
352 \end{bubble} |
|
353 \end{textblock} |
|
354 |
|
355 \end{frame} |
|
356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
357 |
|
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
359 \begin{frame}[fragile] |
|
360 \frametitle{Addition} |
|
361 |
|
362 \begin{textblock}{7}(1,1.5)\footnotesize |
|
363 \begin{minipage}{6cm} |
|
364 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
365 .method public static add(II)I |
|
366 .limit locals 2 |
|
367 .limit stack 4 |
|
368 iload 0 |
|
369 ldc 0 |
|
370 if_icmpne If_else_2 |
|
371 iload 1 |
|
372 goto If_end_3 |
|
373 If_else_2: |
|
374 iload 0 |
|
375 ldc 1 |
|
376 isub |
|
377 iload 1 |
|
378 invokestatic defs/defs/add(II)I |
|
379 invokestatic defs/defs/suc(I)I |
|
380 If_end_3: |
|
381 ireturn |
|
382 .end method |
|
383 \end{lstlisting} |
|
384 \end{minipage} |
|
385 \end{textblock} |
|
386 |
|
387 \begin{textblock}{7}(6,6.2) |
|
388 \begin{bubble}[7cm]\small |
|
389 \begin{lstlisting}[language=Lisp, |
|
390 basicstyle=\ttfamily, |
|
391 numbers=none, |
|
392 xleftmargin=1mm] |
|
393 def add(x, y) = |
|
394 if x == 0 then y |
|
395 else suc(add(x - 1, y)); |
|
396 \end{lstlisting} |
|
397 \end{bubble} |
|
398 \end{textblock} |
|
399 |
|
400 \end{frame} |
|
401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
402 |
|
403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
404 \begin{frame}[fragile] |
|
405 \frametitle{Factorial} |
|
406 |
|
407 \begin{textblock}{7}(1,1.5)\footnotesize |
|
408 \begin{minipage}{6cm} |
|
409 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
410 .method public static facT(II)I |
|
411 .limit locals 2 |
|
412 .limit stack 4 |
|
413 iload 0 |
|
414 ldc 0 |
|
415 if_icmpne If_else_2 |
|
416 iload 1 |
|
417 goto If_end_3 |
|
418 If_else_2: |
|
419 iload 0 |
|
420 ldc 1 |
|
421 isub |
|
422 iload 0 |
|
423 iload 1 |
|
424 imul |
|
425 invokestatic fact/fact/facT(II)I |
|
426 If_end_3: |
|
427 ireturn |
|
428 .end method |
|
429 \end{lstlisting} |
|
430 \end{minipage} |
|
431 \end{textblock} |
|
432 |
|
433 \begin{textblock}{7}(6,7) |
|
434 \begin{bubble}[7cm]\small |
|
435 \begin{lstlisting}[language=Lisp, |
|
436 basicstyle=\ttfamily, |
|
437 numbers=none, |
|
438 xleftmargin=1mm] |
|
439 def facT(n, acc) = |
|
440 if n == 0 then acc |
|
441 else facT(n - 1, n * acc); |
|
442 \end{lstlisting} |
|
443 \end{bubble} |
|
444 \end{textblock} |
|
445 |
|
446 \end{frame} |
|
447 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
448 |
|
449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
450 \begin{frame}[fragile] |
|
451 |
|
452 \begin{textblock}{7}(1,-0.2)\footnotesize |
|
453 \begin{minipage}{6cm} |
|
454 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}] |
|
455 .method public static facT(II)I |
|
456 .limit locals 2 |
|
457 .limit stack 4 |
|
458 (*@\hl{facT\_Start:} @*) |
|
459 iload 0 |
|
460 ldc 0 |
|
461 if_icmpne If_else_2 |
|
462 iload 1 |
|
463 goto If_end_3 |
|
464 If_else_2: |
|
465 iload 0 |
|
466 ldc 1 |
|
467 isub |
|
468 iload 0 |
|
469 iload 1 |
|
470 imul |
|
471 (*@\hl{istore 1} @*) |
|
472 (*@\hl{istore 0} @*) |
|
473 (*@\hl{goto facT\_Start} @*) |
|
474 If_end_3: |
|
475 ireturn |
|
476 .end method |
|
477 \end{lstlisting} |
|
478 \end{minipage} |
|
479 \end{textblock} |
|
480 |
|
481 \begin{textblock}{7}(6,7) |
|
482 \begin{bubble}[7cm]\small |
|
483 \begin{lstlisting}[language=Lisp, |
|
484 basicstyle=\ttfamily, |
|
485 numbers=none, |
|
486 xleftmargin=1mm] |
|
487 def facT(n, acc) = |
|
488 if n == 0 then acc |
|
489 else facT(n - 1, n * acc); |
|
490 \end{lstlisting} |
|
491 \end{bubble} |
|
492 \end{textblock} |
|
493 |
|
494 \end{frame} |
|
495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
496 |
|
497 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
498 \begin{frame}[c, fragile] |
|
499 \frametitle{Tail Recursion} |
|
500 |
|
501 A call to \texttt{f(args)} is usually compiled as\medskip |
|
502 |
|
503 {\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
|
504 args onto stack |
|
505 invokestatic .../f |
|
506 \end{lstlisting}}\pause |
|
507 |
|
508 |
|
509 A call is in tail position provided:\medskip |
|
510 |
|
511 {\small\begin{itemize} |
|
512 \item \texttt{if Bexp then \hl{Exp} else \hl{Exp}} |
|
513 \item \texttt{Exp ; \hl{Exp}} |
|
514 \item \texttt{Exp op Exp} |
|
515 \end{itemize}}\medskip |
|
516 |
|
517 then a call \texttt{f(args)} can be compiled as\medskip\small |
|
518 |
|
519 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none] |
|
520 prepare environment |
|
521 jump to start of function |
|
522 \end{lstlisting} |
|
523 |
|
524 \end{frame} |
|
525 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
526 |
|
527 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
528 \begin{frame}[c, fragile] |
|
529 \frametitle{Tail Recursive Call} |
|
530 \footnotesize |
|
531 |
|
532 \begin{textblock}{13}(-0.3,2) |
|
533 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
534 def compile_expT(a: Exp, env: Mem, name: String): Instrs = |
|
535 ... |
|
536 case Call(n, args) => if (name == n) |
|
537 { |
|
538 val stores = args.zipWithIndex.map |
|
539 { case (x, y) => "istore " + y.toString + "\n" } |
|
540 args.flatMap(a => compile_expT(a, env, "")) ++ |
|
541 stores.reverse ++ |
|
542 List ("goto " + n + "_Start\n") |
|
543 } |
|
544 else |
|
545 { |
|
546 val is = "I" * args.length |
|
547 args.flatMap(a => compile_expT(a, env, "")) ++ |
|
548 List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n") |
|
549 } |
|
550 \end{lstlisting} |
|
551 \end{textblock} |
|
552 |
|
553 \end{frame} |
|
554 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
34 |
555 |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
556 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
36 \mode<presentation>{ |
557 \mode<presentation>{ |
37 \begin{frame}[c] |
558 \begin{frame}[c] |
38 |
559 |
197 |
718 |
198 \end{frame}} |
719 \end{frame}} |
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
720 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
200 |
721 |
201 |
722 |
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
203 \mode<presentation>{ |
|
204 \begin{frame}[c] |
|
205 \frametitle{Our Compiler} |
|
206 |
|
207 \begin{center} |
|
208 \begin{tikzpicture}[scale=1] |
|
209 |
|
210 \node (0) at (-2.3,0) {}; |
|
211 |
|
212 \node (A) at (0,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; |
|
213 \node [below right] at (A.north west) {lexer}; |
|
214 |
|
215 \node (B) at (3,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; |
|
216 \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; |
|
217 |
|
218 \node (C) at (6,0) [draw=black, rectangle, very thick, minimum height=18mm, minimum width=20mm] {}; |
|
219 \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; |
|
220 |
|
221 \node (1) at (8.4,0) {}; |
|
222 |
|
223 \draw [->,line width=4mm] (0) -- (A); |
|
224 \draw [->,line width=4mm] (A) -- (B); |
|
225 \draw [->,line width=4mm] (B) -- (C); |
|
226 \draw [->,line width=4mm] (C) -- (1); |
|
227 \end{tikzpicture} |
|
228 \end{center} |
|
229 |
|
230 lexer input: string\medskip\\ |
|
231 lexer output: sequence of tokens\\ |
|
232 \mbox{}\hfill(white space and comments filtered out)\medskip\\ |
|
233 parser output: abstract syntax tree\medskip\\ |
|
234 code gen output: assembler byte code / \\ |
|
235 \mbox{}\hfill assembler machine code |
|
236 \end{frame}} |
|
237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
238 |
|
239 |
|
240 |
|
241 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
242 \mode<presentation>{ |
|
243 \begin{frame}[c] |
|
244 \frametitle{\begin{tabular}{c}For-Loops\end{tabular}} |
|
245 |
|
246 |
|
247 \begin{center}\Large |
|
248 \texttt{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \texttt{upto} \;\textit{AExp}\; \texttt{do} \textit{Block} |
|
249 \end{center}\bigskip |
|
250 |
|
251 \begin{center} |
|
252 \begin{minipage}{8cm} |
|
253 \begin{tabular}{l} |
|
254 \texttt{for i := 2 upto 4 do \{}\\ |
|
255 \hspace{5mm}\texttt{write i}\\ |
|
256 \texttt{\}}\ |
|
257 \end{tabular} |
|
258 \end{minipage} |
|
259 \end{center} |
|
260 \end{frame}} |
|
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
262 |
|
263 |
|
264 |
|
265 |
|
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
267 \mode<presentation>{ |
|
268 \begin{frame}[c] |
|
269 \frametitle{\begin{tabular}{c}While-Language\end{tabular}} |
|
270 |
|
271 |
|
272 \begin{center} |
|
273 \bl{\begin{tabular}{@{}lcl@{}} |
|
274 $Stmt$ & $\rightarrow$ & $\text{skip}$\\ |
|
275 & $|$ & $Id := AExp$\\ |
|
276 & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ |
|
277 & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\\ |
|
278 & $|$ & $\alert{\text{write}\; Id}$\\ |
|
279 & $|$ & $\alert{\text{read}\; Id}$\medskip\\ |
|
280 $Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ |
|
281 & $|$ & $Stmt$\medskip\\ |
|
282 $Block$ & $\rightarrow$ & $\{ Stmts \}$\\ |
|
283 & $|$ & $Stmt$\medskip\\ |
|
284 $AExp$ & $\rightarrow$ & \ldots\\ |
|
285 $BExp$ & $\rightarrow$ & \ldots\\ |
|
286 \end{tabular}} |
|
287 \end{center} |
|
288 |
|
289 |
|
290 \end{frame}} |
|
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
292 |
|
293 |
|
294 |
|
295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
296 \mode<presentation>{ |
|
297 \begin{frame}[c] |
|
298 \frametitle{\begin{tabular}{c}Interpreter\end{tabular}} |
|
299 |
|
300 \begin{center} |
|
301 \bl{\begin{tabular}{@{}lcl@{}} |
|
302 $\text{eval}(n, E)$ & $\dn$ & $n$\\ |
|
303 $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\ |
|
304 $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\ |
|
305 $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\ |
|
306 $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\ |
|
307 $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\ |
|
308 $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\ |
|
309 $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\ |
|
310 \end{tabular}} |
|
311 \end{center} |
|
312 |
|
313 \end{frame}} |
|
314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
315 |
|
316 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
317 \mode<presentation>{ |
|
318 \begin{frame}[c] |
|
319 \frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}} |
|
320 |
|
321 \begin{center} |
|
322 \bl{\begin{tabular}{@{}lcl@{}} |
|
323 $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\ |
|
324 $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\ |
|
325 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\ |
|
326 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\; |
|
327 \text{eval}(cs_1,E)$}\\ |
|
328 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\ |
|
329 \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\ |
|
330 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\ |
|
331 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\; |
|
332 \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\ |
|
333 \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\ |
|
334 $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\ |
|
335 \end{tabular}} |
|
336 \end{center} |
|
337 |
|
338 \end{frame}} |
|
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
340 |
|
341 |
|
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
343 \mode<presentation>{ |
|
344 \begin{frame}[t] |
|
345 \frametitle{\begin{tabular}{c}Compiling Writes\end{tabular}} |
|
346 |
|
347 {\Large\bl{write $x$}} |
|
348 |
|
349 \begin{center} |
|
350 \small\bl{\begin{tabular}{l} |
|
351 .method public static write(I)V\hspace{1cm}\textcolor{black}{(library function)}\\ |
|
352 \;\; .limit locals 5 \\ |
|
353 \;\; .limit stack 5 \\ |
|
354 \;\; iload 0 \\ |
|
355 \;\; getstatic java/lang/System/out Ljava/io/PrintStream;\\ |
|
356 \;\; swap \\ |
|
357 \;\; invokevirtual java/io/PrintStream/println(I)V \\ |
|
358 \;\; return \\ |
|
359 .end method\bigskip\bigskip\\ |
|
360 % |
|
361 \normalsize |
|
362 iload $E(x)$\\ |
|
363 invokestatic write(I)V\\ |
|
364 \end{tabular}} |
|
365 \end{center} |
|
366 |
|
367 \end{frame}} |
|
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
369 |
|
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
371 \mode<presentation>{ |
|
372 \begin{frame}[c] |
|
373 |
|
374 \begin{center} |
|
375 \small\bl{\begin{tabular}{l} |
|
376 .class public XXX.XXX\\ |
|
377 .super java/lang/Object\\ |
|
378 \\ |
|
379 .method public <init>()V\\ |
|
380 \;\; aload\_0\\ |
|
381 \;\; invokenonvirtual java/lang/Object/<init>()V\\ |
|
382 \;\; return\\ |
|
383 .end method\\ |
|
384 \\ |
|
385 .method public static main([Ljava/lang/String;)V\\ |
|
386 \;\; .limit locals 200\\ |
|
387 \;\; .limit stack 200\\ |
|
388 \\ |
|
389 \textcolor{black}{(here comes the compiled code)}\\ |
|
390 \\ |
|
391 \;\; return\\ |
|
392 .end method\\ |
|
393 \end{tabular}} |
|
394 \end{center} |
|
395 |
|
396 \end{frame}} |
|
397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
398 |
723 |
399 \end{document} |
724 \end{document} |
400 |
725 |
401 %%% Local Variables: |
726 %%% Local Variables: |
402 %%% mode: latex |
727 %%% mode: latex |