RUI: Provable Safety for Performance-Improving Free Theorems-Based Program Transformations

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

Proposal Number 0429072 Provable Safety for Performance-Improving Free Theorems-Based Program Transformations Patricia Johann Rutgers University New Brunswick This research focuses on techniques for formally proving the safety of certain transformations which improve the performance of programs written in pure functional languages. The transformations under consideration are based on so-called "inequational free theorems". Such transformations can significantly reduce the tension between expressivity and efficiency in functional languages by automatically removing data constructors and other data-manipulating operators from programs which process data uniformly; formal proofs of safety ensure that transformations which do so do not alter in unexpected ways the observable behavior of the programs to which they are applied. Inequational free theorems-based program transformations for purely strict functional languages, strict functional languages with explicit laziness annotations, and nonstrict languages with polymorphic strictness primitives are considered, and operational, as well as denotational, semantics-based approaches to their provable safety are investigated. In addition, qualified type systems are used to conduct a fine-grained analysis of the ways in which the standard equational free theorems for nonstrict languages are weakened for functional languages which are not purely nonstrict.