РЕФАЛ

а л г о р и т м и ч е с к и й я з ы к р ек у р с и в н ы х ф у н к ц и й,- алгоритмический язык, ориентированный на задачи преобразования символьной информации; в первоначальном варианте назывался "метаалгоритмическим языком" (см. |1]). Р. был создан как универсальный метаязык для описания преобразований языковых объектов. Он используется для трансляции с одного алгоритмич. языка на другой, для машинного выполнения аналитич. выкладок, доказательства теорем, перевода с естественных языков и т. п. Запись алгоритма на Р. представляет описание нек-рого числа рекурсивных функций на множестве выражений (т. изображается на Р. в виде , где - з н а к к о н к р е т и з а ц и и, служащий для явного указания на необходимость вычисления значения функции, а символ означает закрывающую скобку для Описание функции распадается на несколько предложений (п р а в и л к о н к р е т и з а ц и и), относящихся к случаям, когда аргумент имеет тот или иной частный вид. Напр., функция сложения в рекурсивной арифметике описывается на Р. двумя предложениями:

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

Для реализации программ на Р. разработаны эффективные трансляторы (см. [3], [4]; пример использования Р. для машинного выполнения выкладок в теоретич. физике см. в [5]).

Лит.:[1] Т у рч и н В. Ф., "Кибернетика", 1968, № 4, с. 45-54; [2] Т у р ч и н В. Ф., С е р д о б о л ь с к и й В. И., "Кибернетика", 1969, № 3, с. 58-62; [3] Ф л о р е н ц е в С. Н., О л ю н и н В. Ю., Т у р ч и н В. Ф., "Тр. 1 Всесоюзн. конференции по программированию", К., 1968, с. 114 - 33; [4] Романенко С. А., Т у р ч и н В. Ф., "Тр. 2-й Всесоюзн. конференции по программированию", Нивосиб., 1970, с. 31-42; [5] Б у д н и к А. П. [и др.], "Ядерная физика", 1971, т. 14, с. 304 - 13. В. Ф. Турчин.