В этой статье слишком много ссылок на первоисточники . ( Август 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Парадигма | Сопоставление с образцом и перезапись терминов |
---|---|
Разработано | Валентин Турчин |
Разработчик | Валентин Турчин, С. Флоренцев, В. Олюнин и др. |
Впервые появился | 1968 г. |
Печатная дисциплина | сильный , динамичный |
Веб-сайт | http://www.refal.net |
Основные реализации | |
Рефал-2, Рефал-5, Рефал-6, Рефал + |
Рефал ( «Алгоритмический язык рекурсивных функций» ; русский : РЕФАЛ ) «- это функциональный язык программирования, ориентированный на символьные вычисления», включая « обработку строк , языковой перевод , [и] искусственный интеллект ». [1] Это один из старейших членов этого семейства, впервые задуманный в 1966 году как теоретический инструмент, а первая реализация появилась в 1968 году. Рефал был предназначен для объединения математической простоты с практичностью для написания больших и сложных программ.
Один из первых языков функционального программирования, который сделал это, и в отличие от Лиспа того времени, Refal основан на сопоставлении с образцом . Его сопоставление с образцом работает вместе с перезаписью терминов .
Базовая структура данных Lisp и Prolog - это линейный список, построенный последовательной операцией cons , таким образом, с доступом O (n) к n- му элементу списка . Списки Рефала строятся и сканируются с обоих концов, при этом сопоставление шаблонов работает как для вложенных списков, так и для списков верхнего уровня. Фактически, основная структура данных Refal представляет собой дерево, а не список . Это дает свободу и удобство в создании структур данных при использовании только математически простых механизмов управления сопоставлением с образцом и заменой.
Refal также включает функцию, называемую морозильной камерой, для поддержки эффективной частичной оценки .
Рефал может применяться для обработки и преобразования древовидных структур аналогично XSLT . [2]
Основы [ править ]
Этот раздел читается как учебник и может потребовать очистки . Пожалуйста, помогите улучшить эту статью, чтобы сделать ее нейтральной по тону и соответствовать стандартам качества Википедии . ( Август 2020 г. ) |
Пример Refal Hello World показан ниже.
$ ENTRY Go {= <Привет>;}Привет { = <Prout 'Hello world'>;}
Приведенная выше программа включает две функции: Go и Hello. Функция записывается как имя функции, за которым следует тело функции в фигурных скобках. Функция Go помечается как точка входа в программу с помощью директивы $ ENTRY.
Выражения в телах функций можно рассматривать как «вызовы» функций в синтаксисе, подобном Lisp . Например, функция Hello вызывает встроенную функцию Prout со строкой «Hello world» в качестве аргумента. Однако смысл и механизм звонка совершенно разные. Чтобы проиллюстрировать разницу, рассмотрим следующую функцию, которая определяет, является ли строка палиндромом .
Pal {= True; s.1 = Верно; s.1 e.2 s.1 = <Pal e.2>; e.1 = Ложь; }
В этом примере показана функция с более сложным телом, состоящим из четырех предложений (предложений). Предложение начинается с образца, за которым следует знак равенства, за которым следует общее выражение с правой стороны. Предложение заканчивается точкой с запятой. Например, образец второго предложения функции - «s.1», а выражение - «Истина».
Как показывает пример, шаблоны включают переменные шаблона, которые имеют форму символа, определяющего тип переменной (то, что переменная соответствует), за которым следует идентификатор переменной. Переменные, начинающиеся с буквы "s", соответствуют одному символу, а переменные, начинающиеся с буквы "e", соответствуют произвольному выражению. Идентификатор переменной может быть произвольной буквенно-цифровой последовательностью, необязательно отделенной от идентификатора типа точкой.
Функция выполняется путем сравнения своего аргумента с образцами предложений в том порядке, в котором они появляются в определении, до первого совпадающего образца. Затем функция заменяет аргумент выражением в правой части совпадающего предложения.
Если результат применения функции включает подвыражение в угловых скобках (как это будет после применения третьего предложения нашего примера), результат дополнительно обрабатывается Refal путем вызова функции, обозначенной первым символом в скобках. Выполнение останавливается, когда у результата больше нет угловых скобок, которые можно раскрыть таким образом.
Таким образом, функцию Pal можно неформально читать как: «Если выражение пустое, замените его на True. В противном случае, если выражение представляет собой единственный символ, замените его на True. В противном случае, если выражение является символом, за которым следует произвольное выражение e. 2, за которым следует тот же символ, замените его выражением <Pal e.2>. (Другими словами, выбросьте два одинаковых символа в начале и в конце и выполните рекурсию). В противном случае замените выражение на False. (Шаблон e.1 всегда совпадает) ".
Ниже приведены три пошаговых трассировки выполнения, помеченные номерами предложений, применяемыми на каждом этапе для создания следующего.
<Приятель 'полдень'> (# 3) <Pal 'oo'> (# 3) <Приятель> (# 1) Правда
<Приятель 'вау'> (# 3) <Приятель> (# 2) Правда
<Приятель 'револьвер'> (# 3) <Приятель 'эволюционировать'> (# 3) <Приятель 'volv'> (# 3) <Приятель> (# 4) Ложь
Теперь мы видим, что пример Hello World фактически выполняется как последовательность следующих преобразований выражений:
Заполните машину начальным выражением, отмеченным $ ENTRY: <Go> (примените предложение в Go) <Привет> (примените предложение в Привет) <Prout 'Hello world'> (Prout - это встроенная функция, которая печатает и ничего не расширяет) (нечего применять; стоп)
Другие примеры [ править ]
Факториал [ править ]
Факт {0 = 1; sN = <* sN <Факт <- sN 1 >>>; }
Здесь 0 совпадает с 0 числом и дает 1. На любом другом символе, который является числом, умножьте его на результат (Факт (- sN 1)). Обратите внимание на стиль префикса операторов.
Факториал с петлями [ править ]
Факт {sn = <Loop sn 1>; }; Петля { 0 sf = sf; sn sf = <цикл <- sn 1> <* sn sf >>; }
Как можно видеть, sn действует как счетчик циклов.
Равенство [ править ]
Равный { (д.1) (д.1) = Т; (e.1) (e.2) = F; }
Здесь функция определяется как, если даны два условия, и термины совпадают, то первое предложение совпадает и дает True. иначе второе предложение совпадает и дает False.
Важным свойством Refal является то, что все функции в refal имеют один аргумент. (Но можно разложить на термины в выражении, как указано выше.)
Если [ редактировать ]
Определить управляющие структуры легко
Если { T Тогда (e.1) Else (e.2) = e.1; F Тогда (e.1) Else (e.2) = e.2; }
Здесь e1 оценивается только тогда, когда введенное выражение соответствует 'True'. Затем e1 Else e2 то же самое для e2.
Сожмите пробелы [ править ]
Сжимать { e.1 '__' e.2 = <Сжать e.1 '_' e.2>; е.1 = е.1; }
(Использование '_' вместо пробела char, чтобы сделать вызов функции понятным.) Первое предложение соответствует всякий раз, когда функция Squeeze встречает двойные пробелы в своем входном выражении и заменяет его одиночным пробелом. Второе предложение соответствует только тогда, когда первое не соответствует, и возвращает результирующее значение, которое является текущим выражением.
Сжать с использованием явного зацикливания [ править ]
Сжимать { '__' e.1 = <Сжать '_'e.1>; sA e.1 = sA <Сжать e.1>; знак равно };
Ссылки [ править ]
- Турчин, Валентин Ф. (1989). «Справочное и руководство по программированию РЕФАЛ-5» . Городской колледж Нью-Йорка, издательство New England Publishing Co., Холиок.
- ↑ Турчин, Валентин Ф. (1989). «Введение в Рефал» . Руководство по программированию и справочнику РЕФАЛ-5 . Хольок: New England Publishing Co. Архивировано из оригинала на 2008-07-03 . Проверено 5 апреля 2010 .
- ^ "Архивная копия" . Архивировано из оригинала на 2007-12-06 . Проверено 18 марта 2008 .CS1 maint: archived copy as title (link)
Внешние ссылки [ править ]
- Рефал домашняя страница