Programming with non-determinism: a rewriting based approach
Juan Rodríguez Hortalá · 2010
Este trabajo trata acerca del uso del indeterminismo como un recurso expresivo de los lenguajes de programacion. En los lenguajes indeterministas se ofrecen primitivas que pueden ser utilizadas para expresar computos cuyo resultado final no esta totalmente determinado por los datos de entrada. En estos lenguajes, en los que la concurrencia no tiene porque estar presente, el indeterminismo es parte del modelo de computo. La programacion logico-funcional, o en general, la programacion declarativa multiparadigma, constituye un importante campo de investigacion que intenta integrar en el mismo lenguaje las principales virtudes de varios paradigmas independientes: programacion logica, programacion funcional perezosa e incluso programacion con restricciones. Dos representantes modernos de esta linea son los lenguajes Toy y Curry, que comparten sus caracteristicas principales. En estos lenguajes se emplean sistemas de reescritura de terminos no confluentes como programas, de esta manera soportando funciones no estrictas e indeterministas, que son una de las caracteristicas distintivas del paradigma. En esta tesis hemos intentado hacer algunas contribuciones al campo de la programacion logico-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 semanticas, donde tratamos de aportar construcciones y resultados que esperamos puedan ser de utilidad para profundizar en la comprension del significado de los programas, o como herramientas para la manipulacion, analisis y transformacion de programas. Tambien nos hemos ocupado de aspectos mas practicos, 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 semanticos, algunos de ellos surgiendo de la combinacion de semanticas ya existentes, otros presentando propuestas semanticas mas novedosas.