r2 - 03 Jun 2005 - 01:49:43 - OrloVYou are here: TWiki >  Refaldevel Web > RefalPlus > RefalPlusBook > RefalPlusBookChapI

Глава I. Программирование на Рефале Плюс

В данной главе мы даем неформальный обзор основных изобразительных средств языка Рефал Плюс, приводим примеры программ и обсуждаем некоторые приемы программирования на Рефале Плюс. Полное описание Рефала Плюс содержится в главе II "Синтаксис и семантика Рефала Плюс", куда и следует обращаться за недостающими тонкостями и подробностями. Если в примерах программ встречаются вызовы неизвестных функций, следует обращаться за их описанием к главе III "Библиотека функций" и к разделу "Алфавитный указатель функций".

1. Первый пример

По сложившейся традиции, начнем с рассмотрения простейшей программы на Рефале Плюс:

     $use STDIO;              /* Импорт функций ввода-вывода */
                              /* из модуля STDIO */
     Main                     /* Определение главной функции */
       = <Println "Hello!">;  /* Печать и перевод строки */

Эта программа состоит из двух директив. Первая директива

          $use STDIO;

говорит о том, что в программе будут использоваться библиотечные функции ввода-вывода, которые должны быть импортированы из модуля STDIO. Вторая директива является определением функции Main. По принятому в Рефале Плюс соглашению, работа программы всегда начинается с вызова функции Main.

Функция Main всегда имеет пустой аргумент. В данной программе она вызывает библиотечную функцию Println с аргументом "Hello!", в результате чего на стандартное устройство вывода выводится цепочка литер

          Hello!

а вслед за ней - литера "конец строки", после чего работа программы заканчивается.

2. Структуры данных

2.1. Объектные выражения

Данные, обрабатываемые программами написанными на языке Рефал Плюс, являются так называемыми объектными выражениями.

Ниже, в качестве примера, приведены 3 объектных выражения

          "Петр" "Иванович" 33 "года"
          ("Маша" 17) ("Клава" 24) ("Эльвира" 6)
          ("мой" "дом") "имеет" ("большие" ("светлые" "окна"))

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

Кроме скобок вышеприведенные выражения содержат символы. Вот примеры символов:

          "John" "Джон" "джоН" "ку-ку" 1988 -99999999999999

В общем случае объектные выражения состоят из символов и скобок. Всякое объектное выражение - это последовательность объектных термов (которая может быть пустой). Объектный терм - это либо символ, либо объектное выражение, заключенное в круглые скобки "(" и ")". Таким образом, всякое объектное выражение - это последовательность символов и скобок, в которой скобки "правильно расставлены".

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

Рефал-система обеспечивает ввод и вывод объектных выражений и все необходимые при этом преобразования. При вводе выражений, входной поток литер разбивается на лексемы. Каждая лексема изображает символ или скобку. Лексемы отделяются друг от друга пробелами (при этом переход на следующую строку считается эквивалентным пробелу).

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

В текстах Рефал-программ могут появляться в виде констант следующие символы: символы-литеры, символы-слова и символы-числа.

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

Символ-слово представляет собой цепочку литер и изображается в виде этой цепочки литер, заключенной в двойные кавычки.

Если слово начинается с прописной латинской буквы, вопросительного знака (?) или восклицательного знака (!) и содержит только латинские буквы, цифры, литеры минус (-), вопросительный знак (?) и восклицательный знак (!), то окружающие его двойные кавычки можно опустить.

Примеры слов:

          "Вася"
          "Вот-Слово"
          "вот-очень-очень-длинное-Слово"
          X-25m3s--
          "равно?"
          ?-?
          ?

Символ-число является целым числом. Изображается в виде непустой последовательности десятичных цифр, перед которой может стоять знак "+" или "-". Например:

     237
     -99999999999999999999999999999999999999999999999
     +13

Разрядность целых чисел произвольна.

2.2. Представление данных в виде объектных выражений

Объектные выражения особенно удобны для представления символьных (т.е. не чисто числовых) данных.

Пусть, например, мы хотим выбрать представление в виде объектных выражений для алгебраических формул. Нам нужно уметь представлять константы, переменные и формулы, которые получаются в результате применения бинарной операции к двум более простым формулам. Обозначим через [p] объектное выражение, которое является представлением формулы p. Тогда мы можем считать, что представлением целых чисел являются соответствующие символы-числа, представлением переменных являются соответствующие символы-слова, а для бинарных операций имеют место соотношения

          [p+q]     =    ("плюс" [p] [q])
          [p-q]     =    ("минус" [p] [q])
          [pхq]     =    ("умн" [p] [q])
          [p/q]     =    ("дел" [p] [q])
            q
          [p ]      =    ("степ" [p] [q])

Таким образом, формула

              2
          (X+Y )-512

представляется в виде

          ("минус" ("плюс" X ("степ" Y 2)) 512)

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

Первым делом нужно обозначить название и цвет каждой фигуры. Например ("бел" "Король"), ("черн" "пешка"). Затем нужно указать поле каждой фигуры. Например ("e" 2), ("h" 7). Теперь мы можем представить всю позицию в виде последовательности объектных термов, каждый из которых содержит имя и цвет фигуры, а также ее поле. Например

          (("бел" "Король")   ("g" 5))
          (("черн" "Король")  ("a" 7))
          (("бел" "Пешка")    ("c" 6))
          (("бел" "Конь")     ("g" 1))
          (("черн" "Конь")    ("a" 8))

2.3. Объекты и значения

В самом широком смысле под объектами обычно понимают некоторые сущности, которые существуют во времени, развиваются, но при этом остаются сами собой.

Хорошим примером объекта может служить человек, который рождается, растет, развивается и умирает, все же оставаясь, в каком-то смысле, тем же самым человеком.

Другой знаменитый пример принадлежит Гераклиту (расцвет творческих сил которого приходится приблизительно на 504-501 гг. до н.э.). Гераклит учил, что нельзя дважды войти в одну и ту же реку, ибо "на входящих в ту же самую реку набегают все новые и новые воды" [Гер 500]. Таким образом, река тоже может служить хорошим примером объекта.

Под значениями в широком смысле обычно понимают некоторые сущности, которые не меняются, не развиваются и, в этом смысле, находятся вне времени.

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

Конечно, значение можно считать частным, вырожденным случаем объекта (а именно, застывшим объектом, не способным к развитию), но мы все же обычно будем называть "объектами" только такие объекты, которые не являются значениями.

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

В рамках языка Рефал термины "объект" и "значение" имеют более специальный смысл.

Любое значение в языке Рефал представляет собой некоторое объектное выражение.

Любой объект в языке Рефал представляет собой "контейнер" который может содержать объектные выражения и другую информацию.

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

Наглядно взаимосвязь между именем объекта, объектом и содержимым объекта можно изобразить следующим образом:

          R --> [ ... ]

Рефал Плюс имеет дело с объектами следующих типов.

Объекты-функции содержат скомпилированные определения функций. Они создаются во время компиляции программы.

Все остальные объекты могут создаваться как статически (т.е. во время компиляции программы), так и динамически (т.е. в процессе исполнения программы).

Объекты-ящики предназначены для хранения объектных выражений. Каждый ящик содержит ровно одно объектное выражение.

Объекты-таблицы предназначены для хранения конечных множеств упорядоченных пар. Каждая пара содержит два объектных выражения, первое из которых является ключом, а второе - значением, связанным с этим ключом. Все ключи в таблице должны быть попарно различны. Таким образом, каждому ключу в таблице однозначно соответствует связанное с ним значение.

Объекты-каналы дают возможность выполнять операции вводавывода.

Объекты-векторы предназначены для хранения конечных последовательностей объектных выражений.

Объекты-строки предназначены для хранения конечных последовательностей литер.

2.4. Сборка мусора

В языке Рефал Плюс имеется возможность порождать объекты во время работы программы, но не предусмотрено никаких специальных средств для явного уничтожения объектов. Таким образом, может случиться так, что в процессе выполнения Рефал-программы память будет заполняться все новыми и новыми объектами, хотя многие из них будут уже и не нужны. Конечно, теоретически это не создает никаких проблем, однако, поскольку Рефал-программы исполняются с помощью реальных компьютеров, память которых конечна, во всех реализациях языка Рефал предусмотрен механизм сборки мусора.

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

На рисунке 2.1 схематически изображены значения переменных, а также объекты и их содержимое. Звездочки изображают некоторые элементы выражений, которые не являются символами-ссылками. Для удобства изложения, все объекты на рисунке пронумерованы. Символы-ссылки обозначены цифрами.

Видно, что по ссылке из значения одной из переменных можно добраться до объекта 1, и из него - до объекта 4. По ссылке из значения другой переменной можно непосредственно добраться до объекта 2 и косвенно (через объект 2) до объектов 4, 5, 6, 3. Таким образом, нет способа извлечь информацию из объектов 7 и 8. Если в этот момент запустить сборку мусора, то объекты 7 и 8 будут уничтожены. Если теперь убрать ссылку на объект 1 из значения переменной, то станет недоступным и объект 1. Если же ссылку на объект 1 оставить, но убрать ссылку на объект 2 из значений переменных, то окажутся ненужными все объекты, кроме 1 и 4.

          ЗНАЧЕНИЯ  ПЕРЕМЕННЫХ:
          [* * 1 * * * * * * 2 * * * * *]

          1:[* * * 4]
          2:[4 * * 5]
          3:[* * 5]
          4:[* * *]
          5:[* 6 * 3]
          6:[* * 4 *]
          7:[3 * 8]
          8:[* 7]

Рис.2.1. Объекты и ссылки.

3. Вычисление и анализ объектных выражений

3.1. Результатные выражения

Результатные выражения в языке Рефал являются аналогом общеизвестных арифметических выражений. Так, например, арифметическому выражению X*Y+3 в Рефале Плюс соответствует следующее результатное выражение:

          <"+" <"*" sX sY> 3>

Угловые скобки обозначают вызов функции. Причем первый символ-слово после левой угловой скобки обозначает имя функции, а все остальное соответствует аргументом функции. Благодаря тому, что аргумент функции всегда явно заключается в угловые "функциональные" скобки, отпадает необходимость использовать круглые скобки для группировки операций. Например, выражение X*(A+B) на Рефале записывается как

          <"*" sX <"+" sA sB>>

в то время как выражение X*A+B на Рефале записывается в виде

          <"+" <"*" sX sA> sB>

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

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

          {V1 = Oe1, ..., Vn = Oen}

будет изображать среду, в которой переменные V1, ..., Vn имеют значения Oe1, ..., Oen соответственно.

Ясно, что запись арифметических выражений в виде результатных выражений довольно громоздка, однако, как мы увидим в дальнейшем, у нее есть и определенные преимущества.

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

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

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

А именно, если у нас имеются два результатных выражения Re' и Re'', то запись

          Re' Re''

тоже является результатным выражением, которое означает, что надо вычислить Re' и Re'', а полученные результаты сцепить вместе. Т.е. если результатом вычисления Re' и Re'' являются объектные выражения Oe' и Oe'' соответственно, то результатом вычисления Re' Re'' является объектное выражение Oe' Oe''.

Если у нас имеется результатное выражение Re, то запись

          ( Re )

тоже является результатным выражением, которое означает, что надо вычислить Re, а полученный результат заключить в круглые скобки. Т.е. если результатом вычисления Re является объектное выражение Oe, то результатом вычисления ( Re ) является ( Oe ).

Например, результатом вычисления результатного выражения

          sX '+' sY (eZ)

в среде {sX = 25, sY = 36, eZ = A (B C) D} является объектное выражение

          25 '+' 36 (A (B C) D)

3.2. Переменные

Каждая переменная в Рефале Плюс должна начинаться с признака типа переменной. Признак типа указывает на множество допустимых значений переменной и должен быть одной из четырех букв: s, t, v или e. В соответствии с этим все переменные делятся на четыре категории: s-переменные, t-переменные, v-переменные и e-переменные.

Значениями s-переменных могут быть только символы, значениями t-переменных - только объектные термы, значениями v-переменных - только непустые объектные выражения. Что касается e-переменных, то их значениями могут быть произвольные объектные выражения.

В дальнейшем мы будем говорить, что некоторая переменная является ve-переменной, если она является либо v-переменной, либо e-переменной.

3.3. Форматы функций

С чисто формальной точки зрения все функции в языке Рефал Плюс имеют ровно один аргумент и всегда выдают ровно один результат. Однако, во многих случаях, мы заранее знаем, какую структуру должны иметь аргумент и результат. Например, функция "+" всегда должна получать на входе объектное выражение, состоящее из двух символов и всегда выдает на выходе объектное выражение, состоящее из одного символа.

Ограничения, накладываемые на структуру аргументов и результатов функций, описываются с помощью объявлений функций. Так, например, объявление функции "+" имеет вид:

          $func "+" sX sY = sZ;

В общем случае объявление функции Fname имеет вид

          $func Fname Fin = Fout;

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

Входной и выходной форматы должны быть "жесткими", т.е. на одном уровне скобок может находиться не более чем одна ve-переменная. Например, формат (e)(e) является жестким, а формат e A e - не является.

Все аргументы и результаты функции должны иметь структуру предписанную ее объявлением. Объявление функции должно предшествовать ее первому использованию в каком-либо результатном выражении в программе. При этом, если функция определена в самой программе, ее объявление появляется в тексте программы явно. Если же функция определена в другом модуле, ее объявление должно быть импортировано в программу с помощью директивы $use.

Во время компиляции программы производится проверка того, что во всех вызовах функции структура ее аргумента соответствует ее входному формату. Например, результатное выражение

          <"+" 2 <"+" sX sY>>

построено правильно. По отношению ко внутреннему вызову функции это очевидно, но для того, чтобы проверить корректность наружного вызова, уже требуется привлечь информацию о структуре результата функции "+". А именно, заменяем <"+" sX sY> на выходной формат функции "+", в результате чего получается <"+" 2 s>. Отсюда видно, что аргумент наружного вызова соответствует входному формату функции "+". С другой стороны, если мы напишем в программе результатное выражение

          <"+" 2 <"+" sX sY> 3>

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

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

3.4. Образцы

В языке Рефал Плюс основным средством анализа объектных выражений являются образцы.

Образцы могут содержать символы, круглые скобки и переменные. Например:

          A B C
          tX (eY B)

Каждый образец изображает множество объектных выражений, которые могут быть получены из него путем замены переменных на произвольные значения, удовлетворяющие их типам. Например, образец A eX изображает множество объектных выражений, которые начинаются с символа A, а образец sX sY - множество объектных выражений, состоящих ровно из двух символов.

Если одна и та же переменная входит в образец несколько раз, то все ее вхождения должны иметь одно и то же значение. Например, образец tX tX изображает множество выражений, состоящих из двух одинаковых термов.

Если нам задано объектное выражение Oe и образец P, то всегда можно сопоставить Oe с P и установить, имеет ли Oe структуру, предписанную образцом P. Если да, то мы говорим, что Oe успешно сопоставляется с P, в противном случае мы говорим, что результатом сопоставления является неуспех.

В результате успешного сопоставления Oe с P переменные, входящие в P, связываются с соответствующими частями выражения Oe. Таким образом, результатом сопоставления Oe с P является некоторая среда Env. Например, если мы сопоставим AAA BBB CCC с образцом eX sY, результатом сопоставления будет среда {eX = AAA BBB, sY = CCC}.

Попробуем теперь сопоставить выражение A B C с образцом e1 sX e2. Мы обнаружим, что это можно сделать тремя различными способами, в результате чего получаются три разных среды:

          {e1 = ,    sX = A, e2 = B C}
          {e1 = A,   sX = B, e2 = C}
          {e1 = A B, sX = C, e2 = }

Что считать результатом сопоставления в подобных случаях? В Рефале Плюс эта проблема решается следующим образом. Считается, что правильными являются все варианты сопоставления, однако одни варианты "предшествуют" другим, т.е. имеют приоритет.

А именно, пусть Env1 и Env2 - два варианта сопоставления Oe с P. Рассмотрим все вхождения переменных в P. Если Env1 и Env2 не совпадают, они приписывают некоторым переменным различные значения. Найдем в P самое первое слева вхождение переменной которому Env1 и Env2 приписывают разные значения и сравним длину этих значений. Если значение, приписываемое средой Env1, короче, чем значение, приписываемое средой Env2, то считается, что Env1 "предшествует" Env2, т.е. имеет приоритет перед Env2, в противном случае считается, что Env2 "предшествует" Env1.

Например, сопоставим объектное выражение (A1 A2 A3)(B1 B2) с образцом e1 (eX sA eY) e2. В результате получится следующее множество вариантов сопоставления

     {e1 = , eX = ,      sA = A1, eY = A2 A3, e2 = (B1 B2)}
     {e1 = , eX = A1,    sA = A2, eY = A3,    e2 = (B1 B2)}
     {e1 = , eX = A1 A2, sA = A3, eY = ,      e2 = (B1 B2)}
     {e1 = (A1 A2 A3), eX = ,   sA = B1, eY = B2, e2 = }
     {e1 = (A1 A2 A3), eX = B1, sA = B2, eY = ,   e2 = }

где варианты сопоставления перечислены в соответствии с их приоритетами, т.е. самый первый вариант находится на первом месте и т.д.

Описанный выше способ упорядочения вариантов сопоставления называется сопоставлением слева направо. Однако в Рефале Плюс имеется возможность упорядочивать варианты сопоставления и справа налево, при этом упорядочение происходит не по самому левому вхождению переменной, а по самому правому. Чтобы изменить порядок сопоставления, следует приписать к образцу слева ключевое слово $r. Например, если мы сопоставим объектное выражение (A1 A2 A3)(B1 B2) с образцом $r e1 (eX sA eY) e2, множество вариантов сопоставления будет упорядочено следующим образом:

     {e1 = (A1 A2 A3), eX = B1, sA = B2, eY = ,   e2 = }
     {e1 = (A1 A2 A3), eX = ,   sA = B1, eY = B2, e2 = }
     {e1 = , eX = A1 A2, sA = A3, eY = ,      e2 = (B1 B2)}
     {e1 = , eX = A1,    sA = A2, eY = A3,    e2 = (B1 B2)}
     {e1 = , eX = ,      sA = A1, eY = A2 A3, e2 = (B1 B2)}

3.5. Тропы, хвосты и источники

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

Вычисление тропы выполняется в некоторой среде и приводит к получению некоторого значения.

В Рефале Плюс весьма экономно используются ключевые слова и разделители, в связи с чем могут возникать синтаксические проблемы. Так, например, тропы могут начинаться с результатных выражений. Пусть Q - одна из таких троп, а Re - некоторое результатное выражение. Попробуем записать Q сразу вслед за Re. В результате получается двусмысленная конструкция Re Q в которой невозможно понять, где кончается Re и где начинается Q.

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

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

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

В дальнейшем, при описании Рефала Плюс, мы будем обозначать тропы через Q, хвосты - через R, а источники - через S.

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

3.6. Огражденные тропы

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

          , Q

которая с синтаксической точки зрения является хвостом, а во всех прочих отношениях эквивалентна тропе Q.

3.7. Результатные выражения в качестве источников

Всякое результатное выражение Re является источником, а значит - и тропой. Приписав к нему запятую, получаем хвост

          , Re

Вычисление источников вида Re сводится к вычислению результатного выражения Re. Если при этом получается объектное выражение Oe, то Oe считается результатом источника.

3.8. Правые части

Всякая конструкция вида

          = Q

где Q - некоторая тропа, называется правой частью. С синтаксической точки зрения правые части являются хвостами, а значит - и тропами.

Вычисление правой части = Q сводится к вычислению тропы Q. Если при этом получается объектное выражение Oe, то Oe считается результатом всей правой части.

На первый взгляд кажется, что различие между тропами вида Re и тропами вида = Re - чисто синтаксическое, но это не так. Тонкая разница между ними проявляется в том случае, если вычисление Re приводит к неуспеху, и к этому вопросу мы вернемся позднее.

4. Функции определяемые в программе

4.1. Определения функций

Рефал-программа состоит из определений функций, каждое из которых имеет следующий вид:

          Fname \{ Snt1; Snt2; ... Sntn; };

или

          Fname  { Snt1; Snt2; ... Sntn; };

где Fname - имя функции, а Snt1, Snt2, ..., Sntn - предложения. (Тонкое различие между "\{" и "{" для нас пока не существенно и будет рассмотрено позднее.)

Каждое предложение Sntj имеет вид Pj Rj, где Pj - входной образец предложения, а Rj - хвост предложения.

Определение функции имеет следующий смысл. Предположим, что требуется вычислить вызов функции Fname вида

          <Fname Re>

Тогда первым делом вычисляется результатное выражение Re. Предположим, что в результате этого получилось объектное выражение Oe. Тогда делается попытка сопоставить Oe с входными образцами P1, P2, ..., Pn, пока не найдется такой образец Pj, для которого сопоставление проходит успешно, т.е. имеется хотя бы один вариант сопоставления Oe с P. После этого из всех вариантов сопоставления Oe с P выбирается "самый первый" вариант Env, после чего в среде Env вычисляется хвост Rj. Если при этом получится некоторое объектное выражение Oe', оно и считается результатом вызова функции.

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

     Sumsq(X,Y) = X*X + Y*Y

в то время как на Рефале ее определение принимает следующий вид:

     $func Sumsq sX sY = sZ;

     Sumsq
       {
       sX sY = <"+" <"*" sX sX> <"*" sY sY>>;
       };

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

Если объявление функции имеет вид

          $func Fname Fin = Fout;

то компилятор выполняет проверку, что все входные образцы P1, P2, ..., Pn являются "уточнениями" входного формата Fin, а все хвосты R1, R2, ..., Rn заведомо вырабатывают результаты удовлетворяющие выходному формату Fout.

При записи определений функций разрешается использовать следующие сокращения.

Если в предложении Sntj хвост Rj состоит из одной запятой, его разрешается опускать, в результате чего предложение Sntj принимает вид Pj.

Если определение функции содержит только одно предложение Snt, т.е. имеет вид

          Fname \{ Snt; };

его разрешается записывать в сокращенном виде следующим образом:

          Fname Snt;

Например, определение функции Sumsq может быть записано следующим образом:

     Sumsq  sX sY = <"+" <"*" sX sX> <"*" sY sY>>;

4.2. Локальные переменные

Определим функцию Sq-Sub1, вычитающую из аргумента единицу и возводящую полученное число в квадрат:

          Sq-Sub1(X) = (X-1)*(X-1)

Простейшее определение на Рефале имеет вид:

     $func Sq-Sub1 sX = sZ;

     Sq-Sub1  sX = <"*" <"-" sX 1> <"-" sX 1>>;

Очевидный недостаток такого определения в том, что дважды производятся одни и те же вычисления: а именно, дважды вычисляется выражение <"-" sX 1>. Этого можно избежать посредством введения вспомогательной функции Sq:

     $func Sq-Sub1 sX = sZ;
     $func Sq      sY = sZ;

     Sq-Sub1  sX = <Sq <"-" sX 1>>;
     Sq       sY = <"*" sY sY>;

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

          S :: He R

где S - источник, R - хвост, а He - так называемое "жесткое выражение". Жесткое выражение состоит из символов, скобок и переменных и должно удовлетворять следующим ограничениям. Вопервых He не может содержать два вхождения одной и той же переменной, во-вторых, на каждом уровне скобок может находиться не более одной ve-переменной. Легко видеть, что жесткое выражение Hе является в то же время и форматным выражением, и во время компиляции программы выполняется проверка, что S заведомо вырабатывает результаты, удовлетворяющие формату He.

Тропа S :: He R вычисляется следующим образом. Первым делом вычисляется источник S. Если в результате получается объектное выражение Oe, то переменные из He связываются с соответствующими частями Oe, после чего вычисляется хвост R, и полученный результат считается результатом всей конструкции.

Теперь мы можем записать определение функции Sq-Sub1 следующим образом:

     $func Sq-Sub1 sX = sZ;

     Sq-Sub1  sX =
       <"-" sX 1> :: sY,
         <"*" sY sY>;

Обратите внимание, что при вычислении тропы S :: He R, источник S вычисляется в той среде, в которой находится вся конструкция. После этого среда пополняется значениями переменных из He, после чего хвост R вычисляется уже в новой, исправленной среде. Таким образом, результатом вычисления тропы

     100 :: sX, <"+" sX 1> :: sX = sX

является 101.

В тех случаях, когда жесткое выражение He - пустое, тропа вида S :: R может быть записана в сокращенном виде как S R. Такая конструкция называется условием и обычно применяется в тех случаях, когда требуется вычислить S не для получения какого-то объектного выражения, а ради побочных эффектов, возникающих при вычислении S. Например, в результате вычисления тропы

     <Println "A">, <Println "B">, <Println "C"> =

будет напечатано три строчки, первая из которых будет содержать литеру A, вторая - литеру B, а третья - литеру C.

Если же в присваивании S :: He R хвост R состоит из одной запятой, его можно опустить, в результате чего получается конструкция S :: He.

4.3. Рекурсия

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

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

Рассмотрим, например, следующую задачу. Пусть требуется определить функцию Reverse, которая "переворачивает" выражение, т.е. переставляет термы аргумента в обратном порядке. А именно, если на вход поступает объектное выражение вида

          Ot1 Ot2 ... Otn

где Ot1, Ot2, ..., Otn - некоторые объектные термы, то на выходе должно получиться объектное выражение

          Otn ... Ot2 Ot1

Если бы длина входного выражения была ограничена, например, если бы мы знали, что n<=3, можно было бы разобрать четыре разных случая и написать следующее определение функции:

     $func Reverse e.Exp = e.Exp;

     Reverse
       {
       = ;
       t1 = t1;
       t1 t2 = t2 t1;
       t1 t2 t3 = t3 t2 t1;
       };

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

Можно, однако, преодолеть это затруднение с помощью рекурсии. В данном случае можно рассуждать следующим образом. Рассмотрим входное выражение

          Ot1 Ot2 ... Otn

Если n=0, то результатом должно быть пустое выражение. Если же n>=1, то можно свести исходную задачу к более простой: отбросить первый терм входного выражения, получив выражение длины n-1,

          Ot2 ... Otn

и перевернуть это более короткое выражение. Получится

          Otn ... Ot2

Теперь ясно, что если к этому выражению приписать справа Ot1, мы как раз и получим желаемый результат

          Otn ... Ot2 Ot1

Эти рассуждения приводят нас к следующему рекурсивному определению функции Reverse

     Reverse
       {
       = ;
       t.X e.Rest = <Reverse e.Rest> t.X;
       };

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

     Reverse
       {
       = ;
       e.Rest t.X = t.X <Reverse e.Rest>;
       };

Нетрудно заметить также, что в действительности сущность решения состоит в том, что мы разбиваем исходное выражение Oe на два непустых выражения Oe1 и Oe2 меньшего размера, таких, что

          Oe = Oe1 Oe2

Теперь мы можем перевернуть каждое из выражений Oe1 и Oe2 по-отдельности. Пусть при этом получатся выражения Oe1' и Oe2' соответственно. Тогда ясно, что

          Oe2' Oe1'

равно результату обращения исходного выражения Oe.

Если Рефал реализован на многопроцессорной машине таким образом, что обращение выражений Oe1 и Oe2 можно выполнять одновременно, оказывается, что выгодно, чтобы Oe1 и Oe2 были приблизительно одинаковой длины. Тогда получаем следующий вариант описания функции, в котором используются библиотечные функции из модулей ACCESS и ARITHM:

     $func Reverse e.Exp = e.Exp;

     Reverse
       {
       = ;
       t1 = t1;
       eX,
         <Length e.X> :: sLen,
         <Div sLen 2> :: sDiv,
         = <Reverse <Middle sDiv 0 eX>>
           <Reverse <Left   0 sDiv eX>>;
       };

5. Неуспехи и аварии

5.1. Неуспех при вычислении результатных выражений и троп

До сих пор мы считали, что результатом вычисления тропы Q является некоторое объектное выражение Oe. В действительности, однако, это вычисление может закончиться неуспехом или аварией.

В случае неуспеха результатом вычисления является особое значение, "неуспех", которое не является объектным выражением.

Простейший способ породить неуспех - это вычислить хвост вида

          $fail

В случае аварии результатом вычисления является особое значение, которое не является объектным выражением и имеет вид $error(Oe), где Oe - некоторое объектное выражение, которое является сообщением об ошибке. Обычно Oe начинается с символа-слова, являющегося именем функции, во время работы которой возникла авария. Например, если мы попытаемся вычислить вызов функции

          <DIV 10 0>

возникнет авария "деление на ноль", а результатом вычисления этого вызова будет

          $error(DIV "Divide by zero")

Значения вида $error(Oe) обладают следующим свойством. Пусть нам требуется вычислить некоторую конструкцию. Тогда, если при вычислении некоторой составной части этой конструкции получается результат $error(Oe), дальнейшее вычисление конструкции прекращается и результатом вычисления всей конструкции считается $error(Oe). Единственным исключением из этого правила является конструкция $trap, специально предназначенная для "перехвата" аварий.

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

5.2. Перестройки

Рассмотрим следующую задачу: пусть нам задано некоторое объектное выражение Oe, которое заведомо содержит на нулевом уровне не менее двух символов-литер '+'. Требуется разбить это выражение Oe на три части OeX, OeA и OeY, такие, что Oe = OeX '+' OeA '+' OeY, и при этом OeX и OeY не содержат '+' на нулевом уровне скобок. Функцию, решающую данную задачу назовем "++". Тогда, например

          <"++" 'AAA+BBB+CCC+DDD+EEE'> => 
               ('AAA')('BBB+CCC+DDD')('EEE')

Таким образом, требуется найти в Oe самый левый '+' и самый правый '+'. Самый левый '+' легко найти с помощью сопоставления Oe с образцом $l eX '+' eP, а самый правый - с помощью сопоставления с образцом $r eQ '+' eY. Внутри одного образца сопоставление выполняется либо слева направо, либо справа налево, поэтому мы не можем объединить эти два образца в один, и вынуждены выполнять сопоставление в два приема. Таким образом, мы можем решить задачу следующим образом:

     $func "++"    eZ       = (eX)(eA)(eY); 
     $func "++Aux" (eX)(eP) = (eX)(eA)(eY);

     "++"     $l eX '+' eP = <"++Aux" (eX)(eP)>; 
     "++Aux"  $r (eX)(eA '+' eY) = (eX)(eA)(eY);

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

Перестройками называются тропы вида

          S : Snt

где S - источник, а Snt - предложение вида P R, состоящее из образца P и хвоста R.

Если хвост R состоит из одной запятой, его разрешается опускать, в результате чего перестройка принимает вид S : P.

Вычисление перестроек производится следующим образом. Сначала вычисляется S. Если получится неуспех, то результатом всей перестройки считается неуспех. Если же в результате вычисления S получится объектное выражение Oe, то Oe сопоставляется с образцом P. При этом, на рассматриваемые варианты сопоставления накладывается дополнительное ограничение: если в той среде, в которой вычисляется перестройка, значения некоторых переменных уже определены, то рассматриваются только те варианты сопоставления, для которых эти переменные сохраняют прежние значения.

Например, если переменная sX уже имеет значение 1, то в результате сопоставления объектного выражения 1 2 1 2 с образцом eA sX eB получатся только два варианта сопоставления

          {eA = , sX = 1, eB = 2 1 2}
          {eA = 1 2, sX = 1, eB = 2}

а не четыре.

Пусть теперь Env1, Env2, ..., Envn - все получившиеся варианты сопоставления, перечисленные в соответствии с порядком, введенным ранее для вариантов сопоставления. Далее делается попытка вычислить R, используя значения переменных из первого варианта сопоставления. Если результатом вычисления R является объектное выражение Oe, оно и считается результатом перестройки. Если же вычисление хвоста R завершилось неуспехом , то этот неуспех "перехватывается", т.е. самый первый вариант сопоставления отбрасывается и делается попытка точно так же вычислить R для оставшихся вариантов сопоставления.

Если для всех вариантов сопоставления результатом вычисления хвоста R является неуспех, то и результатом всей перестройки является неуспех.

Например, вычисление тропы

          'ABC' : $r e1 sX e2, <Print sX> $fail

приведет к тому, что будет напечатанa последовательность литер 'CBA', после чего вычисление тропы завершится с результатом "неуспех".

Теперь мы можем дать новое определение функции "++", не использующее вспомогательную функцию "++Aux":

     $func "++"  eZ = (eX)(eA)(eY);

     "++" 
       $l eX '+' eP, 
         eP : $r eA '+' eY 
           = (eX)(eA)(eY);

5.3. Перехват неуспехов

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

Отрицаниями условий называются тропы вида

          # S R

где S - источник, а R - хвост. Если хвост R состоит из одной запятой, его разрешается опускать, в результате чего отрицание условия принимает вид # S.

С синтаксической точки зрения любое отрицание условия является хвостом.

Вычисление таких хвостов производится следующим образом. Первым делом делается попытка вычислить источник S. Если в результате этого получается пустое объектное выражение, результатом всего хвоста является неуспех. Если же результатом вычисления источника S является неуспех, то вычисляется хвост R, и то, что получится, считается результатом всей конструкции.

Распутьями называются тропы вида

          \{ Q1; Q2; ... Qn; }

где Q1, Q2, ..., Qn - некоторые тропы. С синтаксической точки зрения любое распутье является источником.

Вычисление распутья происходит следующим образом. Первым делом делается попытка вычислить тропу Q1. Если в результате этого получается объектное выражение Oe, оно считается результатом всего распутья. Если же результатом вычисления тропы Q1 является неуспех, то делается попытка вычислить \{Q2; ..., Qn;}, и то, что получится, является результатом всего распутья. Таким образом, распутье "перехватывает" неуспехи.

Если результатом вычисления всех троп является неуспех, то и результатом всего распутья является неуспех.

Рассмотрим, например, тропу

          1 :: sX,
          \{ sX : 0 = 1; sX : 1 = 0; }

Она вычисляется следующим образом. Первым делом выполняется определение локальной переменной 1 :: sX, в результате чего sX получает значение 1. После этого делается попытка вычислить первую тропу распутья, т.е. sX : 0 = 1. При попытке выполнить сопоставление sX : 0 выясняется, что сопоставление проходит неуспешно, поэтому результатом этой тропы является неуспех. Вследствие этого делается попытка вычислить следующую тропу sX : 1 = 0, в результате чего получается результат 0, который и является результатом вычисления всей тропы.

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

          { Q1; Q2; ... Qn; }

Его отличие от предыдущего варианта проявляется в том, что если результатом вычисления всех троп является неуспех, то результатом вычисления распутья является ошибка $error(Fname "Unexpected fail"), где Fname - имя функции, в которой находится распутье.

Таким образом, мы можем считать, что пара скобок \{ ... } "прозрачна" для неуспехов, в то время как пара скобок { ... } для них "непрозрачна", ибо неуспех не может "выскочить" из распутья { Q1; Q2; ... Qn; }.

Довольно часто встречаются тропы следующего вида:

          S : Ve, \{Ve : Snt1; Ve : Snt2; ..., Ve : Sntn;}
          S : Ve,  {Ve : Snt1; Ve : Snt2; ..., Ve : Sntn;}

где Ve - некоторая e-переменная, которая больше нигде в определении функции не используется, а каждое из предложений Sntj имеет вид Pj Rj. Для таких троп предусмотрена, соответственно, следующая сокращенная форма записи:

          S : \{Snt1; Snt2; ... Sntn;}
          S :  {Snt1; Snt2; ... Sntn;}

называемая выбором, при этом конструкции \{Snt1; Snt2; ... Sntn;} и {Snt1; Snt2; ... Sntn;} называются образцовыми распутьями.

Хвосты Rj, состоящие из одной запятой, разрешается опускать, в результате чего соответствующие предложения Pj Rj принимают вид Pj.

Так, например, распутье { sX : 0 = 1; sX : 1 = 0; } более кратко записывается в виде выбора sX : { 0 = 1; 1 = 0; }, а распутье \{ sX : A,; sX : B,; } может быть сокращено до sX : \{ A; B; }

С синтаксической точки зрения, все выборы являются источниками, что позволяет записывать, например, присваивания следующего вида:

          sX : { 0 = 1; 1 = 0; } :: sY = <"+" sX sY>

При этом сначала вычисляется источник sX : {0 = 1; 1 = 0;}, затем полученный результат присваивается переменной sY, после чего вычисляется тропа = <"+" sX sY>.

5.4. Управление перехватом неуспехов

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

Заборами называются хвосты вида \? Q , а отсечениями - хвосты вида \! Q .

Заборы и отсечения являются пометками в программе, позволяющими управлять распространением неуспехов. А именно, всякое отсечение \! Q должно находиться внутри некоторого забора \? ... \! Q ... . Вычисление отсечения \! Q производится следующим образом. Первым делом вычисляется тропа Q. Если это вычисление завершается с некоторым результатом X, этот результат считается результатом всей конструкции \? ... \! Q ... .

В частности, если X - неуспех, то неуспехом заканчивается и вычисление всей конструкции \? ... \! Q ... .

Рассмотрим пример, иллюстрирующий использование заборов и отсечений. Предположим, что мы пытаемся вычислить следующую тропу:

          eA : e1 '+' e2 '-' e3
            = (e1)(e2)(e3)

Если значение переменной eA содержит '+' а вслед за ним - '-' на нулевом уровне скобок, то в результате сопоставления с образцом будут найдены самый левый '+' и ближайший за ним '-', после чего вычисление тропы успешно завершается. Теперь рассмотрим случай, когда eA содержит '+' на нулевом уровне, но не содержит на нулевом уровне ни одного '-'. Тогда первым делом будет найден первый '+', а затем будет просмотрена вся оставшаяся часть выражения, чтобы найти '-'. Поскольку это сделать не удастся, будет выполнено удлинение значения переменной e1, после чего снова будет выполнен поиск '-' в оставшейся части выражения. Между тем, этого можно было бы и не делать, ибо если '-' не нашелся первый раз, он заведомо не найдется и во второй раз.

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

          eA : e1 '+' еX, 
            eX : e2 '-' e3 
              = (e1)(e2)(e3)

Теперь, если сопоставление значения eX с образцом e2 '-' e3 завершается неуспешно, делается попытка испробовать следующий вариант сопоставления для eA : e1 '+' еX. Этого, однако, можно избежать добавив \? и \! следующим образом:

          \? eA : e1 '+' еX 
            \! eX : e2 '-' e3 
              = (e1)(e2)(e3)

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

5.5. Смысл правых частей

Правые части, имеющие вид = Q , где Q - некоторая тропа, являются еще более мощным средством ограничения перебора, чем заборы и отсечения.

Чтобы объяснить смысл правых частей, нам придется предварительно ввести некоторые понятия.

Пусть какая-то конструкция входит в качестве составной части в некоторую другую конструкцию. Мы будем говорить, что эта внутренняя конструкция является вассалом, если результат ее работы, согласно семантике языка, считается результатом работы объемлющей конструкции. Например, в тропе S :: He R хвост R является вассалом, ибо результат вычисления R считается результатом вычисления всей конструкции.

Если некоторая конструкция не является вассалом объемлющей конструкции, мы будем говорить, что она является сувереном. Например, в тропе S :: He R источник S является сувереном, ибо его результат не считается результатом всей конструкции (хотя и может использоваться в R).

А именно, если определение функции имеет вид Fname Palt , то образцовое распутье Palt является сувереном.

Если тропа имеет один из следующих видов: S R , S :: He R , S : P R или # S R , то источник S является сувереном.

Если источник имеет вид S : Palt , то источник S является сувереном.

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

Теперь мы можем описать семантику правых частей.

Пусть покровителем правой части = Q является некоторая объемлющая конструкция ... = Q ... . Тогда первым делом вычисляется тропа Q. Если это вычисление завершилось с некоторым результатом X, то X считается результатом всего покровителя ... = Q ... .

В частности, если X - неуспех, то и значением покровителя ... = Q ... будет неуспех, даже если внутри него расставлены ловушки, предназначенные для перехвата неуспехов.

Например, результатом вычисления тропы

          \{ A B C : $l e sX e, sX : B, sX} :: sY, sY

будет символ B, ибо sX принимает значение A, сопоставление которого с символом B терпит неуспех, в результате чего sX принимает новое значение B, и вычисление успешно завершается. Но если мы заменим запятую на равенство, мы получим тропу

          \{ A B C : $l e sX e = sX : B, sX} :: sY, sY

вычисление которой терпит неудачу.

На использование заборов, отсечений, и правых частей накладываются некоторые ограничения.

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

На пути от \! к соответствующему ему \? не должно быть ни одного = .

5.6. Откатные и безоткатные функции

Все функции, определяемые и используемые в программе на Рефале Плюс делятся на две категории: откатные и безоткатные.

Если функция Fname - безоткатная, то вычисление вызова <Fname Re> не может закончиться получением неуспеха. Если же функция Fname - откатная, то вычисление вызова <Fname Re> вообще говоря может закончиться получением неуспеха в качестве результата.

До сих пор мы считали, что объявления функций имеют вид

          $func  Fname Fin = Fout;

однако это верно только в том случае, если функция Fname - безоткатная. Если же Fname - откатная, ее объявление должно иметь вид

          $func? Fname Fin = Fout; 

Теперь мы можем более точно описать семантику определений функций. Пусть определение функции Fname имеет вид

          Fname Palt

где Palt - образцовое распутье вида \{P1 R1; P2 R2; ... Pn Rn;} или {P1 R1; P2 R2; ... Pn Rn;}, и пусть требуется вычислить ее вызов <Fname Re>. Тогда прежде всего вычисляется результатное выражение Re. Если при этом получается неуспех, то вызов функции Fname не выполняется и считается, что результатом вычисления <Fname Re> является неуспех. Предположим теперь, что в результате вычисления Re получилось объектное выражение Oe. Тогда выполняется вызов функции, а именно, вычисляется источник

          Oe : Palt

в пустой среде, т.е. в среде, в которой ни одна переменная не имеет значения. Пусть в результате этого получилось значение X.

Если X - объектное выражение, то X считается результатом вызова <Fname Re>. Если же X является неуспехом, то дальнейшие действия зависят от того, является ли функция Fname откатной.

Если Fname - откатная, и X является неуспехом, то результатом вызова <Fname Re> считается неуспех.

Если Fname - безоткатная, и X является неуспехом, то этот неуспех "перехватывается" и преобразуется в ошибку $error(Fname "Unexpected fail").

6. Логические условия

6.1. Проверки и предикаты

В некоторых случаях в процессе работы программы требуется проверить справедливость некоторого условия и, в зависимости от результатов проверки, направить вычисления либо по одному, либо по другому пути. При программировании на Рефале Плюс мы будем придерживаться следующего соглашения. Тропа Q будет называться условием, если результатом ее вычисления является либо пустое объектное выражение, либо неуспех. Если результат - пустое выражение, мы считаем, что условие выполнено, а если результат - неуспех, мы считаем, что условие не выполнено. Таким образом, пустой результат означает, что результат проверки - "истина", а неуспех означает, что результат проверки - "ложь".

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

Некоторые функции входящие в библиотеку функций используются только для проверки условий. Такие функции называются предикатами. В Рефале Плюс функции-предикаты выдают пустое выражение, если их аргументы удовлетворяют условию и выдают неуспех в случае, если их аргументы не удовлетворяют условию. Например, функция "<" проверяет, что ее первый аргумент меньше второго. А именно, результатом вычисления вызова вида <"<" (Oe1)(Oe2)> является пустое выражение, если объектное выражение Oe1 "меньше" чем объектное выражение Oe2. Если же это не так - результатом является неуспех.

Если в программе определяется некоторая функция-предикат, ее объявление должно иметь следующий вид:

          $func? Fname Fin = ;

Дальше мы рассмотрим различные способы использования и комбинирования условий.

6.2. Ветвления

Пусть у нас имеется условие, заданное источником S и две тропы Q' и Q". Рассмотрим тропу

          \? {S \! Q'; \! Q";}

Тогда, если результат вычисления S - пустое выражение, то вычисляется тропа Q', и то, что получится, является результатом всей конструкции. Если же результат вычисления источника S - неуспех, то вычисляется тропа Q", и то, что получится, является результатом всей конструкции.

Следует обратить внимание на использование отсечений \! . Они существенны в том случае, если вычисление Q' или Q" заканчивается неуспехом. Предположим, что они убраны, в результате чего тропа приобретает следующий вид:

          { S, Q'; Q";}

Тогда, если условие S выполнено, производится вычисление тропы Q'. Предположим, однако, что вычисление тропы Q' заканчивается неуспехом. Тогда этот неуспех не будет выдан в качестве результата всей конструкции, а будет перехвачен, что приведет к вычислению тропы Q". В данном случае это совсем не то, что нам было нужно. Таким образом, первое отсечение необходимо, чтобы предотвратить "перескок" на следующую тропу в распутье.

Теперь рассмотрим случай, когда условие S не выполнено, т.е. результатом вычисления S является неуспех. В этом случае неуспех перехватывается и начинается вычисление тропы Q". Предположим, что вычисление тропы Q" завершается неуспехом. В этом случае неуспех перехватывается и делается попытка вычислить следующую тропу в распутье. Но, поскольку следующей тропы нет, возникает ситуация ошибки, а это опять таки не то, что мы хотели!

Если ветвление имеет вид

          \? {S \! = Q'; \! = Q";}

его можно записать более кратко следующим образом:

          { S = Q'; = Q";}

(что мы и будем часто делать в дальнейшем).

Рассмотрим следующий пример. Определим функцию Min-Oe, которая сравнивает два объектных выражения Oe1 и Oe2 и выдает Oe1, если Oe1 предшествует Oe2. Если же Oe1 равно Oe2 или Ое2 предшествует Oe1, то Min-Oe выдает Oe2.

     $func Min-Oe (eX)(eY) = e.Min-X-Y;

     Min-Oe  (eX)(eY) =
       {
       <"<" (eX)(eY)>
         = eX;
         = eY;
       };

Теперь рассмотрим случай, когда условие задано тропой Q и нужно вычислить тропу Q', если условие выполнено, либо тропу Q", если условие не выполнено. Этого можно достичь, заключив Q в фигурные скобки и превратив его в источник \{ Q; }. После этого ветвление может быть записано следующим образом.

     \? { \{Q;} \! Q'; \! Q";}

6.3. Логические связки

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

* Логическое "И"

Пусть у нас имеются два условия и требуется проверить, что они оба выполнены.

Если оба условия заданны тропами: Q' и Q" достаточно вычислить тропу

          \{ Q';}, Q"

Если первое условие задано источником S, второе - тропой Q достаточно вычислить тропу S, Q.

И наконец, если оба условия заданы результатными выражениями Re' и Re", достаточно вычислить результатное выражение Re' Re".

* Логическое "ИЛИ"

Пусть у нас имеются два условия и требуется проверить, что хотя бы одно из них выполнено.

Если оба условия заданны тропами: Q' и Q" достаточно вычислить тропу

          \{ Q'; Q"; }

* Логическое "НЕ"

Пусть у нас имеется условие заданное тропой Q и требуется проверить, что оно не выполнено. Этого можно достичь, вычислив тропу

          # \{Q;}

которая является сокращенной записью для тропы # \{Q;}, .

Если же условие задано источником S, достаточно вычислить тропу

          # S

которая является сокращенной записью для тропы # S , .

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

6.4. Пример: программа дифференцирования

Опишем функцию, которая будет выполнять символьное дифференцирование формул [Хен 83]. Чтобы не загромождать изложение мы будем рассматривать только простые формулы, в которые входят целые числа, переменные, а также операции + и *, хотя обобщить рассмотрение на случай более сложных формул не составило бы большого труда.

Будем обозначать через x и y произвольные переменные, через i - произвольное целое число, через e - произвольную формулу, а через Dx(e) - результат дифференцирования e по x. Тогда правила дифференцирования можно записать в виде

     Dx(x)          =    1
     Dx(y)          =    0              (где y не равно x)
     Dx(i)          =    0
     Dx(e1 + e2)    =    Dx(e1) + Dx(e2)
     Dx(e1 * e2)    =    e1 * Dx(e2) + e2 * Dx(e1)

Прежде чем писать программу дифференцирования, нужно выбрать для формул представление в виде объектных выражений. Обозначим через [e] представление формулы e. Выберем следующее представление

     [x]            =    x
     [i]            =    i
     [e1 + e2]      =    (Sum  [e1] [e2])
     [e1 * e2]      =    (Prod [e1] [e2])

Теперь не составляет труда определить функцию Diff, первым аргументом которой является переменная, по которой надо дифференцировать, а вторым аргументом - формула, подлежащая дифференцированию. Результатом работы является продифференцированная формула.

     $func Diff sX tE = tE;

     Diff  sX tE =
       tE :
       {
       sX = 1;
       sY = 0;
       (s.Oper t.E1 t.E2) =
         <Diff sX tE1> :: t.DxE1,
         <Diff sX tE2> :: t.DxE2,
         s.Oper :
         {
         Sum   = (Sum t.DxE1 t.DxE2);
         Prod  = (Sum (Prod t.E1 t.DxE2) (Prod t.E2 t.DxE1));
         };
       };

Это определение функции Diff страдает очевидным недостатком: формулы, которые получаются в результате дифференцирования, содержат слишком много частей, которые можно сократить. Например

          DX(3*(X*X)+5)  =  (3*((X*1)+(X*))+(X*X)*0)+0

в соответствии с приведенными выше правилами дифференцирования. Между тем, после очевидных упрощений эту формулу можно привести к виду

          3*(X+X)

Для этого достаточно применить к формуле следующие правила преобразования:

          0 + e2     ==>   e2
          e1+ 0      ==>   e1
          0 * e2     ==>   0
          e1* 0      ==>   0
          1 * e2     ==>   e2
          e1* 1      ==>   e1

(Более сложные преобразования мы не рассматриваем, чтобы не загромождать изложения.)

Существует два способа реализовать эти упрощения. Можно сначала построить результат дифференцирования полностью, а затем анализировать его, пытаясь сделать упрощения. Другой способ - делать упрощения сразу же, в процессе дифференцирования. Мы поступим именно так.

Определим функции Sum и Prod. Эти функции будут получать на входе две формулы, и выдавать формулу, которая является их суммой или произведением соответственно. При этом будут сразу же делаться упрощающие преобразования.

     $func Sum  t1 t2 = t;
     $func Prod t1 t2 = t;

     Sum
       {
       0  t2 = t2;
       t1 0  = t1;
       t1 t2 = (Sum t1 t2);
       };

     Prod
       {
       0  t2 = 0;
       1  t2 = t2;
       t1 0  = 0;
       t1 1  = t1;
       t1 t2 = (Prod t1 t2);
       };

Теперь переделаем определение функции Diff, вставив в соответствующие места вызовы функций Sum и Prod.

     Diff  sX tE =
       tE :
       {
       sX = 1;
       sY = 0;
       (s.Oper t.E1 t.E2) =
         <Diff sX tE1> :: t.DxE1,
         <Diff sX tE2> :: t.DxE2,
         s.Oper :
         {
         Sum   = <Sum t.DxE1 t.DxE2>;
         Prod  = <Sum <Prod t.E1 t.DxE2> <Prod t.E2 t.DxE1>>;
         };
       };

6.5. Пример: сравнение множеств

В качестве примера использования логических связок и рекурсии рассмотрим следующую задачу.

Как известно из теории множеств, два множества считаются равными, если они состоят из одних и тех же элементов. Предположим, что мы хотим запрограммировать на Рефале операцию сравнения конечных множеств на равенство. Для этого прежде всего следует придумать какой-то способ изображения множеств в виде объектных выражений. Сначала рассмотрим множества, элементами которых могут быть только символы (в смысле Рефала). Тогда множество символов {Os1, Os2, ..., Osn} можно изобразить в виде объектного выражения

          Os1 Os2 ... Osn

При этом оказывается, что одному и тому же множеству могут соответствовать несколько его изображений. Например, множество {John, Mary} можно изобразить как в виде выражения John Mary, так и в виде выражения Mary John , или даже в виде Mary John John Mary . Таким образом, неравные выражения могут изображать равные множества.

Как известно, элементы множеств сами могут быть множествами. Поэтому мы теперь несколько усложним нашу задачу. Предположим, что рассматриваемые нами множества могут содержать в качестве элементов как символы, так и множества (которые, в свою очередь снова могут содержать множества и т.д.). Теперь мы должны как-то изобразить те элементы множества которые сами являются множествами.

Мы поступим следующим образом. Если элемент множества - символ Os, мы будем его изображать в виде символа Os. Если же элемент множества - множество X, мы будем изображать его в виде терма вида (X'), где X' - изображение множества X. Таким образом, множество {A, {A,B}, {A}} можно изобразить, например, в виде выражения A (A B) (A) .

Теперь постараемся определить функцию-предикат Eqset? , которая будет определять, являются ли два ее аргумента представлениями одного и того же множества. Для этого мы постараемся разложить понятие равенства множеств на более простые понятия.

А именно, два множества A и B равны в том и только том случае, если A является подмножеством B и B является подмножеством A. Далее, множество A является подмножеством множества B в том и только том случае, если для любого элемента X множества A верно, что X принадлежит B.

Поэтому мы определим не одну, а четыре функции-предиката: Eqset? будет проверять, что ее аргументы представляют одно и то же множество, Subset? будет проверять, что множество, представляемое первым аргументом, является подмножеством множества, представляемого вторым аргументом, El? будет проверять, что ее первый аргумент представляет элемент, входящий в множество, представляемое вторым аргументом, а Eqel? будет проверять, что ее аргументы представляют один и тот же элемент множества.

Интересно отметить, что если два элемента множества сами являются множествами, то их сравнение приводит к необходимости сравнивать два множества, поэтому функция Eqel? вынуждена вызвать функцию Eqset? . Таким образом, оказывается, что функция Eqset? в конечном итоге рекурсивно определяется через себя.

     $func? Eqset?  (eA)(eB) = ;
     $func? Subset? (eA)(eB) = ;
     $func? El?     tX  (eA) = ;
     $func? Eqel?   tX  tY   =;

     Eqset?  (eA)(eB) =
       <Subset? (eA)(eB)><Subset? (eB)(eA)>;

     Subset?  (eA)(eB) =
       eA :
       {
       = ;
       tX eR = <El? tX (eB)><Subset? (eR)(eB)>;
       };

     El?  tX (eA) =
       eA : tY eR,
       \{ <Eqel? tX tY>; <El? tX (eR)>; };

     Eqel?  tX tY =
       \{
       tX tY : s s
         = tX : tY;
       tX tY : (eA)(eB)
         = <Eqset? (eA)(eB)>;
       };

7. Использование селекторов прямого доступа

Одним из типичных случаев, когда требуется прямой доступ к частям выражения, являются алгоритмы, основанные на методе "разделяй и властвуй". Этот метод заключается в том, что исходная задача разбивается на подзадачи меньшего размера и решается для этих подзадач. Затем решение исходной задачи получается исходя из решений подзадач. Как правило, принцип "разделяй и властвуй" применяется совместно с принципом балансировки, гласящим, что исходную задачу следует разбивать на подзадачи примерно равного размера [АХУ 79].

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

Одним из способов решения этой задачи является сортировка слиянием [АХУ 79], когда исходное множество чисел S разбивается на два непересекающихся множества S1 и S2 примерно равного размера. Затем S1 и S2 упорядочиваются независимо друг от друга. В результате получаются две упорядоченные последовательности чисел Q1 и Q2, которые соединяются (сливаются) в одну упорядоченную последовательность Q, которая и является решением исходной задачи.

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

     $func MSort eS = eS;
     $func Merge (eX)(eY) = eZ;

     MSort  eS =
       <Length eS> :: sLen,
       {
       <"<=" (sLen) (1)>
         = eS;
         = <Div sLen 2> :: sK,
           <Left 0 sK eS> :: eS1,
           <Middle sK 0 eS> :: eS2,
             <Merge ( <MSort eS1> )( <MSort eS2> )>;
       };

Теперь определим функцию Merge, которая получает на входе две упорядоченные последовательности и объединяет их в одну упорядоченную последовательность.

     Merge  (eX)(eY) =
       {
       eX :
         = eY;
       eY :
         = eX;
       (eX)(eY) : (sA eXRest)(sB eYRest)
         = {
           <"<=" (sA)(sB)>
             = sA <Merge (eXRest)(eY)>;
             = sB <Merge (eX)(eYRest)>;
         };
       };

8. Функции выдающие несколько результатов

8.1. Сквозной просмотр выражений

Рассмотрим несколько примеров, демонстрирующих полезность функций выдающих несколько результатов.

Предположим, что требуется определить функцию NMB, заменяющую все символы выражения на их порядковые номера. Например

     <NMB A (B A) C A>   =>   1 (2 3) 4 5

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

     $func NMB      e.Exp    = e.Exp;
     $func NMB-Exp  e.Exp sN = e.Exp sN;
     $func NMB-Term t.Exp sN = t.Exp sN;

     NMB  e.Exp =
       <NMB-Exp e.Exp 1> :: e.Exp s,
         e.Exp;

     NMB-Exp  e.Exp sN =
       e.Exp :
       {
       = sN;
       tX e.Rest =
         <NMB-Term tX sN> :: tX sN,
         <NMB-Exp e.Rest sN> :: e.Rest sN,
           tX e.Rest sN;
       };

     NMB-Term  tX sN =
       tX :
       {
       s =
         sN <"+" sN 1>;
       (eE) =
         <NMB-Exp eE sN> :: eE sN,
           (eE) sN;
       };

8.2. Быстрая сортировка

Следующий пример - так называемая быстрая сортировка [АХУ 79], сущность которой заключается в следующем.

Пусть требуется отсортировать множество целых чисел S. Выберем из S произвольное число X и разобьем S на три подмножества S1, S1 и S3, такие, что S1 содержит числа, которые меньше X, S2 содержит числа, равные X, а S3 содержит числа, которые больше X. Отсортируем S1, S2 и S3, пусть при этом получились упорядоченные последовательности Q1, Q2 и Q3 (сортировка множества S2 - тривиальна, ибо все его элементы равны X). Тогда мы можем соединить Q1, Q2 и Q3 в новую последовательность Q1 Q2 Q3, которая и будет решением исходной задачи.

Определим функцию QSort, которая будет сортировать поданную на вход последовательность описанным выше методом. Для разбиения исходного множества чисел на три части используется функция Split.

     $func QSort  eS = eQ;
     $func Split  sX eS = (eS1)(eS2)(eS3);
     $func Split-Aux  sX (eS1)(eS2)(eS3) eS = (eS1)(eS2)(eS3);

     QSort  eS =
       {
       eS :
         = ;
       eS : t
         = eS;
       eS : sX e
         = <Split sX eS> :: (eS1)(eS2)(eS3),
             <QSort eS1> eS2 <QSort eS3>;
       };

     Split  sX eS =
         <Split-Aux sX ()()() eS>;

     Split-Aux  sX (eS1)(eS2)(eS3) eS =
       eS :
       {
       =
         (eS1)(eS2)(eS3);
       sY eRest =
         {
         <"<" (sY)(sX)>
           = <Split-Aux sX (eS1 sY)(eS2)(eS3) eRest>;
         <">" (sY)(sX)>
           = <Split-Aux sX (eS1)(eS2)(eS3 sY) eRest>;
           = <Split-Aux sX (eS1)(eS2 sY)(eS3) eRest>;
         };
       };

9. Итеративные циклы

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

          S" $iter S' :: He R

и синтаксически является тропой. При этом, источники S" и S' являются суверенами, а хвост R - вассалом (что существенно, если они содержат правые части вида = Q ).

Если хвост R состоит из одной запятой, его разрешается опускать. Также, если жесткое выражение He - пустое, его разрешается опускать вместе с ключевым словом "::".

Тропа-поиск вводит новые локальные переменные (так же, как и тропа-присваивание S :: He R ). Начальные значения этих переменных получаются путем вычисления источника S". Затем делается попытка вычислить хвост R. Если она завершается успешно, то полученный результат считается результатом всей конструкции. Если же вычисление хвоста R кончается неуспехом, то вычисляются новые значения для переменных, входящих в He (для этого вычисляется источник S', причем при этом используются старые значения переменных). Далее делается новая попытка вычислить хвост R и т.д.

Таким образом, тропа-поиск как бы пытается подобрать для переменных из He такие значения, при которых вычисление хвоста R успешно завершится.

Точный смысл конструкции поиска проще всего можно определить через смысл более простых конструкций: присваивания и распутья. А именно, поиск S" $iter S' :: He R эквивалентен тропе

          S" :: He, \{ R; S' $iter S' :: He R; }

Эта тропа опять содержит конструкцию поиска, которую можно "развернуть" с помощью точно такого же преобразования. Получаем

          S" :: He, \{ R;
               S' :: He, \{ R;
                    S' $iter S' :: He R;
          };}

повторив этот процесс бесконечное число раз, получаем, что исходная конструкция поиска эквивалентна бесконечной конструкции

          S" :: He, \{ R;
               S' :: He, \{ R;
                    S' :: He, \{ R;
           ...
           ... };};}

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

     $func Fact sN = sFact;

     Fact
       {
       0 = 1;
       sN = <"*" sN <Fact <"-" sN 1>>>;
       };

Недостаток этого рекурсивного определения в том, что происходит накопление вызовов функции "*", ожидающих пока рекурсия развернется до конца. Можно дать "более итеративное" определение функции Fact (при этом потребуется вспомогательная функция FactAux).

     $func Fact sN = sFact;
     $func Fact-Aux sR sK = sFact;

     Fact  sN =
       <Fact-Aux 1 sN>;

     Fact-Aux  sR sK =
       {
       sK : 0
         = sR;
         = <Fact-Aux <"*" sR sK> <"-" sK 1>>;
       };

То же самое изображается с помощью конструкции поиска следующим образом.

     $func Fact sN = sFact;

     Fact  sN =
       1 sN
         $iter <"*" sR sK> <"-" sK 1>
           :: sR sK,
       sK : 0,
         = sR;

10. Перебор с возвратом

10.1. Задача о ферзях

Рассмотрим классическую задачу о восьми ферзях [Хен 83]. Как известно, в шахматах ферзи атакуют друг друга по горизонтали, по вертикали или по диагоналям шахматной доски. Задача состоит в том, чтобы найти такое размещение 8 ферзей на доске 8х8, чтобы никакие два ферзя не атаковали друг друга.

Мы будем решать несколько более общую задачу, считая, что требуется разместить n ферзей на доске размера nхn.

Занумеруем вертикали и горизонтали доски числами от 1 до n. Будем говорить, что поле имеет координаты (i,j) или, другими словами, является полем (i,j), если оно находится на пересечении i-й вертикали и j-й горизонтали.

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

Таким образом, поля (i,j) и (i1,j1) лежат на одной диагонали, если i+j = i1+j1 или i-j = i1-j1. Это условие легко проверить. А именно, если вычисление тропы

     \{
     <"+" sI sJ> :: sN1, <"+" sI1 sJ1> :: sN2, sN1 : sN2;
     <"-" sI sJ> :: sN1, <"-" sI1 sJ1> :: sN2, sN1 : sN2;
     }

завершается успешно, поля (i,j) и (i1,j1) лежат на одной диагонали.

Теперь надо выбрать способ, которым мы будем кодировать расположение ферзей на доске.

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

          I1 J2 ... In

где число Ik означает, что на k-й вертикали ферзь находится на горизонтали с номером Ik.

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

          I1 I2 ... Ik

где Im - номер горизонтали для ферзя на m-й вертикали.

Теперь мы можем определить предикат Attack?, который выдает пустое выражение, если поле (i,j) атаковано ферзями, уже стоящими на доске, и выдает неуспех, если это поле не атаковано.

     $func? Attack?     sI sJ ePos = ;

     Attack?  sI sJ ePos =
       ePos : $r eRest e, eRest : e sJ1,
       <Length eRest> :: sI1,
       \{
       sI1 : sI;
       sJ1 : sJ;
       <"+" sI sJ> :: sN1, <"+" sI1 sJ1> :: sN2, sN1 : sN2;
       <"-" sI sJ> :: sN1, <"-" sI1 sJ1> :: sN2, sN1 : sN2;
       };

Отметим, что проверку i1=i можно и убрать, поскольку в нашей программе функция Attack? будет вызываться только таким образом, что параметр i будет заведомо больше, чем номера столбцов у тех ферзей, которые уже поставлены на доску.

Теперь опишем функцию Next-Queen?, которая пытается добавить к частично построенной позиции нового ферзя, перебирая различные горизонтали. Если ферзя удается поставить, но этот ферзь не последний, делается попытка поставить следующего ферзя и т.д. Если очередного ферзя поставить не удается, происходит возврат назад и делается попытка переставить на новое место предыдущего ферзя.

     $func? Next-Queen? sI sN ePos = ePos;

     Next-Queen?  sI sN ePos =
       1 $iter \{ <"<" (sJ) (sN)> = <"+" sJ 1>; }
         :: sJ,
       # <Attack? sI sJ ePos>,
       ePos sJ :: ePos,
       \? {
       sI : sN
         \!  ePos;
         \!  <Next-Queen? <"+" sI 1> sN ePos>;
       };

Некоторые тонкости в определении функции Next-Queen? заслуживают пояснения.

Во-первых, конструкция поиска делает попытку вычислить свое тело, последовательно пробуя для переменной j значения 1, 2, ..., n и увеличивая значение переменной j на 1 после каждой неудачной попытки вычислить свое тело.

Во-вторых, неудача при вычислении тела конструкции поиска может возникнуть по двум причинам: либо поле (i,j) атаковано ферзями, уже стоящими на доске, и тогда успешно завершится вызов функции Attack?, а значит потерпит неудачу отрицание этого условия, либо очередного ферзя можно поставить на поле (i,j), но не удается разместить следующих ферзей, и тогда терпит неудачу рекурсивный вызов функции Next-Queen?.

Теперь осталось определить последнюю функцию Solution?, которая имеет один аргумент - размер доски, и выдает решение задачи, если оно существует, либо терпит неудачу, если решение не существует:

     $func? Solution?   sN = ePos;

     Solution?  sN =
       <Next-Queen? 1 sN >;

10.2. Задача о цепочках:

Рассмотрим следующую задачу [Вир 77]. Требуется найти объектное выражение Oe, обладающее следующими свойствами.

     (1)  Oe не содержит скобок, а всякий входящий в него символ 
          является одним из символов 1, 2 или 3.
     (2)  Oe имеет заданную длину len.
     (3)  Не существует таких объектных  выражений  Oea,  Oeb  и 
          Oec, что Oec - не пусто и при этом
                    Oe = Oea Oec Oec Oeb
          т.е. Oe не содержит двух смежных непустых  совпадающих 
          подвыражения.

Для построения требуемого выражения можно поступить следующим образом: начать с пустого выражения, а затем постепенно добавлять к нему числа, следя за тем, чтобы не получалось запрещенной комбинации. При этом, чтобы гарантировать, что цепочка не имеет вида Oea Oec Oec Oeb, где Oec - непустое, достаточно после добавления каждого числа проверять, что не образовалось выражение вида

          Oea Oec Oec

Для распознавания выражений такого вида определим предикат Unacceptable?.

     $func? Unacceptable? e.String = ;

     Unacceptable?  e.String =
       <Div <Length e.String> 2> :: s.Max,
       {
       s.Max : 0
         = $fail;
         = 1
           $iter \{ <"<" (sK) (s.Max)> = <"+" sK 1>; }
           :: sK,
           <Right 0 sK <Middle 0 sK e.String>> :: eU,
           <Right 0 sK e.String> :: eV,
           eU : eV;
       };

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

     $func? Extend?       s.Len e.String = e.String;

     Extend?  s.Len e.String =
       {
       <Length e.String> : s.Len
         = e.String;
         = 1 $iter \{ <"<" (s.Digit) (3)> = <"+" s.Digit 1>; }
             :: s.Digit,
           e.String s.Digit :: e.String,
           # <Unacceptable? e.String>,
             <Extend? s.Len e.String>;
       };

Теперь осталось определить начальную функцию Find-String?, которая получает в качестве параметра желаемую длину цепочки, и выдает искомую цепочку (если она существует), либо терпит неудачу (если она не существует).

     $func? Find-String?  s.Len = e.String;

     Find-String?  s.Len =
       <Extend? s.Len >;

11. Пример: компилятор для простого императивного языка (на отдельной странице)

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback