ghc-dup: 809df9f2e4a7d6c4769f248e6fe8c93fa76e24d4
1: \documentclass[preprint]{sigplanconf}
2:
3:
4: \usepackage[T1]{fontenc}
5: \usepackage[safe]{tipa} % for \textlambda
6: \usepackage[utf8]{inputenc}
7: \usepackage[english]{babel}
8: \usepackage{etex}
9: \usepackage{stmaryrd}
10: \usepackage{amsmath}
11: \usepackage{amsfonts}
12: \usepackage{amssymb}
13: \usepackage{mathtools}
14: \usepackage[amsmath,thmmarks]{ntheorem}
15: %\usepackage{algorithm2e}
16: \usepackage{tikz}
17: \usepackage{wrapfig}
18: \usepackage[numbers]{natbib}
19: \usepackage{mathpazo}
20: \usepackage{microtype}
21: \usepackage{booktabs}
22: \usepackage{mathpartir}
23: \usepackage{upgreek}
24: \usepackage{enumerate}
25:
26: \newcommand\pfun{\mathrel{\ooalign{\hfil$\mapstochar\mkern5mu$\hfil\cr$\to$\cr}}}
27:
28: \usepackage{hyperref}
29:
30: \usetikzlibrary{shapes.geometric}
31: \usetikzlibrary{calc}
32: \usetikzlibrary{shapes.multipart}
33: \usetikzlibrary{arrows}
34:
35: \urlstyle{sf}
36: \makeatletter
37: % Inspired by http://anti.teamidiot.de/nei/2009/09/latex_url_slash_spacingkerning/
38: % but slightly less kern and shorter underscore
39: \let\UrlSpecialsOld\UrlSpecials
40: \def\UrlSpecials{\UrlSpecialsOld\do\/{\Url@slash}\do\_{\Url@underscore}}%
41: \def\Url@slash{\@ifnextchar/{\kern-.11em\mathchar47\kern-.2em}%
42: {\kern-.0em\mathchar47\kern-.08em\penalty\UrlBigBreakPenalty}}
43: \def\Url@underscore{\nfss@text{\leavevmode \kern.06em\vbox{\hrule\@width.3em}}}
44: \makeatother
45:
46: \theorembodyfont{}
47: \newtheorem{theorem}{Theorem}
48: \newtheorem{lemma}[theorem]{Lemma}
49: \theoremstyle{nonumberplain}
50: \theoremheaderfont{\scshape}
51: \theoremsymbol{\ensuremath{\blacksquare}}
52: \theoremseparator{.}
53: \newtheorem{proof}{Proof}
54:
55: \usepackage{listings}
56: \newcommand{\li}{\lstinline[style=Haskell]}
57: \lstnewenvironment{haskell}{\lstset{style=Haskell}}{}
58: \lstdefinestyle{Haskell}{language=Haskell
59: ,columns=flexible
60: ,basewidth={.365em}
61: ,keepspaces=True
62: ,texcl=true
63: % ,escapechar=!
64: ,basicstyle=\sffamily
65: ,stringstyle=\itshape
66: ,showstringspaces=false
67: ,literate={->}{$\,\to\,$}2
68: {<-}{$\,\leftarrow\,$}2
69: {=>}{$\,\Rightarrow\,$}2
70: {→}{$\,\to\,$}2
71: % {\\}{\textlambda}1
72: {>>}{{>>}\hspace{-1pt}}2
73: % {+}{{$+$}}1
74: {[]}{[\,]\ }1
75: % {--}{{---\ }}1
76: {++}{{$+\!\!+$\ }}1
77: % {\ .}{{$\,\circ\,$}}2
78: {\ .\ }{{$\,\circ\,$}}2
79: ,keywords={type,data,where,let,in,case,of}
80: }
81:
82: \newcommand{\ci}{\lstinline[style=Cmm]}
83: \lstnewenvironment{cmm}{\lstset{style=Cmm}}{}
84: \lstdefinestyle{Cmm}{language=C
85: ,columns=fullflexible
86: ,texcl=true
87: % ,escapechar=!
88: ,commentstyle=\sffamily\itshape
89: ,basicstyle=\small\ttfamily
90: % ,stringstyle=\itshape
91: % ,showstringspaces=false
92: % ,keywords={type,data,where,let,in,case,of}
93: }
94:
95:
96:
97: \conferenceinfo{Haskell Implementors Workshop}{Sep 14 2012, Copenhagen}
98: \copyrightyear{2012}
99: \copyrightdata{Joachim Breitner}
100:
101: \titlebanner{---preprint---}
102: \preprintfooter{Joachim Breitner: dup -- Explicit un-sharing in Haskell}
103: \title{dup -- Explicit un-sharing in Haskell}
104: %\subtitle
105:
106: \authorinfo{Joachim Breitner}{Karlsruhe Institute of Technology}{breitner@kit.edu}
107:
108:
109: \begin{document}
110: \maketitle
111: % \allowdisplaybreaks[1]
112:
113: \begin{abstract}
114: We propose two operations to prevent sharing in Haskell that do not require modifying the data generating code, demonstrate their use and usefulness, and compare them to other approaches to preventing sharing. Our claims are supported by a formal semantics and a prototype implementation.
115: \end{abstract}
116:
117: %\tableofcontents
118:
119: \category{D.1.1}{Programming Techniques}{Applicative (Functional) Programming}
120: \category{D.3.3}{Programming Languages}{Language Constructs and Features}[Data types and structures]
121: \category{E.2}{Data storage representation}{}
122:
123: \keywords space leak, lazy evaluation, sharing, functional programming, natural semantics
124:
125:
126: \section{Introduction}
127:
128: Thanks to the immutable nature of data in a pure functional programming language such as Haskell, there are many possibilities for sharing, i.e.\ one object in memory can used in multiple places in the program. In general, this is a good thing, as it can save both execution time (by not calculating the data again) and memory space (by not copying the data).
129:
130: But there are cases where sharing can hurt, and sometimes hurt badly. A famous example (\citep{wikibook,lazy-evaluators}) is the following function:
131: \begin{haskell}
132: let l = [1..100000000]
133: f :: [Int] -> Int
134: f xs = last xs + head xs
135: in f l
136: \end{haskell}
137: This program is space-leaky and will quickly run out of memory. If we substitute the term for \li-xs- in the body of \li-f- and evaluate that expression, it runs quickly and in constant memory. We have avoided the sharing of \li-xs- between the calls to \li-last- and \li-head- and the list elements can be garbage collected as soon as they have been consumed by \li-last-. This came at the expense of evaluating the list twice, which is fine, as the list is \emph{large} but \emph{cheap to calculate}.
138:
139: But this source transformation, as well as other source transformations to avoid sharing (see Section \ref{sec:unit} and \ref{sec:church}), is not always possible or desirable, e.g.\ when the parameter passed to \li-f- comes from library code not under the control of the programmer. Therefore, we propose a new primitive operation \li-dup- which copies a (possibly unevaluated) value on the heap.
140: \begin{haskell}
141: data Box a = Box a
142: dup :: a -> Box a
143: \end{haskell}
144: Its value semantics are that of \li!(\x -> Box x)!; the wrapping in \li-Box- just serves the purpose of controlling the exact point of execution of \li-dup- by case-analyzing the \li-Box-. Using \li-dup- allows us to modify in the above example only the code of \li-f- to prevent sharing and achieve constant memory usage:
145: \begin{haskell}
146: let f xs = case dup xs of
147: Box xs' -> last xs' + head xs
148: l = [1..100000000]
149: in f l
150: \end{haskell}
151: In Section \ref{sec:unsharing}, we demonstrate the use of \li-dup- and other approaches on the more elaborate example introduced in Section \ref{sec:example}, taking on the programmer’s point of view.
152:
153: An sharp-witted reader with knowledge of a typical implementation of a Haskell runtime might already have noticed that just copying the object on the heap representing the parameter \li-xs- might not be enough: If, for example, the first cons-cell of \li-xs- is already evaluated, then \li-dup xs- will copy that cell, but the thunk representing the tail of the list will still be shared between \li-xs'- and \li-xs-, and \li-f- will again devour memory. Such things may occur without the programmer’s knowledge, e.g.\ during a compiler optimization pass.
154:
155: To that end, we propose a variant of \li-dup-, called \li-deepDup-, which effectively copies the complete heap referenced by its argument. This happens -- as one would expect for anything related to Haskell -- lazily: The objects referenced by the parameter are copied if and when they are needed. In other words: After having evaluated a function which only works on \li-deepDup-’ed copies of its parameters, nothing this evaluation has created on the heap is referenced anymore, unless it is referenced by the function's return value (this is formalized in Theorem \ref{thm:deepdup}).
156:
157: Our specific contributions are:
158: \begin{itemize}
159: \item We introduce primitives that give the programmer the possibility to explicitly prevent sharing.
160: \item In contrast to approaches based on source transformations, using \li-dup- and \li-deepDup- does \emph{not} require changes to the generating code.
161: \item We provide precise semantics in the context of Launchbury’s natural semantics for Lazy Evaluation (Section \ref{sec:semantics}) and prove that the recursive variant \li-deepDup- is effective.
162: \item We show the feasibility of our approach using a proof-of-concept implementation targeting code compiled by an unmodified GHC. (Section \ref{sec:prototype})
163: \end{itemize}
164:
165: \section{The running example}
166: \label{sec:example}
167:
168: For the remainder of the paper, we will use one running example to demonstrate and discuss the use of \li-dup-. The task at hand, inspired by the minimax algorithm that searches for an optimal strategy in a two-player turn-based game, is to find a path through a (possibly infinite) tree that maximizes some valuation of the nodes. So abstractly, we have a type \li-S- of states, a valuation function \li-value-, an initial state \li-init- and for every state \li-s-, a list of successor states \li-succs s-. For the sake of simplicity of the presentation, we assume this \li-succs s- to be always non-empty (see also Figure~\ref{fig:ex}).
169:
170: \begin{figure}
171: \begin{haskell}
172: -- The problem specification
173: type S = ...
174: init :: S
175: succs :: S -> [S]
176: value :: S -> Integer
177:
178: -- The search tree code
179: data Tree = Node S [Tree]
180: fstChild :: Tree -> Tree
181: fstChild (Tree _ (x:xs)) = x
182:
183: tree :: S -> Tree
184: tree s = Node s (map tree (succs s))
185:
186: solve :: Tree -> [S]
187: solve (Node n ts) = n : solve picked
188: where
189: rated = [ (t, rate depth t) | t <- ts ]
190: picked = fst (maximumBy (comparing snd) rated)
191: depth = ...
192:
193: rate :: Int -> Tree -> Integer
194: rate 0 (Node s _) = value s
195: rate d (Node _ ts) = maximum (map (rate (d-1)) ts)
196:
197: main = do
198: let t = tree init
199: print $ solve t !! 10000
200: doSomethingElseWith t
201: \end{haskell}
202: \caption{The running example}
203: \label{fig:ex}
204: \end{figure}
205:
206: Based on these functions, we define a search tree and a solver. The solver picks the successor with the highest rating, whereas the rating is the highest value of nodes at a configurable depth.
207:
208: Assume a constant number of successors $b$, $b>0$, and that the value of \li-depth- is $d$. Consider what happens when we want to calculate the first 10\,000 elements of the solution: The \li-rate- function will evaluate lots of nodes that will \emph{not} be picked for the solution. But as they are still referenced by the tree \li-t-, the garbage collector cannot get rid of them. So in addition to the 10\,000 interesting nodes, roughly $10\,000\cdot (b-1)\cdot b^{d-1}$ nodes are evaluated that the programmer knows are not required to be kept around. The first row of Figure \ref{fig:evaluation} depicts the heap during this evaluation, with $d=1$ and $b=2$.
209:
210: \newcommand{\stats}[1]{\ref*{#1}}
211: More concretely with $d=4$, $b=4$, \li-type S = Word32- and a very cheap \li-succs- and \li-value- functions, this program requires \stats{stats:Original:Shared:mem}~MB of system memory (as reported by the GHC runtime as “total memory in use” when passed the \ci!-s! option) and runs in \stats{stats:Original:Shared:time} seconds.%
212: \footnote{All statistics are obtained on a machine with 2~GHz and sufficient (32~GB) RAM. The complete code used to generate these statistics is available in the \ci!ghc-dup! repository at \url{http://darcs.nomeata.de/ghc-dup}.} Sharing is indeed the problem here: If we remove the last line of \li-main-, the program runs in \stats{stats:Original:Unshared:mem}~MB of memory and takes \stats{stats:Original:Unshared:time} seconds.
213:
214: \section{Unsharing the example}
215: \label{sec:unsharing}
216:
217: \begin{figure*}
218: \centering
219: \input{statstable}
220: \caption{Time and space performance for $b=4$ and $d=4$}
221: \label{fig:stats}
222: \end{figure*}
223:
224: \newcommand{\thefirstevaluationmatrix}{
225: \node[right] {\rmfamily original:};
226: \&
227: \node[solve] (root) {T};
228: \draw (root.north) -- +(0mm,2mm);
229: \&
230:
231: \&
232:
233: \node[solve] (root) {N}
234: child {node [rate] {T}}
235: child {node {T}};
236: \draw (root.north) -- +(0mm,2mm);
237:
238: \&
239: \node[solve] (root) {N}
240: child {node [rate] {N}
241: child {node {N} child {node {T}} child {node {T}}}
242: child {node {N} child {node {T}} child {node {T}}}
243: }
244: child {node {T}};
245: \draw (root.north) -- +(0mm,2mm);
246:
247: \&
248: \node[solve] (root) {N}
249: child {node {N}
250: child {node {N} child {node {T}} child {node {T}}}
251: child {node {N} child {node {T}} child {node {T}}}
252: }
253: child {node[rate] {N}
254: child {node {N} child {node {T}} child {node {T}}}
255: child {node {N} child {node {T}} child {node {T}}}
256: }
257: ;
258: \draw (root.north) -- +(0mm,2mm);
259:
260: \&
261:
262: \node (root) {N}
263: child {node {N}
264: child {node {N} child {node {T}} child {node {T}}}
265: child {node {N} child {node {T}} child {node {T}}}
266: }
267: child {node [solve] {N}
268: child {node {N} child {node {T}} child {node {T}}}
269: child {node {N} child {node {T}} child {node {T}}}
270: };
271: \draw (root.north) -- +(0mm,2mm);
272:
273: \\
274: \node[right]{\rmfamily \textsf{solveDup}:};
275: \&
276: \node[solve] (root) {T};
277: \draw (root.north) -- +(0mm,2mm);
278: \&
279:
280: \node at (-6mm,0mm) (root) {T};
281: \draw (root.north) -- +(0mm,2mm);
282: \node[solve] (root2) {T};
283: \draw[double] (root) -- (root2);
284: \&
285:
286: \node at (-6mm,0mm) (root) {T};
287: \draw (root.north) -- +(0,2mm);
288: \node[solve](root2) {N}
289: child {node [rate] {T}}
290: child {node {T}};
291: \draw[double] (root) -- (root2);
292:
293: \&
294: \node at (-6mm,0mm) (root) {T};
295: \draw (root.north) -- +(0,2mm);
296: \node[solve](root2) {N}
297: child {node [rate] {N}
298: child {node {N} child {node {T}} child {node {T}}}
299: child {node {N} child {node {T}} child {node {T}}}
300: }
301: child {node {T}};
302: \draw (root.north) -- +(0,2mm);
303: \draw[double] (root) -- (root2);
304:
305: \&
306: \node at (-6mm,0mm) (root) {T};
307: \draw (root.north) -- +(0,2mm);
308: \node[solve](root2) {N}
309: child {node {N}
310: child {node {N} child {node {T}} child {node {T}}}
311: child {node {N} child {node {T}} child {node {T}}}
312: }
313: child {node [rate] {N}
314: child {node {N} child {node {T}} child {node {T}}}
315: child {node {N} child {node {T}} child {node {T}}}
316: }
317: ;
318: \draw (root.north) -- +(0,2mm);
319: \draw[double] (root) -- (root2);
320:
321: \&
322:
323: \node at (-6mm,0mm) (root) {T};
324: \draw (root.north) -- +(0,2mm);
325: \draw [gray] node(root2) {N}
326: child {node {N}
327: child {node {N} child {node {T}} child {node {T}}}
328: child {node {N} child {node {T}} child {node {T}}}
329: }
330: child {node[solve,black] {N}
331: child[black] {node {N} child {node {T}} child {node {T}}}
332: child[black] {node {N} child {node {T}} child {node {T}}}
333: };
334: \draw (root.north) -- +(0,2mm);
335: \draw[gray,double] (root) -- (root2);
336:
337: \\
338: \node[right]{\rmfamily \textsf{rateDup}:};
339: \&
340: \node[solve] (root) {T};
341: \draw (root.north) -- +(0mm,2mm);
342: \&
343:
344: \node[solve] (root) {N}
345: child {node [rate] {T}}
346: child {node {T}};
347: \draw (root.north) -- +(0mm,2mm);
348:
349: \&
350: \node[solve] (root) {N}
351: child {node (rate) {T}}
352: child {node {T}};
353: \path (rate) +(6mm,0) node[rate] (rate2) {T};
354: \draw (root.north) -- +(0mm,2mm);
355: \draw[double] (rate) -- (rate2);
356:
357:
358: \&
359: \node[solve] (root) {N}
360: child {node (rate) {T}
361: +(6mm,0) node[rate] (rate2) {N}
362: child {node {N} child {node {T}} child {node {T}}}
363: child {node {N} child {node {T}} child {node {T}}}
364: }
365: child {node {T}};
366: \draw (root.north) -- +(0mm,2mm);
367: \draw[double] (rate) -- (rate2);
368:
369: \&
370: \node[solve] (root) {N}
371: child {node (rate') {T}
372: +(6mm,0) node[gray] (rate'2) {N}
373: child[gray] {node {N} child {node {T}} child {node {T}}}
374: child[gray] {node {N} child {node {T}} child {node {T}}}
375: }
376: child {node (rate) {T}
377: +(6mm,0) node[rate] (rate2) {N}
378: child {node {N} child {node {T}} child {node {T}}}
379: child {node {N} child {node {T}} child {node {T}}}
380: }
381: ;
382: \draw (root.north) -- +(0mm,2mm);
383: \draw[double] (rate) -- (rate2);
384: \draw[double,gray] (rate') -- (rate'2);
385:
386: \&
387:
388: \node (root) {N}
389: child {node (t1) {T}
390: +(6mm,0) node[gray] (t1') {N}
391: child[gray] {node {N} child {node {T}} child {node {T}}}
392: child[gray] {node {N} child {node {T}} child {node {T}}}
393: }
394: child {node [solve] (t2) {T}
395: +(6mm,0) node[gray] (t2') {N}
396: child[gray] {node {N} child {node {T}} child {node {T}}}
397: child[gray] {node {N} child {node {T}} child {node {T}}}
398: };
399: \draw (root.north) -- +(0mm,2mm);
400: \draw[gray,double] (t1) -- (t1');
401: \draw[gray,double] (t2) -- (t2');
402: \\
403: }
404:
405: \newcommand{\thesecondevaluationmatrix}{
406: \node[right]{\rmfamily \textsf{solveDup}:};
407: \&
408: \node[solve] (root) {N}
409: child {node {T}}
410: child {node {T}};
411: \draw (root.north) -- +(0mm,2mm);
412: \&
413:
414: \node at (-6mm,0mm) (root) {N};
415: \draw (root.north) -- +(0mm,2mm);
416: \node[solve] (root2) {N}
417: child {node {T}}
418: child {node {T}};
419: \draw[double] (root) -- (root2);
420: \draw (root) -- (root2-1);
421: \draw (root) -- (root2-2);
422: \&
423:
424: \node at (-6mm,0mm) (root) {N};
425: \draw (root.north) -- +(0,2mm);
426: \node[solve](root2) {N}
427: child {node [rate] {T}}
428: child {node {T}};
429: \draw[double] (root) -- (root2);
430: \draw (root) -- (root2-1);
431: \draw (root) -- (root2-2);
432:
433: \&
434: \node at (-6mm,0mm) (root) {N};
435: \draw (root.north) -- +(0,2mm);
436: \node[solve](root2) {N}
437: child {node [rate] {N}
438: child {node {N} child {node {T}} child {node {T}}}
439: child {node {N} child {node {T}} child {node {T}}}
440: }
441: child {node {T}};
442: \draw (root.north) -- +(0,2mm);
443: \draw[double] (root) -- (root2);
444: \draw (root) -- (root2-1);
445: \draw (root) -- (root2-2);
446:
447: \&
448:
449: \node at (-6mm,0mm) (root) {N};
450: \draw (root.north) -- +(0,2mm);
451: \draw node[solve] (root2) {N}
452: child {node {N}
453: child {node {N} child {node {T}} child {node {T}}}
454: child {node {N} child {node {T}} child {node {T}}}
455: }
456: child {node[rate] {N}
457: child {node {N} child {node {T}} child {node {T}}}
458: child {node {N} child {node {T}} child {node {T}}}
459: };
460: \draw (root.north) -- +(0,2mm);
461: \draw[double] (root) -- (root2);
462: \draw (root) -- (root2-1);
463: \draw (root) -- (root2-2);
464:
465: \&
466:
467: \node at (-6mm,0mm) (root) {N};
468: \draw (root.north) -- +(0,2mm);
469: \draw node[gray] (root2) {N}
470: child {node {N}
471: child[black] {node {N} child {node {T}} child {node {T}}}
472: child[black] {node {N} child {node {T}} child {node {T}}}
473: edge from parent[gray]
474: }
475: child {node[solve,black] {N}
476: child[black] {node {N} child {node {T}} child {node {T}}}
477: child[black] {node {N} child {node {T}} child {node {T}}}
478: edge from parent[gray]
479: };
480: \draw (root.north) -- +(0,2mm);
481: \draw[gray,double] (root) -- (root2);
482: \draw (root) -- (root2-1);
483: \draw (root) -- (root2-2);
484:
485: \\
486: \node[right]{\rmfamily \textsf{solveDeepDup}:};
487: \&
488: \node[solve] (root) {N}
489: child {node {T}}
490: child {node {T}};
491: \draw (root.north) -- +(0mm,2mm);
492: \&
493:
494: \node at (-6mm,0mm) (root) {N}
495: child {node {T}}
496: child {node {T}}
497: ;
498: \draw (root.north) -- +(0mm,2mm);
499: \node[solve] (root2) {N}
500: child {node[rate] {D}}
501: child {node {D}};
502: \draw[double] (root) -- (root2);
503: \draw[->] (root2-1) -- (root-1);
504: \draw[->] (root2-2) -- (root-2);
505:
506: \&
507:
508: \node at (-6mm,0mm) (root) {N}
509: child {node {T}}
510: child {node {T}}
511: ;
512: \draw (root.north) -- +(0mm,2mm);
513: \node[solve] (root2) {N}
514: child {node[rate] {T}}
515: child {node {D}};
516: \draw[double] (root) -- (root2);
517: \draw[double] (root2-1) -- (root-1);
518: \draw[->] (root2-2) -- (root-2);
519:
520: \&
521:
522: \node at (-6mm,0mm) (root) {N}
523: child {node {T}}
524: child {node {T}}
525: ;
526: \draw (root.north) -- +(0mm,2mm);
527: \node[solve] (root2) {N}
528: child {node[rate] {N}
529: child {node {N} child {node {T}} child {node {T}}}
530: child {node {N} child {node {T}} child {node {T}}}
531: }
532: child {node {D}};
533: \draw[double] (root) -- (root2);
534: \draw[double] (root2-1) -- (root-1);
535: \draw[->] (root2-2) -- (root-2);
536:
537: \&
538: \node at (-6mm,0mm) (root) {N}
539: child {node {T}}
540: child {node {T}}
541: ;
542: \draw (root.north) -- +(0mm,2mm);
543: \node[solve] (root2) {N}
544: child {node {N}
545: child {node {N} child {node {T}} child {node {T}}}
546: child {node {N} child {node {T}} child {node {T}}}
547: }
548: child {node[rate] {N}
549: child {
550: node {N} child {node {T}} child {node {T}}
551: }
552: child {
553: node {N} child {node {T}} child {node {T}}
554: }
555: edge from parent
556: };
557: \draw[double] (root) -- (root2);
558: \draw[double] (root2-1) -- (root-1);
559: \draw[double] (root2-2) -- (root-2);
560:
561:
562: \&
563: \node at (-6mm,0mm) (root) {N}
564: child {node {T}}
565: child {node {T}}
566: ;
567: \draw (root.north) -- +(0mm,2mm);
568: \node[gray] (root2) {N}
569: child[gray] {node {N}
570: child {node {N} child {node {T}} child {node {T}}}
571: child {node {N} child {node {T}} child {node {T}}}
572: }
573: child {node[solve] {N}
574: child[black] {
575: node {N} child {node {T}} child {node {T}}
576: }
577: child[black] {
578: node {N} child {node {T}} child {node {T}}
579: }
580: edge from parent[gray]
581: };
582: \draw[double,gray] (root) -- (root2);
583: \draw[double,gray] (root2-1) -- (root-1);
584: \draw[double] (root2-2) -- (root-2);
585:
586: \\
587: }
588:
589: % Two figures in one, horrible hack to ensure that the matrix is consistently
590: % spaced between the two figures.
591: \begin{figure*}
592: \centering
593: {
594: \sffamily
595: \begin{tikzpicture}
596: [level/.style={sibling distance=20mm/2^#1,level distance=6mm},
597: every node/.style={inner sep=1pt},
598: solve/.style={draw,circle,inner sep=1pt},
599: rate/.style={draw,rectangle,inner sep=2pt},
600: %every path/.style={->},
601: ]
602:
603: \matrix[column sep={4mm},row sep=4mm, ampersand replacement=\&] (matrix) {
604: \thefirstevaluationmatrix
605: \begin{scope}
606: \path[use as bounding box] (0pt,-5em) -- (0pt,0em);
607: \node[above right] (caption) {};
608: \end{scope}
609: \\
610: \thesecondevaluationmatrix
611: };
612:
613: \path (caption.north west)
614: %+(0,10mm)
615: node [above right] {
616: \parbox{88mm}{
617: \rmfamily
618: %\textbf{Legend:}
619: %\\
620: \textsf{T}: thunk, \textsf{N}: node, $=$: dup’ed closure,
621: \textcolor{gray}{garbage},
622: \\
623: \begin{tikzpicture}[baseline=(n.base)]
624: \node[solve] (n) {T};
625: \end{tikzpicture}:
626: current argument of solve,
627: %\\
628: \begin{tikzpicture}[baseline=(n.base)]
629: \node[rate] (n) {T};
630: \end{tikzpicture}:
631: current argument of rate
632: \\
633: }
634: };
635:
636: \path (matrix.south west)
637: %+(0,10mm)
638: node [above right] {
639: \parbox{88mm}{
640: \rmfamily
641: %\textbf{Legend:}
642: %\\
643: \textsf{D}: \textsf{deepDup} application thunk
644: }
645: };
646: \end{tikzpicture}}\\
647: \raisebox{23em}[0pt][0pt]{%
648: \parbox{\linewidth}{
649: \caption{The heap during original and \textsf{dup}’ed evaluation with $b=2$ and $d=1$}
650: \label{fig:evaluation}
651: }}\\
652: \caption{Comparing \textsf{solveDup} and \textsf{solveDeepDup} applied to a partly evaluated tree with $b=2$ and $d=1$}
653: \label{fig:deepevaluation}
654: \end{figure*}
655:
656: We want to improve the space performance of the program in the example and thus, due to the saved work in the garbage collector, also the runtime performance. In the following, we use \li-dup-, first wrapping the argument of \li-solve-, then the argument of \li-rate-, and \li-deepDup-. We also try two variants that work without new primitives, but require refactoring the generating code. The statistics are collected in Figure \ref{fig:stats}, where all six strategies are applied to
657: \begin{itemize}
658: \item an otherwise unreferenced tree, i.e.\ the example code without the last line of the main function,
659: \item a shared, unevaluated tree as shown in Figure \ref{fig:ex},
660: \item a shared, unevaluated tree wrapped in another thunk, by passing \li-(fstChild t)- to \li-solve-,
661: \item a shared tree that has been partly evaluated forcing \li-seq (fstChild t)- before passing \li-t- to the solver,
662: \item a shared tree that has been fully evaluated by the unmodified solver before,
663: \item a shared, unevaluated tree that is processed twice by the (possibly modified) solver.
664: \end{itemize}
665: In the two variants based on refactoring, the data type used for the tree does not allow for partial or full evaluation, so these runs are omitted.
666:
667: \subsection{Using dup}
668:
669: We now modify the example to use our new primitives. There are a few choices in doing so, with different trade-offs. One candidate for \li-dup-’ing is the function \li-solve-: We know that the parameter \li-t- to \li-solve- is an unevaluated expression, and decoupling that from the \li-t- that we pass to \li-doSomethingElseWith- will allow the garbage collector to clean up the tree as \li-solve- proceeds to process it (Figure \ref{fig:evaluation}, second row). So we wrap \li-solve- in \li-solveDup- and use that in \li-main-.
670: \begin{haskell}
671: solveDup t = case dup t of Box t' -> solve t'
672: \end{haskell}
673: And indeed, we have almost achieved the performance of the original program without sharing: \stats{stats:SolveDup:Shared:mem}~MB and \stats{stats:SolveDup:Shared:time} seconds.
674:
675:
676: Another candidate for \li-dup-’ing is the function \li-rate-:
677: As this is the function whose return value is taken into account when deciding whether to pick the argument or not, we know that in most cases, its argument will not be used any more. Therefore, by creating a wrapper \li-rateDup- that duplicates the argument, and using that in \li-solve-, we allow for the argument and all its children to be garbage collected once \li-rate- has finished.
678: \begin{haskell}
679: rateDup d t = case dup t of Box t' -> rate d t'
680: \end{haskell}
681:
682: Both the runtime and the memory footprint of the program are greatly reduced compared to the original program: It uses \stats{stats:RateDup:Shared:mem}~MB of memory and takes \stats{stats:RateDup:Shared:time} seconds to finish. It is surprising that this even surpasses the speed of the original program without sharing. The reason is that with \li-rate- wrapped in \li-dup-, the first child of the node under inspection of \li-solve- can be freed already when its next child is evaluated by \li-rate- (Figure~\ref{fig:evaluation}, last row, second-to-last column), so the copying garbage collector needs to do even less work.
683:
684: \begin{figure*}
685: \centering
686: \input{statstable-slow}
687: \caption{Time and space performance for $b=4$ and $d=4$ using an expensive \li-succs- function.}
688: \label{fig:statsexpensive}
689: \end{figure*}
690:
691:
692: \subsection{Using deepDup}
693: \label{sec:deepdup}
694: Using \li-dup- is a fragile business and requires the programmer to have a very good idea about what is happening at runtime. It will fail, for example, in two common situations: If the call to \li-solveDup- in \li-main- in Figure \ref{fig:ex} would not just pass the tree \li-t- but rather an expression referencing \li-t-, e.g.
695: \begin{haskell}
696: print $ solveDup (fstChild t) !! 1000
697: \end{haskell}
698: then \li-dup- will only copy this unevaluated expression, but both copies will reference the same unevaluated expression for~\li-t-, and we are back at the original performance (\stats{stats:SolveDup:SharedThunk:mem}~MB, \stats{stats:SolveDup:SharedThunk:time} seconds).
699:
700: The same effect occurs if the tree is already partly evaluated. This may even be caused by a compiler transformation, e.g.\ the wrapper/worker transformation, assuming that \li-doSomethingElseWith- is strict in its argument \citep{unboxed}. Then, the parameter \li-t- is the \li-Node- constructor referencing other nodes or unevaluated trees, and copying the constructor does not help to prevent sharing the referenced data, as shown in the first row of Figure \ref{fig:deepevaluation}.
701:
702: This is where \li-deepDup- comes in:
703: Intuitively, \li-deepDup- takes a complete and private copy of the entire heap reachable from its argument, hence preventing any unwanted evaluation outside this copy. In fact this is done lazily: It will just copy the object specified by its parameter, and change all references therein so that before they are evaluated, \li-deepDup- copies them.
704:
705: So by wrapping \li-solve- in a call to \li-deepDup-:
706: \begin{haskell}
707: solveDeepDup t = case deepDup t of Box t' -> solve t'
708: \end{haskell}
709: we achieve the performance of a successful run with \li-dup- (\stats{stats:SolveDeepDup:SharedThunk:mem}~MB and \stats{stats:SolveDeepDup:SharedThunk:time} seconds), but also in the cases where \li-t- has already been partly evaluated or is wrapped in another unevaluated expression. The second row of Figure \ref{fig:deepevaluation} shows \li-deepDup- at work.
710:
711: Using \li-deepDup- is therefore more reliable and easier to handle: The programmer need not have an exact idea of the evaluation state of the arguments when \li-deepDup- is called. And the recursive copying is surprisingly cheap: Even when the tree is already fully evaluated, e.g. by an earlier call to \li-solve t !! 10000-, the runtime stays the same within the precision of the benchmark.
712: %\footnote{In fact, it is reliably reduced by about one percent; the reason is not yet clear to us.}
713:
714: %\section{Other approaches to unsharing}
715: %\label{sec:sourcetrans}
716:
717:
718: \subsection{The unit type argument pattern}
719:
720: The problem at hand is, of course, not new, and Haskell programmers have solved it one way or the other before, by rewriting the code to allow more control over sharing.
721:
722: \label{sec:unit}
723:
724: A common approach is to replace values that you do not want to be shared by functions, e.g.\ by turning a bound expression \li-let x = e- into a lambda expression \li!let x = \() -> e!. At every point in the program where \li-e- is required, one can get the value of it using \li-x ()-; there will be no sharing between different calls to \li-x ()-
725:
726: One needs to be careful, though, as some compiler optimizations can introduce unwanted sharing again. The code
727: \begin{haskell}
728: xs :: () -> [Int]
729: xs () = [1..10000000]
730:
731: main = do
732: print (last (xs ()))
733: print (head (xs ()))
734: \end{haskell}
735: works as expected without optimization. Passing \ci!-O! to GHC results in sharing again, as a result of the full laziness transformation. In fact, in a discussion of this example on the GHC bug tracker \citep{spaceleakbug}, Claus Reinke suggests an operation like \li-dup- to solve this.%
736: % http://hackage.haskell.org/trac/ghc/ticket/917
737: \footnote{
738: If, however, the type signature of \li-xs- is not given, then no unwanted sharing happens even with \ci!-O!. The inferred most general type of \li-xs- is polymorphic with type class constraints. This implies that additional parameters are being passed under the hood and they successfully prevent sharing.
739: }
740:
741: Applying this pattern to our problem, and aiming for a tree with unshareable subtrees, we can define the following types:
742: \begin{haskell}
743: data UTree' = UNode S [UTree]
744: type UTree = () -> UTree'
745: \end{haskell}
746: The required changes to the functions on trees are mechanical and guided by the type checker. The resulting code, when not hit by some optimization-induced re-sharing, shows very good time and space complexity. If sharing is desired at some points of the program, those parts will have to work with the regular \li-Tree- type, possibly leading to a duplication of code.
747:
748: \subsection{Church encoding}
749: \label{sec:church}
750:
751: An alternative is to restructure the program so that the value that must not be shared is not represented using data constructors but rather as a higher-order function \citep{churchenc,olegchurchenc}. This transformation is known as the Church encoding of a data type, or a variant thereof. For the algebraic tree data type in our running example, we would obtain the following type and conversion functions:
752: \begin{haskell}
753: type CTree = forall a. (S -> [a] -> a) -> a
754:
755: toCTree :: Tree -> CTree
756: toCTree (Node s ts) f = f s $ map (\t -> toCTree t f) ts
757:
758: fromCTree :: CTree -> Tree
759: fromCTree ct = ct Node
760: \end{haskell}
761:
762: A church-encoded tree corresponding to the value \li-tree s- can be nicely created with the following code:
763: \begin{haskell}
764: ctree :: S -> CTree
765: ctree s f = f s $ map (\s' -> ctree s' f) (succs s)
766: \end{haskell}
767:
768: Unfortunately, adapting \li-solve- to this type is a non-trivial task, as the two recursions happening therein (\li-solve- and \li-rate-) need to be folded into one pass:
769: \begin{haskell}
770: csolve :: CTree -> [S]
771: csolve t = fst (t csolve')
772: where
773: csolve' :: S -> [([S], Int -> Int)] -> ([S], Int -> Int)
774: csolve' n rc =
775: ( n : fst (maximumBy (comparing (($ depth) . snd)) rc)
776: , \d -> if d == 0 then value n
777: else maximum (map (($ d-1) . snd) rc))
778:
779: \end{haskell}
780: This additional complexity might make this approach impractical in larger settings.
781: Note, though, that applying this pattern to the list data type turns a list into its right fold and can enable deforestation \citep{deforestation}.
782:
783: \pagebreak[3]
784: \subsection{Comparison and interpretation}
785:
786: As we can see from the statistics in Figure \ref{fig:stats}, the unit type argument pattern is the clear winner in both runtime and space performance. It is ahead of \li-rateDup- for the same reason that made \li-rateDup- faster than \li-solveDup-: Now even the subtrees in recursive calls of \li-rate- are freed immediately.
787: Unfortunately, it requires a thorough refactoring of both the data generating and data consuming code; all combinators working on the data type need to be carefully rewritten to preserve the non-sharing behavior of the lifted data type. Also, the full laziness transformation can break the pattern, making it slightly fragile.
788:
789: The church encoding pattern shows good and predictable memory performance, but exhibits slightly worse runtime behavior. The cases where it is ahead of other approaches it wins only due to the garbage collector overhead induced by unprevented sharing. As the previous pattern, it requires extensive refactoring.
790:
791: Our primitives come with very small overhead when applied to data that is actually unshared, as we show in the first column. In fact, careful use of \li-dup- can improve performance noticeably even if only small pieces of data can be un-shared and thus freed quickly. While \li-dup- is subtle to use, \li-deepDup- is robust and its effect is more precisely defined, as shown in the next section.
792:
793: Obviously, avoiding sharing is a bad idea when the result is expensive to create. Figure~\ref{fig:statsexpensive} runs the same benchmark with an expensive (but otherwise equal) \li-succs- function. If the tree needs to be processed twice, then throwing the result away after the first run (as done in the last column) results in a serious loss of run-time performance. Also for the same reason that the \li-rateDup- and unit lifting variants were faster before they now slow down the program, as parts of the tree are evaluated twice.
794:
795: On the other hand, if the memory footprint becomes larger than the available memory, being able to run the program slowly is still better than not being able to run it at all, so even in this case there can be uses for \li-dup- and \li-deepDup-.
796:
797: \pagebreak[3]
798: \section{A natural semantics}
799: \label{sec:semantics}
800:
801: To substantiate our claims about the usefulness of \li-dup- and especially \li-deepDup-, we give them a precise meaning within Launchbury’s natural semantics for lazy evaluation \citep{launchbury} and prove that all memory allocated by a function whose arguments are wrapped with \li-deepDup- can be freed after the function has been completely evaluated.
802:
803: We extend Launchbury’s semantics for normalized lambda calculus with our two primitives:
804: \newcommand{\mdup}{\text{\textsf{dup}}}
805: \newcommand{\mdeepDup}{\text{\textsf{deepDup}}}
806: \newcommand{\sVar}{\text{Var}}
807: \newcommand{\sExp}{\text{Exp}}
808: \newcommand{\sHeap}{\text{Heap}}
809: \newcommand{\sVal}{\text{Val}}
810: \newcommand{\sValue}{\text{Value}}
811: \newcommand{\sEnv}{\text{Env}}
812: \newcommand{\sApp}[2]{\operatorname{#1}#2}
813: \newcommand{\sLam}[2]{\text{\textlambda} #1.\, #2}
814: \newcommand{\sDup}[1]{\sApp \mdup #1}
815: \newcommand{\sDeepDup}[1]{\sApp \mdeepDup #1}
816: \newcommand{\sLet}[2]{\text{\textsf{let}}\ #1\ \text{\textsf{in}}\ #2}
817: \newcommand{\sred}[4]{#1 : #2 \Downarrow #3 : #4}
818: \newcommand{\sRule}[1]{\text{{\textsc{#1}}}}
819: \newcommand{\fv}[1]{\text{fv}(#1)}
820: \newcommand{\ufv}[1]{\text{ufv}(#1)}
821: \newcommand{\ur}[2]{\text{ur}_{#1}(#2)}
822: \newcommand{\dom}[1]{\text{dom}\,#1}
823: \newcommand{\fresh}[1]{#1'}
824: \begin{alignat*}{2}
825: x,y &\in \sVar
826: \displaybreak[1]
827: \\
828: e &\in
829: \sExp &&\Coloneqq
830: \begin{aligned}[t]&
831: \sLam x e
832: \mid \sApp e x
833: \mid x \mid
834: \\&
835: \sLet {x_1 = e_1,\ldots,x_n = e_n} e \mid
836: \\&
837: \sDup x \mid \sDeepDup x
838: \end{aligned}
839: \displaybreak[1]\\
840: \Gamma, \Delta, \Theta &\in \sHeap &&= \sVar \pfun \sExp
841: \displaybreak[1]\\
842: z &\in \sVal &&\Coloneqq \sLam x e
843: \end{alignat*}
844: His lambda terms are normalized, i.e.\ all bound variables are distinct and all applications are applications of an expression to a variable.
845:
846: The set of free variables of an expression $e$ is $\fv e$. Similarly, the set of unguarded free variables $\ufv e$ of an expression $e$, is inductively defined just like $\fv e$ with the exception that $\ufv {\sDeepDup x} = \emptyset$. A value $\hat z$ is $z$ with all bound variables renamed to completely fresh variables.
847:
848: To avoid having to introduce constructors and case expressions as well we assume $\sDup$ and $\sDeepDup$ to return their result without the wrapping in \li-Box-. This captures the semantics of the Haskell expression\nopagebreak
849: \begin{haskell}
850: (\x. let Box y = dup x in y) :: a -> a.
851: \end{haskell}
852:
853: In addition to the unmodified reduction rules \sRule{Lam}, \sRule{App}, \sRule{Var} and \sRule{Let}, we add the two rules \sRule{Dup} and \sRule{Deep} in Figure~\ref{fig:semrules}. The use of $\ufv e$ instead of $\fv e$ in the rule \sRule{DeepDup} is required to avoid a livelock if $\sDeepDup x$ is evaluated while $x$ is itself bound to $\sDeepDup y$.
854:
855: In the following every heap/term pair $\Gamma : e$ is assumed to be distinctly named, i.e.\ every binding occurring in $\Gamma$ and in $e$ binds a distinct variable; this property is preserved by the reduction rules.
856:
857: \begin{figure*}
858: \parskip1cm
859: \begin{mathpar}
860: \inferrule
861: { }
862: {\sred{\Gamma}{\sLam xe}{\Gamma}{\sLam xe}}
863: \sRule{Lam}
864: \and
865: \inferrule
866: {\sred{\Gamma}e{\Delta}{\sLam y e'}\\ \sred{\Delta}{e'[x/y]}{\Theta}{z}}
867: {\sred\Gamma{\sApp e x}\Theta z}
868: \sRule{App}
869: \and
870: \inferrule
871: {\sred\Gamma e \Delta z}
872: {\sred{\Gamma, x\mapsto e} x {\Delta, x\mapsto z}{\hat z}}
873: \sRule{Var}
874: \and
875: \inferrule
876: {\sred{\Gamma,x_1\mapsto e_1,\ldots,x_n\mapsto e_n} e \Delta z}
877: {\sred{\Gamma}{\sLet{x_1 = e_1,\ldots, x_n = e_n}e} \Delta z}
878: \sRule{Let}
879: \and
880: \inferrule
881: {\sred{\Gamma,x\mapsto e, \fresh x\mapsto \hat e} {\fresh x} \Delta z \\ \fresh x \text{ fresh}}
882: {\sred{\Gamma,x\mapsto e}{\sDup x} \Delta z}
883: \sRule{Dup}
884: \and
885: \inferrule
886: {
887: \sred{
888: \Gamma,
889: x\mapsto e,
890: \fresh x\mapsto \hat e[\fresh y_1/y_1,\ldots, \fresh y_n/y_n],
891: \fresh y_1 \mapsto \sDeepDup y_1,\ldots,
892: \fresh y_n \mapsto \sDeepDup y_n
893: } {\fresh x} \Delta z
894: \\
895: \ufv e = \{y_1,\ldots,y_n\}
896: \\
897: \fresh x,\ \fresh y_1,\ldots,y_n \text{ fresh}
898: }
899: {\sred{\Gamma,x\mapsto e}{\sDeepDup x} \Delta z}
900: \sRule{Deep}
901: \end{mathpar}
902: \caption{Natural semantics extended for \li-dup- and \li-deepDup-}
903: \label{fig:semrules}
904: \end{figure*}
905:
906: \newcommand{\dsem}[2]{\llbracket #1 \rrbracket_{#2}}
907: \newcommand{\esem}[1]{\{\!\!\{#1\}\!\!\}}
908: \newcommand{\case}[1]{\par\vspace{\standardvspace}\noindent\textbf{Case:} #1\nopagebreak\par\noindent\ignorespaces}
909:
910: Besides the natural semantics, Launchbury also defines a denotational semantics. He models values as a lifted function space, denoted \sValue, and environments
911: \[
912: \rho \in \sEnv = \sVar \to \sValue
913: \]
914: as functions from variables into values. He writes $\rho \le \rho'$ if $\rho'$ extends $\rho$, i.e. they differ only for variables where $\rho$ is bottom. The expression $\dsem e \rho$ is the value of the expression $e$ in the environment $\rho$.
915:
916: The semantics of a heap $\Gamma$ is given by $\esem \Gamma \rho$, which is the environment $\rho$ updated by the values specified in the heap. This is defined as a fixed point, as the heap may contain recursive references:
917: \begin{multline*}
918: \esem{ x_1\mapsto e_1,\ldots,x_n\mapsto e_n}\rho \\
919: = \mu \rho'. \rho \sqcup (x_1 \mapsto \dsem{e_1}{\rho'}) \sqcup \cdots \sqcup (x_n \mapsto \dsem{e_n}{\rho'})
920: \end{multline*}
921: This definition makes sense on environments $\rho$ that are consistent with $\Gamma$, i.e.\ if $\rho$ and $\Gamma$ bind the same variable, then they are bound to values for which an upper bound exists.
922:
923: Launchbury proves his natural semantics to be correct with respect to the denotational semantics.
924: Naturally, we want to preserve this property. Our new primitives should be invisible to the denotational semantics, hence we extend the semantics function as follows:
925: \begin{align*}
926: \dsem{\sDup x}\rho &\coloneqq \dsem{x}\rho \\
927: \dsem{\sDeepDup x}\rho &\coloneqq \dsem{x}\rho.
928: \end{align*}
929:
930: \begin{theorem}[Theorem 2 from \citep{launchbury}]
931: If $\sred\Gamma e \Delta z$, then for all environments $\rho$,
932: \[
933: \dsem e {\esem \Gamma \rho} = \dsem z {\esem \Delta \rho}
934: \text{ and }
935: \esem \Gamma \rho \le \esem \Delta \rho.
936: \]
937: \end{theorem}
938: \begin{proof}
939: The proof in \citep{launchbury} is by induction on the derivation; we only have to give it for the two new cases corresponding to the rules \sRule{Dup} and \sRule{Deep}. We assume that the fresh variables in the rules are chosen to be undefined in $\rho$:
940:
941: \case{$\sDup x$}
942: By induction, we know (i) $\dsem{\fresh x}{\esem{\Gamma, x \mapsto e, \fresh x \mapsto \hat e} \rho} = \dsem{z}{\esem \Delta \rho}$ and (ii) $\esem{\Gamma, x \mapsto e, \fresh x \mapsto \hat e} \rho \le \esem \Delta \rho$.
943:
944: For the first part, we have
945: \begin{align*}
946: &\phantom{{}={}}\dsem{\sDup x}{\esem{\Gamma, x\mapsto e}\rho}\\
947: &= \dsem{x}{\esem{\Gamma, x\mapsto e}\rho}\\
948: %&= \esem{\Gamma, x\mapsto e}\rho\ x\\
949: &= \dsem{e}{\esem{\Gamma, x\mapsto e}\rho}\\
950: &= \dsem{\hat e}{\esem{\Gamma, x\mapsto e}\rho}\\
951: &= \dsem{\hat e}{\esem{\Gamma, x\mapsto e, \fresh x \mapsto \hat e}\rho} && \text{$\fresh x$ fresh}\\
952: %&= \esem{\Gamma, x\mapsto e, \fresh x \mapsto e}\rho\ \fresh x \\
953: &= \dsem{\fresh x}{\esem{\Gamma, x\mapsto e, \fresh x \mapsto \hat e}\rho} \\
954: &= \dsem{z}{\esem \Delta \rho} &&\text{by (i)}
955: \end{align*}
956: as desired.
957:
958: The second part follows from (ii) and from $\fresh x$ being fresh:
959: \begin{align*}
960: \esem{\Gamma, x\mapsto e}\rho \le \esem{\Gamma, x\mapsto e, \fresh x\mapsto \hat e} \rho \le \esem{\Delta}\rho
961: \end{align*}
962:
963: \case{$\sDeepDup x$}
964: Let \mbox{$\Gamma'$} denote the heap in the assumption of the rule, i.e. $\Gamma, x\mapsto e, \fresh x\mapsto \hat e[\fresh y_1/y_1,\ldots,\fresh y_n/y_n],\allowbreak \fresh y_1 \mapsto \sDeepDup {y_1},\ldots,\allowbreak\fresh y_n \mapsto \sDeepDup {y_n}$.
965: By induction, we know (i) $\dsem{\fresh x}{\esem{\Gamma'} \rho} = \dsem{z}{\esem \Delta \rho}$ and (ii) $\esem{\Gamma'} \rho \le \esem \Delta \rho$.
966:
967: The newly introduced variables $\fresh y_i$, $i=1,\ldots,n$, have the same semantics as their original counterparts:
968: \[
969: \dsem{\fresh y_i}{\esem{\Gamma'}\rho}
970: %= \esem{\Gamma'}\rho\ y_i
971: = \dsem{\sDeepDup {y_i}}{\esem{\Gamma'}\rho}
972: %\\
973: = \dsem{y_i}{\esem{\Gamma'}\rho}
974: %= \esem{\Gamma'}\rho\ y_i = \esem{\Gamma, x\mapsto e}\rho\ y_i
975: = \dsem{y_i}{\esem{\Gamma, x\mapsto e}\rho}.
976: \]
977: This implies (iii) $\dsem{\hat e[\fresh y_1/y_1,\ldots,\fresh y_n/y_n]}{\esem{\Gamma'}\rho} = \dsem{e}{\esem{\Gamma, x\mapsto e}\rho}$. Hence
978: {\allowdisplaybreaks[1]
979: \begin{align*}
980: &\phantom{{}={}}\dsem{\sDeepDup x}{\esem{\Gamma, x\mapsto e}\rho}\\
981: &= \dsem{x}{\esem{\Gamma, x\mapsto e}\rho}\\
982: &= \dsem{e}{\esem{\Gamma, x\mapsto e}\rho}\\
983: &= \dsem{\hat e[\fresh y_1/y_1,\ldots,\fresh y_n/y_n]}{\esem{\Gamma'}\rho} &&\text{by (iii)}\\
984: &= \dsem{\fresh x}{\esem{\Gamma'}\rho}\\
985: &= \dsem{z}{\esem \Delta \rho} &&\text{by (i)}
986: \end{align*}
987: }
988: and, by (ii),
989: \begin{align*}
990: \esem{\Gamma, x\mapsto e}\rho \le \esem{\Gamma'} \rho \le \esem{\Delta}\rho.
991: \end{align*}
992: \end{proof}
993:
994: More interesting than the semantic correctness of our additional rules is what properties of \li-deepDup- we can prove with them. Following our intuition from the introduction, we formulate the next theorem, where $\Gamma \subseteq \Delta$ means that $\Gamma$ and $\Delta$ agree on the domain of $\Gamma$ and only new variables are bound.
995:
996: \begin{theorem}
997: Consider the expression
998: \[
999: e=\sLet{x_1' = \sDeepDup x_1,\ldots,x_n'= \sDeepDup x_n} e'
1000: \]
1001: with $\fv{e'} \subseteq \{x_1',\ldots,x_n'\}$. If $\sred \Gamma e \Delta z$ and $z$ is a closed value (i.e.\ $\fv{z} = \emptyset$), then $\Gamma \subseteq \Delta$.
1002: \label{thm:deepdup}
1003: \end{theorem}
1004: This implies that any value on the heap $\Delta$ that was created during the evaluation of $e$ can be freed afterwards.
1005:
1006: The theorem is an immediate consequence of statement (a) of the following Lemma~\ref{lem:deepdup}, with $\Gamma_0 = \Gamma$. We will need the notion of the unguarded reachable set $\ur{\Gamma}{e}$ of an expression $e$ in a context $\Gamma$, which is mutually defined for all expressions as the smallest sets which fulfill the equation
1007: \[
1008: \ur{\Gamma}{e} = \ufv e \cup \textstyle\bigcup_{x\in \ufv e}\ur{\Gamma}{\Gamma\ x}.
1009: \]
1010: Note that $\ufv e \subseteq \ufv {e'}$ implies $\ur\Gamma e \subseteq \ur\Gamma {e'}$. %and, more general, $\ufv e \subseteq \ufv {e'} \cup V$ implies $\ur\Gamma e \subseteq \ur\Gamma {e'} \cup V$ if $V$ is TODO.
1011:
1012: \begin{lemma}
1013: \label{lem:deepdup}
1014: Let $\Gamma_0$ be a heap and $U= \dom\Gamma_0$ its domain. If $\sred\Gamma e \Delta z$, $\Gamma_0 \subseteq \Gamma$ and $U \cap \ur \Gamma e = \emptyset$, then
1015: \begin{enumerate}[(a)]
1016: \item $\Gamma_0 \subseteq \Delta$,
1017: \item $U \cap \ur \Delta z=\emptyset$ and
1018: \item \label{lem:deepdup:3} $U \cap \ur\Gamma y = \emptyset$ implies $U\cap \ur\Delta y = \emptyset$ for $y\in \dom\Gamma$.
1019: \end{enumerate}
1020: \end{lemma}
1021:
1022: \begin{proof}
1023: The proof is by induction on the structure of the derivation $\sred\Gamma e \Delta z$.
1024: \case{$\sLam xe$}
1025: Immediate.
1026:
1027: \case{$\sApp e x$}
1028: From $\ur\Gamma{\sApp e x} = \ur\Gamma{e} \cup \ur\Gamma{x}$ and the assumption $U \cap \ur\Gamma{\sApp e x}= \emptyset$ we have $U \cap \ur\Gamma e = \emptyset$ and $U \cap \ur\Gamma x = \emptyset$. From the first induction hypothesis we obtain (i) $\Gamma_0 \subseteq \Delta$, (ii) $U \cap \ur\Delta {\sLam y e'}= \emptyset$ and (iii) $U \cap \ur\Delta{x} = \emptyset$.
1029:
1030: As $\ur\Delta{e'[x/y]} \subseteq \ur\Delta{\sLam ye'} \cup \ur\Delta{x}$, (ii) and (iii) imply $U \cap \ur\Delta{e'[x/y]} = \emptyset$. With (i) we obtain (a) $\Gamma_0\subseteq\Theta$ and (b) $U\cap \ur\Theta z = \emptyset$ from the second induction hypothesis.
1031:
1032: Statement (c) follows immediately from the induction hypothesizes.
1033:
1034: \case{$x$}
1035: Removing a variable from a heap does not increase unreachable sets, so $\ur\Gamma e \subseteq \ur{\Gamma, x\mapsto e}e \subseteq \ur{\Gamma,x\mapsto e} x$. From $x \in \ur{\Gamma,x \mapsto e} x$ and the assumption $U \cap \ur{\Gamma,x\mapsto e}x = \emptyset$ we have $x \notin U$, thus $\Gamma_0 \subseteq \Gamma$, and $U \cap \ur\Gamma e = \emptyset$. From the induction hypothesis we now obtain $\Gamma_0 \subseteq \Delta$ and $U \cap \ur\Delta z = \emptyset$. As $\Delta \subseteq (\Delta, x \mapsto z)$, $\ufv{z} = \ufv{\hat z}$ and $\ur \Delta z = \ur {\Delta, x \mapsto z} {\hat z}$, the statements (a) $\Gamma_0\subseteq(\Delta,x\mapsto z)$ and (b) $ U\cap \ur{\Delta, x\mapsto z}{\hat z} = \emptyset$ follow.
1036:
1037: Let $y\in \dom\Gamma_0$ with $U\cap \ur{\Gamma,x\mapsto e}y=\emptyset$. As $\ur\Gamma y \subseteq \ur{\Gamma,x\mapsto e} y$ we have $U\cap\ur\Gamma y=\emptyset$ and hence $U\cap\ur{\Delta}y=\emptyset$ from the induction hypothesis. This and (b) imply (c), as $\ur{\Delta,x\mapsto z}y \subseteq \ur{\Delta}y \cup \ur{\Delta}z$.
1038:
1039: \case{$\sLet {x_1=e_1,\ldots,x_n=e_n}e$}
1040: For brevity, let $\Gamma' = \Gamma,x_1\mapsto e_1,\ldots,x_n\mapsto e_n$ and $e_{l} = \sLet {x_1=e_1,\ldots,x_n=e_n}e$.
1041: Clearly $\Gamma_0 \subseteq \Gamma \subseteq \Gamma'$.
1042: Also, for each $e_* \in \{e,e_1,\ldots,e_n\}$ we have $\ufv{e_*} \subseteq \ufv{e_l} \cup \{x_1,\ldots,x_n\}$. This implies
1043: {\allowdisplaybreaks[1]
1044: \begin{align*}
1045: \ur{\Gamma'}e
1046: &= \ufv e \cup \textstyle\bigcup_{x\in \ufv e}\ur{\Gamma'}{\Gamma'\ x} \\
1047: &\subseteq
1048: \begin{aligned}[t]
1049: \ufv {e_l} &\cup \{x_1,\ldots,x_n\}\\
1050: &\cup \textstyle\bigcup_{x\in \ufv {e_l}}\ur{\Gamma'}{\Gamma'\ x} \\
1051: &\cup \ur{\Gamma'}{\Gamma'\ x_1} \cup \cdots \cup \ur{\Gamma'}{\Gamma'\ x_n}
1052: \end{aligned}\\
1053: &=
1054: \begin{aligned}[t]
1055: \ufv {e_l} &\cup \{x_1,\ldots,x_n\}\\
1056: &\cup \textstyle\bigcup_{x\in \ufv {e_l}}\ur{\Gamma'}{\Gamma'\ x}\\
1057: &\cup \ur{\Gamma'}{e_1} \cup \cdots \cup \ur{\Gamma'}{e_n}
1058: \end{aligned}\\
1059: &=
1060: \begin{aligned}[t]
1061: \ufv {e_l} &\cup \{x_1,\ldots,x_n\} \\
1062: &\cup \textstyle\bigcup_{x\in \ufv {e_l}}\ur{\Gamma'}{\Gamma'\ x}
1063: \end{aligned}\\
1064: &= \ur{\Gamma'} {e_l} \cup \{x_1,\ldots,x_n\}\\
1065: &= \ur{\Gamma} {e_l} \cup \{x_1,\ldots,x_n\}.
1066: \end{align*}
1067: }
1068: As all bound variables are distinct from variables in the heap, no $x_i\in U$. From $U\cap \ur\Gamma {e_l}
1069: = \emptyset$, we have $U \cap \ur {\Gamma'} e = \emptyset$ and statements (a) and (b) follow from the induction hypothesis.
1070:
1071: For $y\in \dom\Gamma$ the unreachable set of $y$ cannot contain any of $x_1,\ldots,x_n$, as the heap/term pair $\Gamma : e_l$ is distinctly named, so we have $\ur\Gamma{y} = \ur{\Gamma'}y$ and (c) follows from the induction hypothesis.
1072:
1073: \case{$\sDup x$}
1074: Clearly $\Gamma_0 \subseteq \Gamma, x\mapsto e \subseteq \Gamma, x\mapsto e, \fresh x \mapsto \hat e$. Also,
1075: \begin{align*}
1076: \ur{\Gamma,x\mapsto e, \fresh x\mapsto \hat e}{\fresh x}
1077: &= \ur{\Gamma, x\mapsto e, \fresh x\mapsto \hat e}{\hat e} \cup \{\fresh x\}\\
1078: &= \ur{\Gamma, x\mapsto e}{e} \cup \{\fresh x\}\\
1079: &\subseteq \ur{\Gamma, x\mapsto e}{\sDup x} \cup \{\fresh x\}.
1080: \end{align*}
1081: As $x'$ is fresh, $\fresh x\notin U$ and from $U \cap \ur{\Gamma, x\mapsto e}{\sDup x}= \emptyset$ we have $U \cap \ur{\Gamma,x\mapsto e, \fresh x \mapsto \hat e}{\fresh x}=\emptyset$, so the first statement follows from the induction hypothesis.
1082:
1083: Statement (c) follows immediately as $\fresh x$ is fresh.
1084:
1085: \case{$\sDeepDup x$}
1086: Let $\Gamma'$ denote the heap $\Gamma, x\mapsto e, \fresh x\mapsto \hat e[\fresh y_1/y_1,\ldots,\fresh y_n/y_n],\allowbreak \fresh y_1 \mapsto \sDeepDup y_1,\allowbreak \ldots,\allowbreak \fresh y_1 \mapsto \sDeepDup y_1$.
1087: Recall that, by definition, $\ufv {\sDeepDup x}=\emptyset$, hence $\ur{\Gamma'}{\sDeepDup x} = \emptyset$. So
1088: {\allowdisplaybreaks[1]
1089: \begin{align*}
1090: \ur{\Gamma'}{\fresh x}
1091: &= \{\fresh x\} \cup \ur{\Gamma'}{\hat e[\fresh y_1/y_1,\ldots,\fresh y_n/y_n]} \\
1092: &= \{\fresh x\}
1093: \begin{aligned}[t]
1094: &\cup \ufv{\hat e[\fresh y_1/y_1,\ldots,\fresh y_n/y_n]}\\
1095: &\cup \textstyle\bigcup_{z \in \ufv{\hat e[\fresh y_1/y_1,\ldots,\fresh y_n/y_n]}} \ur{\Gamma'}{\Gamma' \ z}
1096: \end{aligned}\\
1097: &= \{\fresh x\}
1098: \begin{aligned}[t]
1099: &\cup \{\fresh y_1,\ldots, \fresh y_n\}\\
1100: &\cup \textstyle\bigcup_{i=1,\ldots,n} \ur{\Gamma'}{\Gamma'\ \fresh y_i}
1101: \end{aligned}\\
1102: &= \{\fresh x\}
1103: \begin{aligned}[t]
1104: &\cup \{\fresh y_1,\ldots, \fresh y_n\}\\
1105: &\cup \textstyle\bigcup_{i=1,\ldots,n} \ur{\Gamma'}{\sDeepDup {y_i}}
1106: \end{aligned}\\
1107: &= \{\fresh x\} \cup \{\fresh y_1,\ldots, \fresh y_n\}
1108: \end{align*}
1109: }
1110: and, as these are all fresh variables, $U \cap \ur{\Gamma'}{\fresh x} = \emptyset$. Clearly, $\Gamma_0 \subseteq (\Gamma, x\mapsto e) \subseteq \Gamma'$, so the first statement follows from the induction hypothesis.
1111:
1112: Statement (c) follows immediately as the additional variables are fresh.
1113: \end{proof}
1114:
1115: Having cast our intuition of \li-dup- and \li-deepDup- into a precise form using a formal semantics, we now explain how we have implemented this semantics, or rather a pragmatic approximation, in a real environment.
1116:
1117: \section{The prototype implementation}
1118: \label{sec:prototype}
1119:
1120: Our implementation\footnote{Available at \url{http://darcs.nomeata.de/ghc-dup}} works with the Glasgow Haskell Compiler (GHC), version 7.4.1, and requires no modifications to the compiler or its runtime: The code is compiled to a usual object file, linked into the resulting binary and called via the foreign function interface.
1121:
1122: GHC compiles Haskell code first to a polymorphic, explicitly typed lambda-calculus called \emph{Core} \citep{core,system-fc}, then to the \emph{Spineless Tagless G-machine} (STG) \citep{stg}. From there, it generates \emph{Cmm} code, an implementation of the portable assembly language C-{}- which is then compiled to machine code, either directly or via LLVM.
1123:
1124: Our work looks at objects in the sense of the STG, so we only need to worry about data representation on the heap \citep{stg}. Design decisions regarding the earlier transformations, such as the evaluation model \cite{evalapply}, are thus not important here.
1125:
1126: \def\ux{2.2cm}\def\uy{0.6cm}
1127: \begin{figure}
1128: \begin{center}
1129: \begin{tikzpicture}[x=\ux, y=\uy,word/.style={shape=rectangle, draw, minimum width=\ux, minimum height=\uy},>=latex]
1130: \draw (0,0) rectangle +(1,1) node[midway] (ip) {Info pointer};
1131: \draw (1,0) rectangle +(1,1) node[midway] {Payload};
1132: (0,0) node[word] (ip) {Info pointer}
1133: ++(0,-1) node[word, minimum width=2*\ux] {Payload};
1134:
1135: \begin{scope}[yshift=-0.7cm, xshift=2.5cm]
1136: \draw
1137: (0,0) node[word] (tbl) {Code pointer}
1138: ++(0,-1) node[word] {Layout info}
1139: ++(0,-1) node[word] {Other fields};
1140: \end{scope}
1141: \draw[*->] (ip.south) |- (tbl.west);
1142: \draw[*->] (tbl.east) -- ++(.5cm,0) node[right] {Entry code};
1143: \end{tikzpicture}
1144: \end{center}
1145: \caption{The common layout of heap objects}
1146: \label{fig:heap}
1147: \end{figure}
1148:
1149: The common layout of all objects, or closures, on the heap is a pointer to a statically allocated \emph{info table}, followed by the payload (Figure \ref{fig:heap}). The info table indicates the type of the object (not to be confused with the type from the type system – these are completely irrelevant at this stage), contains layout information about the payload required by the garbage collector, namely what words are pointers to other objects and what words are not, and the code to be run when the object is evaluated.
1150:
1151: There are various types of objects on the heap, most important are:
1152: \begin{itemize}
1153: \item \emph{Data constructors}, representing fully evaluated values. The payload are pointers to the parameters of the constructor.
1154: \item \emph{Function closures}, representing functions. Locally defined functions capture their free variables, these are stored in the payload.
1155: \item \emph{Thunks}, which are unevaluated expressions. Again, the payload contains references to their free variables.
1156: \item \emph{Applications} of a function to a number of arguments. This closure type is usually only used by the GHC interpreter, but we use it in the implementation of \li-deepDup-.
1157: \item \emph{Indirections}, which point to another object on the heap in their payload. These are created during evaluation and removed by the garbage collector.
1158: \end{itemize}
1159:
1160:
1161: When a thunk is evaluated, it is replaced by an indirection which points to the result of the evaluation, which can be a data constructor or a function closure. This way, when another reference to the thunk is evaluated, the computation is not repeated but the calculated result is used directly, hence the result is \emph{shared}. The indirections do not stay around forever: The next garbage collector run, which copies all live data, will replace references to indirections by whatever the indirection points to.
1162:
1163: As we want to avoid this sharing, we need to prevent the original reference to be replaced by the indirection. We cannot change the code of the thunk, but we can copy the thunk, thus creating a new copy that is not referenced by other code, and then evaluate that.
1164: The essence of the surprisingly simple code is listed in Figure \ref{fig:dupcode}; the closure to duplicate is passed in the register \ci-R1- and \ci-Hp- is the heap pointer which is increased by \ci-ALLOC_PRIM-.
1165:
1166: \begin{figure}
1167: \begin{cmm}
1168: dupClosure {
1169: clos = UNTAG(R1);
1170: // Allocate space for the new closure
1171: (len) = foreign "C" closure_sizeW(clos "ptr") [];
1172: ALLOC_PRIM(WDS(len), R1_PTR, dupClosure);
1173: copy = Hp - WDS(len) + WDS(1);
1174: p = 0;
1175: for: // Copy the info pointer and payload
1176: if(p < len) {
1177: W_[copy + WDS(p)] = W_[clos + WDS(p)];
1178: p = p + 1;
1179: goto for;
1180: }
1181: RET_P(copy);
1182: }
1183: \end{cmm}
1184: \caption{The Cmm code for \li-dup-}
1185: \label{fig:dupcode}
1186: \end{figure}
1187:
1188: As discussed in Section \ref{sec:deepdup}, this simple approach is not always sufficient, and we want a recursive variant, \li-deepDup-. This function, shown in Figure \ref{fig:deepdupcode}, needs to access the info table of the closure to figure out what part of the payload is a pointer to another heap object. For every referenced object, an application thunk is created which applies \li-deepDup- (or rather the variant \li!deepDupFun! with the better suited type \li!a -> a!), unless we are about to \li-deepDup- a \li-deepDup- thunk. In that case, we just copy it, but leave the argument alone, reflecting the use of $\ufv e$ instead of $\fv e$ in the Rule \sRule{Deep} in the formal semantics. The code listing does not include a few shortcuts, e.g.\ data constructors without pointer arguments such as integer values are not copied.
1189:
1190: \begin{figure}
1191: \begin{cmm}
1192: deepDupClosure {
1193: clos = UNTAG(R1);
1194: // Allocate space for the new closure
1195: (len) = foreign "C" closure_sizeW(clos "ptr") [];
1196: ptrs = TO_W_(%INFO_PTRS(%GET_STD_INFO(clos)));
1197: bytes = WDS(len) + ptrs * SIZEOF_StgAP + WDS(ptrs);
1198: ALLOC_PRIM(bytes, R1_PTR, dupClosure);
1199: copy = Hp - WDS(len) + WDS(1);
1200: p = 0;
1201: for1: // Copy the info pointer and payload
1202: if(p < len) {
1203: W_[copy + WDS(p)] = W_[clos + WDS(p)];
1204: p = p + 1;
1205: goto for1;
1206: }
1207: // Do not wrap \textup{deepDup} thunks again
1208: if (W_[copy] == stg_ap_2_upd_info &&
1209: W_[copy + WDS(1)] == Dup_deepDupFun_closure) {
1210: goto done;
1211: }
1212: if
1213: p = 0;
1214: for2: // Wrap all referenced closures in \textup{deepDup} thunks
1215: if(p < ptrs) {
1216: ap = Hp - bytes + WDS(1)
1217: + p * SIZEOF_StgAP + WDS(p);
1218: W_[ap] = stg_ap_2_upd_info;
1219: W_[ap + WDS(1)] = Dup_deepDupFun_closure;
1220: W_[ap + WDS(2)] = W_[clos + WDS(p)];
1221: W_[copy + WDS(p)] = ap;
1222: p = p + 1;
1223: goto for2;
1224: }
1225: done:
1226: RET_P(copy);
1227: }
1228: \end{cmm}
1229: \caption{The Cmm code for \li-deepDup-}
1230: \label{fig:deepdupcode}
1231: \end{figure}
1232:
1233:
1234: \subsection{Limitations of the implementation}
1235: \label{sec:shortcomings}
1236:
1237: Our implementation is but a prototype; it does not yet work in all situations. One large problem is posed by statically allocated thunks: A value, say \li-nats = [0..]-, defined at the module level is compiled to a thunk with closure type \ci-THUNK_STATIC-, also called a constant applicative form (CAF), and receives special treatment by the garbage collector. Copying such a closure to the heap using the code above would make the garbage collector abort, as it does not expect a static thunk to be found on the heap. But it is not possible to change the type of the closure, as the info table containing the type lies directly next to the code. And in order to create a modified info table somewhere else, the code needs to be copied as well. Therefore, \li-dup- and \li-deepDup- currently does not work for static thunks. When it is passed such a thunk, it prints a warning and returns the original reference, retaining sharing.
1238:
1239: It should be possible for \li-dup- to support static thunks with some additional information in the compiled code. Currently, when execution enters a static thunk and the stack and heap checks have been passed, the thunk is replaced by an indirection into the heap and an update frame is pushed on the stack. If there was a way to jump over the code that sets up the indirection and update frame, e.g.\ via an alternative entry point included in the info table, \li-dup- could create a thunk on the heap that calls the static thunk via this route, effectively kicking off evaluation without affecting the original static thunk. For \li-deepDup- things are more complicated, as references to static objects are not part of the heap object, but are scattered throughout the machine code. Moving these references to the heap would solve the issue here at hand, but is clearly too expensive.
1240:
1241: Also, the prototype does not take multithreaded programs into account and will likely produce bad results when used in such an environment, e.g.\ when another thread replaces a thunk by an indirection during the thunk copy loop in \ci-dupClosure-. Similarly, there are several specialized closure type (arrays, mutable references, weak pointers\citep{weakpointers} and others \citep[page HeapObjects]{commentary}). For each of them, we would need to determine whether they can be safely duplicated and if so, whether this is actually useful.
1242:
1243: In the presence of Lazy IO, duplicating thunks can be outright dangerous: Not only can the original and the duplicated thunk evaluate to different values but this can make the program crash, e.g.\ when one copy is done evaluating and causes a file to be closed, while the second copy continues to read from it. Generally everything implemented with \li-unsafePerformIO- is prone to behave badly when combined with \li-dup- or \li-deepDup-.
1244:
1245: Function closures need special treatment as there are cases where code assumes a certain reference to always be a function closure and never a thunk that will evaluate to a function. But this is what \li-deepDup- wants to create. Currently, \li-deepDup- will in this case leave the reference as it is. A solution would be to copy the function closure eagerly, so that the reference in the copy again points to a function closure. This would require more sophisticated code to detect cycles.
1246:
1247: \section{Conclusions and further work}
1248:
1249: While Haskell gives the programmer great devices to get their programs to do the right thing, such as referential transparency and the type system, she has less means to analyze and control their runtime behavior. Several commercial users have mentioned this as one of the main drawbacks of Haskell \citep{sampson,wehr,hesselink}. This problem deserves more attention and we hope that this work is one step towards a Haskell with better controllable and understandable time and space behavior.
1250:
1251: We have shown the feasibility of an explicit sharing-preventing operator in a lazy functional language. We provided two variants, \li-dup- and \li-deepDup-, the former is simpler, but possibly more subtle to put to use effectively, the latter works more predictably, but may impose a larger performance penalty. This is, on a prototypical level, possible with an unmodified Haskell compiler.
1252:
1253: As described in Section \ref{sec:shortcomings}, there is work to be done on the implementation before it can be used in production code. Some of that might require changes to the compiler code. Given how sensitive the code is to changes in the runtime representation of Haskell values, a productive version of \li-dup- would probably have to be shipped along with the compiler.
1254:
1255: %From the programmer’s point of view, our primitives may be a bit delicate to use, as she has few way to specify or analyze the state of evaluation and sharing during the execution of her program. This is a general problem of Haskell and deserves more attention in general. We hope that this work is one step towards a Haskell with better controllable and understandable time and space behavior.
1256:
1257:
1258: \acks
1259:
1260: I would like to thank Andreas Lochbihler for fruitful discussions and proof-reading and the anonymous referees for being supportive of the idea and constructive about the presentation. This work was supported by the Deutsche Telekom Stiftung.
1261:
1262: \bibliographystyle{abbrvnat}
1263: \bibliography{bib}
1264:
1265: \end{document}
Generated by git2html.