4. Выполнение рефал-программы
Рефал-программа состоит из набора функций. Работа рефал-программы заключается в вычислении некоторого рабочего выражения (т.е. набора вызовов функций). Это рабочее выражение называется полем зрения. Начальное поле зрения имеет специальный вид и описано в п.7.
Вычисление рабочего выражения в поле зрения состоит из последовательности шагов. На каждом шаге выполняются следующие действия:
- если в поле зрения нет ни одного функционального терма (знаков "<" и ">"), то происходит нормальная остановка программы;
- если в поле зрения есть функциональные термы, то из них выбирается самый левый терм, который не содержит внутри себя других функциональных термов (он называется ведущим термом для этого шага), после чего выбранный терм вычисляется (способ вычисления описан в п.3.)
- на этом выполнение одного шага заканчивается.
При вычислении одного функционального терма возможны три исхода.
1. Остановка "отождествление невозможно" (см. п.3)
2. Произошло отождествление с одной из левых частей предложений, описывающих функцию, но для формирования результата замены не хватает свободной памяти компьютера. В этом случае происходит остановка "свободная память исчерпана".
3. Произошло отождествление и удалось сформировать результат замены.Результат замены замещает ведущий терм, и работа продолжается.
Задача. Привести пример программы, которая зацикливается, т.е. продолжает вычисления до бесконечности и не останавливается.
Рассмотрим несколько несложных примеров функций.
Пример. Кузнечик прыгает по прямой линии то вправо, то влево на 1 метр (или по несколько раз влево или вправо). Прыжки записаны в виде последовательности букв 'L' (влево) или 'R' (вправо). Определить, где будет кузнечик в конце концов.
Можно просто сосчитать количество прыжков влево и количество прыжков вправо и вычесть одно из другого. Мы еще не умеем пользоваться арифметикой, поэтому попробуем воспользоваться тем, что два различных прыжка сокращаются (т.е. прыгнуть сначала вправо, а затем влево - это оставаться на месте).
При программировании на рефале во многих случаях оказывается удобным следовать словесному описанию алгоритма работы. Например, можно действовать так: "если в последовательности прыжков есть рядомстоящие символы 'LR' или 'RL', то убрать эту пару символов и повторить все сначала, в противном случае закончить работу".
Буквальное повторение этой инструкции на рефале выглядит так (назовем нашу функцию Step):
Step {
e.1 'LR' e.2 = <Step e.1 e.2>;
e.1 'RL' e.2 = <Step e.1 e.2>;
e.1 = e.1;
}
Первое предложение соответствует случаю "если есть символы 'LR' ", второе - случаю "если есть символы 'RL' " , третье - " если нет ни того, ни другого".
Отсутствие в правой части первого предложения выражения 'LR' означает "убрать символы 'LR' ". Аналогично во втором предложении.
Обращение в правой части к функции Step означает "и повторить все сначала".
Отсутствие в правой части третьего предложения обращения к функции Step означает конец вычислений.
Заметим, что порядок предложений существенен. Например, если третье предложение поставить в начало, то первое и второе предложения не будут применяться никогда.
В данном примере мы видим, что при замене левой части на правую функция Step вызывает сама себя. Таким образом, описание функции Step оказалось рекурсивным.
Перейдем теперь к недостаткам этого решения задачи. Рассмотрение недостатков поможет нам понять тонкости выполнения рефал-программы.
Заметим сначала, что человек вряд ли стал следовать вышеприведенному алгоритму. Действительно, после того, как символы 'LR' уже найдены, то остальные пары 'LR' , если они есть, могут находиться только правее, и просматривать повторно уже просмотренную часть выражения бессмысленно.
Итак, недостатком алгоритма являются многократные просмотры последовательности символов.
Как можно избавиться от этого недостатка? Поскольку просмотренная часть выражения может еще понадобиться , то мы не можем ничего выносить за функциональные скобки (как мы делали для функции Go в п.2.)
Поэтому надо как-то отделять просмотренную часть выражения от еще не просмотренной.
Сделаем пояснения насчет структурных скобок. При представлении в памяти компьютера поля зрения структурные скобки представляются так, что по левой скобке сразу можно найти правую и наоборот, не просматривая выражения, заключенного в скобки. Например, если типовое выражение имеет вид
(e.1) e.2
то присвоение значений переменным e.1 и e.2 будет происходить очень быстро.
Таким образом, целесообразно для данного примера поместить уже просмотренную часть выражения в структурные скобки.Подобный прием очень часто используется при программировании на рефале, а вспомогательные скобки называются "сумкой".
Решение с использованием "сумки" приведено ниже .
Step { e.1 = <Step1 ( ) e.1>; }
Step1 {
( ) s.a e.2 = <Step1 (s.a ) e.2>;
(e.1 s.a) s.a e.2 = <Step1 (e.1 s.a s.a) e.2>;
(e.1 s.b) s.a e.2 = <Step1 (e.1 ) e.2>;
(e.1 ) = e.1 ;
}
Первое предложение функции Step1 описывает случаи начала работы, а также те моменты времени, когда кузнечик оказывается на месте старта. Второе предложение рассматривает случай двух одинаковых прыжков. В третьем предложении прыжки разные, поэтому их можно сократить.Последнее предложение заканчивает работу.
Замечание. В описании рекурсивной функции всегда должно быть предложение, которое осуществляет "выход из рекурсии", иначе функция либо зациклится, либо произойдет "отождествление невозможно".
Пример. Написать функцию Symm, которая проверяет выражение, состоящее из символов, на симметричность.
Прежде чем писать предложения функции Symm, надо договориться, что является результатом работы этой функции.
Возможны лишь два результата - "ДА" (симметричное выражение) или "НЕТ" (несимметричное), т.е. функция Symm является предикатом. В математической логике принято обозначать истину символом "1", ложь - символом "0". Поэтому опишем функцию Symm так, чтобы результатом замены являлся символ "1", если выражение симметричное, и символ "0", если несимметричное.
Можно предложить такое решение примера:
Symm {
s.a = '1';
s.a s.a = '1';
s.a e1 s.a = <Symm e.1>;
e.1 = '0';
}
Другими словами, выражение из одного символа является симметричным (предложение 1), из двух одинаковых символов - также симметричным (предложение 2). Если выражение начинается и кончается одинаковыми символами, то для решения вопроса о симметричности надо проверить на симметричность выражение без этих символов (предложение 3). Во всех остальных случаях - выражение не является симметричным (предложение 4).
Задача. В предыдущем примере мы предполагали, что последовательность символов не может быть пустой. Будем считать, что пустое выражение является симметричным. Изменить описание функции Symm, чтобы обрабатывалось пустое выражение. Как решить задачу, не увеличивая число предложений?
Задача. Мы предполагали, что функция Symm обрабатывает строки символов. Изменить описание функции Symm так, чтобы она обрабатывала произвольное объектное выражение (т.е. выражение со скобками).
Пример. Прибавление единицы к числу, записанному в двоичной системе счисления.
Назовем эту функцию Plus1
Plus1 {
e.1 '0' = e.1 '1';
e.1 '1' = <Plus1 e.1> '0';
= '1';
}
Приведенное решение моделирует "сложение столбиком": если число оканчивается на 0, то заменяем этот 0 на 1, если же число оканчивается на 1, то "0 пишем, 1 в уме", т.е. нам надо прибавить единицу к более короткому числу.Последнее предложение понадобится в том случае, когда исходное число состоит только из единиц.
Задача. Написать функцию, прибавляющую единицу к числу, записанному в обычной десятичной системе счисления.
Задача. Сложить два числа в двоичной системе счисления. Обозначим функцию через Add2. Предположим, что формат обращения к функции Add2 следующий
<Add2 (e.N1) e.N2 >
где e.N1, e.N2 - слагаемые. Другими словами, первое слагаемое заключено в скобки, второе - вне скобок.
Пример. Пусть имеются три символа, каждый из которых либо 0, либо 1. Написать функцию, результатом работы которой является один символ: 0, если в исходной последовательности нулей больше чем единиц, или 1 - в противном случае. Другими словами, функция определяет большинство.
Существует много способов написания такой функции. Самый простой способ состоит в реализации наблюдения, что искомый символ должен встречаться по крайней мере два раза:
Alfa {
e.1 s.a e.2 s.a e.3 = s.a ;
}
Заметим, что функция Alfa, описанная в таком виде, будет успешно работать и в том случае, если вместо нулей и единиц подавать на вход, например, символы "А" и "В".
Задача. Пусть имеются три символа, каждый из которых либо 0, либо 1. Написать функцию, результатом работы которой являются два символа, означающие количество единиц в исходной последовательности (в двоичной системе счисления). Например, для последовательности "111" должно получиться "11", для "100" - "01, для "000" - "00".