Reducing the overhead of ML exceptions by selective CPS transformation

Abstract

ML``s exception handling makes it possible to describe exceptional execution flows conveniently. Sometimes, current implementation of exception handling introduce unnecessary overhead. Our goal is to reduce this overhead by source-level transformation. To this end, we transform source programs into variant of continuation-passing style(CPS), replacing handle and raise expressions by continuation-catching and throwing expressions, respectively. CPS-transforming every expression, however, introduces a new cost. We therefore use an exception analysis to transform expressions selectively: if an expression is statically determined to involve exceptions then it is CPS-transformed; otherwise, it is left in direct style. In this article, we formalize this selective CPS transformation, prove its correctness, and present early experimental data indicating its effect on ML programs.