<span style="color: rgb(51, 51, 153);"><font color="#000000">Just to make it explicit, is it </font> <br>  <br>     \a i -&gt;</span><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 &gt;= 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 &gt; 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>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&#39;m going to experiment with data-reify, while the library you&#39;ve mentioned is<br>
OCaml only.<br><br><br><div class="gmail_quote">2011/8/12  <span dir="ltr">&lt;<a href="mailto:oleg@okmij.org">oleg@okmij.org</a>&gt;</span><br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<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 -&gt;<br>
          if i &gt;= 0 then<br>
             a ! i<br>
          else if i &gt; 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&#39; by pulling it out<br>
<br>
        \a i -&gt;<br>
          let t = a ! i in<br>
          if i &gt;= 0 then<br>
             t<br>
          else if i &gt; 0 then<br>
             t + a ! (i-1)<br>
          else ....<br>
<br>
would be wrong, wouldn&#39;t it?<br>
<br>
This issue has been extensively investigated in the Fortran compiler<br>
community; Elliott, Finne and de Moor&#39;s ``Compiling Embedded Languages&#39;&#39;<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      = &quot;ml2006&quot;,<br>
  doi           = &quot;10.1145/1159876.1159880&quot;,<br>
<br>
The upcoming distilled tutorial at DSL 2011<br>
  <a href="http://dsl2011.bordeaux.inria.fr/index.php?option=com_content&amp;view=article&amp;id=2&amp;Itemid=2" target="_blank">http://dsl2011.bordeaux.inria.fr/index.php?option=com_content&amp;view=article&amp;id=2&amp;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       = &quot;Communications of the {ACM}&quot;,<br>
  year          = 1958,<br>
  volume        = 1,<br>
  number        = 8,<br>
  pages         = {3--6},<br>
  doi           =&quot;10.1145/368892.368907&quot;,<br>
  url           = &quot;<a href="http://portal.acm.org/citation.cfm?id=368907" target="_blank">http://portal.acm.org/citation.cfm?id=368907</a>&quot;<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&#39;s<br>
algorithm closely. The library is (hopefully) better described (see<br>
the preface to the English translation of Ershov&#39;s paper). Nowadays,<br>
starting a paper with the phrase ``All unexplained terms are those<br>
from [1]&#39;&#39; (where [1] is the single reference) would not be taken<br>
kindly by reviewers.<br>
<br>
</blockquote></div><br>