- РЕФАЛ
-
РЕФАЛ Семантика: функциональный / сентенциальный
Тип исполнения: зависит от реализации
Появился в: 1966
Автор(ы): Типизация данных: бестиповый
Диалекты: РЕФАЛ-2, РЕФАЛ-5, РЕФАЛ+, РЕФАЛ-0
РЕФАЛ (РЕкурсивных Функций АЛгоритмический) — один из старейших функциональных языков программирования, ориентированный на так называемые «символьные преобразования»: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической ориентацией на написание больших и сложных программ.
Отличительной чертой языка является использование сопоставления с образцом и переписывания термов как основного способа определения функций.
Содержание
Основные принципы
Программа на Рефале может состоять из одного или нескольких модулей (файлов), каждый из которых, в свою очередь, состоит из функций.
Рефал-функция представляет собой упорядоченный набор предложений, состоящих из образца и шаблона. На вход функции подаётся некоторое выражение; вычисление функции состоит в сопоставлении выражения поочерёдно образцам, взятым из первого, второго и т. д. предложений. Если очередное сопоставление проходит успешно, то на основании шаблона, взятого из того же предложения, формируется новое Рефал-выражение, которое и будет результатом функции. В случае, если ни с одним из имеющихся образцов аргумент функции сопоставить не удалось (неуспех), фиксируется ошибка (аварийно завершается вся программа). Во избежание этого часто в конце функции помещают предложение, с образцом которого можно сопоставить вообще произвольное выражение. В некоторых современных реализациях Рефала (например, Рефал+) неуспех любого выражения функции вместо ошибки порождает неуспех самой функции.
Выражения языка Рефал представляют собой последовательности термов, в качестве которых могут выступать:
- обыкновенные символы (буквы, цифры и т. д.), которые в зависимости от диалекта требуется или не требуется заключать в апострофы или кавычки
- символы-метки (идентификаторы, конкретная запись которых варьируется в зависимости от диалекта языка; так, в Рефале-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. Взгляд студента
Основные языки программирования (сравнение • IDE • история • хронология) Используемые
в разработкеАда • APL • Язык ассемблера • ActionScript • ABAP/4 • AutoIt • AWK • Бейсик • Си • Кобол • C++ • C# • Cω • Clarion • Clojure • ColdFusion • Common Lisp • D • dBase • Delphi • Eiffel • Erlang • Euphoria • F# • Форт • Фортран • Gambas • Go • Groovy • HAL/S • Haskell • Icon • Java • JavaScript • Limbo • Lua • Модула-3 • Object Pascal • Objective-C • OCaml • Oz • Parser • Паскаль • Компонентный Паскаль • Perl • PHP • PowerBASIC • Python • ПЛ/1 • Пролог • Ruby • Scala • Scheme • Smalltalk • SQL • PL/SQL • Tcl • Vala • Visual Basic (.NET)
Академические IEC 61131-3 Instruction List • ST • FBD • Ladder Diagram (LD) • SFC
Прочие Эзотерические Визуальные Категории:- Появились в 1966 году
- Языки программирования по алфавиту
- Языки сентенциального программирования
Wikimedia Foundation. 2010.