the duality of computation
We present the ? -calculus, a syntax for ?-calculus + control operators exhibiting symmetries such as program/context and call-by-name/call-by-value. This calculus is derived from implicational Gentzen's sequent calculus LK , a key classical logical system in proof theory. Under the Curry-Howard correspondence between proofs and programs, we can see LK , or more precisely a formulation called LK ? , as a syntax-directed system of simple types for ? -calculus. For ? -calculus, choosing a call-by-name or call-by-value discipline for reduction amounts to choosing one of the two possible symmetric orientations of a critical pair. Our analysis leads us to revisit the question of what is a natural syntax for call-by-value functional computation. We define a translation of ??-calculus into ? -calculus and two dual translations back to ?-calculus, and we recover known CPS translations by composing these translations.
computation control operability symmetry program context systems theory types reduction orientation critic analysis functional translation value direct