Strictness analysis


Strictness analysis

In computer science, strictness analysis refers to any algorithm used to prove that a function in a non-strict functional programming language is strict in one or more of its arguments. This information is useful to compilers because strict functions can be compiled more efficiently. Thus, if a function is proven to be strict (using strictness analysis) at compile time, it can be compiled to use a more efficient calling convention without changing the meaning of the enclosing program.

Note that a function f is said to "diverge" if it returns {ot}: operationally, that would mean that f either causes abnormal termination of the enclosing program (e.g., failure with an error message) or that it loops infinitely. The notion of "divergence" is significant because a strict function is one that always diverges when given an argument that diverges, whereas a lazy (or non-strict) function is one that may or may not diverge when given such an argument. Strictness analysis attempts to determine the "divergence properties" of functions, which thus identifies some functions that are strict.

Approaches to strictness analysis

Forward abstract interpretation

* Strictness analysis can be characterized as a forward abstract interpretation 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 Alan Mycroft, the abstract interpretation used a two-point domain with 0 denoting the set {ot} considered as a subset of the argument or return type, and 1 denoting all values in the type. [cite conference
first = Alan
last = Mycroft
title = The theory and practice of transforming call-by-need into call-by-value
booktitle = Lecture Notes in Computer Science: Proc. 4th intl. symp. on programming, vol. 83
publisher = Springer-Verlag
date = 1980
]

Demand analysis

The Glasgow Haskell Compiler 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. [cite web
authorlink = The GHC Team
title = The GHC Commentary: Demand Analysis
url = http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler
accessdate = 2007-02-04
]

Projection-based strictness analysis

Projection-based strictness analysis, introduced by Philip Wadler and R.J.M. Hughes, uses strictness projections 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 constructor.) A function f is considered head-strict if f = f circ pi, where pi is the projection that head-evaluates its list argument. [cite conference
first = P.
last = Wadler
coauthors = R.J.M. Hughes
title = Projections for strictness analysis
booktitle = Functional programming and computer architecture; LNCS 274
publisher = Springer-Verlag
date = 1987
]

There was a large body of research on strictness analysis in the 1980s.

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Analysis — • The process by which anything complex is resolved into simple, or at least less complex parts or elements Catholic Encyclopedia. Kevin Knight. 2006. Analysis     Analysis      …   Catholic encyclopedia

  • Constructed product result analysis — In the field of compiler implementation in computer science, constructed product result analysis (or CPR analysis) is a static analysis that determines which functions in a given program can return multiple results in an efficient manner.… …   Wikipedia

  • Cross Impact Analysis — is a methodology developed by Theodore Gordon and Olaf Helmer in the 1966 to help determine how relationships between events would impact resulting events and reduce uncertainty in the future.[1] The Central Intelligence Agency (CIA) became… …   Wikipedia

  • Glasgow Haskell Compiler — Infobox Software name = Glasgow Haskell Compiler developer = University of Glasgow latest release version = 6.8.3 latest release date = Jun 17, 2008 operating system = Cross platform genre = Compiler license = BSD website =… …   Wikipedia

  • Strict function — A strict function in the denotational semantics of programming languages is a function f where . The entity , called bottom, denotes an expression which does not return a normal value, either because it loops endlessly or because it aborts due to …   Wikipedia

  • Samson Abramsky — Professor Samson Abramsky FRS is a computer scientist. Since the Year 2000, he has been a Fellow of the Royal Society of Edinburgh, a Fellow of Wolfson College, Oxford and Christopher Strachey Professor of Computing at Oxford University Computing …   Wikipedia

  • Economy (Eastern Orthodox Church) — In the Eastern Orthodox and Greek Catholic Churches and in the teaching of the Church Fathers which undergirds the theology of those Churches, economy or oeconomy (Greek: οικονόμια, economia ) has several meanings. [Lampe, et al, A Patristic… …   Wikipedia

  • Non-interference (security) — This article is about a security policy model. For the Buddhist concept, see Noninterference (Buddhism). Non interference is a strict multilevel security policy model, first described by Goguen and Meseguer in 1982, and amplified further in 1984 …   Wikipedia

  • Mill, John Stuart: Logic and metaphysics — J.S.Mill Logic and metaphysics John Skorupski ENLIGHTENMENT AND ROMANTICISM IN MILL’S PHILOSOPHY Mill’s importance as one of the major figures of nineteenth century politics and culture, and the current interest in him as a moral and political… …   History of philosophy

  • Casualties of the Iraq War — This article is about casualties for the war beginning in 2003. For other wars, see Iraq war (disambiguation) …   Wikipedia