Опубликовано как:
Гасаненко М.Л. Расширение возможностей перебора с откатом (бэктрекинга) // Информационные технологии и интеллектуальные методы. Выпуск №2. СПб.: СПИИРАН, 1997. С.23-35.
Published as:
Russian title:
M.L. Gassanenko. Rasshirenie vozmozhnostej perebora s otkatom (bektrekinga) // Informatsionnye tehnologii i intellektual'nye metody. Vypusk No. 2 - SPb.: SPIIRAN, 1997. P.23-35. (In Russian.)English title of the same book:
M.L. Gassanenko. Enhancing the capabilities of backtracking // Information Technologies and Intellectual methods. Issue No. 2. -- St.Petersburg: SPIIRAS, 1997. P.23-35.
% История документа % pgasmil1.tex -- статья для СПИИРАНовского сборника 1996 г. -- 07.06.96 % pgasmil1.txt -- статья переведена из TeXовского формата вручную -- 07.07.96 % pgasmil1-96.html -- Статья преобразована в формат HTML вручную -- 13.07.99
УДК 681.3.06 Расширение возможностей перебора с откатом (бэктрекинга) М.Л.Гасаненко Санкт-Петербургский институт информатики и автоматизации РАН 199178, Санкт-Петербург, 14-я линия В.О., д.39 Е-mail: mlg@iias.spb.su Аннотация: Метод откатов (бэктрекинг) позволяет оформлять код, отвечающий за перебор, в виде отдельных модулей-итераторов. Это очень удобно, но на применение метода откатов в теле цикла, управляемого таким итератором, накладываются серьезные ограничения, что сужает область применимости таких итераторов. В статье описана структура управления, снимающая упомянутые ограничения и позволяющая сделать откатные процедуры-итераторы универсальным средством описания процессов перебора. Цикл AMONG использует в качестве итератора откатную процедуру и передает управление итератору после успеха тела цикла (а не после отката из тела). Обсуждаются совместимость с операторами отсечения cut и применение при быстром прототипировании. Приводится реализация на языке Форт. Enhancing the capabilities of backtracking M.L.Gassanenko Abstract: The technique of backtracking enables one to create abstract iterator modules, which are very convenient, but there's a severe restriction on the use of backtracking in the body of loops controlled by these iterators. This paper introduces a loop-like control structure that eliminates these restrictions. A backtrackable procedure is used in it as an iterator that controls repeating execution of a backtrackable body; control is transferred to the iterator when the loop body succeeds (and not when it fails). Compatibility with cut statements and employment in rapid prototyping are discussed. A Forth implementation is presented. 1 Введение ========== Бэктрекинг был введен в языки ПРОЛОГ[7,8] и ПЛЭНЕР[6] как метод доказательства теорем. Помимо этого, оказалось, что это очень удобное средство описания процессов перебора[7], хотя откатную процедуру не всегда можно использовать в качестве итератора. В настоящей статье описывается структура управления, компенсирующая этот недостаток откатных процедур и позволяющая сделать откатные процедуры-итераторы универсальным средством описания переборов. 1.1 Метод откатов (бэктрекинг) ------------------------------ Бэктрекингом называется способ организации перебора вариантов в глубину, при котором в точке выбора (точке, где возможен выбор нескольких вариантов) по очереди выбирается каждый из этих вариантов, после чего исполнение программы продолжается (такая передача управления "вперед" называется успехом). При этом на специальном стеке оставляется адрес точки отката (точки возврата), содержащей информацию о том, как получить остальные варианты. Когда обработка варианта заканчивается, делается откат назад, на последнюю точку возврата, где выбирается следующий вариант. Когда вариантов в точке выбора больше не останется, будет сделан откат и из точки выбора, также на последнюю из точек возврата. Действие, вызывающее откат, называется неуспехом. Обычно откатные процедуры используются или как "генераторы", несколько раз вырабатывающие успех и выдающие каждый раз по значению, или как "фильтры", проверяющие, что значение удовлетворяет условию и в зависимости от этого вырабатывающие успех или неуспех (не "пропуская" некоторые значения "дальше"). Совокупность точек отката, находящихся на стеке откатов, будем называть трассой. Нельзя не отметить, что терминология в этой области сложилась, пожалуй, наименее удачным образом, поскольку в русском языке прилагательное от слова "бэктрекинг" неблагозвучно, а от слов "успех" и "неуспех" нельзя образовать глаголов. Бэктрекинг мы будем называть также методом откатов, а процедуру, способную установить точку возврата или вызвать откат --- откатной (backtrackable). Хотя выработку успеха процедурой принято также называть успешным завершением, "успешное завершение" завершением не является --- исполнение процедуры всего лишь откладывается. Процедура, таким образом, представляет собой процесс, который приостанавливается при успехе и возобновляется при откате. Неуспешное же завершение является завершением процедуры--процесса. 1.2 Реализация метода откатов в системе BacFORTH ------------------------------------------------ Одним из способов реализации механизма откатов является реализация успеха как вызова продолжения, а неуспеха --- как возврата из него. В системе BacFORTH[4,11] продолжением для вызванной процедуры является остаток кода вызвавшей процедуры, который и вызывается при успехе. BacFORTH является расширением языка Форт; в Форте адрес остатка кода вызвавшей процедуры помещается при вызове на стек возвратов, к которому возможен доступ из программы (описание языка можно найти в [1,2,3,5,10], в языке используется обратная польская запись, данные хранятся на стеке данных, процедуры называются также словами). Слово ENTER : ENTER >R ; позволяет вызвать фрагмент исполнимого кода, адрес которого передается через стек данных. Далее мы будем рассматривать сразу два уровня кода --- вызывающую процедуру и одну или две вызываемых из ее кода процедуры. Фрагмент кода R@ ENTER сначала копирует со стека возвратов на стек данных адрес остатка кода вызвавшей процедуры, а затем вызывает его. Возврат из вызвавшей процедуры в вызванную будет выполнен или тогда, когда в коде вызвавшей процедуры встретится EXIT , или если еще одна вызываемая ею процедура выполнит код RDROP EXIT ( RDROP уберет со стека возвратов адрес остатка кода вызвавшей процедуры, a EXIT отдаст управление в процедуру, вызвавшую код вызвавшей процедуры). В общем, первая вызываемая процедура вызывает остаток кода вызвавшей процедуры, а тот вызывает вторую вызываемую процедуру. Для отката вторая вызываемая процедура выполняет "возврат через один уровень". Итак, стек откатов есть стек возвратов, и точки отката суть адреса возврата в выработавшие успех и потому отложенные процедуры. К сожалению, нам не удастся просто так определить новую откатную процедуру, используя откатные слова, поскольку мы обнаружим, что на стеке возвратов лежит трасса из точек возврата, а не адрес продолжения --- кода вызвавшей процедуры. Поэтому приходится ввести новый стек продолжений (L-стек), используемый откатными процедурами для хранения адреса продолжения. Слово PRO (пролог ПРОЛОГоподобной процедуры) переносит адрес продолжения на L-стек и обеспечивает корректный неуспех процедуры при откате в слово PRO. Слово CONT вызывает успех процедуры, используя адрес продолжения на L-стеке: : PRO R> R> >L ENTER L> DROP ; : CONT L> >R R@ ENTER R> >L ; Определение нового откатного слова выглядит как : <новое_имя> PRO <откатные_слова> CONT ; В системе BacFORTH реализовано несколько нестандартных структур управления; сейчас нам понадобится блок альтернатив, позволяющий организовать точку выбора: { <альтернатива1> | <альтернатива2> | ... | <альтернативаN> } Это полный аналог прологовского "ИЛИ" --- каждый успех каждой из альтернатив приводит к успеху всего блока; при откате управление передается или на точку возврата в текущей альтернативе, или на следующую альтернативу. Когда все альтернативы будут просмотрены, блок завершится неуспехом. 1.3 Достоинства и недостатки классического бэктрекинга ------------------------------------------------------ Откатные процедуры являются очень удобным способом описания процессов перебора. Они позволяют спрятать все знания о способе перебора внутри единственного модуля с достаточно простым стандартным интерфейсом, т.е. могут быть "модулями, выражающими идею цикла" (в смысле [9]). Код, использующий такие итераторы (а также "фильтры", см. раздел "обсуждение") легко воспринимается человеком, поскольку напоминает диаграммы потоков данных. К сожалению, в использующих бэктрекинг системах область применимости таких откатных итераторов оказывается ограниченной. Обычно цикл с использованием итератора выглядит следующим образом: <итератор> <тело> Когда <итератор> вырабатывает успех, управление передается в <тело>; когда <тело> завершается неуспехом, управление возвращается обратно в <итератор>. В качестве примера приведем определение, распечатывающее содержимое стека. : S. STACK . ; Итератор STACK по очереди копирует каждый из элементов стека на вершину; слово . (точка) печатает эти элементы (снимая их со стека). Точка исполняется по разу для каждого из элементов. Слово ; (точка с запятой) завершает определение, компилируя в его конец EXIT, вызывающий откат в итератор. Второй пример иллюстрирует работу блока альтернатив: слово TEST1 : TEST1 { 1 | 2 | 27 | 5 } . ; выведет на печать "1 2 27 5 ". Эти числа оставляются на стеке альтернативами и распечатываются словом . (точка). Итератор можно оформить и в виде отдельного слова: : VALUES PRO { 1 | 2 | 27 | 5 } CONT ; : TEST2 VALUES . ; Обратите внимание, что последнее определение выглядит почти как определение, распечатывающее только одно число 5: : TEST0 5 . ; Передать управление в итератор после успеха <тела> при использовании только что описанной схемы нельзя, т.е. откатный итератор не всегда может управлять откатным же телом}. В принципе, можно организовать перебор с помощью обычного цикла, если перебор не слишком сложен (в системе BacFORTH традиционные структуры управления могут использоваться совместно с методом откатов). Однако если перебор сложен, имеет смысл оформить его в виде отдельного модуля-итератора, создаваемого и отлаживаемого независимо от тела цикла и допускающего повторное использование. Описываемая ниже конструкция позволяет это сделать. 2 Откат в итератор после успеха тела цикла ========================================== Конструкция выглядит следующим образом: AMONG <итератор> EACH <тело> ITERATE <дальнейшие_действия> Сразу приведем пример --- программу, распечатывающую все подмножества множества {1,2,5}: : SUBSETS AMONG { 1 | 2 | 5 } \ оставлять на стеке по очереди 1,2,5 EACH { | DROP } \ успех сначала с элементом, потом без него \ DROP снимает эл-т множества со стека ITERATE CR STACK . ; \ распечатать стек с новой строки Когда конструкция получает управление, запускается <итератор>, который вырабатывает свое первое значение, завершаясь успехом. На стеке возвратов остается трасса, определяющая состояние итератора. (Состояние итератора должно полностью определяться содержимым стека возвратов, т.к. автоматически восстанавливается только то, что сохранено на стеке возвратов). После этого управление передается в <тело>. Когда <тело> завершается успехом, на вершину стека возвратов копируется трасса итератора. Затем имитируется неуспех, и итератор получает управление. Он вырабатывает новое значение, оно снова обрабатывается <телом>, и т.д. Если же <тело> завершается неуспехом, отката в итератор не делается --- управление получает точка возврата, установленная <телом> на предыдущей итерации. Состояние итератора при этом восстанавливается --- для этого нужно только восстановить значения указателей начала и конца трассы итератора. Когда неуспех случается на первой итерации, вся конструкция завершается неуспехом. Когда итератор не может больше выработать значения, управление передается на <дальнейшие_действия>. Когда <дальнейшие_действия> выработают неуспех, управление вернется на точку возврата, установленную телом, которое сможет возобновить свою работу. Итак, итератор рассматривается как процесс; его состояние определяется трассой, которая хранится на стеке возвратов. Когда надо снова запустить итератор, мы копируем процесс (т.е. его трассу-состояние) и передаем управление новой копии. При откате состояние процесса восстанавливается. Обратите внимание, что процесс-итератор существует как бы в другом измерении: после неуспеха итератора цикл завершается успехом (управление передается на <дальнейшие_действия>) . Действие конструкции AMONG проиллюстрируем еще одной программой: : от1до4 PRO { 1 | 2 | 3 | 4 } CONT ; : B. PRO ( N -> / <- ) DUP . >R CONT \ распечатать число, выработать успех R> . ; \ при откате еще раз распечатать : X от1до4 B. ." # " ; : Y AMONG от1до4 EACH B. ITERATE ." # " ; Процедура X выводит на экран: 1 # 1 2 # 2 3 # 3 4 # 4 а процедура Y печатает: 1 2 3 4 # 4 3 2 1 (каждое значение печатается в первый раз при прохождении "вперед", а второй раз --- при откате; "#" печатается непосредственно перед возбуждением отката). Разумеется, можно использовать и итераторы, зависящие от внешних данных, т.е. такие, состояние которых не полностью определяется стеком возвратов. Разумным примером служит итератор по элементам очереди, в которую тело добавляет новые элементы. 3 Реализация ============ На L-стеке хранятся указатели начала и конца трассы, что ограничивает возможности использования L-стека внутри нашего цикла. Точно таким же свойством обладает стандартный цикл DO...LOOP в отношении стека возвратов. Конструкция BACK <действия> TRACKING задает действия при откате (оставляет на стеке возвратов адрес фрагмента кода между BACK и TRACKING). В принципе, ее можно заменить вспомогательным определением вида : XXX R> ENTER <действия> ; Мнемоники стековых операций построены по следующей схеме: BDROP (Backtrackable DROP) --- обратимый DROP; DROPB (DROP when Backtracking) --- DROP при откате. Информация, которую требуется восстановить при откате, сохраняется на стеке возвратов: : BDROP R> SWAP >R ENTER R> ; Операции L@ , >L , L> , LP@ , LP! и т.п. работают с L-стеком и аналогичны соответствующим операциям для стека возвратов. Ниже приводится реализация для системы Бета-Форт версии 3.2. \ (c) М.Л.Гасаненко, 1990-1995 \ Forth Internals wordset \ NB: Эти определения зависят от реализации Форт-системы !!! : TOKEN+ ( addr -- addr ) 2+ ; \ 16-разрядные эл-ты кода : REF@ ( src -- dest ) DUP @ + ; \ относительные 16-разрядные : REF+ ( src -- addr ) 2+ ; \ ссылки в командах перехода \ ----- Системно-независимая часть ----- \ Полезные определения : CELL- 1 CELLS - ; : REV ( a b c -- c b a ) SWAP ROT ; ( >R> меняет местами верхние эл-ты стеков возвратов и данных ) : >R> ( a -- b ) ( R: b -- a ) R> R> REV >R >R ; \ L-стек VARIABLE LP VARIABLE LP0 : LP@ ( -- a ) LP @ ; : LP! ( a -- ) LP ! ; : >L ( x -- ) LP@ CELL- DUP LP! ! ; : L> ( -- x ) LP@ DUP CELL+ LP! @ ; : L@ ( -- x ) LP@ @ ; : LDROP ( -- ) LP@ CELL+ LP! ; ALIGN 100 CELLS ALLOT HERE 2 CELLS - LP0 ! LP0 @ LP! \ Только для Бета-Форта \ : ABORT+ LP0 @ LP! R@ >R ; ' ABORT+ UABORT ! \ Реализация откатов : ENTER >R ; : PRO R> R> >L ENTER LDROP ; : CONT L> >R SUCC R> >L ; \ BACK ... TRACKING : (CALL) R@ REF+ >R> REF@ >R ; : BACK ?COMP COMPILE (CALL) >MARK 202 ; IMMEDIATE : TRACKING ?COMP 202 ?PAIRS COMPILE EXIT >RESOLVE ; IMMEDIATE \ Блок альтернатив : (START) R@ REF@ >R> REF+ >R ; : { ?COMP 204 COMPILE (START) >MARK 203 ; IMMEDIATE : | ?COMP 203 ?PAIRS COMPILE BRANCH >MARK 205 ROT >RESOLVE COMPILE (START) >MARK 203 ; IMMEDIATE : } ?COMP 203 ?PAIRS COMPILE BRANCH >MARK 205 ROT >RESOLVE COMPILE EXIT BEGIN DUP 204 - WHILE 205 ?PAIRS >RESOLVE REPEAT DROP ; IMMEDIATE \ AMONG ... EACH ... ITERATE \ порождается код: \ (among) (among>) {addr} ... (each) ... (iterate) addr: код_за_циклом : (AMONG) R> \ Адрес (AMONG>) BACK LDROP TRACKING \ При откате убрать указатель трассы итератора RP@ >L \ Указатель начала трассы итератора DUP >R \ (AMONG>): успех цикла при неуспехе итератора TOKEN+ REF+ >R ; \ Обойти (AMONG>) , запустить итератор : (AMONG>) R> \ Адрес ссылки на код за циклом L> RP@ - >R \ Сохранить указатель начала трассы BACK R> RP@ + >L TRACKING \ Восстановить при откате REF@ >R ; \ Передать управление на код за циклом : (EACH) R> \ Адрес тела цикла RP@ >L \ Новый адрес конца трассы итератора BACK LDROP \ При откате убрать адрес конца трассы L@ RP! TRACKING \ и саму трассу итератора >R ; \ Передать управление телу цикла : (ITERATE) RDROP \ Убрать адрес кода, находящегося за циклом L> L> \ Указатели на начало и конец трассы итератора 2DUP RP@ - >R RP@ - >R \ Сохранить указатели трассы итератора BACK LDROP \ Убрать новый указатель начала трассы и R> RP@ + R> RP@ + \ восстановить старые указатели >L >L TRACKING \ при откате OVER - \ Адрес конца и длина трассы итератора RP@ >L \ Новый адрес начала трассы итератора RP@ OVER - RP! \ Отвести место на стеке возвратов RP@ SWAP MOVE \ Скопировать трассу итератора ; \ EXIT передает управление итератору : FINIS RDROP L> >R BACK R> >L TRACKING L@ CELL- @ >R ; : AMONG ?COMP COMPILE (AMONG) COMPILE (AMONG>) >MARK 207 ; IMMEDIATE : EACH ?COMP 207 ?PAIRS COMPILE (EACH) 208 ; IMMEDIATE : ITERATE ?COMP 208 ?PAIRS COMPILE (ITERATE) >RESOLVE ; IMMEDIATE Слово FINIS вызывает окончание (успех) цикла, являясь аналогом слова LEAVE (выход из обычного цикла). Приведенный код ориентирован на ANSI-стандарт Форта и является программой с зависимостями от окружения (главными из которых являются предположение от том, что стек возвратов находится в адресном пространстве данных и что адреса возвратов занимают одну ячейку, что имеет место в "классических" системах). Реализовав слова (AMONG), (AMONG>), (EACH) и (ITERATE) на ассемблере, можно получить ощутимый выигрыш в скорости. 4 Совместимость с операторами отсечения cut =========================================== Применение техники копирования участков стека возвратов требует принятия специальных мер при реализации операторов отсечения. Реализации имеющихся в си.стеме BacFORTH двух разновидностей оператора cut пришлось модифицировать. Первой разновидностью оператора cut являтся конструкция "структурный cut", которая выглядит следующим образом (квадратные скобки здесь являются знаком пунктуации и означают необязательность): CUT: ... -[NO]CUT Слово CUT: отмечает начало отсекаемого фрагмента, слово -CUT удаляет точки возврата до отметки слова CUT: , слово -NOCUT используется в качестве пары для CUT: , если отсечение оказывается не нужным. Второй разновидностью является конструкция "отложенный cut": CUT: ... [NO]CUT< ... [NO]CUT! ... >CUT Она позволяет отметить конец отсекаемой области (словами CUT< и NOCUT<) и лишь через некоторое время принять решение об отсечении (слова CUT! и NOCUT!). Слова CUT! и NOCUT! можно использовать только между [NO]CUT< и >CUT , слово >CUT обозначает конец конструкции. Допускается вложенность. Кроме того, сама конструкция AMONG содержит "встроенный" оператор отсечения, удаляющий трассу итератора при откате из тела. Применение техники копирования участков стека требует, чтобы фрагменты стека возвратов были переместимыми. Они могут содержать абсолютные адреса фрагментов шитого кода, но не должны содержать абсолютных адресов фрагментов стека возвратов. Из упомянутых выше слов модификации не подверглись только CUT: и -CUT , остальные пришлось переписать с использованием относительных адресов. В качестве примера приведем реализацию оператора CUT: ... -[NO]CUT : : CUT: \ отметить начало отсекаемого фрагм. R> RP@ >L \ адр. вершины стека возвр.--> на L-стек BACK LDROP TRACKING \ а при откате - убрать эту отметку >R ; : -CUT R> L> RP! >R ; \ убрать точки возврата до отметки : -NOCUT \ убрать отметку, но не точки возврата R> L> RP@ - >R \ сохранить относит. адрес отметки BACK R> RP@ + >L TRACKING \ восстановить его при откате >R ; 5 Обсуждение ============ Конструкция AMONG позволяет сделать откатные процедуры-итераторы (т.е. процедуры, использующие бэктрекинг и вырабатывающие значения при успехе) универсальным средством описания процессов перебора. При программировании в среде, где такая конструкция отсутствует, оформление всех процессов перебора в виде откатных итераторов сопряжено с определенным риском, поскольку откатная процедура не всегда может управлять циклом с откатным телом; введение конструкции AMONG избавляет метод откатов от указанного недостатка. Среди практически важных задач, программирование которых облегчается при использовании структуры AMONG , можно указать задачу нахождения остовных деревьев графа, к которой приводится, например, задача восстановления подчиненности слов в предложении на русском языке при известной морфологической информации. И "отложенный cut", и структура AMONG оказываются полезны при быстром создании первой версии (прототипа) программы --- на этой стадии предпочтительно иметь более мощные средства, чем минимальный достаточный набор, остающийся в конечной версии. Первый вариант решения может быть не самым эффективным, однако после того, как он получен, появляется возможность рассуждать не только о проблеме, но и о решении, и можно переходить к более эффективным версиям путем постепенного изменения кода при сохранении работоспособности программы в целом. Наличие конструкции AMONG позволяет на стадии прототипирования оформлять все переборы в виде итераторов, сосредоточив внимание на самой задаче, а не на вопросах применимости тех или иных методов; исчезает риск попадания в ситуацию, когда нужные понятия реализованы, но реализации их несовместимы. Таким образом, она ускоряет разработку даже если она не используется вообще или если последующий анализ покажет, что ее использование было неоправданно. На основе оператора "отложенный cut" удобно создавать проблемно-ориентированные операторы-макрокоманды выборочного отсечения (например, в задачах синтаксического разбора); кроме того, он, как и AMONG, позволяет избежать пересмотра уже реализованных решений, когда оказывается, что задача не совсем укладывается в выбранную общую схему. Конструкцию AMONG можно рассматривать как реализацию квантора общности: если процедура M вырабатывает значения x in M а P проверяет выполнение некоторого условия P(x), то AMONG M EACH P ITERATE реализует проверку условия forall x in M P(x) (хотя для простой проверки можно найти более эффективные способы). В системе, где применяются откатные итераторы, проверки условий удобно оформлять в виде откатных процедур-фильтров, используемых в виде: <итератор> <фильтр1> <фильтр2> <тело> что напоминает диаграмму потока данных. Фильтр вырабатывает успех, если условие выполнено, и неуспех в противном случае. Фильтр вырабатывает успех только один раз; он может оставлять точки отката, но повторного успеха при откате не вырабатывает. Интересно, что такой фильтр также можно использовать в конструкции AMONG: AMONG <фильтр> EACH <действия> ITERATE сразу вырабатывает успех, если <фильтр> вырабатывает неуспех, и исполняет <действия>, если <фильтр> вырабатывает неуспех (после успеха <действий> делается откат в <фильтр>, что приводит к неуспеху фильтра и успеху конструкции AMONG). Откатная процедура представлят собой процесс, который то возобновлятся (для порождения данных), то откладывается (на время обработки данных). Копирование состояния процесса позволяет запускать итератор после успеха тела и восстанавливать его состояние при откате. Применение техники копирования участков стека возвратов накладывает незначительные ограничения на содержимое этих участков, т.к. они должны быть переместимыми. Они могут содержать абсолютные адреса фрагментов шитого кода, но не должны содержать абсолютных адресов фрагментов стека возвратов. Впрочем, абсолютный адрес всегда можно заменить относительным. Для работы системы BacFORTH требуется стек возвратов большего, чем для обычной Форт-системы, размера; использование методики копирования участков стека также повышает требования к размеру стека возвратов. В большинстве Форт-систем увеличить размер стека возвратов можно записав в переменную RP0 (в некоторых системах R0) адрес конца области памяти требуемого размера. Можно ожидать повышения требований к размеру стека возвратов при использовании итераторов, оставляющих длинную трассу, поскольку эта трасса будет копироваться на каждой итерации. На первый взгляд может показаться, что копирование участка стека возвратов неэффективно ни по времени, ни по памяти, однако на практике оказывается, что итератор можно написать так, чтобы трасса содержала только действительно необходимую информацию (т.е. ту, которую пришлось бы сохранять в любом случае). Учитывая, что обработка точек отката сводится к передаче управления без какого-либо анализа значений, копирование трассы оказывается наиболее быстрым и надежным способом сохранения состояния процесса. Результаты измерений показали, что программа, перебирающая подмножества множества из 12 элементов, находящихся в двоичном дереве, требует 227 мест на стеке возвратов, т.е. 454 байта, что не так уж много для 4096 перебираемых вариантов, и занимает при этом менее 1 экрана: : RESTB \ при откате восстановить число на вершине стека R> OVER >R ENTER R> ; : TREE PRO \ перебор элементов дерева ROOT @ \ адрес корня BEGIN { RESTB CELL+ @ \ адрес левого поддерева | RESTB @ CONT EXIT \ выдать значение в вершине | CELL+ CELL+ @ \ адрес правого поддерева } ?DUP 0= UNTIL ; \ перебор, пока не 0 : SUBT AMONG TREE EACH { | DROP } ITERATE ." { " BACK ." } " TRACKING STACK . ; Следует отметить следующие черты языка Форт, сделавшие возможным применение описанной выше методики: легкость введения новых структур управления; использование интерпретатором кода отдельного стека; доступ к стеку возвратов; управление кодогенерацией; возможность увеличения размера существующих стеков; доступ к любым компонентам системы. 6 Заключение ============ Метод откатов позволяет упрятывать информацию о способе перебора внутри одного модуля-итератора. Это очень удобно, но имеет место ограничение на применение метода откатов в теле цикла, управляемого таким итератором. Конструкция AMONG снимает это ограничение, в результате чего откатные процедуры-итераторы могут использоваться как универсальное средство описания переборов. Наличие таких средств, как конструкция AMONG и "отложенный cut" позволяет ускорить построение прототипа програмы, даже если эти сверхмощные средства не появляются в конечной версии продукта. Литература ========== [1] Баранов С.Н., Ноздрунов Н.Р. Язык Форт и его реализации. --- Л.: Машиностроение, 1988. --- 158 с. [2] Броуди Л. Начальный курс программирования на языке Форт. --- М.: Финансы и статистика, 1990. --- 352 c. [3] Бураго А.Ю., Кириллин В.А., Романовский И.В. Форт --- язык для микропроцессоров. --- Л.: Знание, 1989. --- 36 с. [4] Гасаненко М.Л. Новые синтаксические конструкции и бэктрекинг для языка Форт.//Проблемы технологии программирования --- СПб:СПИИРАН, 1993. --- С. 148--162. [5] Келли М., Спайс Н. Язык программирования Форт. --- М.:Радио и связь, 1993. --- 318 с. [6] Пильщиков В.Н. Язык Плэнер. --- М.:Наука, 1983. --- 207 с. [7] Стерлинг, Л., Шапиро, Э. Искусство программирования на языке Пролог. --- М.:Мир, 1990. --- 333 с. [8] Хоггер, К. Введение в логическое программирование. --- М.:Мир, 1988. --- 348 с. [9] Цейтин Г.С. На пути к сборочному программированию //Программирование. --- 1990. --- N 1. --- С. 78--92. [10] American National Standard for Information Systems --- Programming Languages --- Forth. --- American National Standard Institute, Inc., 1993. --- 212 p. [11] Gassanenko, M.L. BacFORTH: an Approach to New Control Structures.//Proceedings of the EuroForth'94 Conference, 4-6 November 1994, Royal Hotel, Winchester. --- p. 39--43.