Рекурсивный Функциональный Алгоритмический язык

В конце 60-х годов двадцатого века появилась статья [10] Валентина Федоровича Турчина, в которой он излагал идеи универсального метаязыка программирования, названного им РЕФАЛ. Первая реализация РЕФАЛа появилась в 1968 году. За теоретическую основу В.Ф. Турчиным были взяты алгорифмы Маркова [6] — модель вычислений, разработанная выдающимся русским математиком Андреем Андреевичем Марковым. Насколько мне известно, РЕФАЛ является единственным оригинальным языком программирования широкого применения, разработанным в России. Некоторые замыслы, заложенные в РЕФАЛ, до настоящего времени являются четкими чертами, отличающими его от других функциональных языков программирования. Предлагаемая читателю статья рассчитана на учителей информатики и математики. Излагая основные идеи построения РЕФАЛа, мы попытаемся показать, что этот язык программирования может служить хорошим инструментом развития учеников — снарядом для “гимнастики ума”. Автор также описывает современное состояние реализаций РЕФАЛа, которые могут быть использованы на уроках информатики. Немного жертвуя точностью изложения, мы будем избегать описания излишних технических деталей, которые можно найти в книге В.Ф. Турчина [1]. РЕФАЛ является алгоритмически полным языком, ориентированным на обработку и преобразование текстов. При его разработке В.Ф. Турчин попытался максимально приблизить данные РЕФАЛа к текстам на естественных языках.

Текст, который вы сейчас читаете, представляет собой конечную последовательность букв азбуки, структурированную знаками препинания и пробелами. В РЕФАЛе роль знаков препинания играют круглые скобки (которые также используются и в естественных языках, и которые должны быть сбалансированы). В предыдущем предложении показан пример использования скобок. Таким образом, операция заключения в скобки является элементарной операцией конструирования данных РЕФАЛа.

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

Другая, всеми используемая, операция над текстами настолько естественна, что ее обычно не замечают. Это приписывание одного текста к другому. Если вы остановите свой взгляд на точке, которая завершает данное предложение, то текст статьи будет разделен на две части: перед точкой (включая ее) и после точки. Обе части также являются текстами; вторая часть, которую вы сейчас читаете, приписана к первой части, которую вы уже прочитали. Операция приписывания является второй элементарной операцией построения данных языка РЕФАЛ. Ее существенным отличием от операции заключения в скобки является ассоциативность. Ассоциативность приписывания позволяет опускать скобки самой этой операции и использовать их совершенно в другом смысле, что и делается в РЕФАЛе (как мы уже указали выше). Теперь мы готовы привести несколько простых примеров данных языка РЕФАЛ (сложным примером является весь текст данной статьи; с некоторыми оговорками, которые мы здесь опускаем).

'Эта строка является данным РЕФАЛа, состоящим из 81 логической единицы - символов.'

"Это" "данное" "языка" "РЕФАЛ" "состоит" "из" "десяти" "логических" "единиц" '.'

В первом примере текст '81' с точки зрения РЕФАЛа является двумя текстовыми символами, равноправными со всеми другими символами; то есть с ними нельзя производить арифметических операций. Мы можем разрезать текст из нашего примера на два и приписать второй кусок после первого:

'Эта строка является данным РЕФАЛа, состоящим из ' '81 логической единицы - символов.'

Здесь первый кусок содержит завершающий его пробел, а все вместе никак неразличимо с точки зрения РЕФАЛа от первого примера. Вот еще одно эквивалентное синтаксическое представление того же самого данного:

'Эта строка является данным РЕФАЛа, состоящим из ' '81' ' логической единицы - символов.'

Теперь уже третья часть начинается с пробела (включая его). Попробуем убрать кавычки с ’81’.

Получаем:

'Эта строка является данным РЕФАЛа, состоящим из ' 81 ' логической единицы - символов.'

Это тоже данное РЕФАЛа, но оно отличается от предыдущего тем, что 81 уже является самостоятельной логической единицей — натуральным числом, с которым можно производить арифметические операции. Таким образом, все данное, полученное нами после последнего преобразования, содержит уже не 81, а 80 логических единиц. Чтобы завершить наше введение во множество данных языка РЕФАЛ, необходимо добавить, что пустой текст (не содержащий ни одной логической единицы) также является полноправным данным РЕФАЛа; обозначать его можно либо так ’ ’, либо вообще опуская всякое обозначение (то есть ничем).

1. Системы линейных уравнений над натуральными числами и их обобщение

Вернемся к истокам нашей карьеры. Хотел написать “в первый класс”, но, подумав, решил, что карьера начинается уже в детском саду.

Первый алфавит, с которым мы знакомимся, состоит из одного символа — счетной палочки. Составляя тексты из этих символов, мы учимся считать. Обозначим палочку прописной латинской буквой 'I'. Используя операцию приписывания и знак равенства, можно записать любое линейное уравнение в натуральных числах. Несколько примеров таких уравнений приведены ниже:

x x ' I ' = ' I I I I I '

x ' I ' y = ' I I ' z ' I I I '

x x =

x ' I ' = ' I ' x

Чтобы увидеть, что это действительно линейные уравнения, вспомним, что приписывание палочек является операцией сложения, тогда в более привычных (нетекстовых) обозначениях эти уравнения выглядят так:

2x + 1 = 5

x + 1 + y = 2 + z + 3

2x = 0

x + 1 = 1 + x

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

x y = ' I I I '

x 'I' = ' I I ' y

эквивалентна следующему уравнению:

x y (x ' I ') = ' I I I ' (' I I ' y)

Решением подобных уравнений занимается абстрактная РЕФАЛ-машина при выполнении РЕФАЛ-программы. Чтобы приблизить ситуацию к более реальной, займемся ее обобщением. Первое, что мы сделаем, это раскрасим счетные палочки в разные цвета. В этом случае, приписывая (“складывая”) палочки, мы получим обобщение множества натуральных чисел. Вместо раскраски можно на каждой палочке написать одну из букв азбуки, тогда при сложении — приписывании будут получаться тексты. Если азбука содержит не менее двух букв, то операция сложения уже не обладает свойством коммутативности: при перестановке слагаемых сумма может измениться. Именно по этой причине мы не упрощали вышеприведенные примеры. Теперь мы можем записать следующий пример уравнения:

x 'р' y = 'пример'

Это уравнение имеет два решения: x = 'п', y = 'имер' и x = 'приме', y = ' '. Естественно ввести специальный тип переменных, которые могут принимать в качестве своих значений только логические единицы текста (о которых мы писали выше). Другими словами, переменные, которые бы позволили выделять конкретные одноэлементные последовательности (одноэлементные тексты).

К переменным с таким свойством будем приписывать приставку "s.". Переменные с областью допустимых значений, совпадающей со всем множеством РЕФАЛ-данных, будем предварять приставкой "e.". Например: s.x, e.y.

Уравнение:

s.x 'р' e.y = 'пример'

имеет единственное решение

s.x = 'п', e.y = 'имер'.

Уравнение:

s.x 'р' e.y = "приме" 'р'

тоже имеет единственное решение

s.x = "приме", e.y = ''.

В РЕФАЛе есть еще один тип переменных, который мы рассмотрим далее, в разделе 6.

Линейные уравнения над текстами являются интересным объектом для математических исследований школьников. Эти уравнения могут не иметь решений, могут иметь одно решение, могут иметь конечное множество решений, могут иметь бесконечное множество решений. Перечислим несколько случаев, когда уравнения такого вида решаются просто:

1) все переменные находятся с одной стороны от знака равенства (например, слева);

2) уравнения с одной переменной (которая может входить в уравнение несколько раз);

3) каждая e-переменная входит в уравнение не более двух раз.

2. Рекурсия и математическая индукция

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

Fib {

= 'I';

'I' = 'I';

e.n 'II' = <Fib e.n 'I'> <Fib e.n>;

}

Здесь фигурные скобки указывают границы определения, а имя определения Fib проставлено перед открывающей фигурной скобкой. В РЕФАЛе вызов функции (просьба о вычислении значения функции на конкретных аргументах) синтаксически обозначается угловыми скобками; причем, имя функции ставится после открывающей угловой скобки. Определение Fib состоит из трех предложений. Каждое предложение заканчивается знаком точки с запятой ";" и состоит из левой и правой частей, разделенных знаком равенства.

В первом предложении написано, что нулевой член последовательности Фибоначчи равен единице (число ноль у нас, естественно, представлено отсутствием счетных палочек).

Второе предложение говорит о том, что первый член последовательности Фибоначчи также равен единице.

Третье предложение утверждает, что если номер члена последовательности больше единицы, тогда соответствующий член последовательности вычисляется по правилу, указанному в правой части предложения. То есть нужно вычислить член последовательности с номером на единицу меньше данного и к нему приписать член последовательности с номером на две единицы меньше данного; это и есть индукционный шаг, а первые два предложения отвечают за базис индукции.

Вспоминая, что операция приписывания в унарной системе означает сложение, перепишем данное выше определение в более привычных для читателя математических обозначениях:

Fib(0) = 1;

Fib(1) = 1;

Fib(n + 2) = Fib(n + 1) + Fib(n);

Обсудим, каким образом происходит в РЕФАЛе процесс вычисления четвертого члена последовательности Фибоначчи.

Мы должны попросить абстрактную РЕФАЛ-машину вычислить вызов <Fib 'IIII'>. Далее происходят следующие действия:

1. РЕФАЛ-машина решает уравнение '' = 'IIII', левая часть которого совпадает с левой частью первого предложения определения Fib, а в правой части стоит аргумент вызова <Fib 'IIII'>. Это уравнение противоречиво, что является причиной перехода машины к следующему пункту.

2. РЕФАЛ-машина решает уравнение 'I' = 'IIII', левая часть которого совпадает с левой частью второго предложения определения Fib. Это уравнение также не имеет корней.

3. Переходим к третьему предложению и решаем уравнение e.n 'II' = 'IIII', которое имеет единственное решение e.n = 'II'. Полученное значение переменной e.n подставляем в правую часть этого предложения. Получаем выражение <Fib 'III'> <Fib 'II'>, которое теперь и является целью нашего вычисления.

4. Заменяем начальную цель вычисления <Fib 'IIII'> на <Fib 'III'> <Fib 'II'>. Теперь мы должны вычислить выражение <Fib 'III'> <Fib 'II'>, в которое входят два вызова функции Fib. Выбираем первый из них (слева направо). Далее происходят действия, аналогичные вышеописанным. Будем следить только за преобразованием цели вычислений, опуская процесс решения уравнений.

5. Выражение <Fib 'III'> <Fib 'II'> будет преобразовано к виду <Fib 'II'> <Fib 'I'> <Fib 'II'>.

6. Теперь вычисляется вызов <Fib 'II'>, и выражение <Fib 'II'> <Fib 'I'> <Fib 'II'> будет преобразовано в выражение <Fib 'I'> <Fib ''> <Fib 'I'> <Fib 'II'>. Далее будем шаг за шагом выписывать изменения цели вычислений.

7. 'I' <Fib ''> <Fib 'I'> <Fib 'II'>

8. 'I' 'I' <Fib 'I'> <Fib 'II'>

9. 'II' 'I' <Fib 'II'>

10. 'III' <Fib 'I'> <Fib ''>

11. 'IIII' <Fib ''>

12. 'IIIII'

В последней строчке написан результат вычисления начального вызова <Fib 'IIII'>. Заметим, что в поисках первого непротиворечивого уравнения мы перебирали предложения определения функции Fib сверху вниз. РЕФАЛ-машина всегда перебирает предложения именно по этому правилу, хотя в данном примере порядок перебора предложений несущественен.

Если мы раскрасим палочки в правых частях базисных предложений определения Fib в разные цвета, то получим последовательность, обобщающую последовательность чисел Фибоначчи. Члены обобщенной последовательности называются словами Фибоначчи. Слова Фибоначчи обладают многими интересными свойствами. Можно поставить перед учениками следующую исследовательскую задачу.

Задача 1. Написать на РЕФАЛе программы, которые вычисляют первое слово Фибоначчи (обозначим его f_n), такое, что уравнение

1) e.x s.i e.y s.i e.y e.z = f_n

2) e.x s.i e.y s.i e.y s.i e.y e.z = f_n

3) e.x s.i e.y s.i e.y s.i e.y s.i e.y e.z = f_n

имеет решения.

В последнем случае они обнаружат интересное поведение РЕФАЛ-программы. И это хороший повод попробовать разобраться в проблеме.

Читатель, знакомый с другими широко распространенными функциональными языками программирования (потомками LISPа), уже заметил, что множество данных РЕФАЛа является более выразительным по сравнению с S-выражениями (LISP-списками), которые используются в этих языках. Это свойство РЕФАЛа отражается и в синтаксисе программ, и в стиле мышления при программировании, который стимулируется языком. Наш первый пример уже показывает преимущества РЕФАЛа. Приведем еще несколько важных с этой точки зрения примеров.

Каждый текстовый редактор предоставляет возможность поиска первого вхождения указанной строки в тексте. Следующая простейшая РЕФАЛ-программа решает эту задачу.

Search {

e.string (e.prefix e.string e.text) = e.string e.text;
e.string (e.text) = "Строка не найдена!";

}

Например, результатом следующего вызова

<Search 'про' ('Следующая простейшая

РЕФАЛ-программа решает эту задачу.')>

будет текст: 'простейшая РЕФАЛ-программа решает эту задачу.'

С формальной точки зрения любая программа на РЕФАЛе имеет только один аргумент. Наш пример показывает, как с помощью структурных скобок можно легко проимитировать дополнительные аргументы. Мы просто заключаем эти аргументы в структурные скобки. За этим простым трюком стоит интересный глубокий факт, на который полезно указать ученикам при обсуждении такого, на первый взгляд странного, свойства РЕФАЛа.

Является ли использование структурных скобок, которые не принадлежат (по определению!) алфавиту исследуемого текста, принципиальным для имитации дополнительного аргумента? Можно ли решить эту задачу в рамках алфавита, на котором написан текст? Если алфавит содержит не менее двух разных букв, то ответ положителен. Нужно закодировать исходные текстовые аргументы, продублировав все символы, и на границе аргументов поставить два разных символа. В нашем случае результат кодировки будет следующим:

'ппрроопрССллееддууюющщааяя '

'ппррооссттееййшшааяя РРЕЕФФААЛЛ--'

'ппррооггррааммммаа '

'рреешшааеетт ээттуу ззааддааччуу..'

Здесь каждый отрезок, состоящий из пробелов, содержит ровно два пробела. Теперь легко распознать границу, разделяющую аргументы. Это единственное место, где после символа, стоящего на нечетной позиции, следует символ отличный от него (в нашем примере 'пр').

Для закрепления обсуждаемых понятий хорошим упражнением может быть реализация на РЕФАЛе функций описанной выше кодировки и раскодировки, реализация функции Search без использования структурных скобок. Последнее покажет ученикам удобство использования структурирования текстов посредством скобок.

Вернемся к вычислению вызова

<Search 'про' ('Следующая простейшая '

'РЕФАЛ-программа решает эту задачу.')>

посредством РЕФАЛ-машины. Она решает уравнение:

e.string (e.prefix e.string e.text)

= 'про' ('Следующая простейшая '

'РЕФАЛ-программа решает эту задачу.')

которое имеет два решения:

1) e.string = 'про', e.prefix = 'Следующая ',

e.text = 'стейшая РЕФАЛ-программа решает эту задачу.';

2) e.string = 'про',

e.prefix = 'Следующая простейшая РЕФАЛ-',

e.text = 'грамма решает эту задачу.'.

РЕФАЛ выбирает первое из этих двух решений для подстановки в правую часть первого предложения. Как и требовалось в постановке нашей исходной задачи. Правило выбора конкретного решения из нескольких следующее: переменные в левой части перенумеруем согласно их первым вхождениям (слева направо). В нашем случае e.string получит номер 1, e.prefix — номер 2, e.text — номер 3. Тогда из всех возможных решений выбираются те решения, длина значений первой переменной в которых самая маленькая. Если таких решений несколько, то выбираем из них те, длина значений второй переменной в которых самая маленькая, — и так далее, пока не получим одно решение.

Заметим, что в этом примере нельзя переставить порядок предложений в программе Search. Если мы их переставим, то значением программы всегда будет "Строка не найдена!" — независимо от ее аргументов.

Следующая программа переворачивает свой аргумент, — ее результат нужно читать справа налево.

Reverse {
= ;
s.x e.y = <Reverse e.y> s.x;
}

Здесь стоит обратить внимание на первое предложение, которое говорит о том, что результат переворачивания пустого текста есть пустой текст. Второе предложение осуществляет шаг индукции по длине текста,
а первое представляет собой базис индукции.

Вот два примера вычисления этой программы:

<Reverse 'перевернуть'> = 'ьтунревереп'

<Reverse "пере" "вернуть"> = "вернуть" "пере"

3. Арифметика

Целочисленная арифметика в РЕФАЛе является точной. Другими словами, ограничение на разрядность (длину) целых чисел отсутствует. Представление целых чисел зависит от конкретного диалекта РЕФАЛа. Представление целых чисел, используемое в РЕФАЛе-5, является хорошим поводом для обсуждения с учениками (или для закрепления) понятий, связанных с различными системами счисления.

Целые числа в РЕФАЛе-5 представляются в системе счисления по основанию 2³². Целое число, по определению, принадлежит области допустимых значений s-переменной тогда и только тогда, когда оно является цифрой в этой системе счисления. Чтобы избежать путаницы с десятичными цифрами, мы будем называть цифры в системе счисления по основанию 2³² макроцифрами.

Как и в десятичной системе счисления, произвольное натуральное число есть последовательность макроцифр. Например,

2³² = 1 0

2³² – 1 = 4294967295

Заметим, что '1' ≠ 1 и '4294967295' ≠ 4294967295.

Отрицательные числа начинаются с символа '–'. Например,

–(232 + 1) = ’–’ 1 1 .

Аналогично разрешается приписывать символ ’+’ перед неотрицательным числом.

Некоторые функции существуют в РЕФАЛ-машине изначально (то есть их не нужно программировать) — они называются встроенными.

Все встроенные функции арифметики целых чисел (сложение — Add (или +), вычитание — Sub (или –), умножение — Mul (или *), деление — Div (или /), деление с остатком — Divmod, остаток от деления — Mod, сравнение — Compare) логически имеют два аргумента, первый из которых заключен в структурные скобки. Например,

<Add (1 0) 1> = 1 1

Результат деления с остатком есть пара:

<Divmod (e.n) e.m> = (e.q) e.r

— где e.n = e.q*e.m + e.r, 0 Ј |e.r| < |e.m| и знак остатка e.r совпадает со знаком делимого e.n.

Функция сравнения двух целых чисел Compare возвращает ’+’, если первое больше второго, ’–’, если первое меньше второго, и ’0’, если числа равны.

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

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

FIB {

0 = 1;

1 = 1;

e.n = <Add (<FIB <Sub (e.n) 1>)

<FIB <Sub (e.n) 2>>>;

}

Здесь мы впервые использовали композицию функций. Школьникам можно предложить, например, следующие задачи. (См. также [7].)

Задача 2. Дана последовательность цифр натурального числа n, данного в системе счисления по основанию 232. Построить последовательность цифр числа n в десятичной системе счисления.

Задача 3. Реализовать на РЕФАЛе алгоритм умножения столбиком двух натуральных чисел, данных в системе счисления по основанию 232. Встроенные функции разрешается использовать только тогда, когда их аргументы являются макроцифрами.

4. Функциональность

РЕФАЛ принадлежит к классу функциональных языков программирования.

Язык программирования L называется функциональным, если любая программа P, написанная на языке L, является определением некоторой функции из области определения программы P в множество данных языка L.

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

Причина состоит в том, что в реальных языках программирования всегда существуют программы с побочными действиями. И без таких программ мы не сможем узнать, что же вычислил компьютер, и вычислил ли вообще что-нибудь.

Среди реальных (не чисто теоретических) языков программирования функциональными принято называть те языки, в которых число выразительных синтаксических средств, позволяющих конструировать программы с побочными действиями, сведено до минимума. Типичным свойством функционального языка программирования является отсутствие в нем глобальных переменных.

Рассмотренные нами выше примеры программ являются чисто теоретическими; в том смысле, что вычислительная машина не покажет результат их вычисления. Чтобы превратить эти программы в практические, нам нужна встроенная процедура печати (или, другими словами, процедура вывода результата вычислений на экран). В РЕФАЛе-5 она называется Prout.

Кроме того, внимательный читатель заметил, что мы не ввели также и синтаксис постановки задачи на вычисление. Мы объяснили, как определять функции на РЕФАЛе, но целевые выражения (задачи на вычисления) описывали неформально. Начальная точка вычислений в РЕФАЛе называется Go и предваряется ключевым словом $ENTRY. Она и используется для описания вычислительной задачи. Для того чтобы получить на экране значение 5-го члена последовательности Фибоначчи, мы должны добавить к описанию последнего нашего примера следующую синтаксическую конструкцию:

$ENTRY Go {

= <Prout <fib 5>>;

}

5. Игры с текстами

РЕФАЛ ориентирован на преобразование текстов. Какие тексты являются простыми, а какие сложными? Классическое рифмованное стихотворение выучить наизусть намного проще, чем белый стих. Кроме того, понятие сложности текста T зависит от нашего понимания T. Запоминание доказательства теоремы при подготовке к экзамену является делом безнадежным, когда школьник не понимает этого доказательства; в то же время, если доказательство понято, то оно легко восстанавливается, исходя из логики взаимозависимости его шагов. А.Н. Колмогоров предложил аппроксимировать понятие взаимозависимости частей данного текста посредством рекурсии.

Со сложностью текстов связано много интересных задач, которые могут увлечь ваших учеников при освоении РЕФАЛа.

Например, можно устроить соревнование по реализации на РЕФАЛе самой короткой программы, которая печатает русские народные сказки “Репка” и “Колобок” (возможно, вы знаете еще какие-то сказки с четко выраженным рекурсивным изложением).

Благородной задачей приобщения молодых людей к поэзии может быть предложение написать программу, определяющую, является ли данное стихотворение венком сонетов.

Венок сонетов состоит из 15 стихотворений, где последняя строка каждого из 14 сонетов является началом следующего сонета. Последний сонет воспроизводит первые строки всех 14 предыдущих сонетов. Венки сонетов можно найти, например, в сборни-
ках стихотворений В.Я. Брюсова, Вяч. И. Иванова,
В.А. Солоухина. В том числе и на страницах электронной сети (см. [9]).

Для решения этих задач вам понадобятся встроенные процедуры ввода/вывода, работающие с файлами. В разных диалектах РЕФАЛа они реализованы по-разному. Их описание можно найти в документации выбранного вами диалекта.

6. Еще один тип переменных

Выше мы ввели "s." и "e." переменные языка РЕФАЛ. В РЕФАЛе есть еще один тип переменных, который позволяет удобно работать со структурными скобками. Вернемся к определенной нами функции Reverse (см. раздел 2).

Если мы попытаемся вычислить значение этой функции на аргументе, содержащем структурные скобки, то РЕФАЛ-машина закончит свою работу в аварийном состоянии. Например, при попытке вычислить такой вызов: <Reverse 'ab' ('cd') 'ijk'>. Причина перехода в аварийное состояние состоит в том, что оба следующие уравнения

                  = ('cd') 'ijk'
s.x e.y = ('cd') 'ijk'

которые будет решать РЕФАЛ-машина (на некотором шаге ее работы), не имеют решения. Функция Reverse не определена на аргументе 'ab' ('cd') 'ijk'.

Сейчас мы дадим два варианта доопределения функции Reverse на все множество РЕФАЛ-данных. В первом случае наша программа ReverseT не будет переворачивать содержимое структурированных частей текста, считая каждую из них за единое целое (в этом и смысл структуризации!). Для этого нам понадобятся t-переменные, область допустимых значений которых содержит в себе область допустимых значений s-переменной, и, кроме того, t-переменная может принимать в качестве своего значения любое данное РЕФАЛа, заключенное в структурные скобки (включая эти скобки).

ReverseT {

= ;

t.x e.y = <ReverseT e.y> t.x;

}

Теперь можно вычислить вызов

<ReverseT 'ab' ('cd') 'ijk'> = 'kji' ('cd') 'ba'.

t-переменные введены в РЕФАЛ для удобства программирования; с логической точки зрения можно обойтись без них. Прежде чем продолжить читать эту статью, читателю предлагается реализовать функцию ReverseT, не используя в программе t-переменных. Если не получится, то следующая программа в нашей статье послужит для вас подсказкой.

Если все же нам необходимо перевернуть все логические единицы (то есть не структурные скобки), то мы должны написать программу, которая заходит внутрь структурных скобок:

ReverseAll {

= ;

s.x e.y = <ReverseAll e.y> s.x;

(e.x) e.y = <ReverseAll e.y> (<ReverseAll e.x>);

}

В этом случае результат вычислений получится следующим:

<ReverseAll 'ab' ('cd') 'ijk'> = 'kji' ('dc') 'ba'

Еще один пример вычисления:

<ReverseAll "ab" ('cd') "ijk"> = "ijk" ('dc') "ab"

7. О некоторых реализациях РЕФАЛа

На данный момент существуют реализации нескольких диалектов РЕФАЛа; синтаксис рассмотренных нами примеров может незначительно отличаться от диалекта к диалекту. Заинтересованный читатель без труда разберется в этих различиях. Опишем текущее состояние реализаций двух диалектов. Здесь мы вынуждены пользоваться некоторыми техническими терминами, не объясняя их.

Реализация РЕФАЛа-5 (автор диалекта В.Ф. Турчин) представляет собой полуинтерпретатор: РЕФАЛ-программа компилируется в некоторый промежуточный язык и далее результат компиляции интерпретируется. На электронной странице РЕФАЛа-5 [11] свободно распространяются исполняемые модули компилятора и интерпретатора, которые могут исполняться под современными версиями операционной системы Windows. Исходные тексты реализации также можно найти на этой странице. Вместе с исходными текстами свободно распространяются и make-файлы, с помощью которых можно собрать исполняемые модули под различными вариантами операционной системы Linux, под операционной системой FreeBSD, а также под некоторыми другими системами. Кроме того, со страницы [11] можно скопировать еще один компилятор РЕФАЛа-5 [5], который выдает более подробную информацию об ошибках, что немаловажно для начинающего пользователя РЕФАЛа.

К достоинствам этой реализации следует отнести компактность, простоту установки, наличие пошагового отладчика программ, который имеет большое значение для освоения РЕФАЛа. Ученик может просматривать результат исполнения каждого шага РЕФАЛ-машины. Недостатком является отсутствие поддержки внутреннего оконного интерфейса; то есть программы исполняются из командной строки операционной системы, и пользователь должен редактировать программы посредством редакторов общего назначения, не ориентированных на синтаксис РЕФАЛа.

Документацией к данной реализации является книга В.Ф. Турчина на английском языке [1]. На странице [11] можно читать эту книгу, находясь в сети, либо скопировать архив на ваш компьютер. В online-версии книги вы можете исполнять (и изменять) РЕФАЛ-программы прямо в Интернете — по ходу чтения книги. Например, при первом знакомстве с языком — еще до установки реализации на вашем компьютере.

На странице [1] имеется русский перевод устаревшей версии книги В.Ф. Турчина. Она также может оказаться очень полезной для первого знакомства с РЕФАЛом-5.
В этой версии книги используется устаревший синтаксис РЕФАЛа-5.

Реализация диалекта РЕФАЛ+ (автор диалекта
С.А. Романенко) представлена в двух вариантах: 1) компилятор в язык программирования C++, 2) компилятор в язык программирования Java (оба компилятора свободно распространяются [2]). Далее пользователю необходимо использовать компиляторы C++ или Java, соответственно. Инструкцию по установке компиляторов под операционными системами Windows и Linux можно найти, двигаясь по ссылкам с электронной страницы [2].

Существует интегрированная среда разработки РЕФАЛ+ программ, работающая в системе Eclipse [13] и включающая в себя: редактор программ, ориентированный на синтаксис РЕФАЛа; анализатор программ, сообщающий об ошибках; возможность исполнения программ из среды; поддержку просмотра документации по языку РЕФАЛ+ на английском языке. Эта среда использует компилятор РЕФАЛа+ в язык Java.

Существование интегрированной среды поддержки следует, несомненно, отнести к достоинствам реализации РЕФАЛа+. К недостаткам следует отнести относительную сложность установки и освоения этой реализации, а также большой размер ресурсов, который требуется для установки и работы этой реализации.

Документацией по диалекту РЕФАЛа+ является русскоязычная книга Р.Ф. Гурина, С.А. Романенко, доступная на электронной странице [3].

8. Обзор литературы

Нижеприводимый список литературы не претендует на полноту. Мы перечислили лишь широкодоступные работы. К сожалению, классические тексты В.Ф. Турчина являются, с одной стороны, раритетами (например, отмеченная нами статья [10]); с другой стороны, с 70-х годов синтаксис РЕФАЛа прошел серьезную эволюцию, — и для начинающего пользователя попытка распознать в этих работах современный РЕФАЛ превратится в серьезную задачу.

Монография В.Ф. Турчина [1], упоминавшаяся нами выше, написана неформальным языком. Книга содержит много упражнений, которые можно использовать на уроках информатики. Книга Р.Ф. Гурина и С.А. Романенко [3] представляет собой формальное описание РЕФАЛа+ и может оказаться сложной для первого знакомства с предметом. Доступная в Интернете версия этой книги также не полностью соответствует современному состоянию диалекта РЕФАЛ+.

С нашей точки зрения, книги В.Ф. Турчина, Р.Ф. Гурина и С.А. Романенко являются взаимодополняющими.

Мы настоятельно рекомендуем работу А.В. Корлюкова [4]. Он дал увлекательное введение в РЕФАЛ посредством программирования алгоритмов классической алгебры, доступной для понимания хорошими школьниками.

Много упражнений по языку РЕФАЛ можно найти в записках лекций А.П. Немытых [7]. Подробная документация на русском языке по языку FLAC (диалекту РЕФАЛа, ориентированному на компьютерную алгебру) размещена на электронной странице [12].

Список литературы

1. Turchin V.F. Refal-5. Programming Guide and Reference Manual, Holyoke, Massachusetts, New England Publishing Co., 1989. По адресу http://www.botik.ru/pub/local/scp/refal5/   доступна электронная версия книги (2000). По адресу http://www.refal.org/rf5_frm.htm   доступен русский перевод устаревшей версии книги.

2. Гурин Р.Ф., Климов Ю.А., Орлов А.Ю., Романенко С.А. // РЕФАЛ+: исполняемые модули и исходные тексты. http://rfp.botik.ru/ .

3. Гурин Р.Ф., Романенко С.А. Язык программирования РЕФАЛ ПЛЮС. М.: ИНТЕРТЕХ, 1991 (электронная версия доступна на странице http://www.refal.net/doc_ref_plus.html ).

4. Корлюков А.В. // Введение в программирование на языке РЕФАЛ с приложениями в алгебре, 2001. http://www.refal.net/~korlukov/refbook/index.htm .

5. Гао Кси, Немытых А.П. // CREFAL: компилятор РЕФАЛа-5 в язык сборки, 2004. http://www.botik.ru/pub/local/scp/refal5/ .

6. Марков А.А., Нагорный Н.М. Теория алгорифмов. Изд. 2-е (Завод 2), испр. и доп. М.: УРСС, 2001.

7. Немытых А.П. // Лекции по языку программирования РЕФАЛ (черновик), 2006. http://www.botik.ru/pub/local/scp/ugp/seminars.html .

8. Семенов А.Л. Математика текстов. М.: МЦНМО, 2002.

9. Солоухин В.А. Венок сонетов. http://botik.ru/pub/local/scp/ugp/venok.html.

10. Турчин В.Ф. Метаязык для формального описания алгоритмических языков. // В сборнике: Цифровая вычислительная техника и программирование. М.: Советское радио, 1966, с. 116–119.

11. Турчин В.Ф., Турчин Д.В., Конышев А.П., Немытых А.П. РЕФАЛ-5: исполняемые модули и исходные тексты. http://www.botik.ru/pub/local/scp/refal5/   (2000) .

12. Функциональный язык для алгебраических вычислений FLAC. // Сборник статей под ред. А.П. Немытых. http://botik.ru/pub/local/scp/flac/flac.pdf   (1988).

13. Eclipse: открытая расширяемая среда для построения инструментов, облегчающих разработку, распространение и сопровождение программного кода. http://www.eclipse.org/.