| REFAL | |
|---|---|
| Semántica | funcional / oracional |
| clase de idioma | lenguaje de programacion y lenguaje de programacion funcional |
| tipo de ejecución | dependiente de la implementación |
| Apareció en | 1966 |
| Autor | Valentin Turchin |
| sistema de tipos | sin escribir |
| Dialectos | REFAL-2, REFAL-5, REFAL+, REFAL-0 |
| Sitio web | refal.es |
REFAL ( Recursive Functions Algorithmic ) es uno de los lenguajes de programación funcional más antiguos , centrado en cálculos simbólicos : procesamiento de cadenas de caracteres (por ejemplo, cálculos algebraicos); traducción de un idioma (artificial o natural) a otro; resolución de problemas relacionados con la inteligencia artificial . Combina la simplicidad matemática con un enfoque práctico en la escritura de programas grandes y complejos.
Una característica distintiva del lenguaje es el uso de la coincidencia de patrones y la reescritura de términos como la forma principal de definir funciones.
Un programa Refal puede constar de uno o más módulos (archivos), cada uno de los cuales, a su vez, consta de .
Una función refal es un conjunto ordenado de oraciones que consta de un patrón y una plantilla . Se da alguna expresión a la entrada de la función ; la evaluación de una función consiste en comparar la expresión a su vez con las muestras tomadas de la primera, segunda, etc. oraciones. Si la próxima coincidencia tiene éxito, entonces, según la plantilla tomada de la misma oración, se forma una nueva expresión Refal, que será el resultado de la función. Si no fue posible comparar el argumento de la función con ninguna de las muestras disponibles (falla), se registra un error (el programa completo falla). Para evitar esto, a menudo se coloca una oración al final de la función, con una muestra de la cual puede hacer coincidir cualquier expresión en general. En algunas implementaciones modernas de Refal (por ejemplo, Refal+), la falla de cualquier expresión de función en lugar de un error genera la falla de la función misma.
Las expresiones del lenguaje refal son secuencias de términos , que pueden ser:
Dependiendo de la situación, se pueden imponer restricciones a la expresión; por ejemplo, en las muestras está prohibido usar expresiones que contengan corchetes angulares y las variables no pueden estar presentes en el campo de visión de Refal-machine.
Las variables Refal se utilizan en patrones y, dependiendo de su tipo, se pueden hacer coincidir con un solo carácter (es decir, cualquier término, excepto una expresión entre llaves), un solo término (arbitrario) o una expresión arbitraria (es decir, una secuencia de términos de longitud arbitraria). Los tipos de variables correspondientes se denominan variables S, variables T y variables E. El dialecto Refal-2 también admitía variables V, que se asignaban a una expresión arbitraria no vacía ; los dialectos modernos no admiten tales variables.
La semántica del lenguaje Refal se describe en términos de una máquina virtual llamada "refal-machine" o "refal-machine". La máquina tiene un campo de visión , que puede contener una expresión de referencia arbitraria que no contiene variables de referencia.
La ejecución del programa consta de los pasos de la máquina refal, cada uno de los cuales realiza la aplicación de una función a una expresión. Para hacer esto, la máquina de referencia busca en su campo de visión la expresión activa más a la izquierda de las más internas; en otras palabras, se encuentran pares de paréntesis angulares que no contienen otros paréntesis angulares, y si hay varios de tales pares, se selecciona el que está textualmente a la izquierda de los demás en el campo de visión. El primer término de una expresión entre paréntesis angulares debe ser un carácter de etiqueta que sirva como nombre de una función; el resto de la expresión se usa como argumento de la función.
Como se mencionó anteriormente, entre las oraciones que componen una función, existe la primera cuyo patrón puede coincidir con el argumento de la función; durante el emparejamiento, se asignan valores a las variables contenidas en el patrón. Luego, la plantilla extraída de la misma oración se toma como base para formar el resultado de la evaluación de la función; en pocas palabras, el resultado es una expresión obtenida de la plantilla reemplazando las variables con sus valores. Cabe señalar que una plantilla solo puede contener variables que están presentes en la plantilla; por lo tanto, todas las variables incluidas en la plantilla serán reemplazadas por las expresiones correspondientes al generar el resultado, y el resultado ya no contendrá variables. Por otro lado, la plantilla bien puede contener expresiones entre paréntesis angulares.
Al final del paso, el autómata de referencia reemplaza en su campo de visión la expresión activa recién calculada (incluyendo sus paréntesis angulares limitantes) con el resultado obtenido durante el cálculo de la función. Cabe señalar que el número de corchetes angulares en el campo de visión de la máquina de referencia puede aumentar en este caso.
La ejecución del programa finaliza cuando no quedan más corchetes angulares en el campo de visión de la máquina refal. La expresión actualmente a la vista se declara como resultado de ejecutar el programa refal.
Considere el ejemplo más simple de ejecutar un programa en Refal. Sea dada la siguiente función:
palíndromo { s.1 e.2 s.1 = <Palíndromo e.2>; s.1=Verdadero; /* vacío */ = Verdadero; e.1=Falso; }Esta función analiza una expresión y devuelve el carácter de token como resultado Truesi la expresión es un palíndromo y en Falsecaso contrario. La función tiene el nombre Palindrom. Aclaremos que s.1 es una variable tipo S, e.1y e.2 son variables tipo E. Por lo tanto, el cuerpo de la función consta de cuatro cláusulas, la primera de las cuales funcionará si el argumento de la función es una expresión que comienza y termina con el mismo carácter; el segundo se utilizará si el argumento consta de exactamente un carácter; el tercero se usa para un argumento vacío y, finalmente, el cuarto es adecuado para todos los demás casos.
Tenga en cuenta que el patrón en la primera oración contiene una expresión activa, que es una llamada de función recursiva Palindrom. Esto refleja el hecho de que si el primer y el último carácter coinciden, se pueden descartar y el resto de la expresión se comprueba por palindromicidad.
Deje que la siguiente expresión activa aparezca en el campo de visión de la máquina de referencia:
<Palíndromo 'abcba'>Luego, la ejecución constará de tres pasos, después de lo cual aparecerán las siguientes expresiones en el campo de visión:
<Palíndromo 'bcb'> <Palíndromo 'c'> VerdaderoLos primeros dos pasos usaron la primera oración, el último paso la segunda. Dado que después del tercer paso el campo de visión ya no contiene paréntesis angulares, aquí se completa el trabajo de la máquina de referencia.
La primera versión de REFAL a fue creada en 1966 por Valentin Turchin como un metalenguaje para describir la semántica de otros lenguajes. Posteriormente, a raíz de la aparición de implementaciones suficientemente eficaces en un ordenador, empezó a encontrar un uso práctico como lenguaje de programación.
Actualmente, los principales dialectos del idioma son REFAL-2 ( década de 1970 ), REFAL-5 ( 1985 ) y REFAL+ ( 1990 ), que difieren entre sí en detalles de sintaxis y un conjunto de "herramientas adicionales" que amplían la versión original.
El siguiente programa de dialecto REFAL-5 invierte e imprime la cadena de datos de entrada:
$ENTRAR Ir { = <Prot<Reverse<Tarjeta>>>; } reverso { e.Texto = <DoReverse() e.Texto>; } DoReverse { (e.Escaneado) = e.Escaneado; (e.Scanned) s.Next e.Tail = <DoReverse (s.Next e.Scanned) e.Tail>; }El mismo programa se puede escribir de otra forma:
$ENTRAR Ir { = <Prot<Reverse<Tarjeta>>>; } reverso { /* Si la cadena no está vacía, ajusta el primer carácter hasta el final */ s.First e.Tail = <Reverse e.Tail> s.First; /* Procesar cadena vacía */ /* vacío */ = /* vacío */; }El siguiente programa en el dialecto REFAL-5 recibe como entrada una cadena de datos que representa la representación decimal de algún número natural N, después de lo cual calcula e imprime el número de Fibonacci con el número N:
$ENTRAR Ir { = <Prout<Símbolo<FN<Número<Tarjeta>>>>; } FN { /* Llamar a una función auxiliar que implementa el bucle recursivo residual. */ Número de s. = <Número de s.DoFN 0 1>; } /* La función implementa un bucle recursivo residual. Bucle invariable <DoFN s.Counter s.Current s.Next> s.Counter -- número de iteraciones restantes. s.Current: número de Fibonacci correspondiente a la iteración actual. s.Next: el valor del número de Fibonacci para la siguiente iteración. */ DoFN { 0 s.Actual s.Siguiente = s.Actual; s.Contador s.Actual s.Siguiente = <DoFN <Sub a Contador 1> a Siguiente <Agregar a Actual a Siguiente>>; }
| Lenguajes de programación | |
|---|---|
| |