Strictness analysis

<h2 id="approaches-to-strictness-analysis">Approaches to strictness analysis</h2>
<h3>Forward abstract interpretation</h3>
<p>Strictness analysis can be characterized as a forward <a href="/facts/Abstract_interpretation/cj6wjzu1">abstract interpretation</a> which approximates each function in the program by a function that maps divergence properties of the arguments onto divergence properties of the results. In the classical approach pioneered by <a href="/facts/Alan_Mycroft/AeQBnmhM">Alan Mycroft</a>, the abstract interpretation used a two-point <a href="/facts/Domain_theory/G1wRMK2K">domain</a> with 0 denoting the set 
  
    
      
        {
        ⊥
        }
      
    
    {\displaystyle \{\bot \}}
  
 considered as a subset of the argument or return type, and 1 denoting all values in the type.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<h3>Demand analysis</h3>
<p>The <a href="/facts/Glasgow_Haskell_Compiler/4msB3KFN">Glasgow Haskell Compiler</a> (GHC) uses a backward abstract interpretation known as demand analysis to perform strictness analysis as well as other program analyses. In demand analysis, each function is modelled by a function from value demands on the result to value demands on the arguments. A function is strict in an argument if a demand for its result leads to a demand for that argument.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h3>Projection-based strictness analysis</h3>
<p>Projection-based strictness analysis, introduced by <a href="/facts/Philip_Wadler/ShX91nId">Philip Wadler</a> and <a href="/facts/R.J.M._Hughes/1Mp9trs6">R.J.M. Hughes</a>, uses strictness <a href="/facts/Idempotent/khbSpexv">projections</a> to model more subtle forms of strictness, such as head-strictness in a list argument. (By contrast, GHC's demand analysis can only model strictness within product types, i.e., datatypes that only have a single <a href="/facts/Data_constructor/Fn9KhnAb">constructor</a>.) A function 
  
    
      
        f
      
    
    {\displaystyle f}
  
 is considered head-strict if 
  
    
      
        f
        =
        f
        ∘
        π
      
    
    {\displaystyle f=f\circ \pi }
  
, where 
  
    
      
        π
      
    
    {\displaystyle \pi }
  
 is the projection that head-evaluates its list argument.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p><p>There was a large body of research on strictness analysis in the 1980s.
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Mycroft, Alan (1980). "The theory and practice of transforming call-by-need into call-by-value". Lecture Notes in Computer Science: Proc. 4th Intl. Symp. on Programming, Vol. 83. Springer-Verlag. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"The GHC Commentary: Demand analyser in GHC". Retrieved 2014-02-12. <a href="https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Demand" target="_blank">https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Demand</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Wadler, P.; R.J.M. Hughes (1987). "Projections for strictness analysis". Functional programming and computer architecture; LNCS 274. Springer-Verlag. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Strictness analysis open-in-new

Strictness analysis