Probabilistically Accurate Program Transformations
18th International Symposium, SAS 2011, Venice, Italy, September 14-16, 2011. Proceedings
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73897 https://orcid.org/0000-0003-0313-9270 https://orcid.org/0000-0001-8095-8523 |
| _version_ | 1826216094168252416 |
|---|---|
| author | Misailovic, Sasa Roy, Daniel Rinard, Martin C. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Misailovic, Sasa Roy, Daniel Rinard, Martin C. |
| author_sort | Misailovic, Sasa |
| collection | MIT |
| description | 18th International Symposium, SAS 2011, Venice, Italy, September 14-16, 2011. Proceedings |
| first_indexed | 2024-09-23T16:42:13Z |
| format | Article |
| id | mit-1721.1/73897 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:42:13Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/738972022-09-29T20:51:53Z Probabilistically Accurate Program Transformations Misailovic, Sasa Roy, Daniel Rinard, Martin C. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Misailovic, Sasa Roy, Daniel Rinard, Martin C. 18th International Symposium, SAS 2011, Venice, Italy, September 14-16, 2011. Proceedings The standard approach to program transformation involves the use of discrete logical reasoning to prove that the transformation does not change the observable semantics of the program. We propose a new approach that, in contrast, uses probabilistic reasoning to justify the application of transformations that may change, within probabilistic accuracy bounds, the result that the program produces. Our new approach produces probabilistic guarantees of the form ℙ(|D| ≥ B) ≤ ε, ε ∈ (0, 1), where D is the difference between the results that the transformed and original programs produce, B is an acceptability bound on the absolute value of D, and ε is the maximum acceptable probability of observing large |D|. We show how to use our approach to justify the application of loop perforation (which transforms loops to execute fewer iterations) to a set of computational patterns. National Science Foundation (U.S.) (Grant CCF-0811397) National Science Foundation (U.S.) (Grant CCF-0905244) National Science Foundation (U.S.) (Grant CCF-1036241) National Science Foundation (U.S.) (Grant IIS-0835652) United States. Dept. of Energy (Grant DE-SC0005288) 2012-10-11T19:41:16Z 2012-10-11T19:41:16Z 2011-09 2011-09 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-23701-0 http://hdl.handle.net/1721.1/73897 Misailovic, Sasa, Daniel M. Roy, and Martin C. Rinard. “Probabilistically Accurate Program Transformations.” Static Analysis. Ed. Eran Yahav. LNCS Vol. 6887. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 316–333. https://orcid.org/0000-0003-0313-9270 https://orcid.org/0000-0001-8095-8523 en_US http://dx.doi.org/10.1007/978-3-642-23702-7_24 Static Analysis Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
| spellingShingle | Misailovic, Sasa Roy, Daniel Rinard, Martin C. Probabilistically Accurate Program Transformations |
| title | Probabilistically Accurate Program Transformations |
| title_full | Probabilistically Accurate Program Transformations |
| title_fullStr | Probabilistically Accurate Program Transformations |
| title_full_unstemmed | Probabilistically Accurate Program Transformations |
| title_short | Probabilistically Accurate Program Transformations |
| title_sort | probabilistically accurate program transformations |
| url | http://hdl.handle.net/1721.1/73897 https://orcid.org/0000-0003-0313-9270 https://orcid.org/0000-0001-8095-8523 |
| work_keys_str_mv | AT misailovicsasa probabilisticallyaccurateprogramtransformations AT roydaniel probabilisticallyaccurateprogramtransformations AT rinardmartinc probabilisticallyaccurateprogramtransformations |