CUED Publications database

Probabilistically accurate program transformations

Misailovic, S and Roy, DM and Rinard, MC (2011) Probabilistically accurate program transformations. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6887 L. pp. 316-333. ISSN 0302-9743

Full text not available from this repository.


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. © 2011 Springer-Verlag Berlin Heidelberg.

Item Type: Article
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 15 Dec 2015 13:36
Last Modified: 18 Jan 2016 06:19
DOI: 10.1007/978-3-642-23702-7_24