How to CPS Transform a Monad

摘要

CPS transformation is an important tool in the compilation of functional programming languages. For strict languages, such as our web programming language "Rinso" or Microsoft's F#, monadic expressions can help with structuring and composing computations.rnTo apply a CPS transformation in the compilation process of such a language, we integrate explicit monadic abstraction in a call-by-value source language, present a Danvy-Filinski-style CPS transformation for this extension, and verify that the translation preserves simple typing. We establish the simulation properties of this transformation in an untyped setting and relate it to a two stage transformation that implements the monadic abstraction with thunks and introduces continuations in a second step. Furthermore, we give a direct style translation which corresponds to the monadic translation.