Refal

Refal ( «Lenguaje algorítmico de funciones recursivas» ; ruso : РЕФАЛ ) «es un lenguaje de programación funcional orientado a cálculos simbólicos», que incluye « procesamiento de cadenas , traducción de idiomas [y] inteligencia artificial ». ^{[ 1 ]} Es uno de los miembros más antiguos de esta familia, concebido por primera vez en 1966 como una herramienta teórica, con la primera implementación apareciendo en 1968. Refal fue diseñado para combinar la simplicidad matemática con la practicidad para escribir programas grandes y sofisticados.

Refal , uno de los primeros lenguajes de programación funcional en hacerlo, y a diferencia de Lisp de su época, se basa en la coincidencia de patrones . Su coincidencia de patrones funciona en conjunto con la reescritura de términos .

La estructura de datos básica de Lisp y Prolog es una lista lineal construida mediante operaciones cons de forma secuencial, lo que permite un acceso O(n) al enésimo elemento de la lista. Las listas de Refal se construyen y recorren desde ambos extremos, y la coincidencia de patrones funciona tanto para listas anidadas como para la de nivel superior. En efecto, la estructura de datos básica de Refal es un árbol en lugar de una lista . Esto proporciona libertad y comodidad para crear estructuras de datos utilizando únicamente mecanismos de control matemáticamente sencillos, como la coincidencia de patrones y la sustitución.

Refal también incluye una función llamada congelador para facilitar la evaluación parcial eficiente .

Refal se puede aplicar al procesamiento y transformación de estructuras de árbol, de manera similar a XSLT . ^{[ 2 ]}

A continuación se muestra un ejemplo de "Hola Mundo" de Refal.

$ENTRY Ir { = <Hola>;} Hola { = <Pronunciar 'Hola mundo'>; }

El programa anterior incluye dos funciones llamadas Go y Hello. Una función se escribe con su nombre seguido del cuerpo de la función entre llaves. La función Go se marca como el punto de entrada del programa mediante la directiva $ENTRY.

Se podría pensar en las expresiones en los cuerpos de las funciones como "llamadas" a funciones en una sintaxis similar a la de Lisp . Por ejemplo, la función Hello parece llamar a la función integrada Prout con la cadena 'Hello world' como argumento. Sin embargo, el significado y el mecanismo de la llamada son bastante diferentes. Para ilustrar la diferencia, consideremos la siguiente función que determina si una cadena es un palíndromo .

Amigo { = Verdadero; s.1 = Verdadero; s.1 e.2 s.1 = <Pal e.2>; e.1 = Falso; }

Este ejemplo muestra una función con un cuerpo más complejo, compuesto por cuatro oraciones (cláusulas). Cada oración comienza con un patrón seguido de un signo de igual y, a la derecha, una expresión general . La oración finaliza con un punto y coma. Por ejemplo, el patrón de la segunda oración de la función es "s.1" y la expresión es "Verdadero".

Como muestra el ejemplo, los patrones incluyen variables que tienen la forma de un carácter que identifica el tipo de variable (a qué coincide la variable) seguido del identificador de la variable. Las variables que comienzan con una "s" coinciden con un solo símbolo, mientras que las que comienzan con una "e" coinciden con una expresión arbitraria. El identificador de la variable puede ser una secuencia alfanumérica arbitraria, separada opcionalmente del identificador de tipo por un punto.

Una función se ejecuta comparando su argumento con los patrones de sus oraciones en el orden en que aparecen en la definición, hasta encontrar el primer patrón que coincida. A continuación, la función reemplaza el argumento con la expresión que se encuentra a la derecha de la oración coincidente.

Si el resultado de la aplicación de una función incluye una subexpresión entre corchetes angulares (como ocurrirá tras aplicar la tercera frase de nuestro ejemplo), Refal procesará el resultado invocando la función identificada por el primer símbolo entre corchetes. La ejecución se detiene cuando el resultado ya no contiene más corchetes angulares que expandir de esta manera.

La función Pal puede interpretarse informalmente de la siguiente manera: "Si la expresión está vacía, se reemplaza por True. De lo contrario, si la expresión es un solo símbolo, se reemplaza por True. De lo contrario, si la expresión es un símbolo seguido de una expresión arbitraria e.2 seguida del mismo símbolo, se reemplaza por la expresión <Pal e.2>. (En otras palabras, se descartan los dos símbolos idénticos del principio y del final y se aplica la recursión). En caso contrario, se reemplaza la expresión por False. (El patrón e.1 siempre coincide)".

A continuación se muestran tres trazas de ejecución paso a paso anotadas con los números de sentencia aplicados en cada paso para producir el siguiente

<Amigo 'mediodía'> (#3) <Pal 'oo'> (#3) <Amigo> (#1) Verdadero

<Amigo 'wow'> (#3) <Pal 'o'> (#2) Verdadero

<Pal 'revólver'> (#3) <Amigo 'evolucionar'> (#3) <Pal 'volv'> (#3) <Pal 'ol'> (#4) FALSO

Ahora podemos ver que el ejemplo "Hola Mundo" se ejecuta, de hecho, como la secuencia de las siguientes transformaciones de expresiones:

 Inicialice la máquina con la expresión inicial marcada por $ENTRY: <Go> (aplica la frase en Go) <Hola> (aplicar la frase en Hola) <Prout 'Hola mundo'> (Prout es una función integrada que imprime y luego se expande a nada) (no hay nada que aplicar; detenerse)

• Turchin, Valentin F. (1989). "Guía de programación y manual de referencia de REFAL-5" . The City College of New York, New England Publishing Co., Holyoke.

• Página principal de Refal