Refal ( en ruso : РЕФАЛ ) "es un lenguaje de programación funcional orientado a cálculos simbólicos", que incluye " procesamiento de cadenas , traducción de lenguajes , [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 su primera implementación apareció en 1968. Refal tenía como objetivo 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 del 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 la operación cons de manera secuencial, por lo tanto con acceso O(n) al elemento n de la lista . Las listas de Refal se construyen y escanean desde ambos extremos, y la coincidencia de patrones funciona tanto para listas anidadas como para las de nivel superior. En efecto, 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 solo 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 árboles, de forma similar a XSLT . [2]
A continuación se muestra un ejemplo de Refal Hello World .
$ENTRY Go { = <Hola>;}Hola { = <Prout 'Hola mundo'>;}El programa anterior incluye dos funciones llamadas Go y Hello. Una función se escribe como el nombre de la función 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 sintaxis similar a la de Lisp . Por ejemplo, la función Hello parece llamar a la función integrada Prout con la cadena 'Hola mundo' como argumento. Sin embargo, el significado y el mecanismo de la llamada son bastante diferentes. Para ilustrar la diferencia, considere la siguiente función que determina si una cadena es un palíndromo .
Pal { = 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 la variable (con qué coincide la variable) seguido del identificador de la variable. Las variables que comienzan con una "s" coinciden con un solo símbolo, 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. Luego, la función reemplaza el argumento con la expresión del lado derecho de la oración coincidente.
Si el resultado de una aplicación de 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 el resultado invocando la función identificada por el primer símbolo entre corchetes. La ejecución se detiene cuando el resultado ya no tiene más corchetes angulares para expandir de esta manera.
La función Pal puede leerse informalmente así: "Si la expresión está vacía, reemplácela con True. De lo contrario, si la expresión es un solo símbolo, reemplácela con 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, reemplácela con la expresión <Pal e.2>. (En otras palabras, descarte los dos símbolos idénticos al principio y al final y recurra). De lo contrario, reemplace la expresión con False. (El patrón e.1 siempre coincide)."
A continuación se muestran tres rastros de ejecución paso a paso anotados con los números de oración aplicados en cada paso para producir el siguiente.
<Pal 'mediodía'> (#3) <Pal 'oo'> (#3) <Amigo> (#1) Verdadero
<Amigo 'wow'> (#3) <Amigo'> (#2) Verdadero
<Pal 'revólver'> (#3) <Amigo 'evoluciona'> (#3) <Amigo 'volv'> (#3) <Amigo mío> (#4) FALSO
Ahora podemos ver que el ejemplo Hola Mundo de hecho se ejecuta como la secuencia de las siguientes transformaciones de expresión:
Sembrar la máquina con la expresión inicial marcada por $ENTRY: <Go> (aplica la oración en Go) <Hola> (aplica la oración en Hola) <Prout 'Hola mundo'> (Prout es un programa integrado que imprime y expande hasta la nada) (nada que aplicar; parar)
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 (Hecho (- 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 = <Bucle <- sn 1> <* sn sf>>; }Como se puede ver, 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 Falso.
Una propiedad importante de Refal es que todas las funciones de Refal tienen un solo argumento (pero pueden descomponerse en términos en una expresión como la indicada anteriormente).
Definir estructuras de control es fácil
Si { T Entonces (e.1) De lo contrario (e.2) = e.1; F Entonces (e.1) De lo contrario (e.2) = e.2; }Aquí e1 se evalúa solo cuando la expresión ingresada coincide con 'Verdadero'. Entonces e1. De lo contrario, e2. Lo mismo para e2.
Estrujar { e.1'__'e.2 = <Apretar e.1'_'e.2>; e.1 = e.1; }(Se utiliza '_' en lugar del carácter de espacio para que la llamada a la función sea clara). La primera cláusula coincide siempre que la función Squeeze encuentre espacios en blanco dobles en su expresión de entrada y los reemplaza con un solo espacio en blanco. La segunda cláusula coincide solo cuando la primera no los encuentra y devuelve el valor resultante, que es la expresión actual.
Estrujar { '__'e.1 = <Apretar '_'e.1>; sA e.1 = sA <Apretar e.1>; = ; };