Abstract for "Fully Abstract Translations between Functional Languages (Preliminary Report)"
Fully Abstract Translations between Functional Languages (Preliminary Report)
Jon G. Riecke. Appeared in Eighteenth ACM Conference on Principles of Programming Languages, pages 245-254. ACM Press, 1991.

Abstract: We address the problem of finding fully abstract translations between programming languages, i.e., translations that preserve code equivalence and nonequivalence. We give three fully abstract translations between versions of PCF: one from call-by-name (Plotkin 1977; Scott 1969) to call-by-value (Riecke 1990; Sieber 1990; Sitaram and Felleisen 1990), one from call-by-value to lazy (Bloom and Riecke 1989; Cosmadakis, et al 1990), and one from lazy to call-by-value. The translations yield lower bounds on decision procedures for proving equivalences of code. We finally give a definition of ``functional translation'' and show that no such translation exists from call-by-value to call-by-name, or from lazy to call-by-name.