# HG changeset patch # User Christian Urban # Date 1638553511 0 # Node ID 568671822d52f44f2a02ea957bae00fe812711cd # Parent 8706b846a3e08d3e1aa6ed8b6b0fff01971cb4bd updated diff -r 8706b846a3e0 -r 568671822d52 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 8706b846a3e0 -r 568671822d52 cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r 8706b846a3e0 -r 568671822d52 cws/cw05.tex --- a/cws/cw05.tex Tue Nov 30 10:16:47 2021 +0000 +++ b/cws/cw05.tex Fri Dec 03 17:45:11 2021 +0000 @@ -25,11 +25,19 @@ You can do the implementation of your compiler in any programming language you like, but you need to submit the source code with which you generated the LLVM-IR files, otherwise a mark of 0\% will be -awarded. You should use the lexer and parser from the previous -courseworks, but you need to make some modifications to them for the -`typed' fun-language. I will award up to 5\% if a lexer and a parser are -correctly implemented. At the end, please package everything(!) in a zip-file -that creates a directory with the name \texttt{YournameYourFamilyname} +awarded. You are asked to submit the code of your compiler, but also +the generated \texttt{.ll} files. You should use the lexer and parser +from the previous courseworks, but you need to make some modifications +to them for the `typed' fun-language. I will award up to 5\% if a +lexer and a parser are correctly implemented. At the end, please +package everything(!) in a zip-file that creates a directory with the +name + +\begin{center} +\texttt{YournameYourFamilyname} +\end{center} + +\noindent on my end. \subsection*{Disclaimer\alert} @@ -43,18 +51,18 @@ \subsection*{Task} -The goal is to lex and parse the Mandelbrot program shown in -Figure~\ref{mand} and generate corresponding code for the -LLVM-IR. Unfortunately the calculations for the Mandelbrot set require -floating point arithmetic and therefore we cannot be as simple-minded -about types as we have been so far (remember the LLVM-IR is a -fully-typed language and needs to know the exact types of each -expression). The idea is to deal appropriately with three types, -namely \texttt{Int}, \texttt{Double} and \texttt{Void} (they are -represented in the LLVM-IR as \texttt{i32}, \texttt{double} and -\texttt{void}). You need to extend the lexer and parser accordingly in -order to deal with type annotations. The Fun-language includes global -constants, such as +The main goal is to lex and parse 4 Fun-programs, including the +Mandelbrot program shown in Figure~\ref{mand}, and generate +corresponding code for the LLVM-IR. Unfortunately the calculations for +the Mandelbrot Set require floating point arithmetic and therefore we +cannot be as simple-minded about types as we have been so far +(remember the LLVM-IR is a fully-typed language and needs to know the +exact types of each expression). The idea is to deal appropriately +with three types, namely \texttt{Int}, \texttt{Double} and +\texttt{Void} (they are represented in the LLVM-IR as \texttt{i32}, +\texttt{double} and \texttt{void}). You need to extend the lexer and +parser accordingly in order to deal with type annotations. The +Fun-language includes global constants, such as \begin{lstlisting}[numbers=none] val Ymin: Double = -1.3; @@ -70,12 +78,13 @@ \begin{lstlisting}[numbers=none] def foo(n: Int, x: Double) : Double = ... + def id(n: Int) : Int = ... def bar() : Void = ... \end{lstlisting} \noindent The idea is to record all typing information that is given -in the program, but then delay any further typing inference to +in the Fun-program, but then delay any further typing inference to after the CPS-translation. That means the parser should generate ASTs given by the Scala dataypes: @@ -93,8 +102,9 @@ case class Call(name: String, args: List[Exp]) extends Exp case class If(a: BExp, e1: Exp, e2: Exp) extends Exp case class Var(s: String) extends Exp -case class Num(i: Int) extends Exp // integer numbers -case class FNum(i: Float) extends Exp // floating numbers +case class Num(i: Int) extends Exp // integer numbers +case class FNum(i: Float) extends Exp // floating numbers +case class ChConst(c: Int) extends Exp // char constant case class Aop(o: String, a1: Exp, a2: Exp) extends Exp case class Sequence(e1: Exp, e2: Exp) extends Exp case class Bop(o: String, a1: Exp, a2: Exp) extends BExp @@ -120,6 +130,15 @@ \caption{Ascii output of the Mandelbrot program.\label{mand}} \end{figure} +Also note that the second version of the Mandelbrot program and also +the Tower of Hanoi program uses character constants, like \texttt{'a'}, +\texttt{'1'}, \texttt{'$\backslash$n'} and so on. When they are tokenised, +such characters should be interpreted as the corresponding ASCII code (an +integer), such that we can use them in calculations like \texttt{'a' + 10} +where the result should be 107. As usual, the character \texttt{'$\backslash$n'} is the +ASCII code 10. + + \subsection*{LLVM-IR} There are some subtleties in the LLVM-IR you need to be aware of: @@ -175,6 +194,7 @@ case "*" => "mul i32 " case "-" => "sub i32 " case "==" => "icmp eq i32 " + case "!=" => "icmp ne i32 " case "<=" => "icmp sle i32 " // signed less or equal case "<" => "icmp slt i32 " // signed less than }\end{lstlisting} @@ -187,6 +207,7 @@ case "*" => "fmul double " case "-" => "fsub double " case "==" => "fcmp oeq double " + case "!=" => "fcmp one double " case "<=" => "fcmp ole double " case "<" => "fcmp olt double " }\end{lstlisting} @@ -220,8 +241,8 @@ \item \textbf{Build-In Functions}: The `prelude' comes with several build-in functions: \texttt{new\_line()}, - \texttt{skip}, \texttt{print\_int(n)}, \texttt{print\_space()} - and \texttt{print\_star()}. You can find the `prelude' for + \texttt{skip}, \texttt{print\_int(n)}, \texttt{print\_space()}, + \texttt{print\_star()} and \texttt{print\_char(n)}. You can find the `prelude' for example in the file \texttt{sqr.ll}. \end{itemize} diff -r 8706b846a3e0 -r 568671822d52 cwtests/cw02/factors.while --- a/cwtests/cw02/factors.while Tue Nov 30 10:16:47 2021 +0000 +++ b/cwtests/cw02/factors.while Fri Dec 03 17:45:11 2021 +0000 @@ -3,7 +3,7 @@ write "Input n please"; read n; -write "The factors of n are"; +write "\nThe factors of n are"; f := 2; while (f < n / 2 + 1) do { if ((n / f) * f == n) then { write(f) } else { skip }; diff -r 8706b846a3e0 -r 568671822d52 cwtests/cw02/fib.while --- a/cwtests/cw02/fib.while Tue Nov 30 10:16:47 2021 +0000 +++ b/cwtests/cw02/fib.while Fri Dec 03 17:45:11 2021 +0000 @@ -1,4 +1,4 @@ -write "Fib"; +write "Fib: "; read n; minus1 := 0; minus2 := 1; @@ -8,6 +8,7 @@ minus1 := temp; n := n - 1 }; -write "Result"; -write minus2 +write "Result: "; +write minus2 ; +write "\n" diff -r 8706b846a3e0 -r 568671822d52 cwtests/cw03/fib.while --- a/cwtests/cw03/fib.while Tue Nov 30 10:16:47 2021 +0000 +++ b/cwtests/cw03/fib.while Fri Dec 03 17:45:11 2021 +0000 @@ -1,4 +1,4 @@ -write "Fib"; +write "Fib: "; read n; minus1 := 0; minus2 := 1; @@ -8,6 +8,7 @@ minus1 := temp; n := n - 1 }; -write "Result"; -write minus2 +write "Result: "; +write minus2 ; +write "\n" diff -r 8706b846a3e0 -r 568671822d52 slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 8706b846a3e0 -r 568671822d52 slides/slides09.tex --- a/slides/slides09.tex Tue Nov 30 10:16:47 2021 +0000 +++ b/slides/slides09.tex Fri Dec 03 17:45:11 2021 +0000 @@ -75,6 +75,157 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c,fragile] +\frametitle{\mbox{}\hspace{5cm}Factorial} + +\begin{textblock}{7}(0,1.0)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] +.method public static facT(II)I +.limit locals 2 +.limit stack 6 + iload 0 + ldc 0 + if_icmpne If_else_2 + iload 1 + goto If_end_3 +If_else_2: + iload 0 + ldc 1 + isub + iload 0 + iload 1 + imul + invokestatic fact/fact/facT(II)I +If_end_3: + ireturn +.end method +\end{lstlisting} +\end{minipage} +\end{textblock} + +\begin{textblock}{7}(6,7) +\begin{bubble}[7cm]\small +\begin{lstlisting}[language=Lisp, + basicstyle=\ttfamily, + numbers=none, + xleftmargin=1mm,linebackgroundcolor=\color{cream}] +def facT(n, acc) = + if n == 0 then acc + else facT(n - 1, n * acc); +\end{lstlisting} +\end{bubble} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[fragile] + +\begin{textblock}{7}(1,-0.2)\footnotesize +\begin{minipage}{6cm} +\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}] +.method public static facT(II)I +.limit locals 2 +.limit stack 6 +(*@\hl{facT\_Start:} @*) + iload 0 + ldc 0 + if_icmpne If_else_2 + iload 1 + goto If_end_3 +If_else_2: + iload 0 + ldc 1 + isub + iload 0 + iload 1 + imul + (*@\hl{istore 1} @*) + (*@\hl{istore 0} @*) + (*@\hl{goto facT\_Start} @*) +If_end_3: + ireturn +.end method +\end{lstlisting} +\end{minipage} +\end{textblock} + +\begin{textblock}{7}(6,7) +\begin{bubble}[7cm]\small +\begin{lstlisting}[language=Lisp, + basicstyle=\ttfamily, + numbers=none, + xleftmargin=1mm,linebackgroundcolor=\color{cream}] +def facT(n, acc) = + if n == 0 then acc + else facT(n - 1, n * acc); +\end{lstlisting} +\end{bubble} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t, fragile] +\frametitle{Tail Recursion} + +A call to \texttt{f(args)} is usually compiled as\medskip + +{\small\begin{lstlisting}[basicstyle=\ttfamily, numbers=none] + args onto stack + invokestatic .../f +\end{lstlisting}}\pause + + +A call is in tail position provided:\medskip + +{\small\begin{itemize} +\item \texttt{if Bexp then \hl{Exp} else \hl{Exp}} +\item \texttt{Exp ; \hl{Exp}} +\item \texttt{Exp op Exp} +\end{itemize}}\medskip + +then a call \texttt{f(args)} can be compiled as\medskip\small + +\begin{lstlisting}[numbers=none] + prepare environment + jump to start of function +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c, fragile] +\frametitle{Tail Recursive Call} +\footnotesize + +\begin{textblock}{13}(-0.3,3) +\begin{lstlisting}[language=Scala, numbers=none] +def compile_expT(a: Exp, env: Mem, name: String): Instrs = + ... + case Call(n, args) => if (name == n) + { + val stores = + args.zipWithIndex.map { case (x, y) => i"istore $y" } + + args.map(a => compile_expT(a, env, "")).mkString ++ + stores.reverse.mkString ++ + i"goto ${n}_Start" + } else { + val is = "I" * args.length + args.map(a => compile_expT(a, env, "")).mkString ++ + i"invokestatic XXX/XXX/${n}(${is})I" + } +\end{lstlisting} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile]