Especialización principal de tipos para sumas polivariantes

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2006-11-24

Tipo de documento: 

info:eu-repo/semantics/bachelorThesis
 

Formato:

application/pdf

Idioma:

spa

Descripción:

La especialización de programas es una forma de generar programas automáticamente, que consiste en producir distintas versiones de un programa fuente general, cada una especializada según datos particulares conocidos. Por ejemplo, la función recursiva potencia, sabiendo que el exponente será igual a 3, puede especializarse a una versión residual más eficiente (no recursiva) λx.x·x·x , y en forma similar para otros exponentes. La especialización de tipos [Hughes, 1996b; Hughes, 1996a; Hughes, 1998] es una forma de especialización de programas basada en inferencia de tipos. Tanto el programa fuente como su tipo son especializados a un programa y un tipo residuales. La especialización principal de tipos [Martínez Lopez and Hughes, 2002; Martínez López, 2005] es una formulación detallada de este sistema basada en la teoría de tipos calificados [Jones, 1994]. Tiene la propiedad de generar especializaciones principales: para cada expresión y tipo fuente especializables, se puede producir una expresión y un tipo residuales que son más generales que cualquier otra especialización válida, y tales que todas ellas pueden obtenerse a partir de la primera mediante de una noción de instanciación. Un concepto importante en todo sistema de especialización es el de polivarianza, una característica que permite que una única expresión fuente pueda ser especializada a más de una expresión residual. La polivarianza puede obtenerse de distintas formas; en particular, el sistema de especialización de tipos original [Hughes, 1996b] incluye construcciones para productos polivariantes (donde una única expresión fuente e especializa a una tupla de expresiones(e_1´,....e_n´)) y para sumas polivariantes (donde una expresión etiquetada con un constructor In e especializa a varias expresiones con varios constructores In,e_1´….,e_n´In_n).Esta última se conoce también como especialización de constructores [Mogensen, 1993]. La especialización principal de tipos fue formulada sólo para un subconjunto del lenguaje presentado originalmente; en particular, las sumas polivariantes no fueron consideradas. En esta tesis extendemos el sistema con nuevas construcciones y reglas para especializar sumas polivariantes. Demostramos que nuestra contribución preserva todas las propiedades del sistema original, incluyendo la de principalidad, e incorporamos nuestra extensión a PTS, un prototipo de implementación de este sistema.

Identificador:

https://hdl.handle.net/20.500.12110/seminario_nCOM000307_LowenthalQuastler