The λ(λ)-calculus: A dual calculus for unconstrained strategies

摘要

We present a calculus which combines a simple, CCS-like representation of finite behaviors, with two dual binders λ and (λ). Infinite behaviors are obtained through a syntactical fixed-point operator, which is used to give a translation of λ-terms. The duality of the calculus makes the roles of a function and its environment symmetrical. As usual, the environment is allowed to call a function at any given point, each time with a different argument. Dually, the function is allowed to answer any given call, each time with a different behavior. This grants terms in our language the power of functional references. The inspiration for this language comes from game semantics. Indeed, its normal forms give a simple concrete syntax for finite strategies, which are inherently non-innocent. This very direct correspondence allows us to describe, in syntactical terms, a number of features from game semantics. The fixed-point expansion of translated λ-terms corresponds to the generation of infinite plays from the finite views of an innocent strategy. The syntactical duality between terms and co-terms corresponds to the duality between Player and Opponent. This duality also gives rise to a Boehm-out lemma. The paper is divided into two parts. The first one is purely syntactical, and requires no background in game semantics. The second describes the fully abstract game model.