Programación con indeterminismoun enfoque basado en reescritura

Resumen

Este trabajo trata acerca del uso del indeterminismo como un recurso expresivo de los lenguajes de programación. En los lenguajes indeterministas se ofrecen algunas primitivas u otros recursos que pueden ser utilizados para expresar cómputos cuyo res ultado 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. Distintas variantes del indeterminismo han sido emp leadas desde hace mucho tiempo en la especificación de sistemas (por ejemplo las máquinas de Turing o los autómatas indeterministas) o en programación (las construcciones de McCarthy o Dijkstra son ejemplos clásicos). El indeterminismo es especialmen te útil para la resolución de problemas de búsqueda, debido a que permite expresar este tipo de problemas de una forma natural y directa: cada camino alternativo es expresado en el lenguaje mediante una alternativa indeterminista, y es el sistema el que se encarga de manejar por sí mismo el proceso de exploración de las diferentes posibilidades. En un lenguaje determinista, en cambio, es el programador el que está obligado a codificar explícitamente en su algoritmo dicha exploración de las disti ntas alternativas, una tarea habitualmente no trivial y proclive a errores. Por sus grandes capacidades expresivas, el uso del indeterminismo ha despertado un especial interés en el campo de la programación declarativa. En particular este está en la base del lenguaje Prolog, quizás el más famoso representante de los lenguajes indeterministas. Los lenguajes funcionales, también el campo de la programación declarativa, no suelen considerar el indeterminismo como una característica del lenguaje, a unque este no es ajeno a su interés, y en varios trabajos se ha tratado su simulación mediante diferentes construcciones. La programación lógico-funcional (PLF), o en general, la programación declarativa multiparadigma, constituye un importante c ampo 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 d e esta linea son los lenguajes Toy y Curry, que comparten sus características principales.