Рефал

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

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

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

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

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

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

Основы

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

$ENTRY Go { = <Привет>;}Привет {   = <Прут 'Привет, мир'>;}

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

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

 Пал { = Истина;    с.1 = Верно;    s.1 e.2 s.1 = <Pal e.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) <Приятель 'волв'> (#3) <Приятель 'ол'> (#4) ЛОЖЬ

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

 Заполните машину начальным выражением, отмеченным $ENTRY: <Go> (примените предложение в Go) <Привет> (примените предложение в Привет) <Prout 'Hello world'> (Prout — это встроенная функция, которая печатает и ничего не раскрывает)                       (нечего применять; стоп)

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

Факториал

 Факт {0 = 1;    SN = <* SN <Факт <- SN 1>>>; }

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

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

 Факт { sn = <Цикл sn 1>; }; Петля {    0 сф = сф;    sn sf = <Loop <- sn 1> <* sn sf>>; }

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

Равенство

 Равный {    (д.1)(д.1) = Т;    (д.1)(д.2) = F; }

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

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

Если

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

 Если {    T Тогда (д.1) Иначе (д.2) = д.1;    F Тогда (д.1) Иначе (д.2) = д.2; }

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

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

 Сжимать {    e.1'__'e.2 = <Сжать e.1'_'e.2>;    е.1 = е.1; }

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

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

Сжимать {    '__'e.1 = <Сжать '_'e.1>;    sA e.1 = sA <Сжать e.1>;    = ; };

Ссылки

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

^ Турчин, Валентин Федорович (1989). «Знакомство с Рефалом» . Руководство по программированию и справочное руководство REFAL-5 . Холиок: New England Publishing Co. Архивировано из оригинала 3 июля 2008 г. Проверено 5 апреля 2010 г.
^ «Рефал: язык обработки XML-документов» . Архивировано из оригинала 6 декабря 2007 г. Проверено 18 марта 2008 г.

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

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

[1] Турчин, Валентин Федорович (1989). «Знакомство с Рефалом» . Руководство по программированию и справочное руководство REFAL-5 . Холиок: New England Publishing Co. Архивировано из оригинала 3 июля 2008 г. Проверено 5 апреля 2010 г.

[2] «Рефал: язык обработки XML-документов» . Архивировано из оригинала 6 декабря 2007 г. Проверено 18 марта 2008 г.

[1]

[2]