<div>I have been exploring a weak form of runtime strictness analysis in a tracing JIT project of my own in the spirit of TraceMonkey. Basically a tracing JIT doesn&#39;t compile blocks of code but instead once a tracing point has been passed often enough, it starts a trace from that point logging the series of instructions executed to a bounded log. If you make it back to the starting point before the log fills up then you&#39;ve identified a superblock with a bunch of side exits for handling when your assumptions are violated. </div>

<div> </div>
<div>What is interesting is in a lazy setting, if you are tracing a bytecode representation that knows about allocation and thunks, you can do some additional optimizations in here. If on every path to a side exit or the end of the loop you find that the thunk is evaluated you can evaluate it strictly and move its execution earlier in the trace. This gives you a weak form of runtime strictness analysis. If the pointer to that thunk never escapes, then you can unbox the contents of the thunk and operate on its members in registers. Add constant folding, polyinline caching to improve branch prediction for spineless tagless g-machine thunk evaluation, and code migration to the side exits and it becomes an interesting runtime system.</div>

<div> </div>
<div>But the key concern for the sake of the current discussion is that it models strictness analysis and unboxing quite naturally as an artifact of the jitting process. So that said, a form of conservative strictness analysis at runtime is possible.</div>

<div> </div>
<div>-Edward Kmett<br></div>
<div class="gmail_quote">On Sun, Jun 14, 2009 at 7:42 PM, Paul Chiusano <span dir="ltr">&lt;<a href="mailto:paul.chiusano@gmail.com">paul.chiusano@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Hello, 
<div><br></div>
<div>I was recently trying to figure out if there was a way, at runtime, to do better strictness analysis for polymorphic HOFs, for which the strictness of some arguments might depend on the strictness of the strictness of function types that are passed as arguments [1]. As an example, consider foldl. The &#39;seed&#39; parameter of foldl can be made strict as long as the binary function used for the fold is strict in its arguments. Unfortunately, because strictness analysis is done statically, Haskell can&#39;t assume anything about the strictness of the binary function - assuming we only compile one instance of foldl, it must be the most conservative version possible, and that means making the seed parameter lazy. :-(</div>

<div><br></div>
<div>I started thinking about ways you could to a check at runtime for this sort of thing, something to the effect of asking foldl, before heap-allocating a thunk for the seed parameter, whether that parameter could be made strict. foldl could then inspect other arguments that have been supplied, and based on these arguments, evaluate or go ahead with creating a thunk the seed parameter. It&#39;s a runtime cost, sure, but would it be more than the cost of having to do an additional heap allocation? In any case a small runtime cost might be worth it if the analysis becomes more uniform.</div>

<div><br></div>
<div>So, my question is: does doing this sort of runtime analysis seem like a horrible idea? Is it even possible? Has anyone tried this in the past? (So far I haven&#39;t found anything, but would love references if people have them.)</div>

<div><br></div>
<div>Note that I&#39;m not suggesting Haskell should do anything like this. I&#39;m playing around with the ideas because I&#39;m interesting in creating a lazy language and I was hoping to have strictness analysis be very predictable and uniform, something the programmer can count on and use to simply reason about space usage ... which might be hopelessly unrealistic goal! I guess the more general question is - is &quot;perfect&quot; strictness analysis (however that is defined) possible, if we&#39;re willing to incur some runtime cost? What would that look like?</div>

<div><br></div>
<div>Best,</div>
<div>Paul</div>
<div><br></div>
<div>[1]: </div>
<div>More background on my thinking here - a bit half-baked, so bear with me!</div>
<div>  <a href="http://pchiusano.blogspot.com/2009/06/perfect-strictness-analysis-part-1.html" target="_blank">http://pchiusano.blogspot.com/2009/06/perfect-strictness-analysis-part-1.html</a><br></div>
<div>  <a href="http://pchiusano.blogspot.com/2009/06/perfect-strictness-analysis-part-2.html" target="_blank">http://pchiusano.blogspot.com/2009/06/perfect-strictness-analysis-part-2.html</a><br></div><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>