Abstract for "Fully Abstract Translations between Functional Languages"
Fully Abstract Translations between Functional Languages
Jon G. Riecke. Appeared in Mathematical Structures in Computer Science, volume 3, pages 387-415. Cambridge University Press, 1993.

Abstract: We examine the problem of finding fully abstract translations between programming languages, i.e., translations that preserve code equivalence and nonequivalence. We present three examples of fully abstract translations: one from call-by-value to lazy PCF, one from call-by-name to call-by-value PCF, and one from lazy to call-by-value PCF. The translations yield lower bounds on decision procedures for proving equivalences of code. We define a notion of ``functional translation'' that captures the essence of the proofs of full abstraction, and show that some languages cannot be translated into others.