Abstract for "Algebraic Reasoning and Completeness in Typed Languages"
Algebraic Reasoning and Completeness in Typed Languages
Jon G. Riecke and Ramesh Subrahmanyam. Appeared in Twentieth ACM Conference on Principles of Programming Languages, pages 185-195. ACM Press, 1993.

Abstract: We consider the following problem in proving observational congruences in functional languages: given a call-by-name language based on the simply-typed lambda-calculus with algebraic operations axiomatized by algebraic equations E, is the set of observational congruences between terms exactly those provable from (beta), (eta), and E? We find conditions for determining whether beta-eta E-equational reasoning is complete for proving the observational congruences between such terms. We demonstrate the power and generality of the theorems by presenting a number of easy corollaries for particular algebras.