37 |
37 |
38 \normalsize |
38 \normalsize |
39 \begin{center} |
39 \begin{center} |
40 \begin{tabular}{ll} |
40 \begin{tabular}{ll} |
41 Email: & christian.urban at kcl.ac.uk\\ |
41 Email: & christian.urban at kcl.ac.uk\\ |
42 Office: & N7.07 (North Wing, Bush House)\\ |
42 Office: & N\liningnums{7.07} (North Wing, Bush House)\\ |
43 Slides: & KEATS |
43 Slides: & KEATS |
44 \end{tabular} |
44 \end{tabular} |
45 \end{center} |
45 \end{center} |
46 |
46 |
47 \end{frame} |
47 \end{frame} |
48 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
48 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
49 |
49 |
50 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
50 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
51 \begin{frame}[c] |
51 \begin{frame}[t] |
52 \frametitle{The Goal of this Course} |
52 \frametitle{Why Study Compilers?} |
53 |
53 |
54 \begin{center} |
54 John Regehr {\small(LLVM compiler hacker)}\smallskip\\ |
55 \begin{tikzpicture}[scale=1, |
55 |
56 node/.style={ |
56 \begin{bubble}[10.5cm] |
57 rectangle,rounded corners=3mm, |
57 \bf ``\ldots{}It’s effectively a perpetual |
58 very thick,draw=black!50,minimum height=18mm, minimum width=20mm, |
58 employment act for solid compiler hackers.'' |
59 top color=white,bottom color=black!20}] |
|
60 |
|
61 \node at (3.05, 1.8) {\Large\bf Write A Compiler}; |
|
62 |
|
63 \node (0) at (-2.3,0) {}; |
|
64 |
|
65 \node (A) at (0,0) [node] {}; |
|
66 \node [below right] at (A.north west) {lexer}; |
|
67 |
|
68 \node (B) at (3,0) [node] {}; |
|
69 \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; |
|
70 |
|
71 \node (C) at (6,0) [node] {}; |
|
72 \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; |
|
73 |
|
74 \node (1) at (8.4,0) {}; |
|
75 |
|
76 \draw [->,line width=4mm] (0) -- (A); |
|
77 \draw [->,line width=4mm] (A) -- (B); |
|
78 \draw [->,line width=4mm] (B) -- (C); |
|
79 \draw [->,line width=4mm] (C) -- (1); |
|
80 \end{tikzpicture} |
|
81 \end{center} |
|
82 |
|
83 \only<2,3>{ |
|
84 \begin{textblock}{1}(1,2) |
|
85 \begin{bubble}[9.8cm] |
|
86 \normalsize |
|
87 lexer input: a string\smallskip\\ |
|
88 \hspace{5mm}\code{"read(n);"}\medskip\\ |
|
89 lexer output: a sequence of tokens\smallskip\\ |
|
90 \hspace{5mm}\code{key(read); lpar; id(n); rpar; semi} |
|
91 \end{bubble} |
59 \end{bubble} |
92 \end{textblock}} |
60 |
93 |
61 \onslide<1->{ |
|
62 \only<2>{ |
|
63 \begin{itemize} |
|
64 \item {\bf Hardware is getting weirder |
|
65 rather than getting clocked faster} |
|
66 |
|
67 \begin{itemize} |
|
68 \item Almost all processors are |
|
69 multicores nowadays and it looks like there is increasing asymmetry in |
|
70 resources across cores. Processors come with vector units, crypto |
|
71 accelerators etc. We have DSPs, GPUs, |
|
72 ARM big.little, and Xeon Phi. This is only scratching the |
|
73 surface. |
|
74 \end{itemize} |
|
75 \end{itemize}} |
94 \only<3>{ |
76 \only<3>{ |
95 \begin{textblock}{1}(6,7.8) |
77 \begin{itemize} |
96 \begin{tabular}{c} |
78 \item {\bf We’re getting tired of low-level languages and |
97 \includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm] |
79 their associated security disasters} |
98 \footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta) |
80 |
99 \end{tabular} |
81 \begin{itemize} |
100 \end{textblock}} |
82 \item |
101 |
83 We want to write new code, to |
102 \only<4>{ |
84 whatever extent possible, in safer, higher-level |
103 \begin{textblock}{1}(1,1.5) |
85 languages. Compilers are caught right in the middle of these |
104 \begin{bubble}[8.5cm] |
86 opposing trends: one of their main jobs is to help bridge the large |
105 \normalsize |
87 and growing gap between increasingly high-level languages and |
106 parser input: a sequence of token\smallskip\\ |
88 increasingly wacky platforms. |
107 parser output: an abstract syntax tree\smallskip\\ |
89 \end{itemize} |
108 \footnotesize |
90 \end{itemize}}} |
109 \hspace{2cm}\begin{tikzpicture} |
91 |
110 \node {\code{read}} |
92 \end{frame} |
111 child {node {\code{lpar}}} |
93 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
112 child {node {\code{n}}} |
|
113 child {node {\code{rpar}}}; |
|
114 \end{tikzpicture} |
|
115 \end{bubble} |
|
116 \end{textblock}} |
|
117 |
|
118 \only<5,6>{ |
|
119 \begin{textblock}{1}(1,1.5) |
|
120 \begin{bubble}[4cm] |
|
121 \normalsize |
|
122 code generator:\smallskip\\ |
|
123 \hspace{5mm}\code{istore 2}\\ |
|
124 \hspace{5mm}\code{iload 2}\\ |
|
125 \hspace{5mm}\code{ldc 10}\\ |
|
126 \hspace{5mm}\code{isub}\\ |
|
127 \hspace{5mm}\code{ifeq Label2}\\ |
|
128 \hspace{5mm}\code{iload 2}\\ |
|
129 \hspace{5mm}\code{...}\\ |
|
130 \end{bubble} |
|
131 \end{textblock}} |
|
132 |
|
133 \only<6>{ |
|
134 \begin{textblock}{6}(8.4,7) |
|
135 \begin{bubble}[5cm] |
|
136 \mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm] |
|
137 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
|
138 xlabel=n, |
|
139 enlargelimits=0.05, |
|
140 ybar interval=0.7, legend style=small] |
|
141 \addplot file {interpreted2.data}; |
|
142 \addplot file {compiled2.data}; |
|
143 %\legend{interpreted, compiled} |
|
144 \end{axis} |
|
145 \end{tikzpicture}} |
|
146 \end{bubble} |
|
147 \end{textblock}} |
|
148 |
|
149 \end{frame} |
|
150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
151 |
|
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
153 \begin{frame}[c] |
|
154 \frametitle{The subject is quite old} |
|
155 |
|
156 \begin{itemize} |
|
157 \item Turing Machines, 1936 |
|
158 \item Regular Expressions, 1956\\ |
|
159 \item The first compiler for COBOL, 1957\\ (Grace Hopper) |
|
160 \item But surprisingly research papers are still published nowadays |
|
161 \end{itemize} |
|
162 |
|
163 \begin{flushright} |
|
164 \includegraphics[scale=0.3]{pics/hopper.jpg}\\ |
|
165 \footnotesize\textcolor{gray}{Grace Hopper} |
|
166 \end{flushright} |
|
167 |
|
168 \mbox{}\\[-10mm] |
|
169 {\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show, \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}} |
|
170 |
|
171 \end{frame} |
|
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
173 |
94 |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
95 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
175 \begin{frame}[c] |
96 \begin{frame}[c] |
176 \frametitle{Why Bother?} |
97 \frametitle{Why Bother?} |
177 |
98 |
178 \begin{columns}[t] |
99 \begin{columns}[t] |
179 \begin{column}{.5\textwidth} |
100 \begin{column}{.5\textwidth} |
180 Ruby, Python, Java\medskip\\ |
101 Ruby, Python, Java 8\medskip\\ |
181 \begin{tikzpicture}\footnotesize |
102 \begin{tikzpicture}\footnotesize |
182 \begin{axis}[ |
103 \begin{axis}[ |
183 xlabel={$n$}, |
104 xlabel={$n$}, |
184 x label style={at={(1.05,0.0)}}, |
105 x label style={at={(1.05,0.0)}}, |
185 ylabel={time in secs}, |
106 ylabel={time in secs}, |
258 \end{tikzpicture} |
180 \end{tikzpicture} |
259 \end{column} |
181 \end{column} |
260 \end{columns}\bigskip |
182 \end{columns}\bigskip |
261 |
183 |
262 \small\centering |
184 \small\centering |
263 matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{[a*]*b} |
185 matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{(a*)*b} |
264 against $\underbrace{\texttt{a}...\texttt{a}}_n$ |
186 against $\underbrace{\texttt{a}...\texttt{a}}_n$ |
265 \end{frame} |
187 \end{frame} |
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
189 |
|
190 |
|
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
192 \begin{frame}[c] |
|
193 \frametitle{The Goal of this Module} |
|
194 |
|
195 \begin{center} |
|
196 \begin{tikzpicture}[scale=1, |
|
197 node/.style={ |
|
198 rectangle,rounded corners=3mm, |
|
199 very thick,draw=black!50,minimum height=18mm, minimum width=20mm, |
|
200 top color=white,bottom color=black!20}] |
|
201 |
|
202 \node at (3.05, 1.8) {\Large\bf Write a compiler}; |
|
203 |
|
204 \node (0) at (-2.3,0) {}; |
|
205 |
|
206 \node (A) at (0,0) [node] {}; |
|
207 \node [below right] at (A.north west) {lexer}; |
|
208 |
|
209 \node (B) at (3,0) [node] {}; |
|
210 \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; |
|
211 |
|
212 \node (C) at (6,0) [node] {}; |
|
213 \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; |
|
214 |
|
215 \node (1) at (8.4,0) {}; |
|
216 |
|
217 \draw [->,line width=4mm] (0) -- (A); |
|
218 \draw [->,line width=4mm] (A) -- (B); |
|
219 \draw [->,line width=4mm] (B) -- (C); |
|
220 \draw [->,line width=4mm] (C) -- (1); |
|
221 \end{tikzpicture} |
|
222 \end{center} |
|
223 |
|
224 \only<2,3,4>{ |
|
225 \begin{textblock}{1}(1,2.1) |
|
226 \begin{bubble}[9.8cm] |
|
227 \normalsize |
|
228 lexer input: a string\smallskip\\ |
|
229 \hspace{5mm}\code{"read(n);"}\medskip\\ |
|
230 lexer output: a sequence of tokens\smallskip\\ |
|
231 \hspace{5mm}\code{key(read) lpar id(n) rpar semi} |
|
232 \end{bubble} |
|
233 \end{textblock}} |
|
234 |
|
235 \only<3,4>{ |
|
236 \begin{textblock}{1}(6,7.8) |
|
237 \begin{tabular}{c} |
|
238 \includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm] |
|
239 \footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta) |
|
240 \end{tabular} |
|
241 \end{textblock}} |
|
242 |
|
243 \only<4>{ |
|
244 \begin{textblock}{1}(0.5,12)\small |
|
245 \begin{tabular}{l@{}c@{}l} |
|
246 \pcode{if} & $\;\Rightarrow\;$ & keyword\\ |
|
247 \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\ |
|
248 \end{tabular} |
|
249 \end{textblock}} |
|
250 |
|
251 \only<5>{ |
|
252 \begin{textblock}{1}(1,1.5) |
|
253 \begin{bubble}[8.5cm] |
|
254 \normalsize |
|
255 parser input: a sequence of tokens\smallskip\\ |
|
256 |
|
257 {\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\ |
|
258 |
|
259 parser output: an abstract syntax tree\smallskip\\ |
|
260 \footnotesize |
|
261 \hspace{2cm}\begin{tikzpicture} |
|
262 \node {\code{read}} |
|
263 child {node {\code{lpar}}} |
|
264 child {node {\code{n}}} |
|
265 child {node {\code{rpar}}}; |
|
266 \end{tikzpicture} |
|
267 \end{bubble} |
|
268 \end{textblock}} |
|
269 |
|
270 \only<6,7>{ |
|
271 \begin{textblock}{1}(1,1.5) |
|
272 \begin{bubble}[4cm] |
|
273 \normalsize |
|
274 code generator:\smallskip\\ |
|
275 \hspace{5mm}\code{istore 2}\\ |
|
276 \hspace{5mm}\code{iload 2}\\ |
|
277 \hspace{5mm}\code{ldc 10}\\ |
|
278 \hspace{5mm}\code{isub}\\ |
|
279 \hspace{5mm}\code{ifeq Label2}\\ |
|
280 \hspace{5mm}\code{iload 2}\\ |
|
281 \hspace{5mm}\code{...}\\ |
|
282 \end{bubble} |
|
283 \end{textblock}} |
|
284 |
|
285 \only<7>{ |
|
286 \begin{textblock}{6}(8.4,7) |
|
287 \begin{bubble}[5cm] |
|
288 \mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm] |
|
289 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, |
|
290 xlabel=n, |
|
291 enlargelimits=0.05, |
|
292 ybar interval=0.7, legend style=small] |
|
293 \addplot file {interpreted2.data}; |
|
294 \addplot file {compiled2.data}; |
|
295 %\legend{interpreted, compiled} |
|
296 \end{axis} |
|
297 \end{tikzpicture}} |
|
298 \end{bubble} |
|
299 \end{textblock}} |
|
300 |
|
301 \end{frame} |
|
302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
303 |
|
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
305 \begin{frame}[c] |
|
306 \frametitle{The Acad.~Subject is Mature} |
|
307 |
|
308 \begin{itemize} |
|
309 \item Turing Machines, 1936 |
|
310 \item Regular Expressions, 1956\\ |
|
311 \item The first compiler for COBOL, 1957\\ (Grace Hopper) |
|
312 \item But surprisingly research papers are still published nowadays\\ |
|
313 \item ``Parsing: The Solved Problem That Isn't'' |
|
314 \end{itemize} |
|
315 |
|
316 \begin{flushright} |
|
317 \includegraphics[scale=0.3]{pics/hopper.jpg}\\ |
|
318 \footnotesize\textcolor{gray}{Grace Hopper} |
|
319 \end{flushright} |
|
320 |
|
321 |
|
322 \begin{flushright} |
|
323 \mbox{}\\[-6mm] |
|
324 {\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show,\\[-2mm] |
|
325 \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}} |
|
326 \end{flushright} |
|
327 |
|
328 \end{frame} |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 |
267 |
331 |
268 |
332 |
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
333 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
270 \begin{frame}[c] |
334 \begin{frame}[c] |
271 \frametitle{Lectures 1 - 5} |
335 \frametitle{Lectures 1 - 5} |
699 \begin{column}{.5\textwidth} |
765 \begin{column}{.5\textwidth} |
700 \underline{\bf Strand 1}\medskip |
766 \underline{\bf Strand 1}\medskip |
701 \begin{itemize} |
767 \begin{itemize} |
702 \item four programming tasks: |
768 \item four programming tasks: |
703 \begin{itemize} |
769 \begin{itemize} |
704 \item matcher (4\%, 19.10.) |
770 \item matcher (4\%, 12.10.) |
705 \item lexer (5\%, 03.11.) |
771 \item lexer (5\%, 02.11.) |
706 \item parser (5\%, 23.11.) |
772 \item parser (5\%, 23.11.) |
707 \item compiler (6\%, 7.12.) |
773 \item compiler (6\%, 14.12.) |
708 \end{itemize} |
774 \end{itemize} |
|
775 \item in any lang.~you like,\\ but I want to see the code |
709 \end{itemize} |
776 \end{itemize} |
710 \end{column} |
777 \end{column} |
711 |
778 |
712 \hspace{-45pt}\vrule{}\hspace{10pt} |
779 \hspace{-45pt}\vrule{}\hspace{10pt} |
713 \begin{column}{.5\textwidth} |
780 \begin{column}{.5\textwidth} |
714 \underline{\bf Strand 2}\smallskip\begin{itemize} |
781 \underline{\bf Strand 2}\smallskip\begin{itemize} |
715 \item one task: prove the correctness of a regular expression matcher in |
782 \item one task: prove the correctness of a regular expression matcher in |
716 the Isabelle theorem prover |
783 the \underline{Isabelle} theorem prover |
717 \item 20\%, submission 7.12. |
784 \item 20\%, submission on~14.12.\hspace{-5mm}\mbox{} |
718 \end{itemize} |
785 \end{itemize} |
719 \end{column} |
786 \end{column} |
720 \end{columns}\medskip |
787 \end{columns}\medskip |
721 |
788 |
722 \small |
789 \small |