Personal tools
You are here: Home Events Abstract Archives 2004 Call-by-value is dual to call-by-name

Call-by-value is dual to call-by-name

Philip Wadler Laboratory for Foundations of Computer Science School of Informatics University of Edinburgh 4pm 20 January 2004 Room 2511, JCMB, King's Buildings

The rules of classical logic may be formulated in pairs corresponding to De Morgan duals: rules about "and" are dual to rules about "or". A line of work, including that of Filinski (1989), Griffin (1990), Parigot (1992), Danos, Joinet, and Schellinx (1995), Selinger (1998,2001), and Curien and Herbelin (2000), has led to the startling conclusion that call-by-value is the de Morgan dual of call-by-name.

This paper presents a dual calculus that corresponds to the classical sequent calculus of Gentzen (1935) in the same way that the lambda calculus of Church (1932,1940) corresponds to the intuitionistic natural deduction of Gentzen (1935). The paper includes crisp formulations of call-by-value and call-by-name that are obviously dual; no similar formulations appear in the literature. The paper gives a CPS translation and its inverse, and shows that the translation is both sound and complete, strengthening a result in Curien and Herbelin (2000).

Paper available at http://homepages.inf.ed.ac.uk/wadler/topics/call-by-need.html#dual.

Document Actions