Definite assignment analysis: Difference between revisions

Revision as of 00:59, 5 February 2014

Revision as of 10:05, 5 March 2014

Line 2:

==Motivation==

In [[C programming language|C]] and [[C++]] programs, a source of particularly difficult-to-diagnose errors is the nondeterministic behavior that results from reading [[uninitialized variablesvariable]]s; this behavior can vary between platforms, builds, and even from run to run.

There are two common ways to solve this problem. One is to ensure that all locations are written before they are read. [[Rice's theorem]] establishes that this problem cannot be solved in general for all programs; however, it is possible to create a conservative (imprecise) analysis that will accept only programs that satisfy this constraint, while rejecting some correct programs, and definite assignment analysis is such an analysis. The [[Java programming language|Java]]<ref>{{cite web | author = J. Gosling, B. Joy, G. Steele, G. Bracha | title = The Java Language Specification, 3rd Edition | url= http://java.sun.com/docs/books/jls/third_edition/html/defAssign.html | accessdate = December 2, 2008 | pages = Chapter 16 (pp.527&ndash;552)}}</ref> and [[C Sharp (programming language)|C#]]<ref>{{cite web | title = Standard ECMA-334, C# Language Specification | work = ECMA International | url = http://www.ecma-international.org/publications/standards/Ecma-334.htm | accessdate = December 2, 2008 | pages = Section 12.3 (pp.122&ndash;133)}}</ref> programming language specifications require that the compiler report a compile-time error if the analysis fails. Both languages require a specific form of the analysis that is spelled out in meticulous detail. In Java, this analysis was formalized by Stärk et al.,<ref>{{cite book |title=Java and the Java Virtual Machine: Definition, Verification, Validation |last=Stärk |first=Robert F. |coauthors=E. Borger, Joachim Schmid |year=2001 |publisher=Springer-Verlag New York, Inc. |___location=Secaucus, NJ, USA |isbn=3-540-42088-6 |pages=Section 8.3}}</ref> and some correct programs are rejected and must be altered to introduce explicit unnecessary assignments. In C#, this analysis was formalized by Fruja, and is precise as well as sound, in the sense that all variables assigned along all control flow paths will be considered definitely assigned.<ref name="fruja">{{cite journal |doi=10.5381/jot.2004.3.9.a2 |last=Fruja |first=Nicu G. |date=October 2004|title=The Correctness of the Definite Assignment Analysis in C# |journal=Journal of Object Technology |volume=3 |issue=9 |pages=29&ndash;52 |url=http://www.jot.fm/issues/issue_2004_10/article2 |accessdate=2008-12-02 | quote=We actually prove more than correctness: we show that the solution of the analysis is a perfect solution (and not only a safe approximation).}}</ref> The [[Cyclone (programming language)|Cyclone]] language also requires programs to pass a definite assignment analysis, but only on variables with pointer types, to ease porting of C programs.<ref>{{cite web | title = Cyclone: Definite Assignment | work = Cyclone User's Manual | url = http://cyclone.thelanguage.org/wiki/Definite%20Assignment | accessdate = December 16, 2008 }}</ref>