# HG changeset patch # User Christian Urban # Date 1380543496 -3600 # Node ID 25999de692b2fd363e024bb77b16a9a7e885c77b # Parent 010ae7288327cd8e6aaa2d0786c3758877944b92 added slides diff -r 010ae7288327 -r 25999de692b2 progs/app6.scala --- 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)) +} + diff -r 010ae7288327 -r 25999de692b2 progs/re1.scala --- a/progs/re1.scala Fri Sep 27 15:43:25 2013 +0100 +++ b/progs/re1.scala Mon Sep 30 13:18:16 2013 +0100 @@ -1,4 +1,5 @@ - +import scala.language.implicitConversions + abstract class Rexp case object NULL extends Rexp diff -r 010ae7288327 -r 25999de692b2 slides/beamerthemeplaincu.sty --- a/slides/beamerthemeplaincu.sty Fri Sep 27 15:43:25 2013 +0100 +++ b/slides/beamerthemeplaincu.sty Mon Sep 30 13:18:16 2013 +0100 @@ -23,6 +23,9 @@ %%\renewcommand\ttdefault{lmtt} + + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % comic fonts fonts %\DeclareFontFamily{T1}{comic}{}% diff -r 010ae7288327 -r 25999de692b2 slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 010ae7288327 -r 25999de692b2 slides/slides02.tex --- 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{ \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{ +\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{ -\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{ \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{ \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{ +\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{ \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{ -\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{ -\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}}}