Programming with non-determinism: a rewriting based approach

Abstract

Este trabajo trata acerca del uso del indeterminismo como un recurso expresivo de los lenguajes de programación. En los lenguajes indeterministas se ofrecen primitivas que pueden ser utilizadas para expresar cómputos cuyo resultado final no está totalmente determinado por los datos de entrada. En estos lenguajes, en los que la concurrencia no tiene porqué estar presente, el indeterminismo es parte del modelo de cómputo. La programación lógico-funcional, o en general, la programación declarativa multiparadigma, constituye un importante campo de investigación que intenta integrar en el mismo lenguaje las principales virtudes de varios paradigmas independientes: programación lógica, programación funcional perezosa e incluso programación con restricciones. Dos representantes modernos de esta linea son los lenguajes Toy y Curry, que comparten sus características principales. En estos lenguajes se emplean sistemas de reescritura de términos no confluentes como programas, de esta manera soportando funciones no estrictas e indeterministas, que son una de las características distintivas del paradigma. En esta tesis hemos intentado hacer algunas contribuciones al campo de la programación lógico-funcional indeterminista, usando los sistemas de reescritura basados en constructoras como el punto de partida de nuestros formalismos. Nuestros objetivos son diversos, a menudo al nivel de las descripciones semánticas, donde tratamos de aportar construcciones y resultados que esperamos puedan ser de utilidad para profundizar en la comprensión del significado de los programas, o como herramientas para la manipulación, análisis y transformación de programas. También nos hemos ocupado de aspectos más prácticos, y algunos prototipos han sido desarrollados a consecuencia de ello. Unas veces trabajamos en un marco consolidado---concretamente call-time choice o run-time choice---mientras que otras hemos decidido explorar las capacidades expresivas de las funciones indeterministas proponiendo nuevos marcos semánticos, algunos de ellos surgiendo de la combinación de semánticas ya existentes, otros presentando propuestas semánticas más novedosas.