Рефал

Рефал
Семантика	функциональный / сентенциальный
Класс языка	язык программирования и язык функционального программирования
Тип исполнения	зависит от реализации
Появился в	1966
Автор	Валентин Турчин
Система типов	бестиповый
Диалекты	РЕФАЛ-2, РЕФАЛ-5, РЕФАЛ+, РЕФАЛ-0
Сайт	refal.net

Рефал (акроним от слов «рекурсивных функций алгоритмический») — один из старейших функциональных языков программирования, ориентированный на символьные вычисления: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.

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

Основные принципы

Программа на Рефале может состоять из одного или нескольких модулей (файлов), каждый из которых, в свою очередь, состоит из функций.

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

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

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

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

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

Семантика Рефала описывается в терминах виртуальной машины, называемой «рефал-машина» или «рефал-автомат». Машина имеет «поле зрения», в котором может находиться произвольное рефал-выражение, не содержащее рефал-переменных.

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

Среди предложений, составляющих функцию, находится первое такое, образец которого можно сопоставить с аргументом функции; в ходе сопоставления приписываются значения переменным, содержащимся в образце. Затем шаблон, взятый из того же предложения, берётся за основу для формирования результата вычисления функции; попросту говоря, результатом объявляется выражение, полученное из шаблона заменой переменных на их значения. Шаблон может содержать только переменные, имеющиеся в образце; таким образом, все переменные, входящие в шаблон, окажутся при формировании результата заменены на соответствующие выражения, и результат уже содержать переменные не будет. С другой стороны, шаблон вполне может содержать выражения в угловых скобках.

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

Выполнение программы заканчивается, когда в поле зрения рефал-машины не окажется больше угловых скобок. Выражение, содержащееся в этот момент в поле зрения, объявляется результатом выполнения рефал-программы.

Пример исполнения

Функция:

 Palindrom {
     s.1 e.2 s.1 = <Palindrom e.2>;
     s.1 = True;
     /* пусто */ = True;
     e.1 = False;
 }

анализирует выражение и возвращает в качестве результата символ-метку True, если выражение является палиндромом, и False в противном случае. Функция имеет имя Palindrom. Поясним, что s.1 — это переменная S-типа, e.1 и e.2 — переменные E-типа. Таким образом, тело функции состоит из четырёх предложений, первое из которых сработает, если аргумент функции представляет собой выражение, начинающееся и заканчивающееся одним и тем же символом; второе будет использоваться, если аргумент состоит ровно из одного символа; третье задействуется для пустого аргумента и, наконец, четвёртое подойдёт для всех остальных случаев.

Шаблон в первом предложении содержит активное выражение, представляющее собой рекурсивный вызов функции Palindrom. Это отражает тот факт, что, если первый и последний символы совпали, их можно отбросить и проверить на палиндромичность остаток выражения.

Пусть в поле зрения рефал-автомата оказалось следующее активное выражение:

 <Palindrom 'abcba'>

Тогда выполнение будет состоять из трёх шагов, после которых в поле зрения будут находиться следующие выражения:

 <Palindrom 'bcb'>
 <Palindrom 'c'>
 True

На первых двух шагах использовалось первое предложение, на последнем шаге — второе. Поскольку после третьего шага поле зрения больше не содержит угловых скобок, работа рефал-автомата на этом завершается.

История

Первая версия языка была создана в 1966 году Валентином Турчиным в качестве метаязыка для описания семантики других языков. Впоследствии, в результате появления достаточно эффективных реализаций на ЭВМ, он стал находить практическое использование в качестве языка программирования.

В настоящее время основными диалектами языка являются РЕФАЛ-2 (1970-е), РЕФАЛ-5 (1985) и РЕФАЛ+ (1990), отличающиеся друг от друга деталями синтаксиса и набором «дополнительных средств», расширяющих первоначальный вариант.

Примеры программ

Следующая программа на диалекте Рефал-5 обращает и печатает подаваемую на вход строку данных:

$ENTRY Go
{
     = <Prout <Reverse <Card>>>;
}

Reverse
{
     e.Text = <DoReverse () e.Text>;
}

DoReverse
{
     (e.Scanned) = e.Scanned;
     (e.Scanned) s.Next e.Tail = <DoReverse (s.Next e.Scanned) e.Tail>;
}

Эту же программу можно записать иначе:

$ENTRY Go
{
     = <Prout <Reverse <Card>>>;
}

Reverse
{
     /* Если строка не пустая, то переносим первый символ в конец */
     s.First e.Tail = <Reverse e.Tail> s.First;

     /* Обработка пустой строки */
     /* пусто */ = /* пусто */;
}

Следующая программа на диалекте Рефал-5 получает на входе строку данных, представляющую собой десятичное представление некоторого натурального числа N, после чего вычисляет и печатает число Фибоначчи с номером N:

$ENTRY Go
{
     = <Prout <Symb <FN <Numb <Card>>>>;
}

FN
{
     /* Вызов вспомогательной функции, реализующей остаточно-рекурсивный цикл. */
     s.Number = <DoFN s.Number 0 1>;
}

/*
  Функция реализует остаточно-рекурсивный цикл.
  Инвариант цикла <DoFN s.Counter s.Current s.Next>
  s.Counter -- число оставшихся итераций.
  s.Current -- число Фибоначчи, соответствующее текущей итерации.
  s.Next -- значение числа Фибоначчи на следующией итерации.
*/
DoFN
{
     0 s.Current s.Next = s.Current;
     s.Counter s.Current s.Next =
          <DoFN <Sub s.Counter 1> s.Next <Add s.Current s.Next>>;
}

Литература

• Турчин В. Ф. Алгоритмический язык рекурсивных функций (РЕФАЛ). — М.: ИПМ АН СССР, 1968.
• Романенко С. А., Турчин В. Ф. РЕФАЛ-компилятор // Труды 2-й Всесоюзной конференции по программированию. — Новосибирск: ВЦ СО АН, 1970.
• Романенко С. А. Реализация Рефала-2. — М.: ИПМ АН СССР, 1987.
• Смирнов В. К. Аппаратная реализация языка Рефал в ИПМ им.М.В.Келдыша (рус.) // Препринты ИПМ им. М. В. Келдыша. — 2003. — № 99. — С. 1—21.
• Гурин Р. Ф., Романенко С. А. Язык программирования Рефал Плюс. — Переславль: Университет города Переславля, 2006. — 13 с. — ISBN 5-901795-08-3.

Ссылки

• Сайт Рефал-сообщества
• Содружество «РЕФАЛ/Суперкомпиляция»
• wiki-сайт, посвящённый развитию языка
• Самостоятельное изучение Рефала-5. Взгляд студента