РЕФАЛ

РЕФАЛ

Семантика:	функциональный / сентенциальный
Тип исполнения:	зависит от реализации
Появился в:	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.
• Смирнов В.К. [library.keldysh.ru/preprint.asp?id=2003-99 Аппаратная реализация языка Рефал в ИПМ им.М.В.Келдыша] (рус.) // Препринты ИПМ им.М.В.Келдыша. — 2003. — № 99. — С. 1-21.
• Гурин Р.Ф., Романенко С.А. Язык программирования Рефал Плюс. — Переславль: Университет города Переславля, 2006. — 13 с. — ISBN 5-901795-08-3.

Ссылки

• [www.refal.net/ Сайт Рефал-сообщества]
• [www.refal.ru/ Содружество «РЕФАЛ/Суперкомпиляция»]
• [wiki.botik.ru/Refaldevel/ wiki-сайт, посвящённый развитию языка]
• [ulm.uni.udm.ru/~soft/wiki/doku.php?id=refal-5:korsa Самостоятельное изучение Рефала-5. Взгляд студента]

Отрывок, характеризующий РЕФАЛ

– Подать письмо, просьбу его величеству, – сказал Николай с дрожанием голоса.
– Просьба – к дежурному, пожалуйте сюда (ему указали на дверь внизу). Только не примут.
Услыхав этот равнодушный голос, Ростов испугался того, что он делал; мысль встретить всякую минуту государя так соблазнительна и оттого так страшна была для него, что он готов был бежать, но камер фурьер, встретивший его, отворил ему дверь в дежурную и Ростов вошел.
Невысокий полный человек лет 30, в белых панталонах, ботфортах и в одной, видно только что надетой, батистовой рубашке, стоял в этой комнате; камердинер застегивал ему сзади шитые шелком прекрасные новые помочи, которые почему то заметил Ростов. Человек этот разговаривал с кем то бывшим в другой комнате.
– Bien faite et la beaute du diable, [Хорошо сложена и красота молодости,] – говорил этот человек и увидав Ростова перестал говорить и нахмурился.
– Что вам угодно? Просьба?…
– Qu'est ce que c'est? [Что это?] – спросил кто то из другой комнаты.
– Encore un petitionnaire, [Еще один проситель,] – отвечал человек в помочах.
– Скажите ему, что после. Сейчас выйдет, надо ехать.
– После, после, завтра. Поздно…
Ростов повернулся и хотел выйти, но человек в помочах остановил его.
– От кого? Вы кто?
– От майора Денисова, – отвечал Ростов.
– Вы кто? офицер?
– Поручик, граф Ростов.
– Какая смелость! По команде подайте. А сами идите, идите… – И он стал надевать подаваемый камердинером мундир.
Ростов вышел опять в сени и заметил, что на крыльце было уже много офицеров и генералов в полной парадной форме, мимо которых ему надо было пройти.
Проклиная свою смелость, замирая от мысли, что всякую минуту он может встретить государя и при нем быть осрамлен и выслан под арест, понимая вполне всю неприличность своего поступка и раскаиваясь в нем, Ростов, опустив глаза, пробирался вон из дома, окруженного толпой блестящей свиты, когда чей то знакомый голос окликнул его и чья то рука остановила его.
– Вы, батюшка, что тут делаете во фраке? – спросил его басистый голос.
Это был кавалерийский генерал, в эту кампанию заслуживший особенную милость государя, бывший начальник дивизии, в которой служил Ростов.
Ростов испуганно начал оправдываться, но увидав добродушно шутливое лицо генерала, отойдя к стороне, взволнованным голосом передал ему всё дело, прося заступиться за известного генералу Денисова. Генерал выслушав Ростова серьезно покачал головой.
– Жалко, жалко молодца; давай письмо.
Едва Ростов успел передать письмо и рассказать всё дело Денисова, как с лестницы застучали быстрые шаги со шпорами и генерал, отойдя от него, подвинулся к крыльцу. Господа свиты государя сбежали с лестницы и пошли к лошадям. Берейтор Эне, тот самый, который был в Аустерлице, подвел лошадь государя, и на лестнице послышался легкий скрип шагов, которые сейчас узнал Ростов. Забыв опасность быть узнанным, Ростов подвинулся с несколькими любопытными из жителей к самому крыльцу и опять, после двух лет, он увидал те же обожаемые им черты, то же лицо, тот же взгляд, ту же походку, то же соединение величия и кротости… И чувство восторга и любви к государю с прежнею силою воскресло в душе Ростова. Государь в Преображенском мундире, в белых лосинах и высоких ботфортах, с звездой, которую не знал Ростов (это была legion d'honneur) [звезда почетного легиона] вышел на крыльцо, держа шляпу под рукой и надевая перчатку. Он остановился, оглядываясь и всё освещая вокруг себя своим взглядом. Кое кому из генералов он сказал несколько слов. Он узнал тоже бывшего начальника дивизии Ростова, улыбнулся ему и подозвал его к себе.
Вся свита отступила, и Ростов видел, как генерал этот что то довольно долго говорил государю.
Государь сказал ему несколько слов и сделал шаг, чтобы подойти к лошади. Опять толпа свиты и толпа улицы, в которой был Ростов, придвинулись к государю. Остановившись у лошади и взявшись рукою за седло, государь обратился к кавалерийскому генералу и сказал громко, очевидно с желанием, чтобы все слышали его.
– Не могу, генерал, и потому не могу, что закон сильнее меня, – сказал государь и занес ногу в стремя. Генерал почтительно наклонил голову, государь сел и поехал галопом по улице. Ростов, не помня себя от восторга, с толпою побежал за ним.


На площади куда поехал государь, стояли лицом к лицу справа батальон преображенцев, слева батальон французской гвардии в медвежьих шапках.
В то время как государь подъезжал к одному флангу баталионов, сделавших на караул, к противоположному флангу подскакивала другая толпа всадников и впереди их Ростов узнал Наполеона. Это не мог быть никто другой. Он ехал галопом в маленькой шляпе, с Андреевской лентой через плечо, в раскрытом над белым камзолом синем мундире, на необыкновенно породистой арабской серой лошади, на малиновом, золотом шитом, чепраке. Подъехав к Александру, он приподнял шляпу и при этом движении кавалерийский глаз Ростова не мог не заметить, что Наполеон дурно и не твердо сидел на лошади. Батальоны закричали: Ура и Vive l'Empereur! [Да здравствует Император!] Наполеон что то сказал Александру. Оба императора слезли с лошадей и взяли друг друга за руки. На лице Наполеона была неприятно притворная улыбка. Александр с ласковым выражением что то говорил ему.
Ростов не спуская глаз, несмотря на топтание лошадьми французских жандармов, осаживавших толпу, следил за каждым движением императора Александра и Бонапарте. Его, как неожиданность, поразило то, что Александр держал себя как равный с Бонапарте, и что Бонапарте совершенно свободно, как будто эта близость с государем естественна и привычна ему, как равный, обращался с русским царем.
Александр и Наполеон с длинным хвостом свиты подошли к правому флангу Преображенского батальона, прямо на толпу, которая стояла тут. Толпа очутилась неожиданно так близко к императорам, что Ростову, стоявшему в передних рядах ее, стало страшно, как бы его не узнали.
– Sire, je vous demande la permission de donner la legion d'honneur au plus brave de vos soldats, [Государь, я прошу у вас позволенья дать орден Почетного легиона храбрейшему из ваших солдат,] – сказал резкий, точный голос, договаривающий каждую букву. Это говорил малый ростом Бонапарте, снизу прямо глядя в глаза Александру. Александр внимательно слушал то, что ему говорили, и наклонив голову, приятно улыбнулся.
– A celui qui s'est le plus vaillament conduit dans cette derieniere guerre, [Тому, кто храбрее всех показал себя во время войны,] – прибавил Наполеон, отчеканивая каждый слог, с возмутительным для Ростова спокойствием и уверенностью оглядывая ряды русских, вытянувшихся перед ним солдат, всё держащих на караул и неподвижно глядящих в лицо своего императора.
– Votre majeste me permettra t elle de demander l'avis du colonel? [Ваше Величество позволит ли мне спросить мнение полковника?] – сказал Александр и сделал несколько поспешных шагов к князю Козловскому, командиру батальона. Бонапарте стал между тем снимать перчатку с белой, маленькой руки и разорвав ее, бросил. Адъютант, сзади торопливо бросившись вперед, поднял ее.
– Кому дать? – не громко, по русски спросил император Александр у Козловского.
– Кому прикажете, ваше величество? – Государь недовольно поморщился и, оглянувшись, сказал:
– Да ведь надобно же отвечать ему.
Козловский с решительным видом оглянулся на ряды и в этом взгляде захватил и Ростова.
«Уж не меня ли?» подумал Ростов.
– Лазарев! – нахмурившись прокомандовал полковник; и первый по ранжиру солдат, Лазарев, бойко вышел вперед.
– Куда же ты? Тут стой! – зашептали голоса на Лазарева, не знавшего куда ему итти. Лазарев остановился, испуганно покосившись на полковника, и лицо его дрогнуло, как это бывает с солдатами, вызываемыми перед фронт.
Наполеон чуть поворотил голову назад и отвел назад свою маленькую пухлую ручку, как будто желая взять что то. Лица его свиты, догадавшись в ту же секунду в чем дело, засуетились, зашептались, передавая что то один другому, и паж, тот самый, которого вчера видел Ростов у Бориса, выбежал вперед и почтительно наклонившись над протянутой рукой и не заставив ее дожидаться ни одной секунды, вложил в нее орден на красной ленте. Наполеон, не глядя, сжал два пальца. Орден очутился между ними. Наполеон подошел к Лазареву, который, выкатывая глаза, упорно продолжал смотреть только на своего государя, и оглянулся на императора Александра, показывая этим, что то, что он делал теперь, он делал для своего союзника. Маленькая белая рука с орденом дотронулась до пуговицы солдата Лазарева. Как будто Наполеон знал, что для того, чтобы навсегда этот солдат был счастлив, награжден и отличен от всех в мире, нужно было только, чтобы его, Наполеонова рука, удостоила дотронуться до груди солдата. Наполеон только прило жил крест к груди Лазарева и, пустив руку, обратился к Александру, как будто он знал, что крест должен прилипнуть к груди Лазарева. Крест действительно прилип.
Русские и французские услужливые руки, мгновенно подхватив крест, прицепили его к мундиру. Лазарев мрачно взглянул на маленького человечка, с белыми руками, который что то сделал над ним, и продолжая неподвижно держать на караул, опять прямо стал глядеть в глаза Александру, как будто он спрашивал Александра: всё ли еще ему стоять, или не прикажут ли ему пройтись теперь, или может быть еще что нибудь сделать? Но ему ничего не приказывали, и он довольно долго оставался в этом неподвижном состоянии.
Государи сели верхами и уехали. Преображенцы, расстроивая ряды, перемешались с французскими гвардейцами и сели за столы, приготовленные для них.
Лазарев сидел на почетном месте; его обнимали, поздравляли и жали ему руки русские и французские офицеры. Толпы офицеров и народа подходили, чтобы только посмотреть на Лазарева. Гул говора русского французского и хохота стоял на площади вокруг столов. Два офицера с раскрасневшимися лицами, веселые и счастливые прошли мимо Ростова.