В.Н. Пильщиков - Язык Плэнер (1156455), страница 26
Текст из файла (страница 26)
Эти вруплы переменных действуют одновременно, и оик не должны «мешатьз друг другу Вычисление функции РАТИ успешно, если она нашла путь от узла ВЕО к узлу ЕЖР-, и неуспепэно, если такой. путь ле существует. Вначале функция проверяет, не совпадают ли начальный и конечный узлы. Если совпадают, то функция сразу заканчивает свою Работу со влечением Т. Иначе л списке ОВАРН отыскивается подсписок, отмосящийся к узлу ВЕС, после чего в программе определяется развилка, альтернативы которой соответствуют дугам, выходящим из этого узла. В развилке выбирается одна ие этих дуг и вычисляется ее прсдякат.
Если ои имеет значение <ложь», тогда переход по дуге аапрещен,поэтому вырабатывается неуспех, который вастазляет пролрамму выбрать иную дугу. Если же предикат имеет значение евстклаэ, тоща переход по дуге .возможен, поэтому выпоапяется ее оператор. Далее происходит р~ курсивное обращение к фумкции РАТН, для того чтобы определить, существует ли путь к узлу ЕЖР от уала ЖОРЕ-, которым оканчивается выбранная дуга. Если такой путь существует, вычисление рекурсивного обращения успешно, поэтому успешно эаканчиваегся и вычисление текущей активации функции РАТИ. По если пути от ЖОРЕ- к ЕЖР лет, вычисление рекурсивного обращения неуспешно. Выработанный при этом неуспех заставляет программу выбрать иную дугу, выходящую ие уала ВЕС-, после чего описанные действия повторяются, но уже по отношению к новой дуге. Подчеркнем, что при возвратах по неуспеху восстанавливаются прежние значения не только переменных функции РАТН, но и переменных, используемых в преднкатах и операторах графа.
Этим уничтожаются все следы работы операторов графа на неудачно выбранном пути, что обеспечивает возможность правильного продолжения поиска. Без режима воввратов было бы крайне трудно воосганавливать значения этих переменных, так как ни их названия, Пи сами операторы графа эарамее неизвестны. Отметим также, что метод перебора, использованный в функции РАТН, точно такой же, как и в ранее рассмотренных функциях ЯРМ и ФЭ.
Но есть и отличие: в функции РАТИ перебор организован не с помощью возвратов по неуспеху и циклов,а спомощью возвратов и рекурсий. 3.4. Управление режимом возвратов До сих пор мы рассматривали режим возвратов, так сказать, в чистом виде: при появлении в программе неуспеха она всегда возвращалась к последней развилке, где полностью восстанавливалась прежняя обстановка (прелснне значения переменных, списков свойств и т. д.). Но это не всегда удобно. Иногда нужен воз- врат не к последней развилке, а к одной мз предыдущих, и нередко необходимо только частичное восстановление обстановки в развилке. Например, в какой-то момент может быть обнаружено, что ответственность эа неуспех вычислений несет одна мэ предыдущих развилок и что никакой выбор в последующих развилках не приведет к успеху.
Чтобы не вести бессмысленный перебор в последних развилках, надо сразу вернуться к этой предыдущей развилке и исправить .выбор именно здесь. Может быть и так, что при исследовании альтернативы, оказавшейся неуопешной, была получена илформация, представляющая интерес и для других альтернатив. Чтобы не уничтожать такую информацию, следует при воаврате по неуспеху сохранить у переменных и других объектов программы ге значения, поторые они получили при исследовании этой альтернативы, а не восстанавливать их прежние значения, существоеавшие до выбора альтернативы. Для выполнения подобных действий, т. е.
для управления режимом возвратов, в язык введены специальные средства. Но прежде чем рассказать о них, мы уточпим, каким образом в языке осуществляются возвраты по неуспеху и как восстанавливаются прежние значения переменных и других объектов программы. Выполнение программы в режиме возвратов можно сравнить с анализом шахматной позиции, когда делается несколвко ходов вперед и затем оценивается получившаяся позиция, после чего' восстанавливается исходная поаяция и рассматривается другая последовательность ходов.
Каким образом можно восстановить нсхэдкую позицию, когда было сделано несколько ходов впередт Можно поступить так: один раз ааписать расположение фигур в исходной позиции, а затем каждый раз по этой ааписи восстанавливать данную позицию. Но можно поступить иначе: запоминать сделанные ходы, а затем, выполняя обратные ходы, постепенно втсстаназливать исходную позицию. Точно так же существует и два способа организации возвратов по неуспеху. В первом иэ них при появлении развилки запоминается копия текущего состояния программы, а при поивлении неуспеха состояние программы восстанавливается по последней из копий, после чего вычисления возобновляются от этого состояния.
Именно такая трактовка режима возвратов использовалась нами в нредьщущих параграфах. Однако дли планера более точной является иная трактовка — с аобраткыыи ходами». Считается, что попутно с выполнением любой плэнерской программы запоминается некоторая информация о ее действиях. Так, при появлении в программе развилки запоминается это место программы (будем ыеоритгн ставится Р-.гочка) и запоминается, какие альтернативы и в каком порядке должны адесь выбираться. Ковда же изменяется значение какого-.нибудь объекта праграм126 мы, запоминается обрстнььй оператор, предназначенный для отмены произведенного действия. Например, если переменная Х имела значение А и было выполнено [БЕТ Х В], то запоминается обратный оператор [БЕТ Х А]; если же переменная'»' не имела эначения, а переменная Е имела аначенна С и было выполнено [13 (.У»Х) (В Е)], то запоминается два обратных оператора: [Вг(АББ16М Т] и [БЕТ Е С].
Вот такие Р-точки и обратные операторы и запоминаются в соответствующем порядке одновременко с «прямым» выполнением программы. При появлении в программе неуспеха ее анормальное» выполнение прекращается л пачинается распространение неуспеха— как бы обратное вычисление ее: выполняются обраъиые операто- ры в порядке, обратном их аапоминаялю. Тем самым шаг ва шагом ликвидируются ранее произведенные изменения в еначениях объектов провраммы. Раопростраление неуспеха прекращаевся, когда при таком «попятном» движении встретится первая Р-точка (она соответствует последней развилке щюграммы). Р-точна — это «преграда» для неуспеха, она остаяэминеает, «ловит» неуспех* ).
Следовательно, при распространении неуспеха сыполня»отея только те операторы, которые появились после того, как бьша поставлена последняя Р-точка. Осуществив таким образом возврат к последней развилке и восстановление прежних значений своих объектов, программа возвращается в «нормальное» состояние, выбирает первую иэ оставшихся альтернатив развилки я воаобновляет от этой точки свои вычисления.
Когда в развилке выбирается последняя альтернатива, соответствующая Р-точка уничтожается («забывается»), поэтому следующий неуспех будет распространяться уже до предыдущей Р-точки. Именно такой интерпретации выполнения программ в режиме возвратов мы я будем придерживаться в дальнейшем, В частности, воопользуемся ею, чтобы объяснить способы управления этим режимом. Воаможность воавратов к произвольныы развилкам прстраммы- обеспечивается уничтожением ранее поставленных Р-точек. Действительно, при отмене Р-точки в соответствующем месте программы снимаетоя «преграда» для неуспеха.
Поэтому, если уничтожить несколько последних Р-точек программы, а затем выработать обычный неуспех, то он сразу распространится до Р-точки, предшествующей уничтоженным. ° ) Раавилку можно рассматривать как совокупность Р-точки, которая останавливает распрострапение неуопеха, я генератора альтернатив, который выдает по одной альтернативе при каждом обращении к нему.
В основе же частичного восстановлепия обстановки в развилке лежит уннпожение ранее запомненных обратпых операторов, а также выполненно действий беа одновременного аапомииання обратных операторов. В самом деле, отменить при неуспехе побочные эффекты могут только обратные операторы, а в обоих указанных случаях таких операторов не остается. Поэтому при неуспехе соответствующие действия программы не будут отменены, т. е.
не' будут ~восстановлены прежние значения наких-то объектов программы и будут сохранены их последние значения. Встроенные функции яаыва, позволяющие уничтожать Р-точки и обратные операторы и изменять значения объектов программы без запоминания обратных операторов, описываются в следующих параграфах. 3.5. Неотмеияемые действия В этом параграфе рассматрпваются функции с побочным эффектом, при вычислении которых обратные операторы не аапомннаются. Действия таких функций, следовательно, на отмепя|отся при неуспехе. Подобныо функции не столь уж редки в планере.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
