Date: Thu 9 Gen
Time: 15.00
Place: room 214

Speaker: Stefano Guerrini (Univ. of Pennsylvania)
Title: Implementazioni Ottimali di Linguaggi Funzionali
Reference: Catuscia Palamidessi

Abstract. Alla fine degli anni settanta, Levy aveva fornito un lower bound per il costo delle implementazioni di linguaggi funzionali formalizzando le cosiddette riduzioni ottimali del lambda-calcolo. Levy non fu pero' in grado di fornire alcun algoritmo che raggiungesse il lower bound. Solo alla fine degli anni ottanta, Lamping fu in grado di dare una implementazione su grafi otimale rispetto al numero delle beta-riduzioni. Successive riformulazioni dell'algoritmo di Lamping sono poi state fornite da Gonthier, Abadi e Levy e da Asperti. Mostrando tra l'altro sorprendenti relazioni tra le riduzioni ottimali e la geometria della interazione. Lo scopo del talk e' introdurre i problemi di base delle riduzioni ottimali, fornire una presentazione intuitiva dei corrispondenti algoritmi su grafi mostrando le relazioni tra questi e la geometria della interazione.