Рефал
Парадигма | Сопоставление с образцом и переписывание терминов |
---|---|
Разработано | Валентин Турчин |
Разработчик | 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]
Основы
[ редактировать ]Этот раздел читается как учебник . ( август 2020 г. ) |
Пример 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 г.