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

提案编号0429072可证明的安全性性能提高自由定理为基础的程序transformationsPatricia JohannRutgers大学新不伦瑞克本研究的重点是技术正式证明的安全性，某些转换，提高性能的程序编写的纯函数语言。所考虑的转换是基于所谓的“不等式自由定理”。这样的转换可以通过自动从统一处理数据的程序中删除数据构造器和其他数据操作操作符来显着减少函数式语言中表达性和效率之间的紧张关系;安全性的正式证明确保这样做的转换不会以意想不到的方式改变应用它们的程序的可观察行为。不平等的自由定理为基础的程序转换为纯严格的函数式语言，严格的函数式语言明确的懒惰注释，和非严格的语言与多态严格原语被认为是，和操作，以及指称，语义为基础的方法，其可证明的安全性进行了研究。此外，合格的类型系统是用来进行细粒度的分析的方式，其中标准的方程自由定理的非严格语言被削弱的功能语言，而不是纯粹的非严格。

Proposal Number 0429072Provable Safety for Performance-Improving Free Theorems-Based Program TransformationsPatricia JohannRutgers University New BrunswickThis 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.