Resumen:
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.
Abstract:
Program specialization is a form automatic program generation that produces different versions of a given general source program, each of them specialized to particular known data. For example, the recursive function power, if the exponent is known to be 3, can be specialized to a more efficient (non-recursive) function λx.x · x · x, and similarly for other exponents. Type specialization [Hughes, 1996b; Hughes, 1996a; Hughes, 1998] is a form of program specialization based on type inference. Both the source program and its type are specialized to a residual program and a residual type. Principal type specialization [Martínez López and Hughes, 2002; Martínez López, 2005] is a detailed formulation to this system based on the theory of Qualified Types [Jones, 1994]. It has the property of producing principal specializations: for each specializable source expression and type, a residual expression and type can be generated such that they are more general than any other valid specialization, and all of them can be obtained from it by a notion of instantiation. An important notion in any specialization system is that of polyvariance, a feature allowing a single source expression to be specialized to many residual results. Polyvariance can be achieved in more than one way; in particular, the original type specialization system [Hughes, 1996b] includes constructs for polyvariant products (where an expression e is specialized to a tuple of expressions (e´_1, . . . , e´_n)) and polyvariant sums (where a tagged expression In e is specialized to many tagged expressions In_1 e´_1, . . . , In_n e´_n), the latter also known as constructor specialization [Mogensen, 1993]. Principal type specialization was formulated only for a subset of the language presented originally; in particular, polyvariant sum types were not considered. In this thesis, we extend the system with new constructs and rules to specialize polyvariant sums. We prove that our contribution preserves all the properties of the original system, including that of principality, and we incorporate our extension to PTS, a prototype implementation of the specializer.
Citación:
---------- APA ----------
Lowenthal Quastler, Laura Carolina. (2006). Especialización principal de tipos para sumas polivariantes. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000307_LowenthalQuastler
---------- CHICAGO ----------
Lowenthal Quastler, Laura Carolina. "Especialización principal de tipos para sumas polivariantes". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2006.https://hdl.handle.net/20.500.12110/seminario_nCOM000307_LowenthalQuastler
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000307_LowenthalQuastler.pdf
Distrubución geográfica