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 [e] 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, y la primera implementación apareció en 1968. Refal pretendía combinar la simplicidad matemática con la practicidad para escribir programas grandes y sofisticados.
Uno de los primeros lenguajes de programación funcional en hacerlo, y a diferencia del Lisp de su época, Refal se basa en la coincidencia de patrones . Su coincidencia de patrones funciona junto con la reescritura de términos .
La estructura de datos básica de Lisp y Prolog es una lista lineal construida mediante operación contras de manera secuencial, por lo tanto con acceso O(n) al enésimo elemento de la lista . Las listas de Refal se crean y escanean desde ambos extremos, y la coincidencia de patrones funciona tanto para las listas anidadas como para las de nivel superior. De hecho, la estructura de datos básica de Refal es un árbol en lugar de una lista . Esto brinda libertad y conveniencia para crear estructuras de datos mientras se utilizan únicamente mecanismos de control matemáticamente simples de coincidencia y sustitución de patrones.
Refal también incluye una función llamada congelador para respaldar una 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 Refal Hello World .
$ENTRY Ir { = <Hola>;}Hola { = <Prout 'Hola mundo'>;}El programa anterior incluye dos funciones llamadas Ir y Hola. Una función se escribe como el nombre de la función seguido del cuerpo de la función entre llaves. La función Ir se marca como el punto de entrada del programa usando 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 Lisp . Por ejemplo, la función Hola parece llamar a la función Prout incorporada con la cadena 'Hola mundo' como argumento. El significado y el mecanismo de la llamada, sin embargo, es bastante diferente. Para ilustrar la diferencia, considere 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, que consta de cuatro oraciones (cláusulas). Una oración comienza con un patrón seguido de un signo igual seguido de una expresión general en el lado derecho. Una oración termina 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 de patrón que tienen la forma de un carácter que identifica el tipo de variable (lo que coincide con la variable) seguido del identificador de variable. Las variables que comienzan con "s" coinciden con un solo símbolo, las que comienzan con "e" coinciden con una expresión arbitraria. El identificador de variable puede ser una secuencia alfanumérica arbitraria opcionalmente separada 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 el primer patrón que coincida. Luego, la función reemplaza el argumento con la expresión en el lado derecho de la oración coincidente.
Si el resultado de la aplicación de una función incluye una subexpresión entre corchetes angulares (como sucederá después de que se aplique la tercera oración de nuestro ejemplo), Refal procesa aún más el resultado invocando la función identificada por el primer símbolo entre corchetes. La ejecución se detiene cuando el resultado no tiene más corchetes angulares para expandirse de esta manera.
Por lo tanto, la función Pal se puede leer informalmente como: "Si la expresión está vacía, reemplácela con Verdadero. De lo contrario, si la expresión es un solo símbolo, reemplácela con Verdadero. De lo contrario, si la expresión es un símbolo seguido de una expresión arbitraria, por ejemplo. 2 seguido del mismo símbolo, reemplácelo con la expresión <Pal e.2> (En otras palabras, deseche los dos símbolos idénticos al principio y al final y recurra). e.1 siempre coincide)."
Los siguientes son tres seguimientos de ejecución paso a paso anotados con los números de oración aplicados en cada paso para producir la siguiente
<Amigo 'mediodía'> (#3) <Amigo 'oo'> (#3) <Amigo> (#1) Verdadero
<Amigo 'guau'> (#3) <Amigo'> (#2) Verdadero
<Amigo 'revólver'> (#3) <Amigo 'evoluciona'> (#3) <Amigo 'volv'> (#3) <Amigo 'ol'> (#4) FALSO
Ahora podemos ver que el ejemplo de Hola Mundo, de hecho, se ejecuta como la secuencia de las siguientes transformaciones de expresión:
Siembre la máquina con la expresión inicial marcada por $ENTRY: <Ir> (aplicar la frase en Ir) <Hola> (aplica la frase en Hola) <Prout 'Hola mundo'> (Prout es una función incorporada que se imprime y se expande hasta quedar en nada) (nada que aplicar; detenerse)
Hecho { 0 = 1; sN = <* sN <Hecho <- sN 1>>>; }Aquí 0 coincide con 0 el número y produce 1. En cualquier otro símbolo que sea un número, multiplíquelo con el resultado de (Fact (- sN 1)). Tenga en cuenta el estilo de prefijo de los operadores.
Hecho { sn = <Bucle sn 1>; }; Bucle { 0 pies cuadrados = pies cuadrados; sn sf = <Lazo <- sn 1> <* sn sf>>; }Como puede verse, sn actúa como contador de bucle.
Igual { (e.1)(e.1) = T; (e.1)(e.2) = F; }Aquí la función se define como, si se dan dos términos y los términos son iguales, entonces la primera cláusula coincide y produce Verdadero. de lo contrario, la segunda cláusula coincide y produce False.
Una propiedad importante de Refal es que todas las funciones en refal tienen un solo argumento. (Pero puede descomponerse en términos en una expresión como la anterior).
Definir estructuras de control es fácil
Si { T Entonces (e.1) Si no (e.2) = e.1; F Entonces (e.1) Si no (e.2) = e.2; }Aquí, e1 se evalúa solo cuando la expresión ingresada coincide con 'Verdadero'. Luego e1. De lo contrario, e2 es lo mismo para e2.
Estrujar { e.1'__'e.2 = <Apretar e.1'_'e.2>; e.1 = e.1; }(Usando '_' en lugar de espacio char para que la llamada a la función sea clara.) La primera cláusula coincide siempre que la función Squeeze encuentra espacios en blanco dobles en su expresión de entrada y lo reemplaza con un solo espacio en blanco. La segunda cláusula coincide solo cuando la primera no lo hace y devuelve el valor resultante que es la expresión actual.
Estrujar { '__'e.1 = <Apretar '_'e.1>; sA e.1 = sA <Apretar e.1>; = ; };