Bohm theorem and Bohm trees for the Lambda mu-calculus
Parigot's lambda mu-calculus (Parigot, 1992 [1]) is now a standard reference about the computational content of classical logic as well as for the formal study of control operators in functional languages. In addition to the fine-grained Curry-Howard correspondence between minimal classical deductions and simply typed lambda mu-terms and to the ability to encode many usual control operators such as call/cc in the lambda mu-calculus (in its historical call-by-name presentation or in call-by-value versions), the success of the lambda mu-calculus comes from its simplicity, its good meta-theoretical properties both as a typed and an untyped calculus (confluence, strong normalization, etc.) as well as the fact that it naturally extends Church's lambda-calculus. Though, in 2001, David and Py proved [2] that Bohm's theorem, which is a fundamental result of the untyped lambda-calculus, cannot be lifted to Parigot's calculus. In the present article, we exhibit a natural extension to Parigot's calculus, the lambda mu-calculus, in which Bohm's property, also known as separation property, can be stated and proved. This is made possible by a careful and detailed analysis of David and Py's proof of non-separability and of the characteristics of the lambda mu-calculus which break the property: we identify that the crucial point lies in the design of Parigot's lambda mu-calculus with a two-level syntax. In addition, we establish a standardization theorem for the extended calculus, deduce a characterization of solvability, describe Lambda mu-BOhm trees and connect the calculus with stream computing and delimited control. (C) 2012 Published by Elsevier B.V.
bohm theorem bohm trees lambda mu-calculus separation property streams classical lambda-calculi (delimited) control infinitary lambda-calculus shift/reset