A Reflection on Call-By-Value
Amr Sabry, Philip Wadler
Committee:
Technical Report(Apr 1996)
Keywords:

A number of compilers exploit the following strategy: translate a term to continuation-passing style (CPS) and optimize the resulting term using a sequence of reductions. Recent work suggests that an alternative strategy is superior: optimize directly in an extended source calculus. We suggest that the appropriate relation between the source and target calculi may be captured by a special case of a Galois connection known as a reflection. Previous work has focused on the weaker notion of an equational correspondence, which is based on equality rather than reduction. We use as our source language Moggi's computational lambda calculus &lambdac, which is an extension of Plotkin's call-by-value calculus &lambdav. We show that Moggi's monad translation, Plotkin's CPS translation, and Girard's translation to linear logic can all be regarded as reflections from this source language, and we put forward &lambdac as a model of call-by-value computation that improves on &lambdav.