Resumen:
Nuestro trabajo estudia relaciones entre distintos λ-cálculos con patrones a través de la definición de traducciones entre ellos, a nivel sintáctico. Presentamos la traducción de un gran fragmento del cálculo lambda con patrones múltiples (λC) al cálculo lambda con constructores (λB_c). Esto tiene como fin la posibilidad de compilación de un lenguaje de características y operaciones complejas que están “internalizadas", como el primero, en un lenguaje con un sistema de patrones minimales dados por el análisis por casos sobre constantes básicas, como el segundo, que incluye a cambio un conjunto de reglas de propagación de este constructor de análisis por casos. Tenemos también interés en codificar con combinadores ciertos cálculos con patrones. Para esto, presentamos una formulación de un cálculo de combinadores para λB_c. Si bien los combinadores S y K clásicos de la lógica combinatoria son funcionalmente completos (en el sentido de que permiten expresar todos los términos del cálculo lambda), proponemos una extensión de esta lógica a través de otros combinadores posibles para la propagación del constructor del análisis de casos, con el fin de obtener un sistema funcionalmente completo y minimal de combinadores para λB_c. Así, se provee un mecanismo de implementación del pattern matching del mismo modo que la lógica combinatoria clásica provee una implementación del cálculo lambda. Para este nuevo sistema probamos su capacidad de abstracción y la confluencia (la cual garantiza la unicidad de formas normales).
Abstract:
Our work studies relations between different λ-calculi with patterns by means of translations between them, to the syntactical level. We present the translation of a big fragment of the λ-calculus with multiple patterns (λC) to the λ-calculus with constructors (λB_c). This has as goal to make it possible to compile a language of complex characteristics and operations which are internalized, like the former, into another with a minimal pattern system given by the case construct over basic constants, like the latter, which in turn includes a set of rules for propagating this case construct. We are also interested in coding with combinators certain pattern calculi. For this task we present a formulation of a combinator calculus for λB_c. Although the classical combinators S and K of combinatory logic are functionally complete (in the sense that they can represent all the λ-calculus terms), we propose an extension of this logic by means of other possible combinators for handling the propagation of the case construct, the goal being to obtain a minimal functionally complete system of combinators for λB_c. Therefore, a mechanism for implementing pattern matching is given, much in the same way as classical combinatory logic provides an implementation of λ-calculus. For this new system we prove its capability of abstraction and its con uence (which guarantees the uniqueness of normal forms).
Citación:
---------- APA ----------
Santi, Lucio. (2009). Traducciones entre lambda-cálculos con patrones. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000405_Santi
---------- CHICAGO ----------
Santi, Lucio. "Traducciones entre lambda-cálculos con patrones". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2009.https://hdl.handle.net/20.500.12110/seminario_nCOM000405_Santi
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000405_Santi.pdf
Distrubución geográfica