--- a/slides/slides07.tex Thu Nov 07 00:07:16 2019 +0000
+++ b/slides/slides07.tex Thu Nov 14 01:21:02 2019 +0000
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{../slides}
\usepackage{../langs}
@@ -23,9 +24,10 @@
\normalsize
\begin{center}
\begin{tabular}{ll}
- Email: & christian.urban at kcl.ac.uk\\
- Office: & N\liningnums{7.07} (North Wing, Bush House)\\
- Slides: & KEATS (also homework is there)\\
+ Email: & christian.urban at kcl.ac.uk\\
+ Office Hours: & Thursdays 12 -- 14\\
+ Location: & N7.07 (North Wing, Bush House)\\
+ Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
@@ -53,6 +55,25 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
+\frametitle{CW3}
+
+Atomic parsers for tokens
+
+\begin{center}
+\bl{$\texttt{T\_Num(123)}::rest \;\Rightarrow\; \{(\texttt{T\_Num(123)}, rest)\}$}
+\end{center}\bigskip
+
+\begin{itemize}
+\item you consume one or more token from the\\
+ input (stream)
+\item \bl{\texttt{T\_NUM(1), T\_OP(+), T\_NUM(2)}}
+\end{itemize}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
\begin{textblock}{10}(0.5,0.5)
\LARGE
\fontspec{Hoefler Text Black}
@@ -196,42 +217,42 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[t]
+%\frametitle{Interpreted Code}
+%
+%\begin{center}
+%\begin{tikzpicture}
+%\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
+%\addplot+[smooth] file {interpreted.data};
+%\end{axis}
+%\end{tikzpicture}
+%\end{center}
+%
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[c]
+%\frametitle{Java Virtual Machine}
+%
+%\begin{itemize}
+%\item introduced in 1995
+%\item is a stack-based VM (like Postscript, CLR of .Net)
+%\item contains a JIT compiler
+%\item many languages take advantage of JVM's infrastructure (JRE)
+%\item is garbage collected $\Rightarrow$ no buffer overflows
+%\item some languages compiled to the JVM: Scala, Clojure\ldots
+%\end{itemize}
+%
+%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Interpreted Code}
-
-\begin{center}
-\begin{tikzpicture}
-\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
-\addplot+[smooth] file {interpreted.data};
-\end{axis}
-\end{tikzpicture}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Java Virtual Machine}
-
-\begin{itemize}
-\item introduced in 1995
-\item is a stack-based VM (like Postscript, CLR of .Net)
-\item contains a JIT compiler
-\item many languages take advantage of JVM's infrastructure (JRE)
-\item is garbage collected $\Rightarrow$ no buffer overflows
-\item some languages compiled to the JVM: Scala, Clojure\ldots
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\frametitle{Compiling AExps}
-For example \liningnums{\bl{$1 + ((2 * 3) + (4 - 3))$}}:\medskip
+For example \textbf{\bl{1 + ((2 * 3) + (4 - 3))}}:\medskip
\begin{columns}[T]
\begin{column}{.3\textwidth}
@@ -269,7 +290,7 @@
\begin{frame}[t,fragile]
\frametitle{Compiling AExps}
-\liningnums{\textbf{\Large\bl{1 + 2 + 3}}}
+\liningnums{\textbf{\Large\bl{(1 + 2) + 3}}}
\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
ldc 1
@@ -791,25 +812,39 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}}
+\frametitle{Next Compiler Phases}
\begin{itemize}
\item assembly $\Rightarrow$ byte code (class file)
\item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip
\item \texttt{javap} is a disassembler for class files
+\item jasmin and krakatau are assemblers for jvm code
\end{itemize}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Compiled Code\end{tabular}}
+\frametitle{Recall: Interpreted Code}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
+\addplot+[smooth] file {interpreted.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+Loop program
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiled Code}
\begin{center}
\begin{tikzpicture}
@@ -819,15 +854,12 @@
\end{tikzpicture}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}}
+\frametitle{Compiler vs.~Interpreter}
\begin{center}
\begin{tikzpicture}
@@ -842,10 +874,122 @@
\end{tikzpicture}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{A ``Compiler'' for BF*** to C}
+
+ \begin{center}
+ \begin{tabular}{lcl}
+ \bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\
+ \bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\
+ \bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\
+ \bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\
+ \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\
+ \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\
+ \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\
+ \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\
+ & $\Rightarrow$ & ignore everything else\\
+ \end{tabular}
+ \end{center}\bigskip
+
+ \texttt{char field[30000]\\ char *ptr = \&field[15000]}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{BF***}
+
+we need some big array, say \texttt{arr} and 7 (8) instructions:\medskip
+
+\begin{itemize}
+\item \texttt{>} move \texttt{ptr++}
+\item \texttt{<} move \texttt{ptr-{}-}
+\item \texttt{+} add \texttt{arr[ptr]++}
+\item \texttt{-} subtract \texttt{arr[ptr]-{}-}
+\item \texttt{.} print out \texttt{arr[ptr]} as ASCII
+\item \texttt{[} if \texttt{arr[ptr] == 0} jump just after the corresponding \texttt{]}; otherwise \texttt{ptr++}
+\item \texttt{]} if \texttt{arr[ptr] != 0} jump just after the corresponding \texttt{[}; otherwise \texttt{ptr++}
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Arrays in While}
+
+\begin{itemize}
+\item \texttt{new arr[15000]}\medskip
+\item \texttt{x := 3 + arr[3 + y]}\medskip
+\item \texttt{arr[42 * n] := ...}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{New Arrays}
+
+\begin{lstlisting}[mathescape,numbers=none,language=While]
+ new arr[number]
+\end{lstlisting}\bigskip\bigskip
+
+\begin{lstlisting}[mathescape,numbers=none,language=JVMIS]
+ ldc number
+ newarray int
+ astore loc_var
+\end{lstlisting}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Array Update}
+
+\begin{lstlisting}[mathescape,numbers=none,language=While]
+ arr[...] :=
+\end{lstlisting}\bigskip\bigskip
+
+\begin{lstlisting}[mathescape,numbers=none,language=JVMIS]
+ aload loc_var
+ index_aexp
+ value_aexp
+ iastore
+\end{lstlisting}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Array Lookup in AExp}
+
+\begin{lstlisting}[mathescape,numbers=none,language=While]
+ ...arr[...]...
+\end{lstlisting}\bigskip\bigskip
+
+\begin{lstlisting}[mathescape,numbers=none,language=JVMIS]
+ aload loc_var
+ index_aexp
+ iaload
+\end{lstlisting}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Backend}