Extensión del lambda-cálculo para la Modelización de Procesos Concurrentes


Author:
Title:
Language of presentation:
Promotor:
Date of defense:
Institution granting degree:
 Javier Oliver
Ext. del lambda-cálculo para la Modelización de Procesos Concurrentes
Spanish
Prof. Isidro Ramos
September 1996
Universidad Politénica de Valencia, Spain

Abstract

El lambda-cálculo es una teoría sin tipos que interpreta las funciones como reglas, es decir, el proceso de ir de un argumento a un valor, un proceso codificado por una definición. La idea de utilizar el lambda-cálculo como un marco matemático para la descripción y el razonamiento acerca de los sistemas computacionales es antigua. De hecho, gracias al análisis realizado por Turing, se puede afirmar que, a pesar de que su sintaxis es muy simple, el lambda-cálculo es lo suficientemente potente para describir todas las funciones computables mecánicamente. Pero, como mostró G. Berry, la computación que captura el lambda-cálculo es esencialmente secuencial. Un desafío importante que, sobre todo desde finales de los años ochenta, está implicando a muchos investigadores es la construcción de un marco similar al lambda-cálculo para la concurrencia y la comunicación entre procesos.

El objetivo fundamental que guiará el presente trabajo es la formalización de un cálculo que extiende el lambda-cálculo para modelizar la concurrencia y la comunicacián entre procesos. El lenguaje desarrollado se denomina lambda-cálculo Etiquetado Paralelo (LCEP). Su origen está en una propuesta inicial de H. Ait-Kaci (el lambda-cálculo Etiquetado) que describe un lenguaje, extensión del lambda-cálculo, en el que los argumentos de las funciones se seleccionan mediante etiquetas, incluyendo tanto posiciones numéricas como simbólicas. Esta extensión es conservativa en el sentido de que, cuando el conjunto de etiquetas es el conjunto unario {1}, el lambda-cálculo Etiquetado coincide exactamente con el lambda-cálculo, condición que no se cumple en las otras propuestas que vamos a estudiar comparativamente como punto de partida. Para describir el nuevo cálculo vamos a utilizar una semántica operacional dada por un sistema de transición, a partir de la cual propondremos diferentes relaciones de equivalencia para modelar los distintos aspectos relacionados con el comportamiento operacional de los procesos.

Por último, ya que la escritura directa de programas en LCEP resulta demasiado compleja en la mayoría de los casos como para pensar en él como recurso expresivo adecuado para la programación, vamos a definir un lenguaje de más alto nivel, ALEPH, que posee los recursos expresivos deseables en programación y permite aprovechar la potencia computacional del sistema. Mostraremos cómo ALEPH se traduce a LCEP como código máquina y es a través de éste como se realizan las ejecuciones de los programas.

A lo largo del texto es importante descubrir que a través de una sintaxis razonablemente simple es posible expresar todas las características que conlleva la concurrencia dentro de un paradigma funcional.