Registro:
| Documento: | Tesis de Grado |
| Título: | Chequeo de tipos eficiente para Path Polymorphism |
| Título alternativo: | Efficient type checking for path polymorphism |
| Autor: | Edi, Juan Ignacio |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2015 |
| Fecha en portada: | 2015 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Bonelli, Eduardo Augusto |
| Director Asistente: | Viso, Andrés Ezequiel |
| Jurado: | Díaz-Caro, Alejandro; Ríos, Alejandro Norberto |
| Idioma: | Español |
| Palabras clave: | CALCULOS DE PATRONES; CHEQUEO DE TIPOS; PATH POLYMORPHISM; TIPOS RECURSIVOS; OPERADORES ACIPATTERN CALCULI; TYPE CHECKING; PATH POLYMORPHISM; RECURSIVE TYPES; ACI OPERATORS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000673_Edi |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000673_Edi.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000673_Edi |
| Ubicación: | Dep.COM 000673 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Edi, Juan Ignacio. (2015). Chequeo de tipos eficiente para Path Polymorphism. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000673_Edi |
Resumen:
Recientemente fue propuesto un sistema de tipos que combina tipos aplicativos, constantes, unión y recursivos, para capturar estáticamente la noción de Path Polymorphism. Esto se refiere a la capacidad de operar uniformemente sobre estructuras de datos aplicativas definidas de forma recursiva, utilizando una misma función. La esencia de esta característica se manifiesta en patrones de la forma x y, que permiten descomponer una estructura de datos arbitraria en las partes que la conforman. En el presente trabajo estudiamos el problema de type checking para este sistema, realizando esta labor en dos etapas. Primero introducimos un prototipo de implementación que abarca el proceso completo, incluyendo algoritmos para chequeo de equivalencia de tipos y subtipado basados en una caracterización conductual de estas relaciones. Se utilizó Haskell para este primer enfoque, para sacar provecho de la naturaleza funcional del problema. Una vez identificadas las limitaciones del prototipo, se propuso una implementación robusta y eficiente que reduce la complejidad de los pasos clave dentro del proceso, principalmente el chequeo de subtipado. Esta segunda implementación se desarrolló en Scala, utilizando una representación más conveniente para las expresiones de tipos basada en grafos cíclicos.
Abstract:
A type system combining type application, constants as types, union types and recursive types has recently been proposed for statically typing Path Polymorphism, the ability to define functions that can operate uniformly over recursively specified applicative data structures. A typical pattern such functions resort to is x y which decomposes a compound, in other words any applicative tree structure, into its parts. We study type-checking for this type system in two stages. First we introduce a prototype implementation of the whole process that also involves algorithms for checking type equivalence and subtyping based on coinductive characterizations of those relations. We used Haskell for this first approach, to benefit from the functional nature of the problem. After identifying the limitations of the prototype, we propose an efficient and robust implementation that reduces complexity of the key part of the process, namely subtyping check. This was done on Scala using a more convenient representation for type expressions based on cyclic graphs.
Citación:
---------- APA ----------
Edi, Juan Ignacio. (2015). Chequeo de tipos eficiente para Path Polymorphism. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000673_Edi
---------- CHICAGO ----------
Edi, Juan Ignacio. "Chequeo de tipos eficiente para Path Polymorphism". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2015.https://hdl.handle.net/20.500.12110/seminario_nCOM000673_Edi
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000673_Edi.pdf
Distrubución geográfica
