ghc-dup: 15cd3dce353af880f9e9ed8601e53240132d73eb
1: \documentclass{beamer}
2:
3:
4: \newcommand{\hide}{\onslide+<+(1)->}
5:
6: \usepackage[utf8]{inputenc}
7: \usepackage[TS1,T1]{fontenc}
8: \usepackage[english]{babel}
9: \usepackage{listings}
10: \usepackage{xcolor}
11: \usepackage{tikz}
12: \usetikzlibrary{backgrounds}
13: \usepackage{mathpartir}
14:
15: \usetheme[titlepage0]{KIT}
16:
17:
18: \definecolor{light-gray}{gray}{0.95}
19: \lstdefinestyle{haskell}{
20: ,columns=flexible
21: ,basewidth={.365em}
22: ,keepspaces=True
23: ,belowskip=0pt
24: ,backgroundcolor=\color{light-gray}
25: ,frame=single
26: ,xleftmargin=2em
27: ,xrightmargin=2em
28: ,basicstyle=\small\sffamily
29: ,stringstyle=\itshape
30: ,language=Haskell
31: ,texcl=true
32: ,showstringspaces=false
33: ,keywords={module,where,import,data,let,in,case,of}
34: }
35: \lstnewenvironment{haskell}{\lstset{style=haskell}}{}
36:
37:
38: \title{dup -- Explicit un-sharing in Haskell}
39: \subtitle{Haskell Implementors Workshop 2012 -- Lightning Talk}
40: \KITtitleimage[page=3,viewport=190 110 550 400]{dup-hiw-2012}
41: \author{Joachim Breitner}
42: \date{2012-09-14}
43: \iflanguage{ngerman}{%
44: \institute{LEHRSTUHL PROGRAMMIERPARADIGMEN}%
45: }{%
46: \institute{PROGRAMMING PARADIGMS GROUP}%
47: }
48:
49:
50: \begin{document}
51:
52: \maketitle
53:
54: \begin{frame}
55: \frametitle{My motivation}
56: \begin{center}
57: \parbox{.5\linewidth}{
58: \centering
59: We need to provide our programmers with better tools to\\[0.5em]
60: \textbf{analyze}\\[0.5em]
61: and\\[0.5em]
62: \textbf{control}\\[0.5em]
63: the space behaviour of their Haskell programs.
64: }
65: \end{center}
66: \end{frame}
67:
68:
69: \begin{frame}[fragile,t]
70: \frametitle{Sharing can cause space leaks}
71:
72: \begin{haskell}
73: let xs = [1..100000000]
74: in (last xs, length xs)
75: \end{haskell}
76: \vfill
77: \hide
78:
79: \centering
80: \begin{tikzpicture}
81: [level/.style={sibling distance=20mm/2^#1,level distance=6mm},
82: every node/.style={circle,inner sep=1.5pt},
83: eval/.style={circle,fill=black,color=black},
84: %every path/.style={->},
85: ]
86: \path
87: (0,0) node (comma) {(,)}
88: (-1,-1) coordinate (ct1)
89: (1,-1) coordinate (ct2)
90: (0,-3) coordinate (clt);
91: \onslide<2>{\node at (ct1) (t1) {T};}
92: \onslide<3-5>{\node[eval] at (ct1) (t1) {:};}
93: \onslide<6->{\node at (ct1) (t1) {1e8};}
94:
95: \onslide<2->{\node at (ct2) (t2) {T};}
96:
97: \onslide<2-3>{\node at (clt) (lt) {T};}
98: \onslide<4->{\node[alias=cons0] at (clt) (lt) {:};}
99: \onslide<4>{
100: \path (cons0) +(0,-1) node (n) {1};
101: \draw (cons0) -- (n);
102: \path (cons0) +(1,0) node (cons1) {T};
103: \draw (cons0) -- (cons1);
104: }
105: \onslide<5->{
106: \onslide<5-7>{
107: \path (cons0) +(0,-1) node (n) {1};
108: \draw (cons0) -- (n);
109: \path (cons0) +(1,0) node (cons1) {:};
110: \draw (cons0) -- (cons1);
111:
112: \path (cons1) +(0,-1) node (n) {2};
113: \draw (cons1) -- (n);
114: \path (cons1) +(1,0) node (cons2) {:};
115: \draw (cons1) -- (cons2);
116:
117: \path (cons2) +(0,-1) node (n) {3};
118: \draw (cons2) -- (n);
119: \path (cons2) +(1,0) node (cons3) {:};
120: \draw (cons2) -- (cons3);
121: }
122:
123: \path (cons3) +(0,-1) node (n) {4};
124: \draw (cons3) -- (n);
125: \onslide<4>{\path (cons3) +(1,0) node (cons4) {T};}
126: \onslide<5->{\path (cons3) +(1,0) node (cons4) {$\cdots$};}
127: \draw (cons3) -- (cons4);
128: }
129: \draw (comma) -- (t1);
130: \draw (comma) -- (t2);
131: \onslide<2-4>{\draw (t1) -- (lt);}
132: \onslide<5>{\draw (t1) -- (cons3);}
133: \draw (t2) -- (lt);
134: \end{tikzpicture}
135:
136: \vfill
137: \onslide<7->{the programmer might want to avoid to have the list shared}
138:
139: \end{frame}
140:
141: \begin{frame}[fragile,t]
142: \frametitle{Source transformations may help}
143:
144: \begin{haskell}
145: let xs () = [1..100000000]
146: in (last $ xs (), length $ xs ())
147: \end{haskell}
148: \vfill
149:
150: \centering
151: \begin{tikzpicture}
152: [level/.style={sibling distance=20mm/2^#1,level distance=6mm},
153: every node/.style={circle,inner sep=1.5pt},
154: eval/.style={circle,fill=black,color=black},
155: %every path/.style={->},
156: ]
157: \path
158: (0,0) node (comma) {(,)}
159: +(-1,-1) coordinate (ct1)
160: +(1,-1) coordinate (ct2)
161: +(0,-2) coordinate (cf);
162: \onslide<1>{\node at (ct1) (t1) {T};}
163: \onslide<2-5>{\node[eval] at (ct1) (t1) {:};}
164: \onslide<6->{\node at (ct1) (t1) {1e8};}
165:
166: \onslide<1->{\node at (ct2) (t2) {T};}
167:
168: \onslide<1->{\node at (cf) (f) {F};}
169: \path (t1) +(1,-2) coordinate (clt);
170: \onslide<3>{\path (clt) node (lt) {T};}
171: \onslide<4>{\node[alias=cons0] at (clt) (lt) {:};}
172: \onslide<5-6>{\node[alias=cons0,color=gray] at (clt) (lt) {:};}
173: \onslide<4>{
174: \path (cons0) +(0,-1) node (n) {1};
175: \draw (cons0) -- (n);
176: \path (cons0) +(1,0) node (cons1) {T};
177: \draw (cons0) -- (cons1);
178: }
179: \onslide<5-6>{
180: \begin{scope}[color=gray]
181: \path (cons0) +(0,-1) node (n) {1};
182: \draw (cons0) -- (n);
183: \path (cons0) +(1,0) node (cons1) {:};
184: \draw (cons0) -- (cons1);
185:
186: \path (cons1) +(0,-1) node (n) {2};
187: \draw (cons1) -- (n);
188: \path (cons1) +(1,0) node (cons2) {:};
189: \draw (cons1) -- (cons2);
190:
191: \path (cons2) +(0,-1) node (n) {3};
192: \draw (cons2) -- (n);
193: \end{scope}
194:
195: \onslide<5>{
196: \path (cons2) +(1,0) node (cons3) {:};
197: \draw[color=gray] (cons2) -- (cons3);
198: \path (cons3) +(0,-1) node (n) {4};
199: \draw (cons3) -- (n);
200: \path (cons3) +(1,0) node (cons4) {T};
201: \draw (cons3) -- (cons4);
202: }
203: \onslide<6->{
204: \begin{scope}[color=gray]
205: \path (cons2) +(1,0) node (cons3) {:};
206: \draw (cons2) -- (cons3);
207: \path (cons3) +(0,-1) node (n) {4};
208: \draw (cons3) -- (n);
209: \path (cons3) +(1,0) node (cons4) {$\cdots$};
210: \draw (cons3) -- (cons4);
211: \end{scope}
212: }
213: }
214: \draw (comma) -- (t1);
215: \draw (comma) -- (t2);
216: \onslide<1-2>{\draw (t1) -- (f);}
217: \onslide<3-4>{\draw (t1) -- (lt);}
218: \onslide<5>{\draw (t1) -- (cons3);}
219: \draw (t2) -- (f);
220: \end{tikzpicture}
221:
222: \vfill
223: \onslide<7->{works, but fragile -- might be thwarted by compiler optimizations}
224:
225: \end{frame}
226:
227: \begin{frame}[fragile,t]
228: \frametitle{Allow the programmer to copy a thunk: dup}
229:
230: \begin{haskell}
231: let xs = [1..100000000]
232: in (case dup xs of Box xs' -> last xs',
233: case dup xs of Box xs' -> length xs')
234: \end{haskell}
235: \vfill
236:
237: \centering
238: \begin{tikzpicture}
239: [level/.style={sibling distance=20mm/2^#1,level distance=6mm},
240: every node/.style={circle,inner sep=1.5pt},
241: eval/.style={circle,fill=black,color=black},
242: %every path/.style={->},
243: ]
244: \path
245: (0,0) node (comma) {(,)}
246: +(-1,-1) coordinate (ct1)
247: +(1,-1) coordinate (ct2)
248: +(0,-2) coordinate (cot);
249: \onslide<1>{\node at (ct1) (t1) {T};}
250: \onslide<2-5>{\node[eval] at (ct1) (t1) {:};}
251: \onslide<6->{\node at (ct1) (t1) {1e8};}
252:
253: \onslide<1->{\node at (ct2) (t2) {T};}
254:
255: \onslide<1->{\node at (cot) (ot) {T};}
256: \path (t1) +(1,-2) coordinate (clt);
257: \onslide<3>{\path (clt) node (lt) {T};
258: \draw[double] (lt) -- (ot);}
259: \onslide<4>{\node[alias=cons0] at (clt) (lt) {:};}
260: \onslide<5-6>{\node[alias=cons0,color=gray] at (clt) (lt) {:};}
261: \onslide<4>{
262: \path (cons0) +(0,-1) node (n) {1};
263: \draw (cons0) -- (n);
264: \path (cons0) +(1,0) node (cons1) {T};
265: \draw (cons0) -- (cons1);
266: }
267: \onslide<5-6>{
268: \begin{scope}[color=gray]
269: \path (cons0) +(0,-1) node (n) {1};
270: \draw (cons0) -- (n);
271: \path (cons0) +(1,0) node (cons1) {:};
272: \draw (cons0) -- (cons1);
273:
274: \path (cons1) +(0,-1) node (n) {2};
275: \draw (cons1) -- (n);
276: \path (cons1) +(1,0) node (cons2) {:};
277: \draw (cons1) -- (cons2);
278:
279: \path (cons2) +(0,-1) node (n) {3};
280: \draw (cons2) -- (n);
281: \end{scope}
282:
283: \onslide<5>{
284: \path (cons2) +(1,0) node (cons3) {:};
285: \draw[color=gray] (cons2) -- (cons3);
286: \path (cons3) +(0,-1) node (n) {4};
287: \draw (cons3) -- (n);
288: \path (cons3) +(1,0) node (cons4) {T};
289: \draw (cons3) -- (cons4);
290: }
291: \onslide<6>{
292: \begin{scope}[color=gray]
293: \path (cons2) +(1,0) node (cons3) {:};
294: \draw (cons2) -- (cons3);
295: \path (cons3) +(0,-1) node (n) {4};
296: \draw (cons3) -- (n);
297: \path (cons3) +(1,0) node (cons4) {$\cdots$};
298: \draw (cons3) -- (cons4);
299: \end{scope}
300: }
301: }
302: \draw (comma) -- (t1);
303: \draw (comma) -- (t2);
304: \onslide<1-2>{\draw (t1) -- (ot);}
305: \onslide<3-4>{\draw (t1) -- (lt);}
306: \onslide<5>{\draw (t1) -- (cons3);}
307: \draw (t2) -- (ot);
308: \end{tikzpicture}
309:
310: \hide
311: \onslide<7->
312: the consumer, not the generator, controls sharing. no code restructuring.
313:
314: \end{frame}
315:
316: \begin{frame}
317: \frametitle{The sledgehammer: deepDup}
318:
319: \begin{columns}[T,onlytextwidth]
320: \begin{column}{.3\linewidth}
321: morally, \lstinline-deepDup x- copies the whole heap reachable by x
322: \end{column}
323: \begin{column}{.3\linewidth}
324: \centering
325: \begin{tikzpicture}
326: [
327: every node/.style={circle,inner sep=1.3pt},
328: eval/.style={circle,fill=black,color=black},
329: %every path/.style={->},
330: ]
331: \path (0,0) node[eval] (eval) {:};
332: \path<1> (0,-1) node (d1) {D};
333: \path (0,-2) node (t1) {T};
334: \path<2> (1,-2) node (t1') {T};
335: \path<3-> (1,-2) node (t1') {C};
336: \path<2-3> (1,-3) node (d2) {D};
337: \path (0,-4) node (comma) {(,)};
338: \path (-1,-5) node (t2) {T};
339: \path (2,-5) node (t3) {T};
340: \path<4-> (1,-4) node (comma') {(,)};
341: \path<4> (0,-4.5) node (d3) {D};
342: \path<4-6> (1.5,-4.5) node (d4) {D};
343: \path<5> (0,-5) node (t2') {C};
344: \path<6-> (0,-5) node (t2') {C};
345: \path<7> (1,-5) node (t3') {T};
346: \path<8-> (1,-5) node (t3') {I};
347:
348: \draw<1> (eval) -- (d1);
349: \draw<1> (d1) -- (t1);
350: \draw (t1) -- (comma);
351: \draw<2-> (eval) -- (t1');
352: \draw<2-3> (t1') -- (d2);
353: \draw<2-3> (d2) -- (comma);
354: \draw<2>[double] (t1) -- (t1');
355: \draw<4-> (t1') -- (comma');
356: \draw (comma) -- (t2);
357: \draw (comma) -- (t3);
358: \draw<4> (comma') -- (d3);
359: \draw<4> (d3) -- (t2);
360: \draw<5-> (comma') -- (t2');
361: \draw<5>[double] (t2) -- (t2');
362: \draw<4-6> (comma') -- (d4);
363: \draw<4-6> (d4) -- (t3);
364: \draw<7-> (comma') -- (t3');
365: \draw<7>[double] (t3) -- (t3');
366:
367: \begin{scope}[on background layer,every path/.style={
368: line width=.7cm, line cap=round, KITgreen50, line join = round
369: }]
370: \draw<1> (eval.center) -- (d1.center);
371: \draw<2-3> (eval.center) -- (t1'.center) -- (d2.center);
372: \draw<4> (eval.center) -- (t1'.center) -- (d2.center) -- (comma'.center) -- (d3.center)
373: (comma'.center) -- (d4.center);
374: \draw<5-6> (eval.center) -- (t1'.center) -- (d2.center) -- (comma'.center) -- (t2'.center)
375: (comma'.center) -- (d4.center);
376: \draw<7-> (eval.center) -- (t1'.center) -- (d2.center) -- (comma'.center) -- (t2'.center)
377: (comma'.center) -- (t3'.center);
378: \end{scope}
379:
380: \path[use as bounding box] (-1.5,-5.5) (2.5,0);
381: \end{tikzpicture}
382: \end{column}
383: \begin{column}{.3\linewidth}
384: \onslide<9>{%
385: really, \lstinline-deepDup x- copies the whole heap reachable by x lazily
386: }
387: \end{column}
388: \end{columns}
389:
390: \end{frame}
391:
392: \newcommand{\mdup}{\text{\textsf{dup}}}
393: \newcommand{\mdeepDup}{\text{\textsf{deepDup}}}
394: \newcommand{\sVar}{\text{Var}}
395: \newcommand{\sExp}{\text{Exp}}
396: \newcommand{\sHeap}{\text{Heap}}
397: \newcommand{\sVal}{\text{Val}}
398: \newcommand{\sValue}{\text{Value}}
399: \newcommand{\sEnv}{\text{Env}}
400: \newcommand{\sApp}[2]{\operatorname{#1}#2}
401: \newcommand{\sLam}[2]{\text{\textlambda} #1.\, #2}
402: \newcommand{\sDup}[1]{\sApp \mdup #1}
403: \newcommand{\sDeepDup}[1]{\sApp \mdeepDup #1}
404: \newcommand{\sLet}[2]{\text{\textsf{let}}\ #1\ \text{\textsf{in}}\ #2}
405: \newcommand{\sred}[4]{#1 : #2 \Downarrow #3 : #4}
406: \newcommand{\sRule}[1]{\text{{\textsc{#1}}}}
407: \newcommand{\fv}[1]{\text{fv}(#1)}
408: \newcommand{\ufv}[1]{\text{ufv}(#1)}
409: \newcommand{\ur}[2]{\text{ur}_{#1}(#2)}
410: \newcommand{\dom}[1]{\text{dom}\,#1}
411: \newcommand{\fresh}[1]{#1'}
412:
413:
414: \begin{frame}
415: \frametitle{Comes with proofs included.}
416:
417: \begin{mathpar}
418: \inferrule
419: {\sred{\Gamma,x\mapsto e, \fresh x\mapsto \hat e} {\fresh x} \Delta z \\ \fresh x \text{ fresh}}
420: {\sred{\Gamma,x\mapsto e}{\sDup x} \Delta z}
421: \sRule{Dup}
422: \end{mathpar}
423: \vfill
424: \begin{mathpar}
425: \inferrule
426: {
427: \sred{
428: \Gamma,
429: x\mapsto e,
430: \begin{array}[b]{l}
431: \fresh x\mapsto \hat e[\fresh y_1/y_1,\ldots, \fresh y_n/y_n],
432: \\
433: \fresh y_1 \mapsto \sDeepDup y_1,\ldots,
434: \fresh y_n \mapsto \sDeepDup y_n
435: \end{array}
436: } {\fresh x} \Delta z
437: \\
438: \ufv e = \{y_1,\ldots,y_n\}
439: \\
440: \fresh x,\ \fresh y_1,\ldots,y_n \text{ fresh}
441: }
442: {\sred{\Gamma,x\mapsto e}{\sDeepDup x} \Delta z}
443: \sRule{Deep}
444: \end{mathpar}
445: \begin{center}
446: \vfill
447: \vfill
448: (based on Launchbury’s „A natural seantics for lazy evaluation“)
449: \end{center}
450: \end{frame}
451: \begin{frame}
452: \frametitle{Where to read more}
453: See\par {\centering\Large \url{http://arxiv.org/abs/1207.2017}\par} for
454: \begin{itemize}
455: \item more motiviation,
456: \item benchmarked comparison with other approaches to avoid sharing,
457: \item semantics and proofs,
458: \item details on the implementation and
459: \item a description of current shortcomings.
460: \end{itemize}
461: \vfill
462: See\par {\centering\Large \url{http://darcs.nomeata.de/ghc-dup}\par} for
463: \begin{itemize}
464: \item the code.
465: \end{itemize}
466:
467: \end{frame}
468:
469:
470: \begin{frame}[fragile]
471: \frametitle{A related, younger idea}
472:
473: \begin{haskell}
474: import GHC.Prim (noupdate)
475:
476: let xs = noupdate [1..100000000]
477: in (last xs, length xs)
478: \end{haskell}
479: \vfill
480:
481: \centering
482: For a thunk wrapped in\\[0.5em]
483: {\Large \lstinline!noupdate :: a -> a!},\\[0.5em]
484: no blackhole and no update frame is created\\[0.5em]
485: $\Longrightarrow$ sharing is effectively prevented.
486: \vfill
487:
488: (Ask me for my ghc branch.)
489:
490: \end{frame}
491:
492:
493: \begin{frame}[fragile]
494: \frametitle{Also nice: ghc-vis}
495:
496: \centering
497: \textit{Demonstration}
498: \vfill
499: see\\
500: \url{http://hackage.haskell.org/package/ghc-vis}\\
501: and\\
502: \url{http://felsin9.de/nnis/ghc-vis/}
503: \vfill
504:
505: \end{frame}
506:
507:
508:
509: \end{document}
Generated by git2html.