Этот раздел представляет собой неформальное введение в Рефал-5λ, учебник, доступный для новичка, даже для новичка в программировании. Более строго и формально язык будет рассмотрен в следующем разделе (справочник).
Термином Базисный Рефал принято называть семантическое подмножество Рефала, в котором предложения функций состоят только из двух частей, переменные могут иметь тип s-, t- или e- (нет, например, спецификаторов РЕФАЛа-2 [7]) и типы символов (symbol) включают в себя только литеральные символы (characters), числа и слова.
Подмножество Базисного Рефала семантическое. Это значит, что конкретная синтаксическая форма рассмотренных конструкций может сильно отличаться в разных диалектах и реализациях (например, синтаксис РЕФАЛа-2 [7] совсем не похож на синтаксис Рефала-5λ), но перечисленные выразительные средства в языке существуют.
В предыдущей части нам удалось откомпилировать и запустить
программу hello.ref, которая распечатала строчку «Hello, World!».
Давайте теперь научимся читать и понимать её исходный код.
$ENTRY Go { /* 1 */
/* empty */ = <Prout 'Hello, World!'>; /* 2 */
} /* 3 */
Внимательные читатели заметили отличия от программы в предыдущей главе:
добавились строчки, начинающиеся на /* и заканчивающиеся на */.
Это комментарии — любой текст между /* и */ компилятором игнорируется
и используется для пояснения смысла программы читающему её программисту.
В эту программу были добавлены комментарии, просто нумерующие строки
(для удобства ссылки на них из текста руководства) и слово /* empty */,
обращающее внимание читателя на то, что в этом месте программы ничего нет.
Да, звучит на первый взгляд странно, но вскоре всё станет понятнее.
Комментарии, ограниченные знаками /* и */, являются многострочными,
т.е. */ не обязана находиться в той же строке, что и предшествующая ей /*.
Помимо многострочных комментариев также допустимы однострочные — любая
строка, начинающаяся со знака (в первой колонке) *, игнорируется
компилятором.
Например, следующая программа полностью идентична предыдущей, только замусорена большим количеством бесполезных комментариев.
/*
Ньютонометр безусловно не зависит от скорости вращения внутреннего
кольца подвеса, что не кажется странным, если вспомнить о том,
что мы не исключили из рассмотрения периодический кожух.
*/
$ENTRY Go { /* 1 */
* Проекция на подвижные оси, несмотря на некоторую погрешность,
* относительно не зависит от скорости вращения внутреннего кольца
* подвеса, что не кажется странным, если вспомнить о том, что мы
* не исключили из рассмотрения штопор.
/* empty */ = <Prout 'Hello, World!'>; /* 2 */
} /* 3 */
* Источник текста комментариев:
/* https://yandex.ru/referats/?t=gyroscope&s=34928 */
Но вернёмся к нашей функции.
$ENTRY Go { /* 1 */
/* empty */ = <Prout 'Hello, World!'>; /* 2 */
} /* 3 */
Любая программа на Рефале-5λ представляет собой набор функций (язык ведь
функционального программирования всё-таки). И эта программа не исключение.
Здесь определена функция Go. Определение функции записывается как имя
функции, за которым следует блок — тело функции, ограниченное фигурными
скобками (в строках 1 и 3 соответственно). Имя Go неслучайно: любая
программа на Рефале должна содержать единственное определение функции с именем
Go либо GO — процесс выполнения программы есть вычисление функции Go
(или GO) с пустым аргументом.
Непонятное $ENTRY перед именем функции будет прояснено в следующих разделах,
сейчас нам достаточно знать, что ключевое слово $ENTRY обязано предварять
точку входа (entry point) Go или GO в программу.
В строке 2 находится единственное предложение функции Go. Предложение —
это правило, определяющее, как построить значение функции на некотором
подмножестве её аргументов. Функция в общем случае может состоять из нескольких
предложений, каждое из которых завершается знаком ; (точкой с запятой). Точка
с запятой в конце последнего предложения может не ставиться.
Любое предложение состоит из двух частей — левой части, образца, описывающей
подмножество значений аргумента функции, на котором это предложение применимо,
и правой части, результата, описывающей значение функции на этом подмножестве.
Левая и правая части разделяются знаком = (равенства).
Примечание. В дальнейшем будет рассматриваться расширенный синтаксис Рефала, в котором синтаксис предложения будет уже сложнее.
В программе hello.ref единственное предложение говорит о том, что оно
применимо только для пустого аргумента функции (перед равенством ничего
не записано), комментарий /* empty */ подчёркивает этот факт. Правая часть
описывает значение функции Go с пустым аргументом как результат вычисления
функции Prout, которому в качестве аргумента передаётся последовательность
знаков Hello, World!. Вызовы функций на Рефале, в отличие от математической
нотации, оформляются при помощи угловых скобок < и > (знаков «меньше»
и «больше»), при этом имя функции пишется не перед открывающей скобкой, а после
неё.
Функция Prout при любом своём аргументе вычисляет «пустоту», однако её
выполнение имеет побочный эффект — она распечатывает свой аргумент на экране.
Очевидно, ради этого побочного эффекта её и вызывают.
На самом деле, практически все программы на Рефале пишутся ради побочных
эффектов. После завершения вычисления функции Go (или GO), её результат
отбрасывается, и программа завершается. Пользователю достаётся лишь то, что
было выведено на экран функциями типа Prout, записано в файлы, либо передано
«наружу» из процесса вычислений иным путём.
Примечание. Есть исключения из этого правила. Во-первых, это автоматизированные тесты (автотесты) — программы, которые запускают тестируемую функцию, проверяют её результат и завершаются. При успешной проверке программа молча завершается, при неуспешной — аварийно вылетает с ошибкой. Среда запуска тестов умеет различать эти два случая и сообщает пользователю о подобных неуспешных запусках. Другой пример — исследования в области автоматического преобразования и верификации программ, например, при помощи суперкомпиляции. В этом случае пишется какая-нибудь математически интересная функция на Рефале, скармливается инструментальному средству, например, суперкомпилятору РЕФАЛа-5 SCP4 ([1], [2], [3]), после чего изучается результат преобразования или анализа этой функции. Собственно, исследования в области разработки подобных инструментальных средств — это одно из основных применений Рефала на сегодня.
Функция Prout — это одна из функций, входящих в стандартную библиотеку языка,
и по умолчанию неявно доступна к использованию в любой программе. В классическом
РЕФАЛе-5 она является встроенной, т.е. определённой неявно всегда в любой
программе. Рефал-5λ, однако, позволяет писать программы, в которых
не используется стандартная библиотека.
hello.refДавайте подытожим, что мы к этому моменту узнали.
*, а остальные могут быть любыми./*
и заканчивается знаками */.Go или GO
с пустым аргументом.$ENTRY./* empty */ или /* пусто */.'Hello, World!'.F с некоторым аргументом arg записывается как <F arg>.Выполнение программы является вычислением функции Go с пустым аргументом,
вызов функции оформляется при помощи угловых скобок, пустое значение
записывается пустым местом. Значит, правомерно будет записать, что выполнение
программы на Рефале эквивалентно вызову функции <Go> или <Go /*empty*/>.
В первом случае мы между именем функции Go и закрывающей скобкой > мы
не написали ничего (приписали вплотную одно к другому). Во втором случае
для наглядности воткнули комментарий. Обычно вызов функции с пустым аргументом
пишут без комментария внутри.
Прежде чем перейти к рассмотрению других примеров, нужно дать пояснения
по синтаксису, не отражённые в листинге hello.ref.
Во-первых, Рефал — язык со свободным синтаксисом. В нём переход на новую строку — точно такой же пробельный символ, как и пробел или табуляция. Пара исключений — открывающая и закрывающая кавычки должны располагаться в одной строке (разрыв строки не может располагаться внутри последовательности символов) и символ перевода строки завершает однострочный комментарий по определению.
Во-вторых, каждый из знаков внутри одинарных кавычек является самостоятельным,
следующие записи эквивалентны: 'Hello', 'Hel' 'lo', 'H' 'e' 'l' 'l' 'o'.
В-третьих, именем функции может быть любая последовательность букв, цифр,
знаков _ («прочерк») и - («дефис»), начинающаяся с прочерка или буквы.
Например, Go, Hello, A-plus-B, _remove_file, ANSWER_42. Строчные
и прописные буквы различаются, т.е. имена hello, Hello и HELLO различные.
Примечание. Классическая реализация РЕФАЛа-5 не поддерживает имена, которые начинаются на прочерк.
Пример 1. Напишем функцию, которая складывает две двоичные цифры.
BinAdd {
'0' '0' = '0';
'0' '1' = '1';
'1' '0' = <BinAdd '0' '1'>;
'1' '1' = '10';
}
Левые части предложений можно было записать и слитно, например '00',
на работу программы это бы никак не повлияло — они написаны раздельно для
удобочитаемости.
Нетрудно понять, что первое предложение применимо, когда аргумент функции —
'00', т.е. результатом вызова <BinAdd '00'> будет '0', со вторым
и четвёртым предложением тоже всё понятно.
Третье предложение говорит о том, что результат вызова функции
<BinAdd '10'> точно такой же, как и <BinAdd '01'>, от перемены мест
слагаемых сумма не меняется. Можно было написать в правой части сразу '1',
вызов функции был добавлен в правую часть ради демонстрации самого вызова.
Областью определения этой функции будут пары символов '00', '01', '10',
'11'. При попытке вызвать эту функцию с аргументом вне области определения
программа аварийно завершится (т.н. ошибка невозможности отождествления,
«recognition impossible»).
Пример 2. Напишем функцию, которая вычитает две двоичные цифры.
BinSub {
'0' '0' = '0';
'1' '1' = '0';
'1' '0' = '1';
'0' '1' = '-' <BinSub '1' '0'>;
}
Здесь всё аналогично, кроме последнего предложения. В правой части четвёртого
предложения записан символ минуса, вслед за которым находится вызов функции
BinSub. Что это значит? Это значит, что результатом вызова функции
<BinSub '0' '1'> будет знак '-', за которым следует результат вычисления
<BinSub '1' '0'> — '1'. Т.е. результат <BinSub '0' '1'> будет равен
'-' '1' или '-1'.
Пример 3. Напишем функцию, которая проверяет равенство двух двоичных
чисел, не больших 2 (т.е. 10 в двоичной записи) и не меньших -1. Будем считать,
что оба числа в аргументе функции разделяются знаком '='.
IsEqual {
'-1=-1' = 'True'; '-1=0' = 'False'; '-1=1' = 'False'; '-1=10' = 'False';
'0=-1' = 'False'; '0=0' = 'True'; '0=1' = 'False'; '0=10' = 'True';
'1=-1' = 'False'; '1=0' = 'False'; '1=1' = 'True'; '1=10' = 'False';
'10=-1' = 'False'; '10=0' = 'False'; '10=1' = 'True'; '10=10' = 'True';
}
Да, скучно. Да, длинно. Позже мы увидим, как можно сократить эту запись.
Пример 4. Напишем функцию Go, демонстрирующую коммутативность сложения
и некоммутативность вычитания.
$ENTRY Go {
= <Prout '1+0=0+1? ' <IsEqual <BinAdd '1' '0'> '=' <BinAdd '0' '1'>>>
<Prout '1-0=0-1? ' <IsEqual <BinSub '1' '0'> '=' <BinSub '0' '1'>>>;
}
Функции BinAdd, BinSub, IsEqual и Go можно положить в один файл
(назовём его binmath-1.ref) и откомпилировать следующей
командой:
rlc binmath-1.ref
то получится исполнимый файл binmath-1.exe (или binmath-1 на unix-like),
который при запуске напечатает
1+0=0+1? True
1-0=0-1? False
В этом разделе мы рассмотрели функции, у которых в левых частях предложений
записаны различные, но фиксированные значения. И очевидно, областями
определения таких функций являются все явно перечисленные значения
образцов. Понятно, что для написания нетривиальных программ этого чертовски
мало: можно задать только функции с конечной областью определения и для каждого
из значений аргумента придётся написать предложение. Это привело к тому,
что даже такая простая функция, как IsEqual потребовала целых 16 предложений.
О том, как писать функции с бесконечной областью определения, мы узнаем в следующем параграфе.
У внимательного читателя наверняка возник вопрос: а что будет, если несколько
предложений будут иметь одинаковые левые части? Не будет ли это синтаксической
ошибкой? Ответ: не будет. Если аргумент функции таков, что становятся
применимыми несколько предложений, то приоритет имеет то, которое написано выше.
Например, результатом вызова <F 'A'> будет '1', а не '3':
F {
'A' = '1';
'B' = '2';
'A' = '3';
}
Первое предложение имеет приоритет над третьим.
Выше было сказано, что левая часть определяет подмножество значений аргумента, при котором применимо это предложение. Но пока мы рассмотрели только случаи подмножеств, состоящих из одного единственного элемента.
Рефал позволяет записывать в левых частях выражения (точное определение понятия «выражение» будет дано позже), которые, помимо явно заданных символов, содержат неизвестные произвольные фрагменты — переменные.
Множества значений, которые могут принимать переменные, определяются типом переменной. В Рефале есть три типа переменных: s-, t- и e-переменные. t-переменные мы рассмотрим позже, когда будем изучать структурные скобки.
Значением s-переменной или переменной символа может быть любой одиночный символ (symbol). Значением e-переменной или переменной выражения может быть любой фрагмент аргумента функции, в том числе пустой (не совсем любой, на самом деле, но об этом позже).
Переменная записывается как признак типа (s, t, e), за которой следует
знак . («точка») и имя переменной — некоторая последовательность букв и цифр.
Имя переменной часто называют индексом переменной.
Если в выражении переменная встречается несколько раз, то она называется повторной, все её вхождения должны иметь одинаковое значение.
Рассмотрим некоторые выражения с переменными:
s.1 s.2 s.3 — три любых символа, например 'ABC', '999', '@#$'.s.A s.A s.A — три любых одинаковых, символа, например '666', 'www'.s.Edge s.Middle s.Edge — три любых символа, причём первый и последний
должны совпадать. Например: '@$@', 'kek', '^_^'.s.first e.middle s.last — любое выражение, содержащее как минимум два
символа. Например: 'Hello', '10', '0_o'.s.EDGE e.CENTER s.EDGE — любое выражение как минимум из двух символов,
начинающееся и заканчивающееся на одинаковый символ. Например: '++',
'LOOOL', 'revolver'.'(' e.Inner ')' — выражение, начинающееся и заканчивающееся на скобку.
Примеры: '()', '()()', '(ok)'.e.Key '=' e.Value — выражение, содержащее хотя бы один знак равенства.
Например: '=', 'x=1', '-1=10', 'A=B==C=D'.e.Eq e.Eq — выражение чётной длины, которое можно разбить на две
одинаковые половинки: 'ABCABC', '8888', пустое выражение (да, его
тоже можно разбить на два пустых).Переменные могут встречаться как в левой части предложения, так и в правой. При этом в правой части предложения могут использоваться только те переменные, которые есть в левой.
Теперь мы должны уточнить процесс выполнения функции на Рефале.
В следующем разделе этот процесс будет рассмотрен более детально и формально.
Пример 5. Теперь, вооружённые новым знанием, мы можем упростить функцию
IsEqual:
IsEqual {
e.Equal '=' e.Equal = 'True';
e.Left '=' e.Right = 'False';
}
Видно, что, во-первых, функция сократилась с 16 предложений до двух, во-вторых,
её область определения существенно расширилась — она принимает не только
пары двоичных чисел, но и вообще любые выражения, содержащие знак '='.
Первое предложение функции применимо к любым выражениям, которые содержат
хотя бы один знак равенства, и при этом их можно разбить так, что часть,
предшествующая знаку '=', будет совпадать со следующей за ней.
Второе предложение применимо к любому аргументу, содержащему знак равенства.
Очевидно, что для аргументов вида 'ab=ab' применимы оба предложения, первое,
поскольку до и после знака '=' находятся одинаковые выражения, второе,
потому что просто содержит знак равенства. Но, как было сказано выше,
предшествующие предложения имеют приоритет над последующими, поэтому первое
предложение будет обрабатывать только случаи равных «половинок», а второму
будут доставаться все остальные (неравные).
Если оба предложения поменять местами, то результатом функции (на своей области
определения) всегда будет 'False'.
Пример 6. Функция IsPalindrome, проверяющая, является ли аргумент функции
палиндромом.
IsPalindrome {
s.OneSymbol = 'True';
/* empty */ = 'True';
s.Equal e.Middle s.Equal = <IsPalindrome e.Middle>;
e.Other = 'False';
}
Определение этой функции можно прочитать так. Строка из одного символа является палиндромом. Пустая строка тоже является палиндромом. Строка, которая начинается и заканчивается на один и тот же символ, является палиндромом, если «средняя» часть строки тоже является палиндромом. Любая другая строка палиндромом не является.
Вообще, определения функций на ФЯ часто могут читаться как математические определения.
Пример 7. Напишем функцию сложения двух двоичных чисел произвольной длины.
Функции на Рефале принимают один аргумент, а здесь мы хотим передать два.
В первом варианте функции сложения мы избежали этого затруднения, передавая
в функцию два символа. Теперь нам надо передать два выражения произвольной
длины. Каждый из аргументов может состоять только из знаков '0' и '1',
поэтому можно между ними поместить любой символ, кроме нуля и единицы — по нему
можно будет понять, где кончается один аргумент и начинается другой. Будем
использовать символ '+' для наглядности.
Примечание. Позже мы узнаем гораздо более простой, эффективный и универсальный способ разделения аргументов.
BinAdd {
e.Num1 '0' '+' e.Num2 '0' = <BinAdd e.Num1 '+' e.Num2> '0';
e.Num1 '0' '+' e.Num2 '1' = <BinAdd e.Num1 '+' e.Num2> '1';
e.Num1 '1' '+' e.Num2 '0' = <BinAdd e.Num1 '+' e.Num2> '1';
e.Num1 '1' '+' e.Num2 '1'
= <BinAdd <BinAdd e.Num1 '+' '1'> '+' e.Num2> '0';
/* empty */ '+' e.Num2 = e.Num2;
e.Num1 '+' /* empty */ = e.Num1;
}
Нетрудно заметить, что функция реализует сложение двух двоичных чисел в столбик.
Если последние цифры обоих чисел — '1' и '1', то происходит перенос
в следующий разряд — эта дополнительная единица прибавляется к первому
аргументу.
Давайте подытожим:
s.varname, e.ab123, s.123ab.Чисто математически изученного подмножества Рефала достаточно для записи любого сколь угодно сложного алгоритма (см. [4, лекция № 6]). Но на практике этого мало: изученные средства позволяют работать только с «плоскими» строками символов, тогда как многие нетривиальные алгоритмы требуют уже иерархически организованных данных.
Что такое иерархия данных? Это возможность работать с некоторым фрагментом данных, как с одним объектом, абстрагируясь от его внутренней сложной структуры. Например, мы можем работать с текстовым документом как с файлом: перемещать его из папки в папку, копировать, стирать, и при этом не заботиться о том, что внутри него может находиться текст, таблицы, картинки и т.д. На определённом уровне иерархии нас это не интересует.
Для того, чтобы в Рефале с выражением работать как с единым объектом, его заключают в круглые скобки, которые называют структурными скобками. Такой объект, его называют скобочный терм, сам может быть частью другого выражения, которое, в свою очередь, тоже может быть заключено в круглые скобки. Так в Рефале строятся иерархические вложенные данные. Символы (symbols), которые мы рассматривали до этого, тоже являются термами. Таким образом, выражение на Рефале состоит из термов, каждый из которых может быть либо символом, либо скобочным термом, который внутри содержит другое выражение на Рефале.
В отличие от круглых, структурных скобок, угловые скобки вызова функции в правых частях предложений называются скобками конкретизации, скобками активации или скобками вызова функции (все эти словосочетания — синонимы).
Пример 8. Выражение
('abc') 'def' (('ghi') 'j' ('klm') ()) 'nop' ((('rst')))
состоит из 9 термов. Первый терм — скобочный, содержит в себе выражение из трёх
термов-символов, следующие три — печатные знаки 'def', следующий — опять
скобочный, состоящий из трёх скобочных термов и одного символа, при этом
его последний скобочный терм содержит пустое выражение.
В выражении на Рефале скобки должны обязательно образовывать правильную скобочную структуру как в левой, так и в правой части предложений. При этом в правой части предложений круглые и угловые скобки не могут накладываться (overlap) друг на друга.
Уточним наше понимание переменных в свете нового знания.
t.varname) может быть любой
одиночный терм — как символ (symbol), так и выражение в скобках.Пример 9. Изобразим родословную Пушкина в виде выражения на Рефале.
Каждого персонажа родословной мы будем изображать в виде скобочного терма,
который содержит имя персонажа и два терма: отец и мать. Причём, если
предок известен, он изображается в виде такого же персонажа, если нет —
на его месте будет располагаться символ '?'. Таким образом, каждый
из персонажей может быть сопоставлен с образцом вида
(e.Name t.Father t.Mother)
Собственно, родословная [5, 6]:
(
'Александр Сергеевич Пушкин'
(
'Сергей Львович Пушкин'
(
'Лев Александрович Пушкин'
'?' /* не известен отец */
(
'Евдокия Ивановна Головина'
'?' /* не известен отец */
'?' /* не известна мать */
)
)
(
'Ольга Васильевна Чичерина'
('Василий Иванович Чичерин??')
'?' /* не известна мать */
)
)
(
'Надежда Осиповна Пушкина (Ганнибал)'
(
'Осип Абрамович Ганнибал'
('Абрам Петрович Ганнибал (арап Петра Великого)??')
('Христина-Регина фон-Шеберг??')
)
('Мария Алексеевна Пушкина??')
)
)
Примечание. На самом деле родословная А. С. Пушкина известна гораздо глубже, здесь просто для наглядности были пропущены некоторые предки на разных уровнях иерархии.
Пример 10. Давайте напишем функцию, которая принимает генеалогическое
древо и ветвь предка в виде цепочки знаков вида 'MFFM…' — где 'M'
означает мать, 'F' — отец и находит соответствующего предка.
Например, 'F' — отец, 'FF' — дед по отцу, 'MM' — бабка по матери,
'FM' — бабка по отцу, 'FMM' — прабабка по бабке по отцу, пустое выражение —
сам персонаж.
FindAncestor {
/* продвигаемся по отцу */
(e.Name t.Father t.Mother) 'F' e.Branch
= <FindAncestor t.Father e.Branch>;
/* продвигаемся по матери */
(e.Name t.Father t.Mother) 'M' e.Branch
= <FindAncestor t.Mother e.Branch>;
/* у неизвестного персонажа неизвестны и предки */
'?' e.Branch = '?';
/* Ветвь закончилась — искомый человек текущий */
(e.Name t.Father t.Mother) /* empty branch */ = e.Name;
}
Иначе говоря, чтобы по родословной найти какого-то предка по отцу (ветвь
начинается с 'F…'), нужно взять родословную отца (поле t.Father)
и поискать предка в ней (отбросив от начала ветви 'F') — именно это
делает первое предложение. Второе предложение аналогично.
Если родословная на некотором этапе неизвестна, то и любой предок будет неизвестен — этот случай обрабатывает третье предложение. Если ветвь пустая (явно указана пустая ветвь или опустошилась за несколько итераций), то корень текущей родословной и есть искомый человек — последнее четвёртое предложение.
Пример 11. Давайте напишем программу, которая распечатывает некоторых
предков Пушкина (pushkin.ref).
$ENTRY Go {
= <Prout <FindAncestor <Pushkin> 'FF'>>
<Prout <FindAncestor <Pushkin> 'FFF'>>
<Prout <FindAncestor <Pushkin> 'MFF'>>
<Prout <FindAncestor <Pushkin> 'MFM'>>
<Prout <FindAncestor <Pushkin> 'F'>>
<Prout <FindAncestor <Pushkin> 'FM'>>
<Prout <FindAncestor <Pushkin> 'FMF'>>
<Prout <FindAncestor <Pushkin> 'FMFM'>>
}
FindAncestor {
…см. выше…
}
Pushkin {
= (
'Alexander Sergeyevich Pushkin'
(
'Sergey Lvovich Pushkin'
(
'Lev Aleksandrovich Pushkin'
'?' /* unknown father */
(
'Evdokia Ivanovna Golovin'
'?' /* unknown father */
'?' /* unknown mother */
)
)
(
'Olga Vasilievna Chicherina'
('Vasily Ivanovich Chicherin??')
'?' /* unknown mother */
)
)
(
'Nadezhda Ossipovna Pushkina (Gannibal)'
(
'Ossip Abramovich Gannibal'
('Abram Petrovich Gannibal (The Moor of Peter the Great)??')
('Christina Regina von Sioberg??')
)
('Maria Alekseevna Pushkina??')
)
)
}
Функция Pushkin состоит из одного предложения — при любом аргументе возвращает
константу. Т.е. фактически она и является определением константы. Остальное всё
должно быть понятно.
Примечание. Имена предков записаны транслитом — на некоторых операционных системах вывод кириллицы на экран не работает или работает криво. В будущих версиях это будет исправлено.
Для компиляции и запуска программы под Windows введите:
rlc pushkin.ref
pushkin.exe
Под Linux:
rlc pushkin.ref
./pushkin
Программа должна распечатать следующее:
Lev Aleksandrovich Pushkin
?
Abram Petrovich Gannibal (The Moor of Peter the Great)
Christina Regina von Sioberg
Sergey Lvovich Pushkin
Olga Vasilievna Chicherina
Vasily Ivanovich Chicherin
?
Выше мы, когда хотели вызвать функцию с несколькими аргументами, передавали их,
разделяя каким-нибудь знаком, который не может встречаться внутри самих
аргументов (например, '=' в функции IsEqual или '+' в функции BinAdd).
Более грамотной практикой при передаче нескольких аргументов является их
«заворачивание» в скобочные термы. Например, если функция принимает 3 аргумента
произвольной длины — обозначим их как e.1, e.2, e.3, — то их можно
передать как (e.1) e.2 (e.3), e.1 (e.2) (e.3), (e.1) (e.2) e.3
и (e.1) (e.2) (e.3). Последний вариант, помещение каждого аргумента
в скобочный терм, избыточен, но иногда делает программы более понятными. Вообще,
если передаётся в функцию N аргументов, то достаточно завернуть в скобки
только N−1 аргументов.
В следующем разделе мы увидим, что заворачивание аргументов в скобки вместо символов разделителей не только проще (не нужно придумывать символ-разделитель), но и эффективнее с точки зрения времени выполнения программы.
Функции IsEqual и BinAdd мы можем теперь переписать так:
IsEqual {
(e.X) (e.X) = 'True';
(e.X) (e.Y) = 'False';
}
BinAdd {
(e.Num1 '0') e.Num2 '0' = <BinAdd (e.Num1) e.Num2> '0';
(e.Num1 '0') e.Num2 '1' = <BinAdd (e.Num1) e.Num2> '1';
(e.Num1 '1') e.Num2 '0' = <BinAdd (e.Num1) e.Num2> '1';
(e.Num1 '1') e.Num2 '1' = <BinAdd (<BinAdd (e.Num1) '1'>) e.Num2> '0';
(/* empty */) e.Num2 = e.Num2;
(e.Num1) /* empty */ = e.Num1;
}
Выше по тексту мы использовали понятия символы (symbols) и печатные знаки (characters) как синонимы. Но это не так. Помимо печатных знаков (characters), которые далее по тексту мы будем называть символами-литерами (characters), Рефал поддерживает и другие виды символов.
Вообще в Рефале символ (symbol) — это объект, который невозможно разложить при помощи образца на более мелкие фрагменты. Помимо символов-литер, в Рефале есть ещё символы-числа и символы-слова. Символы-слова мы рассмотрим в следующем параграфе.
Символ-число или макроцифра (macrodigit) — это число в диапазоне от 0
до 2³²−1, записанное в десятичном виде. Примеры: 1, 10, 65536,
4294967295 (самая большая макроцифра).
Для работы с макроцифрами в Рефале есть встроенные арифметические функции:
Add — сложение,Sub — вычитание,Mul — умножение,Div — деление (вычисление частного),Mod — вычисление остатка от деления,Divmod — возвращает и частное, и остаток,Compare — сравнивает два числа,Numb — преобразует цепочку литер в число (в десятичной записи),Symb — преобразует число в цепочку литер (тоже в десятичной записи).Читателя должно заинтересовать такое странное слово, как «макроцифра». Объясняем: арифметические функции реализуют арифметику произвольной точности (длинную арифметику, arbitrary-precision arithmetic) — работу с числами произвольной длины. И для представления таких чисел используются цепочки макроцифр.
Точно так же, как в обычной десятичной записи, число 1864 означает
1864 = 1×10³ + 8×10² + 6×10 + 4
в Рефале длинное число, например, 10000000000000000000000 представляется как
542 434162106 2990538752, что обозначает
10000000000000000000000 = 542×(2³²)² + 434162106×2³² + 2990538752
т.е. основанием системы счисления является не 10, а 2³². Для записи
отрицательных чисел в начале цепочки макроцифр следует поставить литеру '-',
в начало положительных чисел можно записывать необязательный знак '+'.
Т.е. числа в общем случае являются цепочками термов произвольной длины (e-переменными), в виде одного символа представляются только небольшие положительные числа (влезающие в одну макроцифру).
Функции Add, Sub, Mul, Div, Mod, Divmod и Compare принимают
два числа. Если первое число — небольшое положительное (макроцифра), то оно
макроцифрой и записывается. Иначе первый аргумент записывается в виде скобочного
терма. Второй аргумент пишется вслед за первым.
Функция Divmod возвращает частное в скобках и остаток. Функция Compare
возвращает знак разности первого и второго числа, соответственно '+', '0'
или '-', когда первое больше, равно или меньше второго.
Функция Numb принимает строку. Если строка начинается с необязательного
знака и десятичных цифр, то функция возвращает число, представимое этими
цифрами. Иначе (если аргумент не начинается с десятичной записи числа) функция
возвращает 0.
Функция Symb обратна функции Numb — преобразует число в десятичную запись
Пример 12. Некоторые вызовы функций и их результаты рядом:
<Add 1 2> 3
<Sub 1 2> '-' 1
<Add 1 2 3> 2 4
<Add (1) 2 3> 2 4
<Add (2 3) 1> 2 4
<Add ('-' 7) 17> 10
<Mul (1 1) 1 1> 1 2 1
<Div (1 2 3) 1 1> 1 1
<Mod (1 2 3) 1 1 2
<Divmod (1 2 3) 1 1> (1 1) 2
<Compare 10 13> '-'
<Compare (0 0 100) 0 100> '0'
<Compare (1 2) 1 0 0> '-'
<Numb '10abcdef'> 10
<Numb '-11113'> '-' 11113
<Numb 'not a number> 0
<Numb '10000000000000000000000'> 542 434162106 2990538752
<Symb 123456> '123456'
<Symb '-' 1 1> '-4294967297'
<Symb 542 434162106 2990538752> '10000000000000000000000'
Пример 13. Функция вычисления факториала. Напомним, что факториал числа N (обозначается N!, читается «эн факториал») — это произведение всех чисел от 0 до N включительно. Т.е. N! = 1×2×…×(N−1)×N. Считается, что 0! = 1.
Можно заметить, что N! = 1×2×…×(N−1)×N = (1×2×…×(N−1))×N = (N−1)!×N. При этом 1! = (1−1)!×1 = 0!×1 = 1×1 = 1. Воспользуемся этим, чтобы написать функцию.
Fact {
0 = 1;
s.N = <Mul (<Fact <Sub s.N 1>>) s.N>;
}
$ENTRY Go {
= <Prout '1! = ' <Symb <Fact 1>>>
<Prout '10! = ' <Symb <Fact 10>>>
<Prout '100! = ' <Symb <Fact 100>>>
}
Заметим, что первый аргумент функции Mul мы завернули в скобки, а первый
аргумент Sub — нет. Почему? Потому что уже
13! = 6227020800 > 4294967296 = 2³².
Т.е. для аргументов, больших 12, факториал уже перестанет влезать в одну
макроцифру. У функции Sub первый аргумент всегда влезает в макроцифру,
поскольку он изначально задаётся макроцифрой и на каждом шаге рекурсии он
только уменьшается. Приведённая выше программа fact.ref
напечатает на экране следующее (последняя строка слишком длинная, для
удобства чтения разбита на части)
1! = 1
10! = 3628800
100! = 9332621544394415268169923885626670049071596826438162146859↓
29638952175999932299156089414639761565182862536979208272237582511↓
85210916864000000000000000000000000
При программировании на Рефале часто возникает потребность промаркировать различные виды объектов или состояний: функция может завершиться успешно или неуспешно, конечный автомат может иметь одно из нескольких состояний, программа может оперировать объектами разных типов (представление токенов в лексическом анализе, узлов синтаксического дерева в синтаксическом анализе и т.д.).
Например, мы хотим написать функцию, которая читает конфигурационный файл и вызывается таким вот образом:
<ReadConfig e.FileName>
Эта функция может либо успешно прочитать конфигурационный файл и вернуть данные конфигурации (мы не будем рассматривать, как они устроены). Функция может обнаружить, что файл конфигурации не существует (в этом случае программа, к примеру, будет использовать некоторую конфигурацию по умолчанию). А может случиться и так, что файл имеет неверный формат, и прочитать его не удалось — программа должна будет выдать понятное сообщение об ошибке и завершиться.
Следовательно, функция нам должна вернуть три разных результата, которые мы должны уметь различить. В первом случае — данные конфигурации. Во втором — признак того, что файла нет. В третьем — сообщение о синтаксической ошибке в файле.
Можно эти случаи просто пронумеровать. В первом случае функция вернёт
макроцифру 1 и данные, во втором — только макроцифру 2 и в третьем —
число 3 и сообщение об ошибке. Да, результаты функции можно будет различить,
но главный недостаток такого решения — числа сами за себя не говорят.
Программист будет вынужден помнить, что, например, для этой функции цифра
3 означает синтаксическую ошибку, а 2 — отсутствие файла, и не наоборот.
А если таких разных функций много? Придётся учить, что каждое число значит
применительно к каждой функции.
Можно возвращать последовательность литер. Например, в первом случае
выводить 'Success' (e.Configuration), во втором — 'File not found',
в третьем — 'Syntax error' (e.ErrorMessage). Текстовые строки уже говорят
сами за себя, понимать программу становится легко. Но у этого решения тоже
есть свой недостаток — текстовые строки — выражения произвольной длины,
и когда функция возвращает другие данные произвольной длины, например,
конфигурацию или сообщение об ошибке, их приходится отделять круглыми скобками.
Более того, избыточно передавать пару десятков символов (symbols), когда
для различия достаточно одного.
Для различия достаточно одного. Может нам сократить по первой букве? Тогда
вместо 'Success' (e.Configuration) мы запишем 'S' e.Configuration,
вместо 'File not found' запишем 'F', вместо 'Syntax error (e.ErrorMessage)
запишем 'S' e.ErrorMessage. Стоп, стоп, стоп. Чем у нас тогда будет
отличаться первый и последний случай? Они оба начинаются на знак 'S',
после которого может следовать выражение произвольной длины. Сократить
по первой букве не получилось — придётся выбирать какие-то другие буквы.
Но тогда всплывёт та же проблема, что и с числами — одиночные буквы плохо
сами за себя говорят.
Вот для решения этой проблемы в Рефале существуют символы-слова
(символы-идентификаторы, составные символы). Это символы (symbols),
сопоставляются с обычной s-переменной, но имеют вид слова без кавычек.
Внешний вид идентификатора точно такой же, как у имени функции: он состоит
из букв, цифр, прочерков и дефисов, но при этом обязан начинаться с буквы
или прочерка. Примеры идентификаторов: Success, FILE_NOT_FOUND,
syntax-error, True, False, Error-404-Not-found, o_0 и т.д.
Теперь уже очевидно, что для нашей функции ReadConfig в возвращаемом значении
нужно использовать идентификаторы. Например, Success e.Config, FileNotFound
и SyntaxError e.Message.
Рефал-5λ, как и классический РЕФАЛ-5, допускает использование произвольных
строк символов в качестве идентификаторов. Для этого строку нужно заключить
в двойные кавычки: "This is one symbol:-)". На практике они используются
довольно редко, но могут быть полезны, когда хочется использовать в качестве
признака-идентификатора комбинацию знаков, которую без кавычек записать нельзя.
Например, "*=", "C++", "=0?" и т.д. Можно записывать в кавычках слова,
которые пишутся и без кавычек тоже — "Success", "SyntaxError" — они будут
идентичны этим же словам без кавычек.
На первый взгляд может показаться, что невозможно записать литеру, представляющую одинарную кавычку, либо составной символ, содержащий внутри двойную кавычку. Но это не так. И в цепочке литер, и в составном символе можно использовать так называемые escape-последовательности — специальные обозначения для некоторых символов.
Escape-последовательность выглядит как знак \, за которым следует один или
несколько других знаков. Все они вместе образуют одну литеру (если записаны
внутри одинарных кавычек), либо один из знаков составного символа. В Рефале-5λ
допустимы следующие escape-последовательности:
\' — одинарная кавычка, ',\" — двойная кавычка, ",\\ — обратная косая черта, \,\n — перевод строки, LF,\r — возврат каретки, CR,\t — знак табуляции,\xHH — символ с кодом HH в шестнадцатеричной записи, например,
\x07 — звуковой сигнал, \x0A — перевод строки (то же, что и \n),
поскольку имеет код 10, \x3F — знак вопроса ?,\<, \>, \(, \) — то же, что и <, >, (, ) —
escape-последовательности, поддерживаемые классическим РЕФАЛом-5,
поддерживаются и в Рефале-5λ.Понятно, что внутри одинарных кавычек можно использовать двойную без
экранирования (знака \), и наоборот. Но для единообразия язык разрешает
писать \" внутри апострофов и наоборот.
Пример 13.
'Abc\ndef\'ghi\\jkl\x6D\x6e' обозначает последовательность
из 17 литер: 'A', 'b', 'c', знак перевода строки, 'd', 'e', 'f',
одинарная кавычка, 'g', 'h', 'i', знак обратной косой черты, 'j',
'k', 'l', 'm', 'n' (последние два записаны в шестнадцатеричной
форме)."Hello, \"World\'!" — это слово, состоящее из 15 знаков. Знак \
перед одинарной кавычкой здесь избыточен, это же слово можно записать как
"Hello, \"World'!" или "Hello, \x22World'".Ранее мы говорили, что функции в правой части предложения после подстановки переменных как-то вычисляются. Теперь пришла пора уточнить, как именно, поскольку без этого невозможно писать эффективные программы и выполнять отладку программ на Рефале-5λ.
Говорят, что программу на Рефале выполняет абстрактная рефал-машина, — воображаемая вычислительная машина, понимающая синтаксис программ на Рефале. У этой машины есть две области памяти: поле программ (program field), хранящее все определения функций программы, и поле зрения (view field), хранящее текущее состояние вычислений. Состояние вычислений описывается в виде активного выражения — выражения языка Рефал, которое содержит скобки активации, но при этом не может содержать переменных.
Рефал-машина выполняет программу по шагам. Каждый шаг — это выполнение следующей последовательности действий.
Начальным содержимым поля зрения является вызов функции GO с пустым
аргументом:
<GO>
если в программе определена функция GO, либо вызов Go:
<Go>
если определена функция Go. Если ни той, ни другой функции нет, то программа
не запустится.
Примечания.
GO или Go в программе отсутствует. В этом случае будет создана
программа, которая при запуске выводит сообщение об ошибке и завершается.
Возможно, это будет исправлено в следующих версиях.Из этого алгоритма можно сделать два важных вывода.
Во-первых, первичным активным подвыражением выбирается самая левая пара скобок
активации, не содержащая внутри себя других скобок активации. Из этого следует,
что Рефал — аппликативный язык, причём порядок вычисления функций чётко
определён: слева-направо. Т.е. если записано несколько вызовов функций в правой
части предложения, то они будут вычисляться слева-направо, от самых внутренних
к самым внешним. Поэтому мы можем использовать функции с побочным эффектом,
(например, Prout) чётко зная, когда этот побочный эффект будет выполняться.
Во-вторых, из семантики поля зрения непосредственно следует, что Рефал реализует так называемую оптимизацию хвостовой рекурсии.
Во многих императивных языках программирования рекурсия довольно дорога — требуются накладные расходы на сохранение контекста вычислений — точки, куда процесс выполнения должен вернуться после завершения хвостового вызова. Причём память на это сохранение выделяется из ограниченной области — системного стека. Контролировать объём системного стека программист, как правило, не может, а при его переполнении программа аварийно завершается. Поэтому в таких языках не следует использовать рекурсию для выполнения циклических повторяющихся действий (тем более, что в императивных языках для этой цели есть операторы цикла).
В Рефале функциям нет нужды сохранять контекст вычислений для возврата значения, поскольку делающая рекурсивный вызов функция завершается до следующего рекурсивного вызова. А это означает, что если рекурсивный вызов в правой части предложения выполняется последним, в поле зрения не будет накапливаться незавершённых вычислений. Т.е. по факту будет наблюдаться не рекурсия (вложенные контексты), а цикл.
Пример 14. Проиллюстрируем это простейшим примером — рассмотрим процесс
вычисления функции Fab, заменяющей все литеры 'a' на литеры 'b'
(программа fab-1.ref):
$ENTRY Go {
= <Prout <Fab 'abracadabra'>>;
}
Fab {
'a' e.Rest = 'b' <Fab e.Rest>;
s.Other e.Rest = s.Other <Fab e.Rest>;
/* empty */ = /* empty */;
}
Начальным содержимым поля зрения будет вызов функции Go:
<Go>
Рефал-машина на первом шаге найдёт этот вызов (он будет первичным активным
подвыражением), увидит имя Go после < и найдёт в поле программ функцию Go.
Функция вызывается с пустым аргументом, первое предложение имеет пустую левую
часть. Переменных в левой и правой части нет, поэтому рефал-машина просто
заменит вызов <Go> на правую часть предложения:
<Prout <Fab 'abracadabra'>>
^^^^^^^^^^^^^^^^^^^
Первичным активным подвыражением здесь будет вызов функции Fab, поскольку
он не содержит вложенных скобок активации (вызов Prout содержит внутри себя
скобки активации вызова Fab).
Рефал-машина увидит Fab после < и попробует отождествить (match) аргумент
'abracadabra' с левой частью первого предложения 'a' e.Rest. Отождествление
возможно: если вместо e.Rest подставить 'bracadabra', то левая часть
превратится в аргумент. Указанную подстановку (e.Rest → 'bracadabra')
рефал-машина применяет к правой части предложения — получается выражение
'b' <Fab 'bracadabra'> и заменяет вызов функции на это выражение:
<Prout 'b' <Fab 'bracadabra'>>
^^^^^^^^^^^^^^^^^^
На третьем шаге первичным активным подвыражением опять будет вызов функции
Fab. Но левую часть первого предложения отождествить с аргументом невозможно:
образец начинается с 'a', но аргумент — с 'b'. Выбирается второе
предложение. Отождествление возможно: существует подстановка переменных
s.Other → 'b', e.Rest → 'racadabra'. Подстановка применяется к правой части,
результат подстановки ('b' <Fab 'racadabra'>) подставляется в поле зрения
на место первичного активного подвыражения:
<Prout 'bb' <Fab 'racadabra'>>
^^^^^^^^^^^^^^^^^
Несколько следующих шагов выполняются в том же духе:
<Prout 'bbr' <Fab 'acadabra'>>
^^^^^^^^^^^^^^^^
<Prout 'bbrb' <Fab 'cadabra'>>
^^^^^^^^^^^^^^^
<Prout 'bbrbc' <Fab 'adabra'>>
^^^^^^^^^^^^^^
<Prout 'bbrbcb' <Fab 'dabra'>>
^^^^^^^^^^^^^
<Prout 'bbrbcbd' <Fab 'abra'>>
^^^^^^^^^^^^
<Prout 'bbrbcbdb' <Fab 'bra'>>
^^^^^^^^^^^
<Prout 'bbrbcbdbb' <Fab 'ra'>>
^^^^^^^^^^
<Prout 'bbrbcbdbbr' <Fab 'a'>>
^^^^^^^^^
На этом этапе рефал-машина выполнит первое предложение функции Fab,
подстановка будет интересна тем, что e.Rest получит значение пустого
выражения.
<Prout 'bbrbcbdbbrb' <Fab>>
^^^^^
Тут тоже рефал-машина будет выполнять функцию Fab, но первое предложение
не подходит (невозможно отождествить выражение, которое начинается на 'a',
с пустым выражением), второе — тоже (невозможно отождествить выражение,
которое начинается на символ с пустым). А вот третье подойдёт — пустая левая
часть успешно отождествляется с пустым аргументом. И рефал-машина заменит
вызов функции <Fab> на пустую правую часть третьего предложения:
<Prout 'bbrbcbdbbrb'>
^^^^^^^^^^^^^^^^^^^^^
Теперь уже первичным активным подвыражением будет вызов функции Prout.
Рефал-машина заметит, что это встроенная функция и вызовет соответствующую
машинную процедуру для вычисления её результата. Машинная процедура напечатает
на экране bbrbcbdbbrb и возвратит пустое выражение. На пустое выражение
заменится вызов Prout в поле зрения.
Поле зрения станет пустым — рефал-машина корректно остановится.
При хвостовой рекурсии, как сказано выше, рекурсивный вызов в правой части
выполняется последним. Продемонстрируем наглядно, почему это так. Рассмотрим
функцию Rec1, которая осуществляет вызов функции F в правой части и самой
себя:
Rec1 {
продолжение = <F ...> <Rec1 ...>;
окончание = rec1-res;
}
Развитие поля зрения будет выглядеть примерно так:
<Rec1 ...>
^^^^^^^^^%
<F ...> <Rec1 ...>
^^^^^^^
f-res <Rec1 ...>
^^^^^^^^^^
f-res <F ...> <Rec1 ...>
^^^^^^^
f-res f-res <Rec1 ...>
^^^^^^^^^^
. . . . .
f-res f-res .... f-res rec1-res
Видно, что невычисленные вызовы функций нигде не накапливаются. На каждом шаге
перед вызовом Rec1 размещается вызов F, который завершается до вызова
Rec1.
Рассмотрим функцию Rec2, которая незначительно отличается от функции Rec1:
Rec2 {
продолжение = <Rec2 ...> <F ...>;
окончание = rec2-res
}
Здесь наоборот — сначала вызывается Rec2, потом F. И поле зрения будет
развиваться совсем иначе:
<Rec2 ...>
^^^^^^^^^^
<Rec2 ...> <F ...>
^^^^^^^^^^
<Rec2 ...> <F ...> <F ...>
. . . . . .
<Rec2 ...> <F ...> <F ...> ... <F ...>
^^^^^^^^^^
rec2-res <F ...> <F ...> ... <F ...>
^^^^^^^
rec2-res f-res <F ...> ... <F ...>
^^^^^^^
. . . . . .
rec2-res f-res ... f-res <F ...>
^^^^^^^
rec2-res f-res ... f-res f-res
Здесь уже накапливаются невычисленные вызовы F, и они накапливаются до тех
пор, пока функция Rec2 не перестанет вызывать себя рекурсивно.
Аналогично получается со вложенными вызовами функций. Рекурсия в функции Rec3
хвостовая:
Rec3 {
продолжение = <Rec3 ... <F ...> ...>;
окончание = rec3-res;
}
<Rec3 ...>
^^^^^^^^^^
<Rec3 ... <F ...> ...>
^^^^^^^
<Rec3 ... f-res ...>
^^^^^^^^^^^^^^^^^^^^
<Rec3 ... <F ...> ...>
^^^^^^^
. . . . .
<Rec3 ... f-res ...>
^^^^^^^^^^^^^^^^^^^^
rec3-res
Рекурсия в функции Rec4 не хвостовая:
Rec4 {
продолжение = <F ... <Rec4 ...> ...>;
окончание = rec4-res;
}
<Rec4 ...>
^^^^^^^^^^
<F ... <Rec4 ...> ...>
^^^^^^^^^^
<F ... <F ... <Rec4 ...> ...> ...>
^^^^^^^^^^
. . . . . .
<F ... <F ... ... <F ... rec4-res ...> ... ...> ...>
^^^^^^^^^^^^^^^^^^^^
. . . . . .
<F ... <F ... f-res ...> ...>
^^^^^^^^^^^^^^^^^
<F ... f-res ...>
^^^^^^^^^^^^^^^^^
f-res
Написанное выше не следует понимать так, что хвостовая рекурсия — всегда хорошо, а нехвостовая — всегда плохо. Просто важно понимать, что в первом случае процесс циклический, поле зрения на каждой итерации возвращается в подобное состояние, а во втором случае разрастается.
В дальнейшем о хвостовой рекурсии мы будем говорить, как о циклах. Классических императивных циклов в Рефале-5λ нет, поэтому такая терминология не должна вызывать путаницы. Просто действительно удобнее говорить в таких случаях о циклических процессах, использовать термин итерация и т.д.
Прежде чем продолжить изучение Рефала-5λ, необходимо ввести несколько важных определений. Выше мы рассматривали различные типы выражений языка Рефал, которые содержат разные синтаксические конструкции. Теперь пришла пора ввести их строгую классификацию.
Примечание. Также часто используют слово «образец» как синоним «левой части», «результат» — как синоним правой части. Это тоже правильная терминология и по контексту обычно понятно, что имеется ввиду.
Все четыре типа выражений можно изобразить в виде вот такой диаграммы:
Объектное выражение: переменные Образцовое выражение:
символы → → → → → → → → → символы, круглые
и круглые скобки скобки, переменные
↓ ↓
↓ скобки вызова ↓ скобки вызова
↓ ↓
Активное выражение: переменные Результатное выражение:
символы, круглые → → → → → → → → → символы, круглые и угловые
и угловые скобки скобки, переменные
Заметим, что объектные и активные выражения существуют только во время выполнения программы — как, соответственно, аргументы функций и содержимое поля зрения (сюда же можно добавить содержимое статических ящиков и копилку, которые будем рассматривать позже). В то время как образцовые и результатные выражения существуют лишь в исходном тексте как левые и правые части предложений. Причиной тому является, очевидно, наличие в них переменных: образцовое выражение есть шаблон, описывающий множество объектных выражений, а результатное — шаблон, по которому строится активное выражение.
Другой важный момент, который необходимо уяснить, чтобы писать эффективные программы на Рефале — это то, как именно рефал-машина осуществляет сопоставление с образцом (pattern matching). Потому что иначе можно случайно написать программу, которая работать будет медленнее, чем могла бы — и всё из-за неправильно составленной левой части.
Выше принцип сопоставления с образцом был описан в декларативной манере, т.е. было описано, каким требованиям должна удовлетворять подстановка значений переменных в левую часть. Напомним эти требования.
Самым интересным требованием тут является последний. Поясним его на примере.
Пример 15. Рассмотрим сопоставление объектного выражения
('abra') ('cadabra') с образцом (e.L1 s.D e.E1) (e.L2 s.D e.R2).
Сопоставление возможно, причём можно построить следующие 8 подстановок
(пустое выражение будем обозначать как []):
e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'c', e.R2 → 'dabra'
e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'cad', e.R2 → 'bra'
e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'cadabr', e.R2 → []
e.L1 → 'a', s.D → 'b', e.R1 → 'ra', e.L2 → 'cada', e.R2 → 'ra'
e.L1 → 'ab', s.D → 'r', e.R1 → 'a', e.L2 → 'cadab', e.R2 → 'a'
e.L1 → 'abr', s.D → 'a', e.R1 → [], e.L2 → 'c', e.R2 → 'dabra'
e.L1 → 'abr', s.D → 'a', e.R1 → [], e.L2 → 'cad', e.R2 → 'bra'
e.L1 → 'abr', s.D → 'a', e.R1 → [], e.L2 → 'cadabr', e.R2 → []
Согласно четвёртому пункту будут выбраны те подстановки, у которых самое
левое вхождение e-переменной будет кратчайшим. Самая левая e-переменная здесь
это e.L1, кратчайшему её вхождению (пустому выражению) соответствуют
первые три подстановки:
e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'c', e.R2 → 'dabra'
e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'cad', e.R2 → 'bra'
e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'cadabr', e.R2 → []
Опять неоднозначность. Смотрим на следующую e-переменную. e.R1 во всех
трёх случаях имеет одинаковую длину. Смотрим на следующую — e.L2.
Кратчайшей подстановке переменной e.L2 среди этих трёх отвечает первая,
где e.L2 → 'c'. Таким образом, будет выбрана подстановка
e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'c', e.R2 → 'dabra'
Примечание. Формально, разобранного выше материала достаточно, чтобы писать корректные программы на Рефале. Но мы, тем не менее, рекомендуем дочитать этот параграф до конца. Во-первых, корректные программы — это не всегда эффективные программы, а без понимания механизма сопоставления с образцом эффективные программы писать невозможно. Во-вторых, даётся важное определение понятия открытых переменных, которые часто будут встречаться в последующем изложении.
Но декларативное описание никак не определяет, каким образом будет выбрана подходящая подстановка. И, что ещё хуже, каковы будут временны́е затраты на сопоставление с таким образцом.
Рассмотрим, как в Рефале-5λ осуществляется сопоставление с образцом.
Примечание. В [9, раздел 2.5] описывается алгоритм сопоставления с образцом немножко с другой точки зрения, и, возможно, кому-то он покажется более понятным. При написании руководства я не хотел его дублировать или дословно пересказывать, поэтому дальнейшее изложение построено в терминах трансляции образца в последовательность элементарных команд.
Далее мы сначала рассмотрим алгоритм, строящий по заданному образцу последовательность элементарных команд сопоставления, затем изучим простое правило, позволяющее понять, какие операции в образце будут выполняться однократно, какие — многократно.
Рефал-5λ — это компилятор, который преобразует исходный текст на Рефале в форму, удобную для выполнения машиной — в последовательность интерпретируемых команд, либо в код на C++. В обоих случаях модель вычислений императивная, т.е. описываются не свойства конечного результата, а элементарные шаги, к этому результату приводящие. В данном случае, последовательно выполняя эти шаги, можно вычислить результат сопоставления: найти подстановку значений переменных, удовлетворяющие четырём требованиям выше, либо доказать, что такой подстановки не существует.
Алгоритм, описанный ниже, формирует по заданному образцу последовательность
команд сопоставления для некоторого абстрактного исполнителя. Исполнитель
рассматривает s- и t-переменные образца как одиночные указатели, e-переменные —
как пары указателей, либо указывающих на первый и последний терм выражения,
либо одновременно хранящих особое, «нулевое» значение. Помимо переменных,
присутствующих в образце, исполнитель пользуется диапазонами — промежуточными
рабочими переменными, которые устроены так же, как и e-переменные — в виде
пары указателей. Диапазоны мы будем просто нумеровать и обозначать как
BN, где N — целое число.
Алгоритм построения при работе будет использовать объекты-указатели, которые
будут обозначаться квадратными скобками с индексами: [N,
]N. Эти указатели могут перемещаться по образцу, перескакивая
через его элементы, причём [N может двигаться только вправо,
а ]N — только влево. Два указателя с одинаковым индексом могут
аннигилировать — исчезать из образца. Аннигилируют они в двух случаях — когда
они непосредственно встречаются, и когда они окружают ещё не сопоставленную
e-переменную, такая переменная называется закрытой.
Жёстким элементом называется часть образца, которая имеет известную длину
в термах: литеральный символ, любая s- или t-переменная и e-переменная,
которая уже получила своё значение, скобочный терм. Жёсткий элемент мы
будем обозначать как He.
Входные данные алгоритма: образцовое выражение P.
Выходные данные алгоритма: последовательность команд сопоставления.
Шаг 1. Поместить слева от образца P указатель [0, справа —
]0:
[0P ]0
Сгенерировать: B0 ← аргумент функции.
Установить переменную NextK ← 1.
Шаг 2. Если в образце есть указатель [N, справа от которого
есть жёсткий элемент (за исключением скобочного терма), передвинуть указатель
за жёсткий элемент:
... [NHe ... → ... He [N ...
Сгенерировать: BN → He BN.
Вернуться к шагу 2.
Шаг 3. (Симметричен шагу 2.) Если в образце есть указатель ]N,
слева от которого есть жёсткий элемент (за исключением скобочного терма),
передвинуть указатель перед жёстким элементом:
... He ]N ... → ... ]N He ...
Сгенерировать: BN → BN He.
Вернуться к шагу 2.
Шаг 4. Если в образце есть указатель [N, справа от которого
располагается круглая скобка (, создать пару новых указателей [K
и [K, где K равно NextK, переместить исходный указатель вправо
за соответствующую ), поместить новые указатели справа от ( и слева от )
соответственно:
... [N (...) ... → ... ([K...]K) [N...
Сгенерировать: BN → (BK) BN.
NextK = NextK + 1
Вернуться к шагу 2.
Шаг 5. (Симметричен шагу 4.) Если в образце есть указатель ]N,
слева от которого располагается круглая скобка ), создать пару новых
указателей [K и ]K, где K равно NextK, переместить
исходный указатель влево за соответствующую (, поместить новые указатели
справа от ( и слева от ) соответственно
... (...) ]N ... → ... ]N ([K...]K)...
Сгенерировать: BN → BN (BK).
NextK = NextK + 1
Вернуться к шагу 2.
Шаг 6. Если в образце есть пара указателей, находящихся рядом друг с другом, удалить их (первый случай аннигиляции):
... [N ]N ... → ... ...
Сгенерировать: BN → [].
Вернуться к шагу 2.
Шаг 7. Если в образце есть пара указателей, окружающих несвязанную ранее e-переменную, удалить их (второй случай аннигиляции):
... [N e.X ]N ... → ... e.X ...
Сгенерировать: e.X ← BN.
Повторимся, такая переменная называется закрытой. При выполнении операции
BN → e.X переменная получает значение соответствующего диапазона.
Вернуться к шагу 2.
Шаг 8. Найти самый левый указатель [N, справа от которого
располагается несвязанная ранее e-переменная, передвинуть указатель за эту
переменную:
... [N e.X ... → ... e.X [N...
Сгенерировать: Loop BN → e.X BN
Здесь формируется уже не одиночная команда сопоставления, а заголовок цикла.
Для каждой пары указателей повторять:
NextK.BK ← BN.NextK ← NextK + 1.Вернуться к шагу 2.
Шаг 9. На данном этапе указатели уже должны закончиться. Завершение работы алгоритма.
Стрелки влево (→) в рассмотренном алгоритме являются элементарными командами
отождествления (recognition), они либо могут выполниться успешно (если значение
слева может быть разбито на части, указанные справа), либо завершиться неудачей.
В случае неудачи управление передаётся на предыдущую команду Loop. Если ранее
по тексту нет команды Loop (т.е. если в образце нет открытых e-переменных),
то считается, что попытка сопоставления оказалась неудачной.
Команда Loop BN → e.X BN при первом проходе присваивает переменной e.X
пустое значение и не меняет BN. При перехвате неудачи сопоставления команда
Loop удаляет первый терм из BN и приписывает его в конец e.X — происходит
удлинение переменной e.X за счёт BN. Если к тому моменту BN оказался
пустым, то операция удлинения оказалась неуспешной — неудача обрабатывается
как описано выше.
Стрелки вправо (←) — это присваивания. Они всегда выполняются успешно.
Пример 16. Составим последовательность элементарных команд для образца
(e.L1 s.D e.R1) (e.L2 s.D e.R2).
Инициализируем нулевую пару указателей и переменную NextK:
[0(e.L1 s.D e.R1) (e.L2 s.D e.R2)]0
NextK ← 1
Генерируем: B0 ← аргумент функции.
Шаги 2 и 3 выполнить не можем. Но можем выполнить шаг 4:
([1e.L1 s.D e.R1]1) [0(e.L2 s.D e.R2)]0
NextK ← 2
Генерируем: B0 → (B1) B0
Опять не можем выполнить шаги 2 и 3 и можем выполнить шаг 4:
([1e.L1 s.D e.R1]1) ([2e.L2 s.D e.R2]2)[0]0
NextK ← 3
Генерируем: B0 → (B2) B0
Шаги 2, 3, 4 и 5 неприменимы. Выполняем шаг 6 — аннигиляцию пары указателей.
([1e.L1 s.D e.R1]1) ([2e.L2 s.D e.R2]2)
Генерируем: B0 → []
Шаги 2–7 неприменимы. Шаг 8 предписывает передвинуть указатель [1
и перенумеровать указатели:
(e.L1 [1s.D e.R1]1) ([2e.L2 s.D e.R2]2)
Генерируем: Loop B1 → e.L1 B1
Меняем указатель 1 на 3:
(e.L1 [3s.D e.R1]3) ([2e.L2 s.D e.R2]2)
Генерируем: B3 ← B1.
NextK ← 4.
Меняем указатель 2 на 4:
(e.L1 [3s.D e.R1]3) ([4e.L2 s.D e.R2]4)
Генерируем: B4 ← B2.
NextK ← 5.
Примени́м шаг 2, поскольку s.D — жёсткий элемент.
(e.L1 s.D [3e.R1]3) ([4e.L2 s.D e.R2]4)
Генерируем: B3 → s.D B3. Заметим, что переменная s.D здесь новая.
Шаги 2–6 неприменимы, шаг 7 (аннигиляция указателей вокруг закрытой e-переменной) применим. Выполняем:
(e.L1 s.D e.R1) ([4e.L2 s.D e.R2]4)
Генерируем: e.R1 ← B3.
Шаги 2–7 недоступны, доступен шаг 8 — цикл удлинения открытой переменной e.L2.
Двигаем указатель и перенумеровываем диапазон:
(e.L1 s.D e.R1) (e.L2 [4s.D e.R2]4)
Генерируем: Loop B4 → e.L2 B4
Меняем указатель 4 на 5:
(e.L1 s.D e.R1) (e.L2 [5s.D e.R2]5)
Генерируем: B5 ← B4.
NextK ← 6.
Примени́м шаг 2:
(e.L1 s.D e.R1) (e.L2 s.D [5e.R2]5)
Генерируем: B5 → s.D B5. Переменная s.D здесь повторная, поскольку
ранее по тексту она уже отождествлялась.
Аннигилируем указатели вокруг e.R2 (шаг 7):
(e.L1 s.D e.R1) (e.L2 s.D e.R2)
Генерируем: e.R2 ← B5.
В образце указателей больше не осталось, генерация кода закончена. Получилось:
1. B0 ← аргумент функции
2. B0 → (B1) B0
3. B0 → (B2) B0
4. B0 → []
5. Loop B1 → e.L1 B1
6. B3 ← B1
7. B4 ← B2
8. B3 → s.D B3, s.D — новая
9. e.R1 ← B3
10. Loop B4 → e.L2 B4
11. B5 ← B4
12. B5 → s.D B5, s.D — повторная
13. e.R2 ← B5
Выполним сопоставление ('abra') ('cadabra') : (e.L1 s.D e.R1) (e.L2 s.D e.R2)
пользуясь описанным алгоритмом.
1. B0 ← аргумент функции
B0 = ('abra') ('cadabra')
2. B0 → (B1) B0, успешно
B0 = ('cadabra')
B1 = 'abra'
3. B0 → (B2) B0, успешно
B0 = []
B1 = 'abra'
B2 = 'cadabra'
4. B0 → [], успешно
B0 = []
B1 = 'abra'
B2 = 'cadabra'
5. Loop B1 → e.L1 B1, выполняется первый раз
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
6. B3 ← B1
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'abra'
7. B4 ← B2
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'abra'
B4 = 'cadabra'
8. B3 → s.D B3, s.D — новая, успешно
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'cadabra'
s.D = 'a'
9. e.R1 ← B3
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'cadabra'
s.D = 'a'
e.R1 = 'bra'
10. Loop B4 → e.L2 B4, выполняется первый раз
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'cadabra'
s.D = 'a'
e.R1 = 'bra'
e.L2 = []
11. B5 ← B4
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'cadabra'
s.D = 'a'
e.R1 = 'bra'
e.L2 = []
B5 = 'cadabra'
12. B5 → s.D B5, s.D — повторная, неуспешно
Потому что B5 начинается 'c…', а s.D == 'a'.
Откатываемся к последней команде Loop
10. Loop B4 → e.L2 B4, возврат при неудаче, успешно.
e.L2 удлиняется на один терм, B4 укорачивается.
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'adabra'
s.D = 'a'
e.R1 = 'bra'
e.L2 = 'c'
B5 = 'cadabra'
11. B5 ← B4
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'adabra'
s.D = 'a'
e.R1 = 'bra'
e.L2 = 'c'
B5 = 'adabra'
12. B5 → s.D B5, s.D — повторная, успешно.
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'adabra'
s.D = 'a'
e.R1 = 'bra'
e.L2 = 'c'
B5 = 'dabra'
13. e.R2 ← B5
B0 = []
B1 = 'abra'
B2 = 'cadabra'
e.L1 = []
B3 = 'bra'
B4 = 'adabra'
s.D = 'a'
e.R1 = 'bra'
e.L2 = 'c'
B5 = 'dabra'
e.R2 = 'dabra'
Алгоритм успешно отработал. Получили подстановку:
e.L1 = [], s.D = 'a', e.R1 = 'bra', e.L2 = 'c', e.R2 = 'dabra'
Заметим, ту же самую, что и при декларативном описании.
Пример 17. Будет ли переменная e.X в образце e.X e.Y (e.X) открытой?
Построим последовательность команд отождествления.
Шаг 1. Инициализация.
Генерируем: B0 ← аргумент функции.
NextK ← 1
Окружаем указателями [0, ]0 образец:
[0e.X e.Y (e.X)]0
Шаги 2–4 неприменимы. Но можем выполнить шаг 5 (отщепление скобочного терма справа):
[0e.X e.Y]0 ([1e.X]1)
Генерируем: B0 → B0 (B1)
NextK ← 2
Шаги 2–5 неприменимы, примени́м шаг 6 (аннигиляция через закрытую переменную):
[0e.X e.Y]0 (e.X)
Генерируем: e.X ← B1.
Теперь, внимание, срабатывает шаг 2. Потому что переменная e.X стала
повторной, имеет фиксированное значение. Т.е. стала жёстким элементом:
e.X [0e.Y]0 (e.X)
Генерируем: B0 → e.X B0, e.X — повторная
Переменная e.Y закрытая (шаг 6):
e.X e.Y (e.X)
Генерируем: e.Y ← B0.
Указателей не осталось, генерация кода завершена. Получилось:
B0 ← аргумент функции
B0 → B0 (B1)
e.X ← B1
B0 → e.X B0, e.X — повторная
e.Y ← B0
Переменная e.X не открытая. Она сначала закрытая (в скобках), потом —
повторная (в начале).
Чтобы увидеть в образце открытые переменные, можно воспользоваться следующим
приёмом. Записываем образец, приписываем в начале и конце знаки @,
подчёркиваем их.
Жёсткими элементами будем считать символы, скобки, s- и t-переменные и повторные e-переменные, одно из вхождений которых уже подчёркнуто.
Затем, пока весь образец не подчёркнут, повторяем:
Знаки @ очевидно нужны, чтобы не выделять в особый случай элементы
в самом начале и в самом конце образца.
Пример 18. Найдём открытые переменные в образце
(e.L1 s.D e.R1) (e.L2 s.D e.R2).
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^ ^
С подчёркнутыми собачками соседствуют скобки:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^ ^^^
Подчёркиваем парные скобки:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^ ^^^ ^^^
Жёстких элементов нет. Есть несколько неподчёркнутых e-переменных.
Самая левая — e.L1. Она открытая, подчёркиваем её:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^^^^^ ^^^ ^^^
s.D — жёсткий элемент:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^^^^^^^^^ ^^^ ^^^
e.R1 — закрытая переменная:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^^^^^^^^^^^^^^^^^ ^^^
e.L2 — открытая:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^^^^^^^^^^^^^^^^^^^^^ ^^^
s.D — жёсткий элемент:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^
e.R2 — закрытая переменная:
@ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Весь образец подчёкнут.
Открытые переменные — e.L1 и e.L2.
Пример 19. Найдём открытые переменные в образце e.X e.Y (e.X):
@ e.X e.Y (e.X) @
^ ^
@ e.X e.Y (e.X) @
^ ^^^
@ e.X e.Y (e.X) @
^ ^ ^^^
@ e.X e.Y (e.X) @
^ ^^^^^^^
e.X — повторная переменная, уже есть подчёркнутое вхождение,
значит e.X — жёсткий элемент
@ e.X e.Y (e.X) @
^^^^^ ^^^^^^^
@ e.X e.Y (e.X) @
^^^^^^^^^^^^^^^^^
Открытых переменных нет.
Вернёмся к примеру с функцией IsEqual. Первоначальный вариант у нас выглядел
так:
IsEqual {
e.X '=' e.X = True;
e.X '=' e.Y = False;
}
Во-первых, функция плоха тем, что если e.X или e.Y содержит знак '=',
то она будет работать некорректно. Сравним к примеру 'a=b=a' и 'b':
<IsEqual 'a=b=a=b'>
True
Но, допустим, мы точно знаем, что её аргументы никогда не содержат знака '='.
Запишем императивный код для первого образца:
1. B0 ← аргумент функции
2. Loop B0 → e.X B0
3. B1 ← B0
4. B1 → '=' B1
5. B1 → e.X B1, e.X — повторная
6. B1 → []
Операции 4 и 5 будут выполняться последовательно для каждого возможного удлинения
открытой переменной e.X. Представьте себе такой вызов:
<IsEqual 'aaa…1000 раз…aaa=bcd'>
Переменную e.X придётся удлинить 1000 раз, пока сопоставление в строке 4
не выполнится успешно.
Второй образец также содержит открытую e-переменную и для этого вызова снова
будет делать 1000 удлинений e.X.
Если разделять аргументы скобками, то избыточных циклов не возникает.
IsEqual {
(e.X) (e.X) = True;
(e.X) (e.Y) = False;
}
Код для первого предложения:
1. B0 → (B1) B0
2. B0 → (B2) B0
3. B0 → []
4. e.X ← B1
5. B2 → e.X B2, e.X — повторная
6. B2 → []
Код для второго предложения
1. B0 → (B1) B0
2. B0 → (B2) B0
3. B0 → []
4. e.X ← B1
5. e.Y ← B2
Открытых переменных нет.
Можно заметить, что в функции IsEqual одна пара скобок избыточна — аргумент
будет правильно разделён на подаргументы, если одну из них стереть:
IsEqual {
e.X (e.X) = True;
e.X (e.Y) = False;
}
или так:
IsEqual {
(e.X) e.X = True;
(e.X) e.Y = False;
}
В этом случае мы сэкономим одну команду отождествления пары скобок (а эта команда дешёвая) и несколько нажатий на клавиши. Но вариант с двумя парами скобок в этом случае выразительнее — сравниваются два одинаковых аргумента, и поэтому мы их одинаково заворачиваем.
Открытые e-переменные — не единственный источник неэффективности. Элементарные операции сопоставления имеют различную стоимость.
Быстро выполняются операции сопоставления с символами, s-переменными, круглыми скобками и новыми t-переменными. Хотелось в этот ряд включить и «сопоставление» с закрытой e-переменной, но она, как мы выяснили, является не сопоставлением, а присваиванием. И она тоже выполняется эффективно.
Медленно выполняются операции сопоставления с повторными e- и t-переменными. Ведь для их сопоставления необходимо проверить равенство их значений, а сами значения могут быть достаточно «тяжёлыми». Допустим, у нас есть функция
IsEqual {
(e.X) (e.X) = True;
(e.X) (e.Y) = False;
}
Императивный код для первого предложения будет иметь вид
1. B0 → (B1) B0
2. B0 → (B2) B0
3. B0 → []
4. e.X ← B1
5. B2 → e.X B2, e.X — повторная
6. B2 → []
Циклов по открытым переменным нет, в строке 5 имеем элементарную команду отождествления повторной e-переменной.
Пусть функция IsEqual вызывается как
<IsEqual ('aaa…1000 раз…aaa') ('aaa…999 раз…aab')>
Команда в строке 5 будет сканировать диапазон B2 слева направо. И прежде
чем она увидит отличие в 1000-м символе, она убедится в равенстве предыдущих
999 букв 'a'.
При рассмотрении условий, присваиваний и блоков позже мы увидим, что повторные переменные могут появляться очень внезапно и могут сильно снижать быстродействие, оставаясь практически незаметными в исходном коде. Особенно, если избегать копирования переменных, делая функции «прозрачными».