in "let t= a!i" a!i might be out of bounds ?<br><br>
<div class="gmail_quote">On Fri, Aug 12, 2011 at 9:52 AM, Anton Kholomiov <span dir="ltr"><<a href="mailto:anton.kholomiov@gmail.com">anton.kholomiov@gmail.com</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote"><span style="COLOR: rgb(51,51,153)"><font color="#000000">Just to make it explicit, is it </font> <br> <br>
\a i -></span>
<div class="im"><br style="COLOR: rgb(51,51,153)"><span style="COLOR: rgb(51,51,153)"> let t = a ! i in</span><br style="COLOR: rgb(51,51,153)"><span style="COLOR: rgb(51,51,153)"> if i >= 0 then</span><br style="COLOR: rgb(51,51,153)">
<span style="COLOR: rgb(51,51,153)"> t</span><br style="COLOR: rgb(51,51,153)"><span style="COLOR: rgb(51,51,153)"> else if i > 0 then</span><br style="COLOR: rgb(51,51,153)"><span style="COLOR: rgb(51,51,153)"> t + a ! (i-1)</span><br style="COLOR: rgb(51,51,153)">
<span style="COLOR: rgb(51,51,153)"> else ....</span><br><br></div>bad idea, because of last else-case? Can it be mended with<br>one another pass for if-expressions?<br><br>The upcoming distilled tutorial at DSL 2011 - thank you for the link.<br>
<br>I'm going to experiment with data-reify, while the library you've mentioned is<br>OCaml only.<br><br><br>
<div class="gmail_quote">2011/8/12 <span dir="ltr"><<a href="mailto:oleg@okmij.org" target="_blank">oleg@okmij.org</a>></span>
<div>
<div></div>
<div class="h5"><br>
<blockquote style="BORDER-LEFT: rgb(204,204,204) 1px solid; MARGIN: 0pt 0pt 0pt 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote"><br>I guess you mean the function that converts an abstract syntax tree to<br>a directed acyclic graph (DAG).<br>
<br>Just for completeness I should mention that if the object language has<br>effects including non-termination, one has to be careful eliminating<br>seemingly common expressions. For example, in<br><br> \a i -><br>
if i >= 0 then<br> a ! i<br> else if i > 0 then<br> a ! i + a ! (i-1)<br> else ....<br><br>we see the expression (a ! i) repeated in both branches of<br>the conditional. Eliminating the `duplicate' by pulling it out<br>
<br> \a i -><br> let t = a ! i in<br> if i >= 0 then<br> t<br> else if i > 0 then<br> t + a ! (i-1)<br> else ....<br><br>would be wrong, wouldn't it?<br>
<br>This issue has been extensively investigated in the Fortran compiler<br>community; Elliott, Finne and de Moor's ``Compiling Embedded Languages''<br>(JFP 2003) talks about it at length.<br><br><br>The standard technique to detect occurrences of common subexpressions<br>
is so-called hash-consing. There are (OCaml) libraries for it:<br><br> author = {Jean-Christophe Filli{\^a}tre and Sylvain Conchon},<br> title = {Type-Safe Modular Hash-Consing},<br> pages = {12--19},<br>
crossref = "ml2006",<br> doi = "10.1145/1159876.1159880",<br><br>The upcoming distilled tutorial at DSL 2011<br> <a href="http://dsl2011.bordeaux.inria.fr/index.php?option=com_content&view=article&id=2&Itemid=2" target="_blank">http://dsl2011.bordeaux.inria.fr/index.php?option=com_content&view=article&id=2&Itemid=2</a><br>
<br>will present a Haskell library for hash-consing. The library can work<br>with the standard Haskell Hash-tables or without them (using Data.Map,<br>for example). The library does _not_ rely on Stable names and other<br>
internal GHC operations with unstable semantics. The library will find<br>all common sub-expressions.<br><br><br>Incidentally, despite the Lisp-sounding name, hash-consing was<br>invented before Lisp. It was described, for the English audience, in<br>
the first volume of Comm. ACM, in 1958:<br><br>@Article{ Ershov-hash-consing,<br> author = {A. P. Ershov},<br> title = {On programming of arithmetic operations},<br> journal = "Communications of the {ACM}",<br>
year = 1958,<br> volume = 1,<br> number = 8,<br> pages = {3--6},<br> doi ="10.1145/368892.368907",<br> url = "<a href="http://portal.acm.org/citation.cfm?id=368907" target="_blank">http://portal.acm.org/citation.cfm?id=368907</a>"<br>
}<br><br>The translation is quite accurate, as far as I could see, but misses<br>the flowcharts and the diagram of the original paper. This short paper<br>fully describes what we now call hash tables, hash functions, useful<br>
properties of hash functions, and hash-consing. The article analyzes<br>the time complexity of the algorithm. Since the algorithm has two<br>exits, writing programs in the continuation-passing style must have been<br>familiar back then.<br>
<br><br>The library to be presented at DSL 2011 unwittingly follows Ershov's<br>algorithm closely. The library is (hopefully) better described (see<br>the preface to the English translation of Ershov's paper). Nowadays,<br>
starting a paper with the phrase ``All unexplained terms are those<br>from [1]'' (where [1] is the single reference) would not be taken<br>kindly by reviewers.<br><br></blockquote></div></div></div><br><br>_______________________________________________<br>
Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br>