Рефал - Википедия - Refal

Рефал
ПарадигмаСопоставление с образцом и Перезапись терминов
РазработаноВалентин Турчин
РазработчикВалентин Турчин, С. Флоренцев, В. Олюнин и др.
Впервые появился1968 (1968)
Печатная дисциплинасильный, динамичный
Интернет сайтhttp://www.refal.net
Основной реализации
Рефал-2, Рефал-5, Рефал-6, Рефал +

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

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

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

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

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

Основы

Рефал Привет, мир пример показан ниже.

$ ENTRY Go {= ;} Hello {= ;}

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

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

 Pal {= True; s.1 = Верно; s.1 e.2 s.1 = ; e.1 = Ложь; }

В этом примере показана функция с более сложным телом, состоящим из четырех фразы (пункты). Предложение начинается с шаблон за которым следует знак равенства, за которым следует общий выражение с правой стороны. Предложение заканчивается точкой с запятой. Например, образец второго предложения функции - «s.1», а выражение - «True».

Как показывает пример, шаблоны включают переменные шаблона которые имеют форму символа, определяющего тип переменной (то, что переменная соответствует), за которым следует идентификатор переменной. Переменные, начинающиеся с буквы "s", соответствуют одному символу, а переменные, начинающиеся с буквы "e", соответствуют произвольному выражению. Идентификатор переменной может быть произвольной буквенно-цифровой последовательностью, необязательно отделенной от идентификатора типа точкой.

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

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

Таким образом, функцию Pal можно неформально читать как: «Если выражение пустое, замените его на True. В противном случае, если выражение представляет собой единственный символ, замените его на True. В противном случае, если выражение является символом, за которым следует произвольное выражение e. 2, за которым следует тот же символ, замените его выражением . (Другими словами, выбросьте два одинаковых символа в начале и в конце и выполните рекурсию). В противном случае замените выражение на False. (Шаблон e.1 всегда совпадает) ".

Ниже приведены три пошаговых трассировки выполнения, помеченные номерами предложений, применяемыми на каждом этапе для создания следующего.

  (# 3)  (# 3)  (# 1) Верно
  (# 3)  (# 2) Верно
  (# 3)  (# 3)  (# 3)  (# 4) Ложь

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

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

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

Факториал

 Факт {0 = 1; s.N = <* s.N <Факт <- s.N 1 >>>; }

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

Факториал с петлями

 Факт {s.n = ; }; Петля {0 s.f = s.f; s.n s.f = <Цикл <- s.n 1> <* s.n s.f >>; }

Как видно, s.n действует как счетчик циклов.

Равенство

 Равно {(e.1) (e.1) = T; (e.1) (e.2) = F; }

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

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

Если

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

 Если {T Then (e.1) Else (e.2) = e.1; F Тогда (e.1) Else (e.2) = e.2; }

Здесь e1 оценивается только тогда, когда введенное выражение соответствует 'True'. Затем e1 Else e2 то же самое для e2.

Выдавить заготовки

 Squeeze {e.1 '__' e.2 = ; е.1 = е.1; }

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

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

 Squeeze {'__' e.1 = ; s.A e.1 = s.A ; знак равно };

Рекомендации

  • Турчин, Валентин Ф. (1989). «Справочное и руководство по программированию РЕФАЛ-5». Городской колледж Нью-Йорка, издательство New England Publishing Co., Холиок.
  1. ^ Турчин, Валентин Ф. (1989). «Введение в Рефал». Руководство по программированию и справочное руководство РЕФАЛ-5. Holyoke: New England Publishing Co. Архивировано из оригинал на 2008-07-03. Получено 2010-04-05.
  2. ^ «Архивная копия». Архивировано из оригинал на 2007-12-06. Получено 2008-03-18.CS1 maint: заархивированная копия как заголовок (связь)

внешняя ссылка