Рефал ( «Рекурсивный алгоритмический язык функций» ; русский : РЕФАЛ ) «является функциональным языком программирования, ориентированным на символьные вычисления», включая « обработку строк , языковой перевод [и] искусственный интеллект ». [1] Это один из старейших членов этого семейства, впервые задуманный в 1966 году как теоретический инструмент, а первая реализация появилась в 1968 году. Рефал был предназначен для объединения математической простоты с практичностью для написания больших и сложных программ.
Один из первых функциональных языков программирования, который сделал это, и в отличие от Lisp своего времени, Refal основан на сопоставлении с образцом . Его сопоставление с образцом работает в сочетании с перезаписью терминов .
Базовая структура данных Lisp и Prolog представляет собой линейный список, построенный с помощью операции cons в последовательном порядке, таким образом, с доступом O(n) к n -му элементу списка . Списки Refal строятся и сканируются с обоих концов, причем сопоставление с образцом работает как для вложенных списков, так и для списка верхнего уровня. По сути, базовая структура данных Refal представляет собой дерево, а не список . Это дает свободу и удобство в создании структур данных, используя только математически простые механизмы управления сопоставлением с образцом и подстановкой.
Refal также включает функцию, называемую заморозкой, для поддержки эффективной частичной оценки .
Refal может применяться для обработки и преобразования древовидных структур, аналогично XSLT . [2]
Ниже показан пример Refal Hello World .
$ENTRY Перейти { = <Привет>;}Привет { = <Prout 'Привет, мир'>;}Программа выше включает две функции с именами Go и Hello. Функция записывается как имя функции, за которым следует тело функции в фигурных скобках. Функция Go помечается как точка входа программы с помощью директивы $ENTRY.
Можно было бы думать о выражениях в телах функций как о "вызовах" функций в синтаксисе, подобном Lisp . Например, функция Hello, по-видимому, вызывает встроенную функцию Prout со строкой "Hello world" в качестве аргумента. Однако значение и механизм вызова совершенно иные. Чтобы проиллюстрировать разницу, рассмотрим следующую функцию, которая определяет, является ли строка палиндромом .
Пал { = Истина; с.1 = Верно; с.1 е.2 с.1 = <Пал е.2>; е.1 = Ложь; }В этом примере показана функция с более сложным телом, состоящим из четырех предложений (клауз). Предложение начинается с шаблона, за которым следует знак равенства, за которым следует общее выражение с правой стороны. Предложение завершается точкой с запятой. Например, шаблон второго предложения функции — «s.1», а выражение — «True».
Как показывает пример, шаблоны включают переменные шаблона , которые имеют форму символа, идентифицирующего тип переменной (то, чему соответствует переменная), за которым следует идентификатор переменной. Переменные, начинающиеся с "s", соответствуют одному символу, те, которые начинаются с "e", соответствуют произвольному выражению. Идентификатор переменной может быть произвольной буквенно-цифровой последовательностью, опционально отделенной от идентификатора типа точкой.
Функция выполняется путем сравнения своего аргумента с шаблонами своих предложений в том порядке, в котором они появляются в определении, до первого совпадающего шаблона. Затем функция заменяет аргумент выражением в правой части совпавшего предложения.
Если результат применения функции включает подвыражение в угловых скобках (как это будет после применения третьего предложения нашего примера), результат далее обрабатывается Refal путем вызова функции, идентифицированной первым символом в скобках. Выполнение останавливается, когда в результате больше нет угловых скобок для расширения таким образом.
Таким образом, функцию Pal можно неформально прочитать как: «Если выражение пустое, замените его на True. В противном случае, если выражение представляет собой один символ, замените его на True. В противном случае, если выражение представляет собой символ, за которым следует произвольное выражение e.2, за которым следует тот же символ, замените его на выражение <Pal e.2>. (Другими словами, отбросьте два одинаковых символа в начале и в конце и выполните рекурсию). В противном случае замените выражение на False. (Шаблон e.1 всегда совпадает)».
Ниже приведены три пошаговых трассировки выполнения, аннотированные номерами предложений, применяемых на каждом этапе для получения следующего.
<Пал 'полдень'> (#3) <Пал 'у'> (#3) <Приятель> (#1) Истинный
<Приятель 'вау'> (#3) <Пал 'о'> (#2) Истинный
<Приятель 'револьвер'> (#3) <Пал 'эволюционируй'> (#3) <Пал 'volv'> (#3) <Пал 'ол'> (#4) ЛОЖЬ
Теперь мы видим, что пример Hello World на самом деле выполняется как последовательность следующих преобразований выражений:
Заполните машину начальным выражением, отмеченным $ENTRY: <Go > (применить предложение на языке Go) <Привет > (примените предложение в Hello) <Prout 'Hello world'> (Prout — встроенная функция, которая печатает и расширяется до нуля) (нечего применять; стоп)
Факт { 0 = 1; sN = <* sN <Факт <- sN 1>>>; }Здесь 0 соответствует 0 числу и возвращает 1. Для любого другого символа, который является числом, умножьте его на результат (Факт (- sN 1)) Обратите внимание на префиксный стиль операторов.
Факт { sn = <Цикл sn 1>; }; Петля { 0 сф = сф; sn sf = <Цикл <- sn 1> <* sn sf>>; }Как видно, sn действует как счетчик циклов.
Равный { (e.1)(e.1) = Т; (e.1)(e.2) = F; }Здесь функция определяется следующим образом: если даны два термина, и они одинаковы, то первое предложение соответствует и возвращает значение True. В противном случае второе предложение соответствует и возвращает значение False.
Важным свойством Refal является то, что все функции в refal являются одноаргументными. (Но могут быть разложены на термы в выражении, как указано выше.)
Определить структуры управления легко
Если { T Тогда (e.1) Иначе (e.2) = e.1; F Тогда (e.1) Иначе (e.2) = e.2; }Здесь e1 оценивается только тогда, когда введенное выражение соответствует значению «Истина». Тогда e1 Иначе e2 то же самое для e2.
Сжимать { e.1'__'e.2 = <Сжать e.1'_'e.2>; е.1 = е.1; }(Использование '_' вместо пробела, чтобы сделать вызов функции понятным.) Первое предложение соответствует всякий раз, когда функция Squeeze встречает двойные пробелы в своем входном выражении, и заменяет их одним пробелом. Второе предложение соответствует только тогда, когда первое не совпало, и возвращает результирующее значение, которое является текущим выражением.
Сжимать { '__'e.1 = <Сжать '_'e.1>; sA e.1 = sA <Сжатие e.1>; = ; };