--- a/progs/app6.scala Fri Sep 27 15:43:25 2013 +0100
+++ b/progs/app6.scala Mon Sep 30 13:18:16 2013 +0100
@@ -1,11 +1,16 @@
-def deriv (r: Rexp, c: Char) : Rexp = r match {
+def der (r: Rexp, c: Char) : Rexp = r match {
case NULL => NULL
case EMPTY => NULL
case CHAR(d) => if (c == d) EMPTY else NULL
- case ALT(r1, r2) => ALT(deriv(r1, c), deriv(r2, c))
+ case ALT(r1, r2) => ALT(der(r1, c), der(r2, c))
case SEQ(r1, r2) =>
- if (nullable(r1)) ALT(SEQ(deriv(r1, c), r2), deriv(r2, c))
- else SEQ(deriv(r1, c), r2)
- case STAR(r) => SEQ(deriv(r, c), STAR(r))
+ if (nullable(r1)) ALT(SEQ(der(r1, c), r2), der(r2, c))
+ else SEQ(der(r1, c), r2)
+ case STAR(r) => SEQ(der(r, c), STAR(r))
}
+def ders (s: List[Char], r: Rexp) : Rexp = s match {
+ case Nil => r
+ case c::s => ders(s, der(c, r))
+}
+
--- a/slides/slides02.tex Fri Sep 27 15:43:25 2013 +0100
+++ b/slides/slides02.tex Mon Sep 30 13:18:16 2013 +0100
@@ -1,6 +1,6 @@
\documentclass[dvipsnames,14pt,t]{beamer}
-\usepackage{beamerthemeplainculight}
-\usepackage[T1]{fontenc}
+\usepackage{beamerthemeplaincu}
+%%\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{mathpartir}
\usepackage[absolute,overlay]{textpos}
@@ -17,6 +17,7 @@
\usetikzlibrary{shapes}
\usetikzlibrary{shadows}
\usetikzlibrary{positioning}
+\usetikzlibrary{plotmarks}
\usetikzlibrary{calc}
\usepackage{graphicx}
@@ -25,8 +26,13 @@
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
+\makeatletter
+\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
+\@empty\z@\@empty
+\makeatother
+
\lstset{language=Java,
- basicstyle=\ttfamily,
+ basicstyle=\consolas,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
@@ -47,7 +53,7 @@
private,protected,requires,return,sealed,%
super,this,throw,trait,true,try,%
type,val,var,while,with,yield},
- otherkeywords={=>,<-,<\%,<:,>:,\#,@},
+ otherkeywords={=>,<-,<\%,<:,>:,\#,@,->},
sensitive=true,
morecomment=[l]{//},
morecomment=[n]{/*}{*/},
@@ -57,7 +63,7 @@
}
\lstset{language=Scala,
- basicstyle=\ttfamily,
+ basicstyle=\consolas,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
@@ -71,10 +77,64 @@
showstringspaces=false}
% beamer stuff
-\renewcommand{\slidecaption}{AFL 02, King's College London, 3.~October 2012}
+\renewcommand{\slidecaption}{AFL 02, King's College London, 2.~October 2013}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+% The data files, written on the first run.
+\begin{filecontents}{re-python.data}
+1 0.029
+5 0.029
+10 0.029
+15 0.032
+16 0.042
+17 0.042
+18 0.055
+19 0.084
+20 0.136
+21 0.248
+22 0.464
+23 0.899
+24 1.773
+25 3.505
+26 6.993
+27 14.503
+28 29.307
+#29 58.886
+\end{filecontents}
+
+\begin{filecontents}{re-ruby.data}
+1 0.00006
+2 0.00003
+3 0.00001
+4 0.00001
+5 0.00001
+6 0.00002
+7 0.00002
+8 0.00004
+9 0.00007
+10 0.00013
+11 0.00026
+12 0.00055
+13 0.00106
+14 0.00196
+15 0.00378
+16 0.00764
+17 0.01606
+18 0.03094
+19 0.06508
+20 0.12420
+21 0.25393
+22 0.51449
+23 1.02174
+24 2.05998
+25 4.22514
+26 8.42479
+27 16.88678
+28 34.79653
+\end{filecontents}
+
+
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -97,7 +157,7 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Of$\!$fice: & S1.27 (1st floor Strand Building)\\
+ Office: & S1.27 (1st floor Strand Building)\\
Slides: & KEATS
\end{tabular}
\end{center}
@@ -113,7 +173,7 @@
A \alert{language} is a set of strings.\bigskip
-A \alert{regular expression} specifies a set of strings or language.
+A \alert{regular expression} specifies a set of strings, or language.
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -121,15 +181,43 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Strings\end{tabular}}
+
+Different ways of writing strings:
+
+\begin{center}
+\begin{tabular}{ccc}
+\bl{\consolas"$hello$"}\quad{} & \bl{$[h, e, l, l, o]$} & \quad\bl{$h\!::\!e\!::\!l\!::\!l\!::\!o\!::\!N\!il$}\bigskip\\
+\bl{\consolas ""} & \bl{$[]$} & \bl{$N$\!$il$}
+\end{tabular}
+\end{center}\pause
+
+The concatenation operation on strings and sets of strings:
+
+\begin{center}
+\begin{tabular}{l}
+\bl{{\consolas"$f\!oo$"}$\;@\;${\consolas"$bar$"}$\;=\;${\consolas"$f\!oobar$"}}\medskip\\
+\bl{$A \;@\; B \dn \{ s_1 @ s_2 \mid s_1 \in A \wedge s_2 \in B\}$}
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
Their inductive definition:
-\begin{textblock}{6}(2,5)
+\begin{textblock}{6}(2,6.5)
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
\bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\
- & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\
+ & \bl{$\mid$} & \bl{$\epsilon$} & empty string / {\consolas""} / $[]$\\
& \bl{$\mid$} & \bl{c} & character\\
& \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\
& \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\
@@ -137,25 +225,23 @@
\end{tabular}
\end{textblock}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
-
-Their implementation in Scala:
-
-{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{app51.scala}}}
-
+
+\only<2->{
+\begin{textblock}{9}(4,0.5)
+\begin{tikzpicture}
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\normalsize\color{darkgray}
+\begin{minipage}{9cm}
+\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{../progs/app51.scala}}}}
+\end{minipage}};
+\end{tikzpicture}
+\end{textblock}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
@@ -163,31 +249,25 @@
\begin{textblock}{15}(1,4)
\begin{tabular}{@ {}rcl}
- \bl{$L$($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$}\\
- \bl{$L$($\epsilon$)} & \bl{$\dn$} & \bl{$\{$""$\}$}\\
- \bl{$L$(c)} & \bl{$\dn$} & \bl{$\{$"c"$\}$}\\
- \bl{$L$(r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{$L$(r$_1$) $\cup$ $L$(r$_2$)}\\
- \bl{$L$(r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{$L$(r$_1$) @ $L$(r$_2$)}\\
- \bl{$L$(r$^*$)} & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}\\
+ \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\
+ \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{$""$\}$}\\
+ \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{"c"\}$}\\
+ \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
+ \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\
\end{tabular}\bigskip
-\hspace{5mm}\textcolor{gray}{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\
-\textcolor{gray}{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$}
+\only<2->{
+\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{""\}$}\\
+\textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}}
\end{textblock}
-\only<2->{
-\begin{textblock}{5}(11,5)
-\textcolor{gray}{\small
-A @ B\\
-\ldots you take out every string from A and
-concatenate it with every string in B
-}
-\end{textblock}}
+
-\only<3->{
+\only<1->{
\begin{textblock}{6}(9,12)\small
\bl{$L$} is a function from regular expressions to sets of strings\\
-\bl{$L$ : Rexp $\Rightarrow$ Set[String]}
+\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
\end{textblock}}
@@ -200,7 +280,7 @@
\large
\begin{center}
-What is \bl{$L$(a$^*$)}?
+What is \bl{$L(a^*)$}?
\end{center}
\end{frame}}
@@ -218,18 +298,18 @@
\begin{center}
\begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l}
-&\bl{(a + b) + c} & \bl{$\equiv^?$} & \bl{a + (b + c)} & \onslide<2->{\YES}\\
-&\bl{a + a} & \bl{$\equiv^?$} & \bl{a} & \onslide<3->{\YES}\\
-&\bl{(a $\cdot$ b) $\cdot$ c} & \bl{$\equiv^?$} & \bl{a $\cdot$ (b $\cdot$ c)} & \onslide<4->{\YES}\\
-&\bl{a $\cdot$ a} & \bl{$\equiv^?$} & \bl{a} & \onslide<5->{\NO}\\
+&\bl{$(a + b) + c$} & \bl{$\equiv^?$} & \bl{$a + (b + c)$} & \onslide<2->{\YES}\\
+&\bl{$a + a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<3->{\YES}\\
+&\bl{$(a \cdot b) \cdot c$} & \bl{$\equiv^?$} & \bl{$a \cdot (b \cdot c)$} & \onslide<4->{\YES}\\
+&\bl{$a \cdot a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<5->{\NO}\\
&\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\
&\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\
-\FORALLR &\bl{r $\cdot$ $\epsilon$} & \bl{$\equiv^?$} & \bl{r} & \onslide<8->{\YES}\\
-\FORALLR &\bl{r + $\epsilon$} & \bl{$\equiv^?$} & \bl{r} & \onslide<9->{\NO}\\
-\FORALLR &\bl{r + $\varnothing$} & \bl{$\equiv^?$} & \bl{r} & \onslide<10->{\YES}\\
-\FORALLR &\bl{r $\cdot$ $\varnothing$} & \bl{$\equiv^?$} & \bl{r} & \onslide<11->{\NO}\\
-&\bl{c $\cdot$ (a + b)} & \bl{$\equiv^?$} & \bl{(c $\cdot$ a) + (c $\cdot$ b)} & \onslide<12->{\YES}\\
-&\bl{a$^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$ + (a $\cdot$ a$^*$)} & \onslide<13->{\YES}
+\FORALLR &\bl{$r \cdot \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<8->{\YES}\\
+\FORALLR &\bl{$r + \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<9->{\NO}\\
+\FORALLR &\bl{$r + \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<10->{\YES}\\
+\FORALLR &\bl{$r \cdot \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<11->{\NO}\\
+&\bl{$c \cdot (a + b)$} & \bl{$\equiv^?$} & \bl{$(c \cdot a) + (c \cdot b)$} & \onslide<12->{\YES}\\
+&\bl{$a^*$} & \bl{$\equiv^?$} & \bl{$\epsilon + (a \cdot a^*)$} & \onslide<13->{\YES}
\end{tabular}
\end{center}
@@ -239,7 +319,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Meaning of Matching\end{tabular}}
+\frametitle{\begin{tabular}{c}The Specification\\[-1mm] of Matching\end{tabular}}
\large
a regular expression \bl{r} matches a string \bl{s} is defined as
@@ -248,8 +328,51 @@
\bl{s $\in$ $L$(r)}\\
\end{center}\bigskip\bigskip\pause
-\small
-if \bl{r$_1$ $\equiv$ r$_2$}, then \bl{$s$ $\in$ $L$(r$_1$)} iff \bl{$s$ $\in$ $L$(r$_2$)}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
+
+\mbox{}\\[-13mm]
+
+\begin{tikzpicture}[y=.2cm, x=.3cm]
+ %axis
+ \draw (0,0) -- coordinate (x axis mid) (30,0);
+ \draw (0,0) -- coordinate (y axis mid) (0,30);
+ %ticks
+ \foreach \x in {0,5,...,30}
+ \draw (\x,1pt) -- (\x,-3pt)
+ node[anchor=north] {\x};
+ \foreach \y in {0,5,...,30}
+ \draw (1pt,\y) -- (-3pt,\y)
+ node[anchor=east] {\y};
+ %labels
+ \node[below=0.6cm] at (x axis mid) {\bl{a}s};
+ \node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+
+ %plots
+ \draw[color=blue] plot[mark=*, mark options={fill=white}]
+ file {re-python.data};
+ \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
+ file {re1.data};
+ \draw[color=green] plot[mark=square*, mark options={fill=white} ]
+ file {re2.data};
+ \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
+ file {re-ruby.data};
+
+ %legend
+ \begin{scope}[shift={(4,20)}]
+ \draw[color=blue] (0,0) --
+ plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Python};
+ \draw[yshift=-\baselineskip, color=brown] (0,0) --
+ plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+ node[right]{\small Ruby};
+ \end{scope}
+\end{tikzpicture}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -259,21 +382,31 @@
\begin{frame}[t]
\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}
-\begin{itemize}
-\item given a regular expression \bl{r} and a string \bl{s}, say yes or no for whether
+\small
+\ldots{}whether a regular expression can match the empty string:
\begin{center}
-\bl{s $\in$ $L$(r)}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+\bl{$nullable(\varnothing)$} & \bl{$\dn$} & \bl{$f\!\/alse$}\\
+\bl{$nullable(\epsilon)$} & \bl{$\dn$} & \bl{$true$}\\
+\bl{$nullable (c)$} & \bl{$\dn$} & \bl{$f\!alse$}\\
+\bl{$nullable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\
+\bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\
+\bl{$nullable (r^*)$} & \bl{$\dn$} & \bl{$true$} \\
+\end{tabular}
\end{center}
-or not.\bigskip\bigskip\pause
-\end{itemize}\pause
-\small
-\begin{itemize}
-\item Identifiers (strings of letters or digits, starting with a letter)
-\item Integers (a non-empty sequence of digits)
-\item Keywords (else, if, while, \ldots)
-\item White space (a non-empty sequence of blanks, newlines and tabs)
-\end{itemize}
+\only<2->{
+\begin{textblock}{9}(3.4,10)
+\begin{tikzpicture}
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\normalsize\color{darkgray}
+\begin{minipage}{9cm}
+\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{../progs/app5.scala}}}}
+\end{minipage}};
+\end{tikzpicture}
+\end{textblock}}
+
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -281,30 +414,13 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}
-
-\small
-whether a regular expression matches the empty string:\medskip
-
-
-{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{app5.scala}}}
-
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}
\large
If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip
\small
-\bl{der c r} gives the answer
+\bl{$der\,c\,r$} gives the answer
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -315,34 +431,31 @@
\begin{center}
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
- \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\
- \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\
- \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then $\epsilon$ else $\varnothing$} & \\
- \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\
- \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{if nullable r$_1$}\\
- & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\
- & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\
- \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)} &\smallskip\\\pause
+ \bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\
+ \bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\
+ \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\
+ \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
+ \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
+ & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\
+ & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
+ \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause
- \bl{ders [] r} & \bl{$\dn$} & \bl{r} & \\
- \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\
+ \bl{$der\!s\, [] r$} & \bl{$\dn$} & \bl{$r$} & \\
+ \bl{$der\!s\, (c\!::\!s) r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
\end{tabular}
\end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Derivative\end{tabular}}
-
-
-{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{app6.scala}}}
-
-
+\only<3->{
+\begin{textblock}{10.5}(2,5)
+\begin{tikzpicture}
+\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
+{\normalsize\color{darkgray}
+\begin{minipage}{10.5cm}
+\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{../progs/app6.scala}}}}
+\end{minipage}};
+\end{tikzpicture}
+\end{textblock}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -354,7 +467,7 @@
{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{app7.scala}}}
+\texttt{\lstinputlisting{../progs/app7.scala}}}