Interaktionens geometri - Geometry of interaction

Den geometri af Interaction (GOI) blev introduceret af Jean-Yves Girard kort efter hans arbejde med lineær logik . I lineær logik kan bevis ses som forskellige slags netværk i modsætning til de flade træstrukturer i sekventuel beregning . For at skelne de rigtige bevisnet fra alle mulige netværk udarbejdede Girard et kriterium, der involverede ture i netværket. Rejser kan faktisk ses som en slags operatør, der handler på beviset. Med udgangspunkt i denne observation beskrev Girard denne operatør direkte fra beviset og har givet en formel, den såkaldte eksekveringsformel , der koder for processen med eliminering af skåret på operatørniveau.

En af de første væsentlige anvendelser af GoI var en bedre analyse af Lampings algoritme til optimal reduktion for lambda-beregningen . GoI havde en stærk indflydelse på spillsemantik til lineær logik og PCF .

GoI er blevet anvendt til optimering af deep compiler til lambda calculi. En afgrænset version af GoI kaldet syntese geometri er blevet brugt til at kompilere programmeringssprog af højere orden direkte til statiske kredsløb.

Referencer

Yderligere læsning