Рефал

Рефал

Парадигма	Сопоставление с образцом и переписывание терминов
Разработано	Валентин Турчин
Разработчик	Valentin Turchin, S. Florentsev, V. Olyunin, et al.
Впервые появился	1968  ( 1968 )
Дисциплина набора текста	сильный , динамичный
Веб-сайт	http://www.refal.net
Основные реализации
Рефал-2, Рефал-5, Рефал-6, Рефал+

Рефал ( «Алгоритмический язык рекурсивных функций» ; русский язык : РЕФАЛ ) «является функциональным языком программирования , ориентированным на символьные вычисления», включая « обработку строк , языковой перевод и [и] искусственный интеллект ». Это один из старейших членов этого семейства, впервые задуманный в 1966 году как теоретический инструмент, а первая реализация появилась в 1968 году. Целью Refal было сочетание математической простоты с практичностью для написания больших и сложных программ.

Один из первых функциональных языков программирования, который сделал это, и в отличие от Lisp своего времени, Refal основан на сопоставлении с образцом . Сопоставление с образцом работает в сочетании с переписыванием терминов .

Базовая структура данных в Лиспе и Прологе представляет собой линейный список, построенный операцией cons последовательной , то есть с доступом O(n) -му элементу списка к n . Списки Refal создаются и сканируются с обоих концов, при этом сопоставление с образцом работает как для вложенных списков, так и для списков верхнего уровня. По сути, базовая структура данных Refal представляет собой дерево, а не список . Это дает свободу и удобство в создании структур данных при использовании только математически простых механизмов управления сопоставлением и заменой образов.

Refal также включает в себя функцию, называемую морозилкой, для поддержки эффективной частичной оценки .

Рефал можно применять для обработки и преобразования древовидных структур аналогично XSLT .

Основы

Пример Refal Hello World показан ниже.

$ENTRY Go { = <Hello>;}
Hello {
   = <Prout 'Hello world'>;
}

В приведенной выше программе есть две функции: Go и Hello. Функция записывается как имя функции, за которым следует тело функции в фигурных скобках. Функция Go помечается как точка входа в программу с помощью директивы $ENTRY.

Выражения в телах функций можно рассматривать как «вызовы» функций в синтаксисе, подобном Lisp . Например, функция Hello вызывает встроенную функцию Prout со строкой «Hello world» в качестве аргумента. Однако смысл и механизм призыва совершенно иной. Чтобы проиллюстрировать разницу, рассмотрим следующую функцию, которая определяет, является ли строка палиндромом .

 Pal { = True;
    s.1 = True;
    s.1 e.2 s.1 = <Pal e.2>;
    e.1 = False;  }

В этом примере показана функция с более сложным телом, состоящим из четырех предложений (предложений). Предложение начинается с образца , за которым следует знак равенства, за которым следует общее выражение в правой части . Предложение заканчивается точкой с запятой. Например, шаблон второго предложения функции — «s.1», а выражение — «True».

Как показано в примере, шаблоны включают переменные шаблона , которые имеют форму символа, определяющего тип переменной (чему соответствует переменная), за которым следует идентификатор переменной. Переменные, начинающиеся с буквы «s», соответствуют одному символу, переменные, начинающиеся с буквы «e», соответствуют произвольному выражению. Идентификатор переменной может представлять собой произвольную буквенно-цифровую последовательность, которая может быть отделена от идентификатора типа точкой.

Функция выполняется путем сравнения своего аргумента с шаблонами ее предложений в том порядке, в котором они появляются в определении, до тех пор, пока не будет найден первый соответствующий шаблон. Затем функция заменяет аргумент выражением в правой части соответствующего предложения.

Если результат применения функции включает подвыражение в угловых скобках (как это происходит после применения третьего предложения нашего примера), результат дополнительно обрабатывается Refal путем вызова функции, идентифицируемой первым символом в скобках. Выполнение прекращается, когда в результате больше нет угловых скобок, которые можно расширить таким образом.

Таким образом, функцию Pal неформально можно прочитать так: «Если выражение пусто, замените его на True. В противном случае, если выражение представляет собой один символ, замените его на True. В противном случае, если выражение представляет собой символ, за которым следует произвольное выражение e. 2, за которым следует тот же символ, замените его выражением <Pal e.2> (Другими словами, отбросьте два одинаковых символа в начале и в конце и замените выражение на False. e.1 всегда совпадает)".

Ниже приведены три пошаговые трассировки выполнения, помеченные номерами предложений, применяемых на каждом этапе для создания следующего.

 <Pal 'noon'>  (#3)
 <Pal 'oo'>    (#3)
 <Pal >        (#1)
 True

 <Pal 'wow'>   (#3)
 <Pal 'o'>     (#2)
 True

 <Pal 'revolver'>  (#3)
 <Pal 'evolve'>    (#3)
 <Pal 'volv'>      (#3)
 <Pal 'ol'>        (#4)
 False

Теперь мы видим, что пример Hello World фактически выполняется как последовательность следующих преобразований выражений:

      Seed the machine with the initial expression marked by $ENTRY:
 <Go >                 (apply the sentence in Go)
 <Hello >              (apply the sentence in Hello)
 <Prout 'Hello world'> (Prout is a built-in that prints and expands to nothing)
                       (nothing to apply; stop)

Другие примеры

Факториал

 Fact { 0 = 1;
    s.N = <* s.N <Fact <- s.N 1>>>; }

Здесь 0 соответствует 0 числу и дает 1. Любой другой символ, являющийся числом, умножьте его на результат (Факт (- SN 1)) Обратите внимание на префиксный стиль операторов.

Факториал с циклами

 Fact { s.n = <Loop s.n 1>; };
 Loop {
    0 s.f = s.f;
    s.n s.f = <Loop <- s.n 1> <* s.n s.f>>; }

Как можно видеть, sn действует как счетчик циклов.

Равенство

 Equal {
    (e.1)(e.1) = T;
    (e.1)(e.2) = F; }

Здесь функция определяется так: если даны два термина, и эти термины одинаковы, то первое предложение соответствует и выдает True. в противном случае второе предложение соответствует и выдает False.

Важным свойством Refal является то, что все функции в refal имеют один аргумент. (Но может быть разложено на члены в выражении, приведенном выше.)

Если

Определить структуры управления легко

 If {
    T Then (e.1) Else (e.2) = e.1;
    F Then (e.1) Else (e.2) = e.2;  }

Здесь e1 оценивается только тогда, когда введенное выражение соответствует «True». Тогда e1 Еще e2 то же самое для e2.

Сжать заготовки

 Squeeze {
    e.1'__'e.2 = <Squeeze e.1'_'e.2>;
    e.1 = e.1; }

(Используя «_» вместо пробела, чтобы сделать вызов функции понятным.) Первое предложение соответствует всякий раз, когда функция Squeeze встречает двойное значение. пробелы во входном выражении и заменяет его одним пробелом. Второе предложение соответствует только тогда, когда первое не соответствует, и возвращает результирующее значение, которое является текущим выражением.

Сжатие с использованием явного цикла

Squeeze {
    '__'e.1 = <Squeeze '_'e.1>;
    s.A e.1 = s.A <Squeeze e.1>;
    = ; };

Ссылки

• Турчин, Валентин Федорович (1989). «Руководство по программированию и справочное руководство REFAL-5» . Городской колледж Нью-Йорка, издательство New England Publishing Co., Холиок.

Внешние ссылки

• Домашняя страница Рефала