The [lambda lambda-bar]-calculus : a dual calculus for unconstrained strategies
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
We present a calculus which combines a simple, CCS-like representation of finite behaviors, with two dual binders lambda and lambda. Infinite behaviors are obtained through a syntactical fixed-point operator, which is used to give a translation of lambda-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 cornes 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 lambda-terms corresponds to the generation of infinite plays from the finite views of an innocent strategy. The syntactical duality between ternis and co-ternis corresponds to the duality between Player and Opponent. This duality also gives vise to a Biihm-out lemma.
Abstract FR:
Nous présentons un calcul qui combine une représentation simple, à la CCS, des comportements finis. Pour cela nous utilisons deux lieurs duaux: lambda et lambda-bar. Les comportements infinis sont obtenus grâce à un opérateur de point fixe, qui est en particulier utilisé pour donner une traduction des lambda termes. La dualité du calcul rend symétriques les rôles d'une fonction et de son environnement. Comme à l'accoutumé, l'environnement est autorisé à appeler une fonction à n'importe quel moment, à chaque fois avec un argument différent. De manière duale, la fonction est autorisée à répondre à n'importe quel appel, avec à chaque fois un comportement différent. Ceci donne aux termes de notre langage le pouvoir des références fonctionnelles. L'inspiration de ce langage provient de la Sémantique des Jeux. En effet, les formes normales donnent une syntaxe concrète simple pour les stratégies finies, qui sont de façon inhérentes non innocentes. Cette correspondance très directe nous permet de décrire, de manière syntaxique, un certain nombre de traits de la Sémantique des Jeux. L'expansion du point fixe dans un lambda terme traduit corresponds à la génération de parties infinies à partir des vues finies d'une stratégie innocente. La dualité syntaxique entre termes et co-termes corresponds à la dualité entre le Joueur et l'Opposant. Cette dualité donne aussi lieu à un lemme de type Bôhm-out.