La noción de principalidad en especialización de tipos

Mostrar todas las versiones(3)

Cuando se consideran las maneras de producir programas, la técnica principal queviene a la mente de cada uno de nosotros es la de escribir el programa a mano. Aunqueexisten técnicas de derivación y herramientas para producir programas automáticamente,su aplicación está usualmente restringida a ciert...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Martínez López, Pablo E.
Otros Autores:	Hughes, John
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2005
Materias:	ESPECIALIZACION PRINCIPAL DE TIPOS ESPECIALIZACION DE TIPOS ESPECIALIZACION DE PROGRAMAS PRODUCCION AUTOMATICA DE PROGRAMAS PROGRAMAS POLIMORFICOS PRINCIPAL TYPE SPECIALISATION TYPE SPECIALISATION PROGRAM SPECIALISATION AUTOMATIC PROGRAM PRODUCTION POLYMORPHIC PROGRAMS
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n4100_MartinezLopez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4100_MartinezLopez_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-tesis_n4100_MartinezLopez_oai
record_format	dspace
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
language	Español
orig_language_str_mv	spa
topic	ESPECIALIZACION PRINCIPAL DE TIPOS ESPECIALIZACION DE TIPOS ESPECIALIZACION DE PROGRAMAS PRODUCCION AUTOMATICA DE PROGRAMAS PROGRAMAS POLIMORFICOS PRINCIPAL TYPE SPECIALISATION TYPE SPECIALISATION PROGRAM SPECIALISATION AUTOMATIC PROGRAM PRODUCTION POLYMORPHIC PROGRAMS
spellingShingle	ESPECIALIZACION PRINCIPAL DE TIPOS ESPECIALIZACION DE TIPOS ESPECIALIZACION DE PROGRAMAS PRODUCCION AUTOMATICA DE PROGRAMAS PROGRAMAS POLIMORFICOS PRINCIPAL TYPE SPECIALISATION TYPE SPECIALISATION PROGRAM SPECIALISATION AUTOMATIC PROGRAM PRODUCTION POLYMORPHIC PROGRAMS Martínez López, Pablo E. La noción de principalidad en especialización de tipos
topic_facet	ESPECIALIZACION PRINCIPAL DE TIPOS ESPECIALIZACION DE TIPOS ESPECIALIZACION DE PROGRAMAS PRODUCCION AUTOMATICA DE PROGRAMAS PROGRAMAS POLIMORFICOS PRINCIPAL TYPE SPECIALISATION TYPE SPECIALISATION PROGRAM SPECIALISATION AUTOMATIC PROGRAM PRODUCTION POLYMORPHIC PROGRAMS
description	Cuando se consideran las maneras de producir programas, la técnica principal queviene a la mente de cada uno de nosotros es la de escribir el programa a mano. Aunqueexisten técnicas de derivación y herramientas para producir programas automáticamente,su aplicación está usualmente restringida a cierta clase de problemas, o ciertos dominios (como los generadores de parsers, o las interfaces visuales). En los casos donde talestécnicas se pueden aplicar, la productividad y la confiabilidad se ven ampliamente incrementadas. Por esa razón, nos interesamos en la producción automática de programasen un marco general. La especialización de programas es una manera particular de producir programasautomáticamente. En ella se utiliza un programa fuente general dado para generardiversas versiones particulares, especializadas, del mismo, cada una resolviendo una instanciaparticular del problema original. La técnica más conocida y más ampliamenteestudiada de especialización de programas es llamada evaluación parcial; se la ha utilizadocon éxito en varias áreas de aplicación diferentes. Sin embargo, la evaluaciónparcial tiene problemas cuando se considera la producción automática de programas contipos. La especialización de tipos es una forma de especialización de programas que puedeproducir automáticamente programas con tipos a partir de uno fuente. Comprendediversas técnicas muy poderosas, tales como especialización polivariante, especializaciónde constructores, conversión de clausuras; es la primera de las variantes de especializaciónde programas que puede generar tipos arbitrarios a partir de un único programa fuente. Creemos que la especialización de tipos puede ser la base sobre la que desarrollar unmarco de producción automática de programas. En esta tesis consideramos la especialización de programas, extendiéndola para producirprogramas polimórficos. Ilustramos eso considerando un intérprete para un lambdacálculo con tipos a la Hindley-Milner, y especializándolo con cualquier programa objetopara producir un programa residual que sea esencialmente igual que el original. En labúsqueda de la generación de polimorfismo, extendemos la especialización de tipos paraque pueda expresar la especialización de programas con información estática incompleta,y probamos que para cada término podemos inferir una especialización particular quepuede ser usada para reconstruir cada uno de las otras especializaciones de tal término. Llamamos especialización de tipos principal a tal técnica, debido a la analogía de estapropiedad con la noción de tipos principales. Nuestra presentación clarifica muchos delos problemas existentes en la especialización de tipos, lo cual puede ser usado como unaguía en la búsqueda de soluciones para ellos. La presentación se divide en cuatro partes. En la primera Parte, presentamos la Especialización de Tipos en su forma original, junto con material complementario. Enla Parte II desarrollamos la presentación de la Especialización de Tipos Principal, explicandotodos los detalles técnicos, dando varios ejemplos, y presentando nuestra implementación del prototipo. En la Parte III describimos las posibilidades de la formulaciónnueva, proveyendo una extensión de la Especialización de Tipos para generar programaspolimórficos. Finalmente, la última parte describe trabajos relacionados, trabajosfuturos, y concluye. Este trabajo es el resultado de siete a˜nos de investigación, realizados durante misestudios de doctorado.
author2	Hughes, John
author_facet	Hughes, John Martínez López, Pablo E.
format	Tesis doctoral Tesis doctoral publishedVersion
author	Martínez López, Pablo E.
author_sort	Martínez López, Pablo E.
title	La noción de principalidad en especialización de tipos
title_short	La noción de principalidad en especialización de tipos
title_full	La noción de principalidad en especialización de tipos
title_fullStr	La noción de principalidad en especialización de tipos
title_full_unstemmed	La noción de principalidad en especialización de tipos
title_sort	la noción de principalidad en especialización de tipos
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2005
url	https://hdl.handle.net/20.500.12110/tesis_n4100_MartinezLopez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4100_MartinezLopez_oai
work_keys_str_mv	AT martinezlopezpabloe lanociondeprincipalidadenespecializaciondetipos
_version_	1766015640981733376
spelling	I28-R145-tesis_n4100_MartinezLopez_oai2023-04-26 Hughes, John Martínez López, Pablo E. 2005-11-15 Cuando se consideran las maneras de producir programas, la técnica principal queviene a la mente de cada uno de nosotros es la de escribir el programa a mano. Aunqueexisten técnicas de derivación y herramientas para producir programas automáticamente,su aplicación está usualmente restringida a cierta clase de problemas, o ciertos dominios (como los generadores de parsers, o las interfaces visuales). En los casos donde talestécnicas se pueden aplicar, la productividad y la confiabilidad se ven ampliamente incrementadas. Por esa razón, nos interesamos en la producción automática de programasen un marco general. La especialización de programas es una manera particular de producir programasautomáticamente. En ella se utiliza un programa fuente general dado para generardiversas versiones particulares, especializadas, del mismo, cada una resolviendo una instanciaparticular del problema original. La técnica más conocida y más ampliamenteestudiada de especialización de programas es llamada evaluación parcial; se la ha utilizadocon éxito en varias áreas de aplicación diferentes. Sin embargo, la evaluaciónparcial tiene problemas cuando se considera la producción automática de programas contipos. La especialización de tipos es una forma de especialización de programas que puedeproducir automáticamente programas con tipos a partir de uno fuente. Comprendediversas técnicas muy poderosas, tales como especialización polivariante, especializaciónde constructores, conversión de clausuras; es la primera de las variantes de especializaciónde programas que puede generar tipos arbitrarios a partir de un único programa fuente. Creemos que la especialización de tipos puede ser la base sobre la que desarrollar unmarco de producción automática de programas. En esta tesis consideramos la especialización de programas, extendiéndola para producirprogramas polimórficos. Ilustramos eso considerando un intérprete para un lambdacálculo con tipos a la Hindley-Milner, y especializándolo con cualquier programa objetopara producir un programa residual que sea esencialmente igual que el original. En labúsqueda de la generación de polimorfismo, extendemos la especialización de tipos paraque pueda expresar la especialización de programas con información estática incompleta,y probamos que para cada término podemos inferir una especialización particular quepuede ser usada para reconstruir cada uno de las otras especializaciones de tal término. Llamamos especialización de tipos principal a tal técnica, debido a la analogía de estapropiedad con la noción de tipos principales. Nuestra presentación clarifica muchos delos problemas existentes en la especialización de tipos, lo cual puede ser usado como unaguía en la búsqueda de soluciones para ellos. La presentación se divide en cuatro partes. En la primera Parte, presentamos la Especialización de Tipos en su forma original, junto con material complementario. Enla Parte II desarrollamos la presentación de la Especialización de Tipos Principal, explicandotodos los detalles técnicos, dando varios ejemplos, y presentando nuestra implementación del prototipo. En la Parte III describimos las posibilidades de la formulaciónnueva, proveyendo una extensión de la Especialización de Tipos para generar programaspolimórficos. Finalmente, la última parte describe trabajos relacionados, trabajosfuturos, y concluye. Este trabajo es el resultado de siete a˜nos de investigación, realizados durante misestudios de doctorado. When considering the ways in which programs are produced, the main techniquethat comes to everybody’s mind is writing by hand. Although derivation techniquesand tools for producing programs exist, their application is usually restricted to certainkind of problems, or certain domains (such as parsing generators, or visual interfaces). In those cases where such techniques can be applied, productivity and reliability arehighly boosted. For that reason, we are concerned with the automatic production ofprograms in a general setting. Program specialisation is a particular way to produce programs automatically. Agiven, general source program is used to generate several particular, specialised versionsof it, each one solving a particular instance of the original problem. The best-known andthoroughly studied technique for program specialisation is called partial evaluation; ithas been successfully used in several different application areas. But partial evaluationfalls short when automatic production of typed programs is considered. Type specialisation is a form of program specialisation that can automatically producetyped programs from some general source one. It comprises several powerful techniques,such as polyvariant specialisation, constructor specialisation, and closure conversion,and it is the first variant of program specialisation that can generate arbitrarytypes from a single source program. We believe that type specialisation can be the basisin which to develop a framework for automatic program production. In this thesis we consider type specialisation, extending it to produce polymorphicprograms. We illustrate that by considering an interpreter for Hindley-Milner typedlambda-calculus, and specialising it to any given object program, producing a residualprogram that is essentially the same as the original one. In achieving the generationof polymorphism, we extend type specialisation to be able to express specialisation ofprograms with incomplete static information, and prove that for each term we can infera particular specialisation that can be used to reconstruct every other for that term. Wecall that principal type specialisation because of the analogy this property has with thenotion of principal types. Our presentation clarifies some of the problems existing intype specialisation, clarification that can be used as a guide in the search for solutionsto them. The presentation is divided in four parts. In the first Part we present Type Specialisationin its original form, together with some background material. In Part II wedevelop the presentation of Principal Type Specialisation, explaining all the technicaldetails, offering several examples, and presenting our prototype implementation. In Part III we describe the posibilities of the new formulation, by providing an extensionof Type Specialisation to generate polymorphic programs. And finally, in the last Partwe describe related and future work and conclude. This work is the result of seven years of research, performed during my PhD studies. Fil: Martínez López, Pablo E.. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n4100_MartinezLopez spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar ESPECIALIZACION PRINCIPAL DE TIPOS ESPECIALIZACION DE TIPOS ESPECIALIZACION DE PROGRAMAS PRODUCCION AUTOMATICA DE PROGRAMAS PROGRAMAS POLIMORFICOS PRINCIPAL TYPE SPECIALISATION TYPE SPECIALISATION PROGRAM SPECIALISATION AUTOMATIC PROGRAM PRODUCTION POLYMORPHIC PROGRAMS La noción de principalidad en especialización de tipos info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4100_MartinezLopez_oai

La noción de principalidad en especialización de tipos

Ejemplares similares