Из Википедии, бесплатной энциклопедии
  (Перенаправлено с языка программирования Refal )
Перейти к навигации Перейти к поиску

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

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

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

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

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

Основы [ править ]

Пример 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., Холиок.
  1. Турчин, Валентин Ф. (1989). «Введение в Рефал» . Руководство по программированию и справочнику РЕФАЛ-5 . Хольок: New England Publishing Co. Архивировано из оригинала на 2008-07-03 . Проверено 5 апреля 2010 .
  2. ^ "Архивная копия" . Архивировано из оригинала на 2007-12-06 . Проверено 18 марта 2008 .CS1 maint: archived copy as title (link)

Внешние ссылки [ править ]

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