Sistemas de tipos en lenguajes lógico-funcionales

Abstract

La programación lógico-funcional es un paradigma de programación declarativa muy expresivo, fruto de la combinación de la programación funcional y la programación lógica. Entre sus principales características destacan la posibilidad de de1nir funciones indeterministas, los patrones de orden superior y el uso de variables libres que se ligan a valores adecuados durante el cómputo. Desde el punto de vista de tipos, los sistemas lógico-funcionales han adoptado demaneradirectaelsistemadetiposdeDamas-Milner,provenientedelámbito funcional, debido a su sencillez y a la existencia de tipos principales y métodos efectivos para la inferencia de tipos. Sin embargo, esta adaptación directa no maneja adecuadamente algunas de las principales características de los lenguajes lógico-funcionales como los patrones de orden superior o las variables libres, dando lugar errores de tipos durante la evaluación. En esta tesis proponemos tres sistemas de tipos adecuados para la programación lógico-funcional cuyo objetivo es manejar correctamente estas características problemáticas desde el punto de vista de los tipos. Los sistemas de tipos propuestos, que tratan diferentes mecanismos de cómputos lógicofuncionales (reescritura y estrechamiento), dan solución a los mencionados problemas, proporcionando resultados técnicos de corrección. Además, suponen un mejora sobre propuestas previas de sistemas de tipos para programación lógico-funcional, ya que salvan algunas de sus limitaciones. Aparte de los resultados teóricos, en esta tesis también se han desarrollado implementaciones de los sistemas de tipos, integrándolos como fase de comprobación de tipos en ramas del sistema lógico-funcional Toy.