On proving the correctness of program transformations based on free theorems for higher-order polymorphic calculi

A number of program transformations currently of interest can be derived from Wadler's ‘free theorems’ for calculi approximating modern functional languages. Although delicate but fundamental issues arise in proving the correctness of free theorems-based program transformations, these issues have usually been left unaddressed in the correctness proofs appearing in the literature. As a result, most such proofs are incomplete, and most free theorems-based transformations are applied to programs in calculi for which they are not actually known to be correct. The purpose of this paper is three-fold. First, we raise and clarify some of the issues that must be addressed when constructing correctness proofs for free theorems-based program transformations. Second, we offer a principled approach to developing such proofs. Third, we use Pitts' recent work on parametricity and observational equivalence to show how our approach can be used to give the first proof that transformations based on the Acid Rain theorems preserve observational equivalence of programs in a polymorphic lambda calculus supporting FPC-style fixpoints and algebraic data types. Correctness of the foldr-build rule, the destroy-unfoldr rule, and the hylofusion program transformation for this calculus follows immediately. The same approach is expected to yield complete correctness proofs for free theorems-based transformations in calculi that even more closely resemble languages with which programmers are concerned in practice.

一些目前感兴趣的程序转换可以从Wadler的“自由定理”中推导出来，用于近似现代函数式语言的演算。虽然微妙的，但基本的问题出现在证明自由定理为基础的程序转换的正确性，这些问题通常被留在文献中出现的正确性证明未解决。因此，大多数这样的证明是不完整的，并且大多数基于自由定理的变换被应用于微积分中的程序，它们实际上并不知道是正确的。本文件有三个目的。首先，我们提出并澄清了一些问题，必须解决时，构建正确性证明自由定理为基础的程序转换。其次，我们提供了一个原则性的方法来开发这样的证明。第三，我们使用皮茨最近的工作参数和观测等价性，以显示我们的方法可以用来给第一个证明，根据酸雨定理的转换保持观测等价性的程序在一个多态lambda演算支持FPC风格的不动点和代数数据类型。这个演算的折叠-构建规则、破坏-展开规则和hylofusion程序转换的正确性立即随之而来。同样的方法有望为微积分中基于自由定理的转换提供完整的正确性证明，这些转换甚至更接近程序员在实践中所关注的语言。