--- a/coursework/cw01.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/coursework/cw01.tex Wed Sep 25 11:24:34 2019 +0100
@@ -1,4 +1,4 @@
-
+% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
@@ -11,7 +11,7 @@
\section*{Coursework 1 (Strand 1)}
-This coursework is worth 4\% and is due on 12 October at
+This coursework is worth 4\% and is due on 11 October at
18:00. You are asked to implement a regular expression matcher
and submit a document containing the answers for the questions
below. You can do the implementation in any programming
@@ -67,8 +67,8 @@
classes for
the extended regular expressions.\footnote{Please call them
\code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES},
- \code{UPTO}, \code{FROM}, \code{BETWEEN}, \code{NOT} or something
- like that.} That means do not treat the extended regular expressions
+ \code{UPTO}, \code{FROM} and \code{BETWEEN}.}
+ That means do not treat the extended regular expressions
by just translating them into the basic ones. See also Question 3,
where you are asked to explicitly give the rules for \textit{nullable}
and \textit{der} for the extended regular expressions. So something like
@@ -280,7 +280,7 @@
Implement the simplification rules in your regular expression matcher.
Consider the regular expression $/ \cdot * \cdot
(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot *
-\cdot /$ and decide wether the following four strings are matched by
+\cdot /$ and decide whether the following four strings are matched by
this regular expression. Answer yes or no.
\begin{enumerate}
Binary file coursework/cw02.pdf has changed
--- a/coursework/cw02.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/coursework/cw02.tex Wed Sep 25 11:24:34 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
@@ -6,7 +7,7 @@
\section*{Coursework 2 (Strand 1)}
-\noindent This coursework is worth 5\% and is due on 2
+\noindent This coursework is worth 5\% and is due on 4
November at 18:00. You are asked to implement the Sulzmann \&
Lu lexer for the WHILE language. You can do the
implementation in any programming language you like, but you
Binary file coursework/cw03.pdf has changed
--- a/coursework/cw03.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/coursework/cw03.tex Wed Sep 25 11:24:34 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
@@ -6,7 +7,7 @@
\section*{Coursework 3}
-\noindent This coursework is worth 5\% and is due on 23
+\noindent This coursework is worth 5\% and is due on 22
November at 18:00. You are asked to implement a parser for the
WHILE language and also an interpreter. You can do the
implementation in any programming language you like, but you
Binary file coursework/cw04.pdf has changed
--- a/coursework/cw04.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/coursework/cw04.tex Wed Sep 25 11:24:34 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
@@ -9,7 +10,7 @@
\section*{Coursework 4 (Strand 1)}
-\noindent This coursework is worth 6\% and is due on 14
+\noindent This coursework is worth 6\% and is due on 13
December at 18:00. You are asked to implement a compiler for
the WHILE language that targets the assembler language
provided by Jasmin or Krakatau (both have very similar
@@ -195,7 +196,7 @@
\end{minipage}
\end{center}
-\subsection*{Question 3 (marked with 1\%)}
+\subsection*{Question 3}
\noindent In this question you are supposed to give the
assembler instructions for the program
Binary file coursework/cw05.pdf has changed
--- a/coursework/cw05.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/coursework/cw05.tex Wed Sep 25 11:24:34 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
@@ -6,7 +7,7 @@
\section*{Coursework (Strand 2)}
-\noindent This coursework is worth 20\% and is due on 14 December at
+\noindent This coursework is worth 20\% and is due on 13 December at
18:00. You are asked to prove the correctness of the regular
expression matcher from the lectures using the Isabelle theorem
prover. You need to submit a theory file containing this proof. The
--- a/langs.sty Tue Jul 30 23:44:56 2019 +0100
+++ b/langs.sty Wed Sep 25 11:24:34 2019 +0100
@@ -1,7 +1,30 @@
\usepackage{listings}
\usepackage{etoolbox}
-\setmonofont[Scale=.95]{Consolas}
-\newfontfamily{\consolas}{Consolas}
+%\setmonofont[Scale=.95]{Consolas}
+%\newfontfamily{\consolas}{Consolas}
+
+\makeatletter
+\let\old@lstKV@SwitchCases\lstKV@SwitchCases
+\def\lstKV@SwitchCases#1#2#3{}
+\makeatother
+\usepackage{lstlinebgrd}
+\makeatletter
+\let\lstKV@SwitchCases\old@lstKV@SwitchCases
+
+\lst@Key{numbers}{none}{%
+ \def\lst@PlaceNumber{\lst@linebgrd}%
+ \lstKV@SwitchCases{#1}%
+ {none:\\%
+ left:\def\lst@PlaceNumber{\llap{\normalfont
+ \lst@numberstyle{\thelstnumber}\kern\lst@numbersep}\lst@linebgrd}\\%
+ right:\def\lst@PlaceNumber{\rlap{\normalfont
+ \kern\linewidth \kern\lst@numbersep
+ \lst@numberstyle{\thelstnumber}}\lst@linebgrd}%
+ }{\PackageError{Listings}{Numbers #1 unknown}\@ehc}}
+\makeatother
+
+
+
\definecolor{codered}{rgb}{0.6,0,0} % for strings
\definecolor{codegreen}{rgb}{0.25,0.5,0.35} % comments
--- a/mk Tue Jul 30 23:44:56 2019 +0100
+++ b/mk Wed Sep 25 11:24:34 2019 +0100
@@ -6,7 +6,8 @@
for sd in $subdirs; do
cd $sd
for fl in *.tex; do
- xelatex $fl
+ echo $fl
+ xelatex $fl | pr -to4
done
cd ..
-done
\ No newline at end of file
+done
Binary file pics/msbug.png has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slides-aux/slides09.tex Wed Sep 25 11:24:34 2019 +0100
@@ -0,0 +1,766 @@
+\documentclass[dvipsnames,14pt,t]{beamer}
+\usepackage{../slides}
+\usepackage{../langs}
+\usepackage{../data}
+\usepackage{../graphics}
+\usepackage{../grammar}
+\usepackage{soul}
+
+\tikzset{onslide/.code args={<#1>#2}{%
+ \only<#1>{\pgfkeysalso{#2}} % \pgfkeysalso doesn't change the path
+}}
+
+\makeatletter
+\newenvironment<>{btHighlight}[1][]
+{\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}}
+{\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}}
+
+\newcommand<>\btHL[1][]{%
+ \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}%
+}
+\def\bt@HL@endenv{%b jm
+ \end{btHighlight}%
+ \egroup
+}
+\newcommand{\bt@HL@box}[2][]{%
+ \tikz[#1]{%
+ \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}%
+ \pgfusepath{use as bounding box}%
+ \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}};
+ }%
+}
+\makeatother
+
+\lstset{morekeywords={def,if,then,else,write,read},keywordstyle=\color{codepurple}\bfseries}
+
+% beamer stuff
+\renewcommand{\slidecaption}{CFL 09, King's College London}
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}
+
+
+\begin{document}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{%
+ \begin{tabular}{@ {}c@ {}}
+ \\[-3mm]
+ \LARGE Compilers and \\[-2mm]
+ \LARGE Formal Languages (8)\\[3mm]
+ \end{tabular}}
+
+ \normalsize
+ \begin{center}
+ \begin{tabular}{ll}
+ Email: & christian.urban at kcl.ac.uk\\
+ Office: & N7.07 (North Wing, Bush House)\\
+ Slides: & KEATS (also home work is there)\\
+ \end{tabular}
+ \end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+\frametitle{Compiling AExps}
+
+For example \bl{$1 + ((2 * 3) + (4 - 3))$}:\medskip
+
+\begin{columns}[T]
+\begin{column}{.3\textwidth}
+\begin{center}
+\bl{\begin{tikzpicture}
+\tikzset{level distance=12mm,sibling distance=4mm}
+\tikzset{edge from parent/.style={draw,very thick}}
\Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]
\end{tikzpicture}}
+\end{center}
+\end{column}
+\begin{column}{.3\textwidth}
+\begin{lstlisting}[language=JVMIS,numbers=none]
+ldc 1
+ldc 2
+ldc 3
+imul
+ldc 4
+ldc 3
+isub
+iadd
+iadd
+\end{lstlisting}
+\end{column}
+\end{columns}\bigskip
+
+\small
+Traverse tree in post-order \bl{$\Rightarrow$} code for
+stack-machine
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Compiling AExps}
+
+\bl{
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{compile}(n, E)$ & $\dn$ & $\pcode{ldc}\;n$\smallskip\\
+$\textit{compile}(a_1 + a_2, E)$ & $\dn$ \\
+\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{iadd}$}\smallskip\\
+$\textit{compile}(a_1 - a_2, E)$ & $\dn$ \\
+\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{isub}$}\smallskip\\
+$\textit{compile}(a_1 * a_2, E)$ & $\dn$ \\
+\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{imul}$}\smallskip\\
+$\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$\\
+\multicolumn{3}{c}{$\qquad\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \pcode{idiv}$}\smallskip\\
+$\textit{compile}(x, E)$ & $\dn$ & $\pcode{iload}\;E(x)$\\
+\end{tabular}
+\end{center}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Compiling Ifs}
+
+For example
+
+\begin{lstlisting}[mathescape,numbers=none,language=While]
+if 1 = 1 then x := 2 else y := 3
+\end{lstlisting}
+
+
+\begin{center}
+\begin{lstlisting}[mathescape,language=JVMIS,numbers=none]
+ ldc 1
+ ldc 1
+ if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$
+ ldc 2
+ istore 0
+ goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$
+L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$
+ ldc 3
+ istore 1
+L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$
+\end{lstlisting}
+\end{center}
+
+\begin{tikzpicture}[remember picture,overlay]
\draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm)
+ -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east);
+ \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm)
+ -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east);
\end{tikzpicture}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Compiling Whiles}
+
+For example
+
+\begin{lstlisting}[mathescape,numbers=none,language=While]
+while x <= 10 do x := x + 1
+\end{lstlisting}
+
+
+\begin{center}
+\begin{lstlisting}[mathescape,language=JVMIS,numbers=none]
+L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$
+ iload 0
+ ldc 10
+ if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$
+ iload 0
+ ldc 1
+ iadd
+ istore 0
+ goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$
+L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$
+\end{lstlisting}
+\end{center}
+
+\begin{tikzpicture}[remember picture,overlay]
+ \draw[->,very thick] (LA) edge [->,to path={-- ++(12mm,0mm)
+ -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east);
+ \draw[->,very thick] (LC) edge [->,to path={-- ++(12mm,0mm)
+ -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east);
\end{tikzpicture}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Compiling Writes}
+
+\small
+\begin{lstlisting}[language=JVMIS,mathescape,
+ numbers=none,xleftmargin=-6mm]
+.method public static write(I)V
+ .limit locals 1
+ .limit stack 2
+ getstatic java/lang/System/out
+ Ljava/io/PrintStream;
+ iload 0
+ invokevirtual java/io/PrintStream/println(I)V
+ return
+.end method
+
+
+
+iload $E(x)$
+invokestatic XXX/XXX/write(I)V
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Compiling Main}
+
+\footnotesize
+\begin{lstlisting}[language=JVMIS,mathescape,
+ numbers=none,xleftmargin=-6mm]
+.class public XXX.XXX
+.super java/lang/Object
+
+.method public <init>()V
+ aload_0
+ invokenonvirtual java/lang/Object/<init>()V
+ return
+.end method
+
+.method public static main([Ljava/lang/String;)V
+ .limit locals 200
+ .limit stack 200
+
+ $\textit{\ldots{}here comes the compiled code\ldots}$
+
+ return
+.end method
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+\frametitle{Functional Programming}
+
+\footnotesize
+\begin{textblock}{13}(0.9,3)
+\begin{lstlisting}[]numbers=none]
+def fib(n) = if n == 0 then 0
+ else if n == 1 then 1
+ else fib(n - 1) + fib(n - 2);
+
+def fact(n) = if n == 0 then 1 else n * fact(n - 1);
+
+def ack(m, n) = if m == 0 then n + 1
+ else if n == 0 then ack(m - 1, 1)
+ else ack(m - 1, ack(m, n - 1));
+
+def gcd(a, b) = if b == 0 then a else gcd(b, a % b);
+\end{lstlisting}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Fun Grammar}
+\bl{
+\begin{plstx}[rhs style=]
+: \meta{Exp} ::= \meta{Var} | \meta{Num}{\hspace{3cm}}
+ | \meta{Exp} + \meta{Exp} | ... | (\meta{Exp})
+ | \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp}
+ | \code{write} \meta{Exp} {\hspace{3cm}}
+ | \meta{Exp} ; \meta{Exp}
+ | \textit{FunName} (\meta{Exp}, ... , \meta{Exp})\\
+: \meta{BExp} ::= ...\\
+: \meta{Decl} ::= \meta{Def} ; \meta{Decl}
+ | \meta{Exp}\\
+: \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ... , $x_n$) = \meta{Exp}\\
+\end{plstx}}
+
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Abstract Syntax Trees}
+
+\footnotesize
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
+abstract class Exp
+abstract class BExp
+abstract class Decl
+
+case class Var(s: String) extends Exp
+case class Num(i: Int) extends Exp
+case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
+case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
+case class Write(e: Exp) extends Exp
+case class Sequ(e1: Exp, e2: Exp) extends Exp
+case class Call(name: String, args: List[Exp]) extends Exp
+
+case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
+
+case class Def(name: String,
+ args: List[String],
+ body: Exp) extends Decl
+case class Main(e: Exp) extends Decl
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Sequences}
+
+Compiling \texttt{exp1 ; exp2}:\bigskip
+
+
+\begin{lstlisting}[mathescape,language=JVMIS, numbers=none]
+$\textit{compile}$(exp1)
+pop
+$\textit{compile}$(exp2)
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Write}
+
+Compiling call to \texttt{write(1+2)}:\bigskip
+
+
+\begin{lstlisting}[mathescape,language=JVMIS, numbers=none]
+$\textit{compile}$(1+2)
+dup
+invokestatic XXX/XXX/write(I)V
+\end{lstlisting}\bigskip
+
+\small
+needs the helper method
+
+\footnotesize
+\begin{lstlisting}[language=JVMIS,
+ xleftmargin=2mm,
+ numbers=none]
+.method public static write(I)V
+ .limit locals 1
+ .limit stack 2
+ getstatic java/lang/System/out Ljava/io/PrintStream;
+ iload 0
+ invokevirtual java/io/PrintStream/println(I)V
+ return
+.end method
+\end{lstlisting}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t, fragile]
+\frametitle{Function Definitions}
+
+\footnotesize
+\begin{lstlisting}[language=JVMIS,
+ xleftmargin=2mm,
+ numbers=none]
+.method public static write(I)V
+ .limit locals 1
+ .limit stack 2
+ getstatic java/lang/System/out Ljava/io/PrintStream;
+ iload 0
+ invokevirtual java/io/PrintStream/println(I)V
+ return
+.end method
+\end{lstlisting}\bigskip
+
+\small We will need for definitions, like\footnotesize\medskip
+
+\begin{lstlisting}[language=JVMIS,
+ xleftmargin=2mm,
+ numbers=none]
+def fname (x1, ... , xn) = ...
+
+.method public static fname (I...I)I
+ .limit locals ??
+ .limit stack ??
+ ??
+.end method
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Stack Estimation}
+\small
+\mbox{}\\[-15mm]
+
+\bl{\begin{center}
+\begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
+$\textit{estimate}(n)$ & $\dn$ & $1$\\
+$\textit{estimate}(x)$ & $\dn$ & $1$\\
+$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &
+$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
+$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ &
+$\textit{estimate}(b) +$\\
+& & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
+$\textit{estimate}(\pcode{write}(e))$ & $\dn$ &
+$\textit{estimate}(e) + 1$\\
+$\textit{estimate}(e_1 ; e_2)$ & $\dn$ &
+$max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
+$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ &
+$\sum_{i = 1..n}\;estimate(e_i)$\medskip\\
+$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &
+$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
+\end{tabular}
+\end{center}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile]
+\frametitle{Successor Function}
+
+\begin{textblock}{7}(1,2.5)\footnotesize
+\begin{minipage}{6cm}
+\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
+.method public static suc(I)I
+.limit locals 1
+.limit stack 2
+ iload 0
+ ldc 1
+ iadd
+ ireturn
+.end method
+\end{lstlisting}
+\end{minipage}
+\end{textblock}
+
+\begin{textblock}{7}(6,8)
+\begin{bubble}[5cm]\small
+\begin{lstlisting}[language=Lisp,
+ basicstyle=\ttfamily,
+ numbers=none,
+ xleftmargin=1mm]
+def suc(x) = x + 1;
+\end{lstlisting}
+\end{bubble}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile]
+\frametitle{Addition Function}
+
+\begin{textblock}{7}(1,1.9)\footnotesize
+\begin{minipage}{6cm}
+\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
+.method public static add(II)I
+.limit locals 2
+.limit stack 5
+ iload 0
+ ldc 0
+ if_icmpne If_else
+ iload 1
+ goto If_end
+If_else:
+ iload 0
+ ldc 1
+ isub
+ iload 1
+ invokestatic XXX/XXX/add(II)I
+ invokestatic XXX/XXX/suc(I)I
+If_end:
+ ireturn
+.end method
+\end{lstlisting}
+\end{minipage}
+\end{textblock}
+
+\begin{textblock}{7}(6,6.6)
+\begin{bubble}[7cm]\small
+\begin{lstlisting}[language=Lisp,
+ basicstyle=\ttfamily,
+ numbers=none,
+ xleftmargin=1mm]
+def add(x, y) =
+ if x == 0 then y
+ else suc(add(x - 1, y));
+\end{lstlisting}
+\end{bubble}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile]
+\frametitle{Factorial}
+
+\begin{textblock}{7}(1,1.5)\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]
+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]
+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}[c, 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}[basicstyle=\ttfamily, 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,2)
+\begin{lstlisting}[language=Scala,basicstyle=\ttfamily, 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) => "istore " + y.toString + "\n" }
+ args.flatMap(a => compile_expT(a, env, "")) ++
+ stores.reverse ++
+ List ("goto " + n + "_Start\n")
+ }
+ else
+ {
+ val is = "I" * args.length
+ args.flatMap(a => compile_expT(a, env, "")) ++
+ List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n")
+ }
+\end{lstlisting}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ \begin{frame}[c]
+ \frametitle{Dijkstra on Testing}
+
+ \begin{bubble}[10cm]
+ ``Program testing can be a very effective way to show the
+ presence of bugs, but it is hopelessly inadequate for showing
+ their absence.''
+ \end{bubble}\bigskip
+
+ \small
+ What is good about compilers: the either seem to work,
+ or go horribly wrong (most of the time).
+
+ \end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\Large Proving Programs to be Correct}
+
+\begin{bubble}[10cm]
+\small
+{\bf Theorem:} There are infinitely many prime
+numbers.\medskip\\
+
+{\bf Proof} \ldots\\
+\end{bubble}\bigskip
+
+
+similarly\bigskip
+
+\begin{bubble}[10cm]
+\small
+{\bf Theorem:} The program is doing what
+it is supposed to be doing.\medskip
+
+{\bf Long, long proof} \ldots\\
+\end{bubble}\bigskip\medskip
+
+\small This can be a gigantic proof. The only hope is to have
+help from the computer. `Program' is here to be understood to be
+quite general (compiler, OS, \ldots).
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}[c]
+\frametitle{Can This Be Done?}
+
+\begin{itemize}
+\item in 2008, verification of a small C-compiler
+\begin{itemize}
+\item ``if my input program has a certain behaviour, then the compiled machine code has the same behaviour''
+\item is as good as \texttt{gcc -O1}, but much, much less buggy
+\end{itemize}
+\end{itemize}
+
+\begin{center}
+ \includegraphics[scale=0.12]{../pics/compcert.png}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Fuzzy Testing C-Compilers}
+
+\begin{itemize}
+\item tested GCC, LLVM and others by randomly generating
+C-programs
+\item found more than 300 bugs in GCC and also
+many in LLVM (some of them highest-level critical)\bigskip
+\item about CompCert:
+
+\begin{bubble}[10cm]\small ``The striking thing about our CompCert
+results is that the middle-end bugs we found in all other
+compilers are absent. As of early 2011, the under-development
+version of CompCert is the only compiler we have tested for
+which Csmith cannot find wrong-code errors. This is not for
+lack of trying: we have devoted about six CPU-years to the
+task.''
+\end{bubble}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
+
--- a/slides.sty Tue Jul 30 23:44:56 2019 +0100
+++ b/slides.sty Wed Sep 25 11:24:34 2019 +0100
@@ -1,29 +1,48 @@
\usepackage[absolute,overlay]{textpos}
\usepackage{xcolor}
-\usepackage{fontspec}
+\usepackage[no-math]{fontspec}
+
+%%%%% CODE FONT
+%\setmonofont[Scale=.95]{Consolas}
+\setmonofont[Scale=.88]{Consolas}
+\newfontfamily{\consolas}{Consolas}
+
+%%%%% MATHFONT
\usepackage[sc]{mathpazo}
-%%\usepackage{CronosPro}
+%\usepackage{fourier}
+%\usepackage{mathspec}
+%\usepackage[varg]{txfonts}
+%\usepackage{mathpple}
+
+%%%%% MAIN TEXT FONT
+\setromanfont{Cronos Pro}
+%\setbeamerfont{normal text}{family={\fontspec{Cronos Pro}}}
+%\setbeamerfont{normal text}{family={\fontspec{Hoefler Text}}}
+%\setromanfont{Cronos Pro}
+%\setromanfont{Hoefler Text}
\usefonttheme{serif}
\defaultfontfeatures{Ligatures=TeX}
\defaultfontfeatures{Mapping=tex-text}
-\setromanfont{Hoefler Text}
-\setmonofont[Scale=.88]{Consolas}
-\newfontfamily{\consolas}{Consolas}
+
+
+%%%% Colours
\definecolor{darkblue}{rgb}{0,0,0.6}
\hypersetup{colorlinks=true}
\hypersetup{linkcolor=darkblue}
\hypersetup{urlcolor=darkblue}
+\hfuzz=320pt
+
\newcommand{\tttext}[1]{{\consolas{#1}}}
-\newcommand{\ZERO}{\mbox{\bf 0}}
-\newcommand{\ONE}{\mbox{\bf 1}}
-\newcommand{\Der}{\textit{Der}}
-\newcommand{\der}{\textit{der}}
-\newcommand{\Ders}{\textit{Ders}}
-\newcommand{\ders}{\textit{ders}}
+\newcommand{\ZERO}{\mathit{\bf 0}}
+\newcommand{\ONE}{\mathit{\bf 1}}
+\newcommand{\Der}{\mathit{Der}}
+\newcommand{\der}{\mathit{der}}
+\newcommand{\Ders}{\mathit{Ders}}
+\newcommand{\ders}{\mathit{ders}}
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
\newcommand{\slidecaption}{}
@@ -31,7 +50,8 @@
% Frametitles
\setbeamerfont{frametitle}{size={\LARGE}}
-\setbeamerfont{frametitle}{family={\fontspec{Hoefler Text Black}}}
+%\setbeamerfont{frametitle}{family={\fontspec{Hoefler Text Black}}}
+\setbeamerfont{frametitle}{family={\fontspec{Cronos Pro Bold Caption}}}
\setbeamercolor{frametitle}{fg=ProcessBlue,bg=white}
\setbeamertemplate{frametitle}{%
Binary file slides/slides01.pdf has changed
--- a/slides/slides01.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/slides/slides01.tex Wed Sep 25 11:24:34 2019 +0100
@@ -202,7 +202,7 @@
\begin{itemize}
\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
\item \bl{$(a^*)^*\cdot b$}
-\item \bl{$([a$\,-\,$z]^+)^*$}
+\item \bl{$([a-z]^+)^*$}
\item \bl{$(a + a \cdot a)^*$}
\item \bl{$(a + a^?)^*$}
\end{itemize}
Binary file slides/slides02.pdf has changed
--- a/slides/slides02.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/slides/slides02.tex Wed Sep 25 11:24:34 2019 +0100
@@ -35,7 +35,7 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office: & N\liningnums{7.07} (North Wing, Bush House)\\
+ Office: & N7.07 (North Wing, Bush House)\\
Slides: & KEATS (also homework is there)
\end{tabular}
\end{center}
@@ -45,7 +45,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
- \frametitle{\Large
+ \frametitle{
Lets Implement an Efficient\\[-2mm]
Regular Expression Matcher}
@@ -300,17 +300,17 @@
\bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ }
\end{center}\bigskip
-For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then
+For \bl{$A = \{\mathit{foo}, \mathit{bar}, \mathit{frak}\}$} then
\begin{center}
\bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
-$\Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
-$\Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\
+$\Der\,f\,A$ & $=$ & $\{\mathit{oo}, \mathit{rak}\}$\\
+$\Der\,b\,A$ & $=$ & $\{\mathit{ar}\}$\\
$\Der\,a\,A$ & $=$ & $\{\}$\pause
\end{tabular}}
\end{center}
-\small
+
We can extend this definition to strings
\[
\bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}}
@@ -324,21 +324,21 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{The Specification\\ for Matching}
+\frametitle{The Specification for Matching}
\begin{bubble}[10cm]
\large
A regular expression \bl{$r$} matches a string~\bl{$s$}
provided
-
\begin{center}
-\bl{$s \in L(r)$}\\
+\bl{$s \in L(r)$}
\end{center}
-\end{bubble}\bigskip\bigskip
+\end{bubble}
-\ldots and the point of the this lecture is
-to decide this problem as fast as possible
-(unlike Python, Ruby, Java etc)
+\bigskip\bigskip
+
+\ldots and the point of the this lecture is to decide this problem as
+fast as possible (unlike Python, Ruby, Java etc)
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -443,7 +443,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Another Homework\\[-2mm] Question}
+\frametitle{Another Homework Question}
\begin{itemize}
\item How many basic regular expressions are there to match
Binary file slides/slides03.pdf has changed
Binary file slides/slides04.pdf has changed
Binary file slides/slides05.pdf has changed
Binary file slides/slides06.pdf has changed
Binary file slides/slides07.pdf has changed
Binary file slides/slides08.pdf has changed
Binary file slides/slides09.pdf has changed
Binary file slides/slides10.pdf has changed
Binary file slides/slides11.pdf has changed
--- a/slides/slides11.tex Tue Jul 30 23:44:56 2019 +0100
+++ b/slides/slides11.tex Wed Sep 25 11:24:34 2019 +0100
@@ -360,7 +360,7 @@
\begin{textblock}{11}(1,4.4)
\begin{center}
\begin{bubble}[10.9cm]\small\centering
- \includegraphics[scale=0.37]{msbug.png}
+ \includegraphics[scale=0.37]{../pics/msbug.png}
\end{bubble}
\end{center}
\end{textblock}}
Binary file slides/slides12.pdf has changed