Implementazione di un algoritmo lineare per l’α-equivalenza di λ-termini con sharing

Sinagra, Emanuele (2018) Implementazione di un algoritmo lineare per l’α-equivalenza di λ-termini con sharing. [Laurea], Università di Bologna, Corso di Studio in Informatica [L-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Creative Commons: Attribuzione - Non commerciale - Non opere derivate 3.0 (CC BY-NC-ND 3.0)

Download (1MB)

Abstract

L'argomento di studio interessa i lambda- termini del lambda-calcolo, il quale rappresenta il prototipo di ogni linguaggio di programmazione funzionale. In particolare la tesi affronta una problematica relativa al costo computazionale delle lambda-riduzioni, ed esattamente la possibilità di implementare in tempo lineare la riduzione dei lambda-termini con sharing sul numero di passi di beta-riduzione, oggetto di studio. L’obiettivo di questa tesi è la prima implementazione dell'algoritmo proposto dal Prof. Claudio Sacerdoti Coen e dal Dott. Ricercatore Beniamino Accattoli, che risolve in tempo lineare sul numero di passi di beta-riduzione il problema della lambda riduzione dei lambda-termini con sharing, detta anche alpha-conversione. Il lavoro svolto consiste nell' implementazione dell'algoritmo in C#, nell’esecuzione dei relativi test funzionali e di efficienza dell'algoritmo. Nella tesi vengono descritte: le strutture dati utilizzate e l'implementazione dell'algoritmo con il relativo codice sorgente; le modalità di test e di verifica funzionale dell'algoritmo; l'analisi dei risultati ottenuti al fine di valutare l'efficienza dell'algoritmo.

Abstract
Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Sinagra, Emanuele
Relatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
alpha-conversione,bisimulazione di grafi,alpha-equivalenza,grafi riducibili,sharing,algoritmo lineare
Data di discussione della Tesi
14 Marzo 2018
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^