Рефал ( «Алгоритмический язык рекурсивных функций» ; русский : РЕФАЛ ) «- это функциональный язык программирования, ориентированный на символьные вычисления», включая « обработку строк , языковой перевод , [и] искусственный интеллект ». [1] Это один из старейших членов этого семейства, впервые задуманный в 1966 году как теоретический инструмент, а первая реализация появилась в 1968 году. Рефал был предназначен для объединения математической простоты с практичностью для написания больших и сложных программ.
Парадигма | Сопоставление с образцом и перезапись терминов |
---|---|
Разработано | Валентин Турчин |
Разработчик | Валентин Турчин, С. Флоренцев, В. Олюнин и др. |
Впервые появился | 1968 г. |
Печатная дисциплина | сильный , динамичный |
Веб-сайт | http://www.refal.net |
Основные реализации | |
Рефал-2, Рефал-5, Рефал-6, Рефал + |
Один из первых языков функционального программирования, который сделал это, и в отличие от Лиспа того времени, Refal основан на сопоставлении с образцом . Его сопоставление с образцом работает вместе с перезаписью терминов .
Базовая структура данных Lisp и Prolog - это линейный список, построенный последовательной операцией cons , таким образом, с доступом O (n) к n- му элементу списка . Списки Рефаля строятся и сканируются с обоих концов, сопоставление с образцом работает как для вложенных списков, так и для списков верхнего уровня. Фактически, основная структура данных Refal представляет собой дерево, а не список . Это дает свободу и удобство в создании структур данных при использовании только математически простых механизмов управления сопоставлением с образцом и заменой.
Refal также включает функцию, называемую морозильной камерой, для поддержки эффективной частичной оценки .
Рефал может применяться для обработки и преобразования древовидных структур аналогично XSLT . [2]
Основы
Пример Refal Hello World показан ниже.
$ ENTRY Go {= <Привет>;}Привет { =; }
Приведенная выше программа включает две функции: Go и Hello. Функция записывается как имя функции, за которым следует тело функции в фигурных скобках. Функция Go помечается как точка входа в программу с помощью директивы $ ENTRY.
Выражения в телах функций можно рассматривать как «вызовы» функций в синтаксисе, подобном Lisp . Например, функция Hello вызывает встроенную функцию Prout со строкой «Hello world» в качестве аргумента. Однако смысл и механизм звонка совершенно разные. Чтобы проиллюстрировать разницу, рассмотрим следующую функцию, которая определяет, является ли строка палиндромом .
Pal {= True; s.1 = Верно; s.1 e.2 s.1 =; e.1 = Ложь; }
В этом примере показана функция с более сложным телом, состоящим из четырех предложений (предложений). Предложение начинается с образца, за которым следует знак равенства, за которым следует общее выражение с правой стороны. Предложение заканчивается точкой с запятой. Например, образец второго предложения функции - «s.1», а выражение - «Истина».
Как показывает пример, шаблоны включают переменные шаблона, которые имеют форму символа, определяющего тип переменной (то, что переменная соответствует), за которым следует идентификатор переменной. Переменные, начинающиеся с буквы "s", соответствуют одному символу, а переменные, начинающиеся с буквы "e", соответствуют произвольному выражению. Идентификатор переменной может быть произвольной буквенно-цифровой последовательностью, необязательно отделенной от идентификатора типа точкой.
Функция выполняется путем сравнения своего аргумента с образцами предложений в том порядке, в котором они появляются в определении, до первого совпадающего образца. Затем функция заменяет аргумент выражением в правой части совпадающего предложения.
Если результат применения функции включает подвыражение в угловых скобках (как это будет после применения третьего предложения нашего примера), результат дополнительно обрабатывается Refal путем вызова функции, обозначенной первым символом в скобках. Выполнение останавливается, когда у результата больше нет угловых скобок, которые можно раскрыть таким образом.
Таким образом, функцию Pal можно неформально читать как: «Если выражение пустое, замените его на True. В противном случае, если выражение представляет собой единственный символ, замените его на True. В противном случае, если выражение является символом, за которым следует произвольное выражение e. 2, за которым следует тот же символ, замените его выражением
Ниже приведены три пошаговых трассировки выполнения, помеченные номерами предложений, применяемыми на каждом этапе для создания следующего.
<Приятель 'полдень'> (# 3)(# 3) <Приятель> (# 1) Правда
<Приятель 'вау'> (# 3) <Приятель> (# 2) Правда
<Приятель 'револьвер'> (# 3) <Приятель 'эволюционировать'> (# 3) <Приятель 'volv'> (# 3) <Приятель> (# 4) Ложь
Теперь мы видим, что пример Hello World фактически выполняется как последовательность следующих преобразований выражений:
Заполните машину начальным выражением, отмеченным $ ENTRY:(примените предложение в Go) <Привет> (примените предложение в Привет)(Prout - это встроенная функция, которая печатает и ничего не расширяет) (нечего применять; стоп)
Другие примеры
Факториал
Факт {0 = 1; sN = <* sN <Факт <- sN 1 >>>; }
Здесь 0 совпадает с 0 числом и дает 1. На любом другом символе, который является числом, умножьте его на результат (Факт (- sN 1)). Обратите внимание на стиль префикса операторов.
Факториал с петлями
Факт {sn =; }; Петля { 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: заархивированная копия как заголовок ( ссылка )