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

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

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

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

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

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

• обыкновенные символы (буквы, цифры, некоторые спецсимволы), которые в зависимости от диалекта требуется или не требуется заключать в апострофы или кавычки;
• символы-метки (идентификаторы, конкретная запись которых варьируется в зависимости от диалекта языка; так, в Рефале-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 году Валентином Турчиным в качестве метаязыка для описания семантики других языков. Впоследствии, в результате появления достаточно эффективных реализаций на ЭВМ, он стал находить практическое использование в качестве языка программирования ^{[ источник не указан 3056 дней ]} .

В настоящее время основными диалектами языка являются РЕФАЛ-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 .

Ссылки