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

RUI：可证明安全性，可提高性能的基于自由定理的程序转换

• 批准号: 0429072
• 负责人: Patricia Johann
• 金额: $ 12.38万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0429072&HistoricalAwards=false
• 关键词: RUI; Provable; Safety; Performance; Improving

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.

提案编号0429072可提供绩效改造的可提供的安全性安全性，基于定理的计划转换 - 约翰里斯特大学新不伦瑞克省这项研究的重点是正式证明以纯粹功能语言编写的计划的某些转换的安全性。所考虑的转换基于所谓的“不合理的自由定理”。通过自动删除数据构造函数和其他数据操纵运算符的程序，这些转换可以显着降低功能语言中表达性和效率之间的张力，这些程序均匀处理数据；正式的安全证明可确保这样做的转换不会以意外的方式改变其应用程序的可观察行为。研究了纯粹的基于严格的功能语言的基于不合理的定理的程序转换，具有明确的懒惰注释的严格功能语言以及具有多态性严格原始原始的非纳入语言，并研究了具有多态性的严格性原始语言，以及操作性以及基于语义的基于语义的基于语义的方法。此外，合格的类型系统用于对非纯粹不纯粹的非收缩语言的功能性语言进行削弱的标准无方程定理的方式进行细粒度分析。