Зырить аржан for Рефал

{{YouTube|6Y5q_oHQ0A4|width=300|height=250}}

== Общие сведения ==
Рефал — это один из старейших функциональных языков программирования, исторически считающийся первым известным языком программирования, разработанным в России (СССР). Язык принципиально ориентирован на обработку символьных строк, манипулирование абстрактными структурами данных и решение специфических задач в области искусственного интеллекта (в понимании вычислительной логики и символьной обработки того времени). В основе вычислительной парадигмы языка лежит глубокое использование рекурсии и механизмов сопоставления с образцом (pattern matching).

== История создания и развитие ==
Концепция языка была разработана советским ученым Валентином Турчиным в 1966 году. Первоначально Рефал проектировался не просто как язык для написания прикладных программ, а как универсальный метаязык, предназначенный для формального описания и алгоритмической трансляции других языков программирования (например, для формализации алгоритмов трансляции с языков Фортран или Алгол). 

Первая эффективно работающая программная имплементация языка появилась в 1968 году, что ставит Рефал в один хронологический ряд с важнейшими историческими разработками конца 1960-х годов (наряду с языками Лого и Симула). После появления первых успешных компиляторов язык начал активно использоваться в академической среде СССР как инструмент программирования. 

В процессе своей эволюции язык прошел через несколько этапов стандартизации и развития диалектов:
В 1970-е годы наибольшее распространение получил диалект Рефал-2.
В 1985 году была выпущена версия Рефал-5.
В 1990 году появился расширенный стандарт Рефал Плюс.

== Архитектура и методология вычислений ==
Выполнение программы на языке Рефал концептуально описывается как работа абстрактного «Рефал-автомата». Данная вычислительная машина обладает так называемым «полем зрения», в котором она рассматривает и обрабатывает текущее Рефал-выражение.

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

== Синтаксис и типы данных ==
Базовой единицей информации в языке является выражение, которое представляет собой последовательность элементов, называемых термами. В качестве термов в Рефале могут выступать:
Обыкновенные символы.
Символы-метки (например, логические маркеры истины и лжи).
Макроцифры (представляющие собой цифровую запись неотрицательных целых чисел).
Числа с плавающей точкой.
Рефал-переменные различных типов.
Произвольные выражения, заключенные в круглые (структурные) скобки.
Произвольные выражения, заключенные в угловые скобки (вызовы функций).

В языке реализована строгая классификация переменных. Существует три предопределенных типа Рефал-переменных, которые используются при сопоставлении с образцом:
S-переменная (symbol) — переменная, способная принимать значение ровно одного символа (или любого простого терма, за исключением выражений, сгруппированных в структурные скобки).
T-переменная (term) — переменная, соответствующая ровно одному любому терму.
E-переменная (expression) — универсальная переменная, способная вмещать в себя в принципе любое выражение, то есть произвольную последовательность любых термов любой длины (включая пустую последовательность).

== Структура функций и сопоставление с образцом ==
Функция в Рефале структурно представляет собой упорядоченный набор предложений (правил вывода). Каждое предложение состоит из левой части (образца или шаблона) и правой части (результирующего блока).

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

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

== Примеры алгоритмов: Палиндром ==
Классическим примером, демонстрирующим декларативную и рекурсивную мощь языка, является алгоритм проверки слова на палиндром. Функция получает на вход произвольную последовательность символов и возвращает метку True (истина), если выражение является палиндромом, и False (ложь) в противном случае.

Алгоритм функции состоит из четырех последовательных логических предложений:
Первое предложение проверяет краевые символы. В образце указывается, что если выражение начинается с S-переменной (например, s1), затем следует E-переменная (e2, представляющая произвольную середину), и заканчивается той же самой S-переменной (s1), то первый и последний символы совпадают. В этом случае функция отбрасывает крайние символы и вызывает саму себя (рекурсивно, в угловых скобках) для оставшейся центральной части e2.
Второе предложение перехватывает ситуацию, когда в выражении остался всего один символ (S-переменная). Один символ всегда является палиндромом самого себя, поэтому функция возвращает True.
Третье предложение срабатывает, если на вход передано абсолютно пустое выражение (все символы успешно попарно сократились). В этом случае также возвращается метка True.
Четвертое предложение является завершающим (общим). Если выражение не подпадает ни под одно из предыдущих правил (то есть первый и последний символы различны), шаблон перехватывает его через E-переменную и возвращает метку False.

Концептуальная структура данного алгоритма:
<pre>
  Палиндром {
    s1 e2 s1 = <Палиндром e2>;
    s1 = True;
       = True;
    e1 = False;
  }
</pre>
В процессе рекурсивного выполнения этой функции автомат будет последовательно «обрезать» крайние символы, пока не останется один символ или пустое место (результат True), либо пока не обнаружится несовпадение краев (результат False). Подобный рекурсивный подход позволяет лаконично реализовывать сложнейшие математические и символьные алгоритмы (в том числе вычисление чисел Фибоначчи и синтаксический анализ).

== См. также ==
[[Short Code]]
[[Учебный алгоритмический язык]]

[[Category:Языки программирования]]

[https://www.youtube.com/watch?v=6Y5q_oHQ0A4 Смотреть видео]