38 \end{frame} |
38 \end{frame} |
39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
40 |
40 |
41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
42 \begin{frame}[c,fragile] |
42 \begin{frame}[c,fragile] |
43 \frametitle{Functional Programming} |
43 \frametitle{The Fun Language} |
44 |
44 |
45 \footnotesize |
45 \footnotesize |
46 \begin{textblock}{13}(0.9,3) |
46 \begin{textblock}{13}(0.9,3) |
47 \begin{lstlisting}[]numbers=none] |
47 \begin{lstlisting}[]numbers=none] |
48 def fib(n) = if n == 0 then 0 |
48 def fib(n) = if n == 0 then 0 |
62 \end{frame} |
62 \end{frame} |
63 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
63 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
64 |
64 |
65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
66 \begin{frame}[c,fragile] |
66 \begin{frame}[c,fragile] |
67 \frametitle{Factorial on the JVM} |
67 \frametitle{Factorial Funct.~on the JVM} |
68 |
68 |
69 \begin{textblock}{7}(1,1.8)\footnotesize |
69 \begin{textblock}{7}(1,1.8)\footnotesize |
70 \begin{minipage}{6cm} |
70 \begin{minipage}{6cm} |
71 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
71 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
72 .method public static facT(II)I |
72 .method public static facT(II)I |
226 \end{frame} |
226 \end{frame} |
227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
228 |
228 |
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
230 \begin{frame}[fragile,c] |
230 \begin{frame}[fragile,c] |
231 \frametitle{LLVM Instructions} |
231 \frametitle{LLVM-IR Instructions} |
232 \small |
232 \small |
233 |
233 |
234 \begin{lstlisting}[language=LLVM] |
234 \begin{lstlisting}[language=LLVM,xleftmargin=0mm] |
235 br i1 %var, label %if_br, label %else_br |
235 br i1 %var, label %if_br, label %else_br |
236 |
236 |
237 icmp eq i32 %x, %y ; for equal |
237 icmp eq i32 %x, %y ; for equal |
238 icmp sle i32 %x, %y ; signed less or equal |
238 icmp sle i32 %x, %y ; signed less or equal |
239 icmp slt i32 %x, %y ; signed less than |
239 icmp slt i32 %x, %y ; signed less than |
250 \frametitle{SSA Format} |
250 \frametitle{SSA Format} |
251 |
251 |
252 \bl{$(1 + a) + (3 + (b * 5))$}\bigskip\bigskip |
252 \bl{$(1 + a) + (3 + (b * 5))$}\bigskip\bigskip |
253 |
253 |
254 \begin{lstlisting}[language=LLVM] |
254 \begin{lstlisting}[language=LLVM] |
255 let tmp0 = add 1 a in |
255 tmp0 = add 1 a |
256 let tmp1 = mul b 5 in |
256 tmp1 = mul b 5 |
257 let tmp2 = add 3 tmp1 in |
257 tmp2 = add 3 tmp1 |
258 let tmp3 = add tmp0 tmp2 in |
258 tmp3 = add tmp0 tmp2 |
259 tmp3 |
259 \end{lstlisting}\bigskip\bigskip |
260 \end{lstlisting} |
260 |
|
261 \hfill Static Single Assignment |
261 |
262 |
262 \end{frame} |
263 \end{frame} |
263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
264 |
265 |
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
292 |
293 |
293 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm] |
294 \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm] |
294 abstract class KExp |
295 abstract class KExp |
295 abstract class KVal |
296 abstract class KVal |
296 |
297 |
|
298 // K-Values |
297 case class KVar(s: String) extends KVal |
299 case class KVar(s: String) extends KVal |
298 case class KNum(i: Int) extends KVal |
300 case class KNum(i: Int) extends KVal |
299 case class Kop(o: String, v1: KVal, v2: KVal) extends KVal |
301 case class Kop(o: String, v1: KVal, v2: KVal) extends KVal |
300 case class KCall(o: String, vrs: List[KVal]) extends KVal |
302 case class KCall(o: String, vrs: List[KVal]) extends KVal |
301 case class KWrite(v: KVal) extends KVal |
303 case class KWrite(v: KVal) extends KVal |
302 |
304 |
|
305 // K-Expressions |
303 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp |
306 case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp |
304 case class KLet(x: String, v: KVal, e: KExp) extends KExp |
307 case class KLet(x: String, v: KVal, e: KExp) extends KExp |
305 case class KReturn(v: KVal) extends KExp |
308 case class KReturn(v: KVal) extends KExp |
306 \end{lstlisting} |
309 \end{lstlisting} |
307 |
310 |
316 \begin{lstlisting}[language=Scala,numbers=none] |
319 \begin{lstlisting}[language=Scala,numbers=none] |
317 def CPS(e: Exp)(k: KVal => KExp) : KExp = |
320 def CPS(e: Exp)(k: KVal => KExp) : KExp = |
318 e match { ... } |
321 e match { ... } |
319 \end{lstlisting} |
322 \end{lstlisting} |
320 \bigskip\bigskip |
323 \bigskip\bigskip |
|
324 |
|
325 the continuation \texttt{k} can be thought of:\medskip |
321 |
326 |
322 \small |
327 \small |
323 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
328 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
324 let tmp0 = add 1 a in |
329 let tmp0 = add 1 a in |
325 let tmp1 = mul (*@$\Box$@*) 5 in |
330 let tmp1 = mul (*@$\Box$@*) 5 in |
371 CPS(e2)(y2 => |
376 CPS(e2)(y2 => |
372 KLet(z, Kop(o, y1, y2), k(KVar(z))))) |
377 KLet(z, Kop(o, y1, y2), k(KVar(z))))) |
373 } ... |
378 } ... |
374 } |
379 } |
375 \end{lstlisting} |
380 \end{lstlisting} |
376 |
381 \mbox{}\\[-8mm]% |
377 \small |
382 % |
378 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
383 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
379 ... |
384 ... |
380 let z = op (*@$\Box_{y_1}$@*) (*@$\Box_{y_2}$@*) |
385 let z = op (*@$\Box_{y_1}$@*) (*@$\Box_{y_2}$@*) |
381 let tmp0 = add 1 a in |
386 let tmp0 = add 1 a in |
382 let tmp1 = mul (*@$\Box\!\!\!\!\raisebox{0.6mm}{\texttt{z}}$@*) 5 in |
387 let tmp1 = mul (*@$\Box\!\!\!\!\raisebox{0.6mm}{\alert{\texttt{z}}}$@*) 5 in |
383 let tmp2 = add 3 tmp1 in |
388 let tmp2 = add 3 tmp1 in |
384 let tmp3 = add tmp0 tmp2 in |
389 let tmp3 = add tmp0 tmp2 in |
385 KReturn tmp3 |
390 KReturn tmp3 |
386 \end{lstlisting} |
391 \end{lstlisting} |
387 |
392 |
399 case Sequence(e1, e2) => |
404 case Sequence(e1, e2) => |
400 CPS(e1)(_ => CPS(e2)(y2 => k(y2))) |
405 CPS(e1)(_ => CPS(e2)(y2 => k(y2))) |
401 ... |
406 ... |
402 } |
407 } |
403 \end{lstlisting} |
408 \end{lstlisting} |
404 \bigskip\bigskip |
409 \bigskip |
405 |
|
406 \small |
|
407 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
|
408 let tmp0 = add 1 a in |
|
409 let tmp1 = mul (*@$\Box$@*) 5 in |
|
410 let tmp2 = add 3 tmp1 in |
|
411 let tmp3 = add tmp0 tmp2 in |
|
412 KReturn tmp3 |
|
413 \end{lstlisting} |
|
414 |
|
415 \end{frame} |
|
416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
417 |
|
418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
419 \begin{frame}[fragile,c] |
|
420 \frametitle{CPS-Translation} |
|
421 \small |
|
422 |
|
423 \begin{lstlisting}[language=Scala,numbers=none] |
|
424 def CPS(e: Exp)(k: KVal => KExp) : KExp = |
|
425 e match { |
|
426 ... |
|
427 case Sequence(e1, e2) => |
|
428 CPS(e1)(_ => CPS(e2)(y2 => k(y2))) |
|
429 ... |
|
430 } |
|
431 \end{lstlisting} |
|
432 \bigskip\bigskip |
|
433 |
410 |
434 \small |
411 \small |
435 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
412 \begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}] |
436 let tmp0 = add 1 a in |
413 let tmp0 = add 1 a in |
437 let tmp1 = mul (*@$\Box$@*) 5 in |
414 let tmp1 = mul (*@$\Box$@*) 5 in |
464 \end{lstlisting} |
441 \end{lstlisting} |
465 |
442 |
466 \end{frame} |
443 \end{frame} |
467 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
468 |
445 |
|
446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
447 \begin{frame}[c,fragile] |
|
448 \frametitle{The Basic Language, 1980+} |
|
449 |
|
450 \begin{lstlisting}[language={[Visual]Basic},numbers=none] |
|
451 5 LET S = 0 |
|
452 10 INPUT V |
|
453 20 PRINT "Input number" |
|
454 30 IF N = 0 THEN GOTO 99 |
|
455 40 FOR I = 1 TO N |
|
456 45 LET S = S + V(I) |
|
457 50 NEXT I |
|
458 60 PRINT S/N |
|
459 70 GOTO 5 |
|
460 99 END |
|
461 \end{lstlisting} |
|
462 |
|
463 \hfill ``Spaghetti Code'' |
|
464 \end{frame} |
|
465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
466 |
|
467 |
|
468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
469 \begin{frame}[c,fragile] |
|
470 \frametitle{Target Specific ASM} |
|
471 |
|
472 \begin{lstlisting}[language={},numbers=none] |
|
473 llc -march=x86-64 fact.ll |
|
474 llc -march=arm fact.ll |
|
475 |
|
476 |
|
477 Intel: xorl %eax, %eax |
|
478 ARM: mov pc, lr |
|
479 \end{lstlisting} |
|
480 |
|
481 \end{frame} |
|
482 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
469 |
483 |
470 |
484 |
471 |
485 |
472 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
473 \begin{frame}[c] |
487 \begin{frame}[c] |