Osprey: A practical type system for validating dimensional unit correctness of C programs

• Main Authors: JIANG, Lingxiao, SU, Zhendong
• 格式: text
• 語言: English
• 出版: Institutional Knowledge at Singapore Management University 2006
• 主題: Gaussian elimination; measurement units; dimensional analysis; constraint-based analysis; type systems; Software Engineering
• 在線閱讀: https://ink.library.smu.edu.sg/sis_research/1331; https://ink.library.smu.edu.sg/context/sis_research/article/2330/viewcontent/OspreyPracticalSystemValidatingUnitCorrect_2006.pdf
• 機構: Singapore Management University

Misuse of measurement units is a common source of errors in scientific applications, but standard type systems do not prevent such errors. Dimensional analysis in physics can be used to manually detect such errors in physical equations. It is, however, not feasible to perform such manual analysis for programs computing physical equations because of code complexity. In this paper, we present a type system to automatically detect potential errors involving measurement units. It is constraint-based: we model units as types and flow of units as constraints. However, standard type checking algorithms are not powerful enough to handle units because of their abelian group nature (e.g., being commutative, multiplicative, and associative). Our system combines techniques such as type inference and Gaussian Elimination to overcome this problem. We have implemented Osprey, a prototype of the system for C programs, and evaluated it on various test programs, including computational physics and mechanical engineering applications. Osprey discovered unknown errors in mature code; it is precise with few false positives; it is also efficient and scales to large programs---we have successfully used it to analyze programs with hundreds of thousands of lines of code.