Заметки по структурному программированию
       

Проблема восьми ферзей


Этот последний раздел заимствован из конспекта моих лекций "Введение в искусство программирования". Я обязан этим примером Н.Вирту (как и многими другими хорошими примерами). Этот раздел добавлен по двум причинам.

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

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

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

У нас нет оператора, генерирующего все эти конфигурации; именно в получении такого оператора состоит наша задача.


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


  1. множество А является подмножеством множества В;
  2. если задан элемент из множества B, то не представляет особого труда установить, принадлежит ли он множеству А;
  3. мы можем получить оператор, генерирующий все элементы множества В.


С помощью генератора (3) элементов множества В можно генерировать по очереди все элементы из В; к ним будет применяться логический критерий (2), который устанавливает, должны ли эти элементы пропускаться или передаваться в генерируемое таким образом множество А. В силу условия (1) этот алгоритм породит все элементы множества А. Сделаем три замечания:


  1. Все наши рассуждения становятся оправданными, когда множество В не идентично множеству А, а поскольку оно должно содержать А в качестве подмножества, оно должно быть больше, чем множество А. Однако для повышения эффективности разумно выбрать множество В "как можно меньшим": чем больше в нем окажется элементов, тем чаще придется отбрасывать его элементы в соответствии с логическим критерием (2).
  2. Нам следует искать такой логический критерий, который легко применяется; по крайней мере, не должно вызывать трудностей установление факта, что некий элемент из В не принадлежит множеству А. Это также диктуется соображениями эффективности, так как можно ожидать, что множество В окажется на порядок больше множества А, т.е. потребуется отбросить большинство элементов из В.
  3. Предполагается, что легче генерировать элементы множества В, чем непосредственно генерировать элементы множества А. Если тем не менее генерация элементов множества В все же представляет трудности, то мы можем снова провести наше рассуждение, повторно применить тот же прием и искать еще большее множество С конфигураций, содержащее В в качестве подмножества и т. д. (Внимательный читатель заметит, что мы именно так поступим при разборе данного примера.)




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


  1. на доске имеются восемь ферзей;
  2. никакие два ферзя не могут взять один другого.




Отбрасывание любого из этих условий дает следующие варианты множества В:


  • В1: все конфигурации из N ферзей на доске, где никакие два ферзя не могут взять один другого;
  • В2: все конфигурации из восьми ферзей на доске.


Но оба эти множества столь несообразно велики, что им соответствуют совершенно бесполезные алгоритмы. Поэтому нам следует проявить больше изобретательности. Возникает вопрос: "Каким образом?"

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

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



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

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

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

(b) Аналогично делаем вывод, что каждая вертикаль будет содержать ровно одного ферзя.

(c) Имеются 15 "восходящих" диагоналей, каждая из которых содержит не более одного ферзя, т. е. восемь восходящих диагоналей содержат ровно по одному ферзю, а семь восходящих диагоналей являются пустыми.

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

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

Последнее свойство является очень важным. (Честно говоря, здесь я не вижу способа компенсировать недостаток изобретательности.) В нашей прежней терминологии это свойство сообщает нам нечто о любой непустой конфигурации из множества В1. Если мы начинаем с какого-то решения (которое является конфигурацией восьми ферзей из множества В1) и удаляем одного ферзя, то мы получаем конфигурацию семи ферзей из множества В1; удаление еще одного ферзя приведет снова к конфигурации из множества В1, и мы можем продолжать этот процесс, пока шахматная доска не опустеет. Можно было бы заснять этот процесс на кинопленку, и, прокручивая ее в обратном направлении, мы бы увидели, как пустая доска постепенно заполняется добавлением одиночных ферзей и как последовательное прохождение различных конфигураций из множества В1 приводит нас к данному решению. (Я не берусь судить, поможет ли читателям этот трюк с обратным прокручиванием киноленты, и упоминаю о нем только потому, что лично мне такие приемы помогают.) При получении такой киноленты любое решение можно сводить к пустой доске многими способами, и имеется в точности столько же способов построения каждого решения при обратном прокручивании пленки.



Можем ли мы извлечь пользу из этой свободы выбора. Мы отвергли множество В1 из-за того, что оно слишком велико, но, быть может, удастся найти в нем подходящее подмножество, в котором каждая непустая конфигурация окажется одноферзевым расширением только одной конфигурации из этого подмножества. Это "свойство расширения" подразумевает, что мы собираемся рассматривать конфигурации, в которых на доске менее чем по восемь ферзей, и что мы хотели бы формировать новые конфигурации, добавляя по одному ферзю к имеющимся конфигурациям. (По-видимому, такая операция будет сравнительно простой).

Итак, наше внимание переключается непосредственно на генерацию элементов (все еще таинственного) множества В. Например, в каком порядке их генерировать? И снова возникает вопрос, которому до сих пор мы не уделили ни малейшего внимания: в каком порядке мы собираемся генерировать решения, т. е. элементы множества A? Можно ли сделать на этот счет какое-то разумное предположение в надежде, что оно поможет нам распутать клубок решений. (Мой опыт подсказывает, что такой вопрос об упорядочивании обычно очень проясняет ситуацию. Дело не только в том, что нам нужно изготовить последовательную программу, которая по определению будет порождать решения в некотором порядке, так что необходимо на каком-то этапе установить этот порядок. Установленный порядок обычно дает нам ключ к доказательству того, что программа будет порождать все решения, причем каждое решение только по одному разу.)

Прежде всего нам нужно найти ответ на вопрос, как мы будем характеризовать имеющиеся у нас решения. Чтобы охарактеризовать решение, мы должны задать позиции восьми ферзей. Сами по себе ферзи не являются упорядоченными, но для горизонталей и вертикалей существует определенный порядок, и мы можем предположить, что они нумеруются от 0 до 7. Согласно свойству (а), каждая горизонталь содержит ровно одного ферзя, и поэтому мы можем упорядочить ферзей в соответствии с номерами занимаемых ими горизонталей. Тогда каждая конфигурация из восьми ферзей может быть задана значением массива integer array x[0:7], где x[i] - номер вертикали, занимаемой ферзем из i-й горизонтали.

В таком случае каждое решение представляет собой "восьмизначное слово" (х[0]... х[7]), и я полагаю, что разумнее всего генерировать эти слова в алфавитном порядке.

Замечание.



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

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

Сначала мы должны генерировать все решения с х[0]=0 (если такие существуют), затем решения с х[0]=1 (если найдутся) и т. д.; из решений с фиксированным значением х[0]=0 нужно сначала генерировать те, у которых х[1]=0 (если такие существуют), затем те, у которых х[1]=1 (если существуют) и т. д. Другими словами, ферзь из горизонтали 0 помещается в вертикаль 0, т. е. в нижний левый угол доски, и остается там до тех пор, пока не завершится генерация всех элементов множества А (и В) с ферзем 0 в этой позиции, и только после этого ферзь 0 передвигается на один квадрат вправо, в следующую вертикаль. При каждом положении ферзя 0 ферзь 1 будет перемещаться слева направо в горизонтали 1, перескакивая через поля, которые находятся под ударом ферзя 0; при каждом комбинированном положении первых двух ферзей ферзь 2 перемещается по горизонтали 2 слева направо, пропуская все поля, которые находятся под ударом предыдущих ферзей, и т. д.

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

Критерием того, что элемент из В принадлежит также множеству А, является равенство N=8.

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



Можно было бы попытаться использовать для этого оператор "ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В" в программе вида

НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ; repeat ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В; if N=8 then ПЕЧАТАТЬ КОНФИГУРАЦИЮ until В ИСЧЕРПАНО

(Здесь мы воспользовались тем фактом, что пустая конфигурация принадлежит B, но не принадлежит A и не является единственным элементом множества В. Мы не сделали никаких предположений относительно существования решений.) Однако программа такой структуры не очень удобна по двум причинам. Во-первых, мы не располагаем готовым критерием распознавания последнего элемента из В, и, по всей видимости, следует обобщить оператор "ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В" таким образом, чтобы он порождал указание "В ИСЧЕРПАНО", когда он применяется к последнему "истинному" элементу множества В. Во-вторых, не вполне ясно, как реализовать оператор "ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В": число ферзей на доске может оставаться неизменным, может уменьшаться и может увеличиваться. Итак, здесь мы сталкиваемся с трудностями. Что можно сделать, чтобы избежать их? До тех пор пока мы считаем последовательность конфигураций из множества В единой и однородной и не подразделяем ее на ряд подпоследовательностей, соответствующая структура программы будет оставаться единым циклом, как в предыдущем варианте. Если мы ищем иную структуру программы, то именно поэтому должны задать себе вопрос: "Как организовать разложение последовательности конфигураций из множества В на ряд подпоследовательностей?" С учетом того, что последовательность конфигураций из множества В должна генерироваться в алфавитном порядке, и по аналогии с основным подразделением в словаре (а именно по первой букве) первичная организация групп является очевидной: по позиции ферзя 0. Если на время забыть о необходимости печатать те конфигурации из В, которые принадлежат также и множеству А, то генерирование всех элементов множества В представляется следующим образом:



НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ; h:=0; repeat УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [0,h]; ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМ ПОЛОЖЕНИЕМ ФЕРЗЯ 0; УБРАТЬ ФЕРЗЯ С ПОЛЯ [0,h]; h1:=h+1 until h=8

Но теперь снова возникает вопрос: как группировать все конфигурации с фиксированным положением ферзя 0? У нас уже готов ответ: в порядке возрастания номеров вертикалей, содержащих ферзя 1, т. е.

h1:=0; repeat if ПОЛЕ [1, h1] СВОБОДНО do

begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [1, h1]; ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМ ПОЛОЖЕНИЕМ ПЕРВЫХ ДВУХ ФЕРЗЕЙ; УБРАТЬ ФЕРЗЯ С ПОЛЯ [1, h] end; h1:=h1 + 1 until h1 =8

Для оператора "ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ с ФИКСИРОВАННЫМ ПОЛОЖЕНИЕМ ПЕРВЫХ ДВУХ ФЕРЗЕЙ" можно написать аналогичный фрагмент программы, и т. д. Вкладывая эти фрагменты один в другой, мы получили бы правильную программу с восьмикратным вложением циклов, причем эти циклы оказались бы весьма и весьма однообразными. Такой способ имеет два недостатка:


  1. он требует непомерной писанины;
  2. он обеспечивает программу решения нашей проблемы для шахматной доски из 8x8 полей, но для решения той же головоломки, например при доске из 10x10 полей, потребовалась бы новая, еще более длинная программа.


Нам нужен способ выполнения всех циклов под управлением одного и того же текста программы. Можем ли мы сделать тексты циклов идентичными? И можем ли мы воспользоваться их идентичностью? Начнем с замечания, что самый внешний и самый внутренний циклы являются исключениями. Самый внешний цикл исключителен в том смысле, что он не содержит проверки, свободно ли поле [0, h], поскольку мы знаем, что оно свободно. Но хотя мы знаем, что оно свободно, не будет вреда от включения условия

if ПОЛЕ [0, h] СВОБОДНО do

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

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



Вместо этого нужно печатать конфигурацию, поскольку найден элемент множества В, принадлежащий одновременно и множеству А. Мы можем совместить самый внутренний цикл с остальными семью циклами, заменив строку "ГЕНЕРИРОВАТЬ" на строку

if ДОСКА ЗАПОЛНЕНА then ПЕЧАТАТЬ КОНФИГУРАЦИЮ else ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ, РАСШИРЯЮЩИЕ ИМЕЮЩУЮСЯ

Для этого мы вводим глобальную переменную "n", служащую счетчиком ферзей, имеющихся на доске. Проверка "ДОСКА ЗАПОЛНЕНА" приобретает вид "n=8", операции над полями могут содержать ип" в качестве первого индекса. Теперь единственное различие между восемью циклами состоит в том, что у каждого из них "свое отдельное h". На этом этапе мы получаем утвердительный ответ на вопрос, можно ли воспользоваться идентичностью циклов. Прохождение через восемь вложенных циклов может вызываться с помощью рекурсивной процедуры "генерировать", описывающей однократное выполнение цикла. С ее помощью вся программа сводится к виду

НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ; п: =0; генерировать

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

procedure генерировать; begin integer h; h:=0; repeat if ПОЛЕ [n, h] СВОБОДНО do begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [n, h]; n:=n+1; if n=8 then ПЕЧАТАТЬ КОНФИГУРАЦИЮ else генерировать; n:=n-1; УБРАТЬ ФЕРЗЯ С ПОЛЯ (n, h] end

h:=h+1 until h=8 end

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

integer array x [0:7]



в котором по очереди задаются номера вертикалей, занимаемых ферзями, а также решили, что скаляр

integer n

следует использовать для представления числа ферзей на доске. Точнее говоря,

п=число ферзей на доске

x[i] при 0<in=номер вертикали, занимаемой ферзем из i-й горизонтали.

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

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

Как это сделать? Например, можно представить себе логический массив из-8х8 элементов, указывающих для каждого поля, является ли оно свободным. Если мы заводим такой массив для всей доски, то добавление ферзя может повлиять на 28 полей. Однако удаление ферзя оказывается при этом трудоемким процессом, так как ниоткуда не следует, что поля, которые не находятся более под ударом этого ферзя, становятся вообще свободными: они могут находиться под ударом одного или нескольких ферзей, остающихся в конфигурации.



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

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


  1. свободными вертикалями;
  2. свободными восходящими диагоналями;
  3. свободными нисходящими диагоналями.


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

boolean array верт [0:7]

где "верт[i]" означает, что i-я вертикаль вся свободна. А как идентифицировать диагонали? Вдоль каждой восходящей диагонали разность между номером горизонтали и номером вертикали является постоянной; а их сумма остается постоянной вдоль каждой нисходящей диагонали. Следовательно, соответствующие разность и сумма оказываются простейшими индексами, позволяющими различать диагонали, и поэтому, чтобы следить за свободными диагоналями, мы вводим массивы

boolean array вос[-7:+7], нис[0:14]



Проверка, является ли свободным поле [п, h], приобретает вид верт[h]вос[п-h]нис[n+h]

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

begin integer n, k; integer array x[0:7]; boolean array верт[0:7], вос[-7:+7], нис[0:14]; procedure генерировать; begin integer h; h:=0; repeat if ПОЛЕ [n,h] СВОБОДНО: (верт[h]вос[n-h]нис[n+h]) do begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [n,h]: x[n]:=h; верт[h]:=false; вос[n-h]:=false; нис[n+h]:=false; n:=n+l if ДОСКА ЗАПОЛНЕНА: (n=8) then begin ПЕЧАТАТЬ КОНФИГУРАЦИЮ: k:=0; repeat печатать (x[k]); k:=k+1 until k=8; новая строка end

else генерировать; n:=n-1; УБРАТЬ ФЕРЗЯ С ПОЛЯ [n,h]: нис[n+h]:=true; вос[n-h]:=true; верт[h]:=true end; h:=h+l until h=8 end; НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ: n:=0; k:=0; repeat верт[k]:=true; k:=k+l until k=8; k:=0; repeat вoc[k-7]:=true; нис[k]:=true; k:=k+l until k=15; генерировать end

В окончательной программе вводится переменная "k"для общих вычислительных надобностей, операторы и выражения снабжаются метками (в прописных буквах). Заметим, что мы совмещаем два уровня описания: то, что было операторами и функциями на более высоком уровне, теперь появляется в виде пояснительных меток. Этой окончательной программой мы завершаем последний раздел. Мы пытались продемонстрировать пример рассуждения, где можно обнаружить прием обратного прослеживания, а также пример рассуждения, в котором можно узнать описывающую его рекурсивную процедуру. Самый существенный вывод из этого раздела состоит, по-видимому, в том, что весь соответствующий анализ и синтез можно выполнять до принятия решения о том, как (и насколько избыточно) конфигурация будет представляться в машинной памяти. Разумеется, такие предварительные рассмотрения принесут хорошие плоды лишь в том случае, когда в конце концов удастся найти подходящее представление конфигураций.Тем не менее, я считаю принципиальным мысленное отделение уровня абстракции, на котором можно позволить себе не заботиться об этом. В заключение хочу поблагодарить терпеливых читателей, дочитавших до этого места.

Содержание раздела