Рефал
Рефал (акроним от слов «рекурсивных функций алгоритмический») — один из старейших функциональных языков программирования, ориентированный на символьные вычисления: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.
Рефал | |
---|---|
Семантика | функциональный / сентенциальный |
Класс языка | язык программирования и язык функционального программирования |
Тип исполнения | зависит от реализации |
Появился в | 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 году Валентином Турчиным в качестве метаязыка для описания семантики других языков. Впоследствии, в результате появления достаточно эффективных реализаций на ЭВМ, он стал находить практическое использование в качестве языка программирования[источник не указан 3393 дня].
В настоящее время основными диалектами языка являются РЕФАЛ-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. Взгляд студента