Geometry of interaction
m (style corrections) |
(reprise de l'intro précisant la différence GoI/sémantique dénotationnelle) |
||
| Line 1: | Line 1: | ||
| − | The ''geometry of interaction'', GoI in short, was defined in the early nineties by Girard as an interpretation of linear logic into operators algebra: formulae were interpreted by Hilbert spaces and proofs by partial isometries. This was a striking novelty as it was the first time that a mathematical model of logic (lambda-calculus) didn't interpret proofs by morphisms and the composition of proofs (allowed by the cut rule) by composition of morphisms, as it is the case in [[Coherent semantics|denotationnal]] or [[Categorical semantics|categorical]] semantics. Instead the GoI was claimed to be an ''operational semantics'' as it interpreted cut elimination as a mathematical process, namely the computation of a series, the ''execution formula'' that is the solution of a ''feed-back'' equation. |
+ | The ''geometry of interaction'', GoI in short, was defined in the early nineties by Girard as an interpretation of linear logic into operators algebra: formulae were interpreted by Hilbert spaces and proofs by partial isometries. This was a striking novelty as it was the first time that a mathematical model of logic (lambda-calculus) didn't interpret a proof of <math>A\limp B</math> as a morphism ''from'' (the space interpreting) <math>A</math> ''to'' the (space interpreting) <math>B</math> and proof composition (cut rule) as the composition of morphisms. Rather the proof was interpreted as an operator acting ''on'' (the space interpreting) <math>A\limp B</math>, that is a morphism from <math>A\limp B</math> to <math>A\limp B</math>. For proof composition the problem was then, given an operator on <math>A\limp B</math> and another one on <math>B\limp C</math> to construct a new operator on <math>A\limp C</math>. This problem was originally expressed as a feedback equation solved by the ''execution formula''. The fact that the execution formula has some formal analogies with Kleene's formula for recursive functions allowed to claim that GoI was an ''operational semantics'', as opposed to traditionnal [[Semantics|denotational semantics]]. |
| − | The first instance of the GoI, that will be described in details in this article, was restricted to the <math>MELL</math> fragment of linear logic (Multiplicative and Exponential fragment) which is enough to encode lambda-calculus. Since then Girard proposed several improvements: firstly the extension to the additive connectives known as ''Geometry of Interaction 3'' and more recently a complete reformulation using Von Neumann algebras that allows to deal with some aspects of [[Light linear logics|implicit complexity]] |
+ | The first instance of the GoI was restricted to the <math>MELL</math> fragment of linear logic (Multiplicative and Exponential fragment) which is enough to encode lambda-calculus. Since then Girard proposed several improvements: firstly the extension to the additive connectives known as ''Geometry of Interaction 3'' and more recently a complete reformulation using Von Neumann algebras that allows to deal with some aspects of [[Light linear logics|implicit complexity]] |
| − | The GoI has been a source of inspiration for various authors. Danos and Regnier have reformulated the original model exhibiting its combinatorial nature using a theory of reduction of paths in proof-nets and showing the link with abstract machines. It has been used in the theory of sharing reduction for lambda-calculus in the Abadi-Gonthier-Lévy reformulation and simplification of Lamping's representation of sharing. It was shown to be related to game semantics and more precisely to the Abramsky-Jagadeesan-Malacaria model of PCF. Finally the original GoI for the <math>MELL</math> fragment has been reformulated in the framework of traced monoidal categories following an idea originally proposed by Joyal. |
+ | The GoI has been a source of inspiration for various authors. Danos and Regnier have reformulated the original model exhibiting its combinatorial nature using a theory of reduction of paths in proof-nets and showing the link with abstract machines; in particular the execution formula appears as the composition of two automata that interact one with the other through their common interface. Also the execution formula has rapidly been understood as expressing the composition of strategies in game semantics. It has been used in the theory of sharing reduction for lambda-calculus in the Abadi-Gonthier-Lévy reformulation and simplification of Lamping's representation of sharing. Finally the original GoI for the <math>MELL</math> fragment has been reformulated in the framework of traced monoidal categories following an idea originally proposed by Joyal. |
Revision as of 12:34, 16 March 2010
The geometry of interaction, GoI in short, was defined in the early nineties by Girard as an interpretation of linear logic into operators algebra: formulae were interpreted by Hilbert spaces and proofs by partial isometries. This was a striking novelty as it was the first time that a mathematical model of logic (lambda-calculus) didn't interpret a proof of 
as a morphism from (the space interpreting) A to the (space interpreting) B and proof composition (cut rule) as the composition of morphisms. Rather the proof was interpreted as an operator acting on (the space interpreting) , that is a morphism from to . For proof composition the problem was then, given an operator on and another one on 
to construct a new operator on 
. This problem was originally expressed as a feedback equation solved by the execution formula. The fact that the execution formula has some formal analogies with Kleene's formula for recursive functions allowed to claim that GoI was an operational semantics, as opposed to traditionnal denotational semantics.
The first instance of the GoI was restricted to the MELL fragment of linear logic (Multiplicative and Exponential fragment) which is enough to encode lambda-calculus. Since then Girard proposed several improvements: firstly the extension to the additive connectives known as Geometry of Interaction 3 and more recently a complete reformulation using Von Neumann algebras that allows to deal with some aspects of implicit complexity
The GoI has been a source of inspiration for various authors. Danos and Regnier have reformulated the original model exhibiting its combinatorial nature using a theory of reduction of paths in proof-nets and showing the link with abstract machines; in particular the execution formula appears as the composition of two automata that interact one with the other through their common interface. Also the execution formula has rapidly been understood as expressing the composition of strategies in game semantics. It has been used in the theory of sharing reduction for lambda-calculus in the Abadi-Gonthier-Lévy reformulation and simplification of Lamping's representation of sharing. Finally the original GoI for the MELL fragment has been reformulated in the framework of traced monoidal categories following an idea originally proposed by Joyal.
