Языки программирования помогают не утонуть в деталях. Язык Лисп хорош тем, что сам управляется со многими из них, предоставляя программисту выжать максимум из ограниченной способности удерживать сложное. Эта глава посвящена тому, как с помощью макросов можно обращаться с ещё одним важным классом подробностей: подробностей преобразования недетерминированного алгоритма в детерминированный.
В главе пять частей. Первая объясняет смысл недетерминированности. Вторая описывает реализацию недетерминированного выбора и неудачи на Scheme с использованием продолжений. В третьей представлена версия на Common Lisp на основе передающих продолжения макросов из 20-ой главы. Четвёртая показывает, как понять оператор отсечения (cut) вне зависимости от Пролога. Последняя предлагает уточнения исходных недетерминированных операторов.
Оператор недетерминированного выбора используется в дальнейшем при написании ATN-компилятора в 23-ей главе и встроенного Пролога в 24-ой.
Недетерминированный алгоритм — алгоритм на основе сверхъестественного предвидения. Зачем говорить о них, не располагая сверхъестественными компьютерами? Потому что недетерминированный алгоритм можно имитировать детерминированным. Это особенно просто в чисто функциональных программах (не имеющих побочных эффектов). В них его можно реализовать с помощью поиска с отступлением.
Эта глава посвящена имитации неопределённости в функциональных программах. Располагая таким имитатором, мы рассчитываем справляться с проблемами, разрешимыми на действительно недетерминированной машине. Зачастую программа с сверхъестественными озарениями пишется проще обычной, так что этот имитатор иметь в наличии хорошо.
Данный раздел очерчивает класс возможностей, предоставляемых нам неопределённостью; следующий демонстрирует их полезность в некоторых программах. Примеры написаны на Scheme. (О некоторых различиях между Scheme и Common Lisp сказано в начале 20-ой главы.)
Недетерминированный алгоритм отличается от детерминированного использованием специальных операторов выбора и неудачи. Выбор принимает ограниченное множество и возвращает один элемент. Чтобы объяснить принцип работы выбора, нужно ввести понятие вычислительного будущего.
Здесь выбор представлен функцией choose, принимающей список и
возвращающей его элемент. Для каждого элемента есть набор будущих,
принимаемых вычислением при условии выбора этого элемента. В
следующем примере
(let ((x (choose '(1 2 3))))
(if (odd? x)
(+ x 1)
x))к моменту достижения choose у вычисления три возможных будущих:
- Если
chooseвозвращает 1, вычисление по ветви “то” вернёт 2. - Если
chooseвозвращает 2, вычисление по ветви “иначе” вернёт 2. - Если
chooseвозвращает 3, вычисление по ветви “то” вернёт 4.
В данном случае мы знаем точное будущее сразу, как только choose
вернёт какое-либо значение. Вообще же каждый выбор связан с набором
возможных будущих, потому что в некоторых из них могут быть
дополнительные выборы. К примеру
(let ((x (choose '(2 3))))
(if (odd? x)
(choose '(a b))
x))после первого выбора имеется два набора будущих:
- Если
chooseвозвращает 2, вычисление по ветви “иначе” вернёт 2. - Если
chooseвозвращает 3, вычисление по ветви “то” разделится на
два возможных будущих, одно из которых возвращает a, другое — b.
У первого набора одно будущее, у второго — два; всего — три.
Здесь важно, что каждый из альтернативных выборов связан со своим набором возможных будущих. Какой из них будет возвращён? Можно предположить, что выбор работает следующим образом:
- Он вернёт лишь тот набор будущих, в котором хотя бы одно не заканчивается неудачей.
- Выбор из нуля альтернатив эквивалентен неудаче.
Так, к примеру, в:
(let ((x (choose '(1 2))))
(if (odd? x)
(fail)
x))каждый возможный выбор имеет по одному будущему. Поскольку выбор 1
содержит вызов fail, может быть выбрано лишь 2. Поэтому выражение в
целом детерминированно, всегда возвращая 2.
Однако, следующее выражение недетерминированно:
(let ((x (choose '(1 2))))
(if (odd? x)
(let ((y (choose '(a b))))
(if (eq? y 'a)
(fail)
y))
x))После первого выбора, у 1 два возможных будущих и у 2 одно. У
первого, однако, будущее детерминированно, поскольку выбор a вызвал
бы fail. Поэтому выражение в целом может вернуть либо b, либо
2.
Наконец, однозначно следующее выражение:
(let ((x (choose '(1 2))))
(if (odd? x)
(choose '())
x))потому что выбор 1 означает последующий выбор без единого варианта.
Так что этот пример эквивалентен пред-предпоследнему.
Возможно, это ещё не стало очевидным, но мы обрели абстракцию изумительной силы. В недетерминированных алгоритмах можно сказать “выбери элемент так, чтобы ничего в дальнейшем не привело к неудаче”. Например, вот полностью корректный алгоритм для установления, есть ли у кого-либо предок по имени Игорь:
Функция Иг(и)
если имя(и) = “Игорь”
вернуть и
иначе если родители(и)
вернуть Иг(выбрать(родители(и)))
иначе неудача
Оператор неудачи используется, чтобы повлиять на значение, возвращаемое выбором. Если встречается неудача, выбор сработал неправильно. Но он по определению выбирает правильно. Поэтому всё, что нам нужно, чтобы предотвратить вычисление определённой ветви - поместить где-либо в ней неудачу. Так, рекурсивно проходя поколения предков, функция Иг на каждом шаге выбирает ветвь, ведущую к Игорю, угадывая, по отцовской или материнской линии идти.
Это как если бы программа могла указать выбору взять один из альтернативных элементов, использовать возвращённое значение сколько понадобится, и ретроспективно решить, используя неудачу как запрет, что выбору нужно было взять. И вуаля, оказывается, что выбор его и взял. Именно в этом смысле говорят, что выбор обладает предвидением.
На деле, конечно, выбор не сверхъестественен. Всякая его реализация имитирует нужное угадывание отступлением от ошибок, подобно мыши в лабиринте. Но всё это отступление - скрываемо. Располагая лишь какими-либо выбором и неудачей, уже можно писать алгоритмы подобно вышеприведённому, как если бы действительно возможно было угадать, по пути какого из предков следовать. Используя выбор, можно получить алгоритм поиска в проблемной области, написав лишь алгоритм её обхода.
Многие классические проблемы можно описать как проблемы поиска, и
недетерминированность часто оказывается для них полезной абстракцией.
Допустим, nodes содержит список вершин в дереве, а функция (kids
n) возвращает наследников вершины n, либо #f в их отсутствие. Мы
хотим определить функцию (descent n1 n2), возвращающую список вершин
на каком либо пути между n1 и её наследником n2. Рисунок 22.1
представляет детерминированный вариант этой функции.
(define (descent n1 n2)
(if (eq? n1 n2)
(list n2)
(let ((p (try-paths (kids n1) n2)))
(if p (cons n1 p) #f))))
(define (try-paths ns n2)
(if (null? ns)
#f
(or (descent (car ns) n2)
(try-paths (cdr ns) n2))))Недетерминированность позволяет программисту не заботится о способе
поиска пути. Можно просто сказать выбору найти вершину n такую,
чтобы от неё до цели был путь. Этот вариант descent, изображённый
на рисунке 22.2, проще.
(define (descent n1 n2)
(cond ((eq? n1 n2) (list n2))
((null? (kids n1)) (fail))
(else (cons n1 (descent (choose (kids n1)) n2)))))Данный вариант не занимается явным поиском вершины на правильном пути.
Он написан в предположении, что choose выбирает желаемую n.
Привыкший лишь к детерминированным программам может и не заметить, что
choose словно угадывает, какая n войдёт в удачное вычисление.
Возможно, ещё убедительнее возможности выбора продемонстрирует
угадывание при вызове функций. На рисунке 22.3 пара функций угадывает
два числа, суммирующихся к заданному. Первая, two-numbers,
недетерминированно выбирает два числа и возвращает их в виде списка.
Вторая, parlor-trick, обращается за ним к первой. Отметим, что
two-numbers не знает о заданном числе.
(define (two-numbers)
(list (choose '(0 1 2 3 4 5))
(choose '(0 1 2 3 4 5))))
(define (parlor-trick sum)
(let ((nums (two-numbers)))
(if (= (apply + nums) sum)
'(the sum of ,@nums)
(fail))))Если два угаданных выбором числа не образуют требуемой суммы,
вычисление не удаётся. Можно считать, что choose избегает неудачных
вычислительных путей, если есть хоть один удачный. Предположительно,
при задании числа в правильном диапазоне, choose угадывает верно;
так и происходит:[fn:: Поскольку порядок вычисления аргументов в
Scheme (в отличие от Common Lisp, в котором он слева направо), этот
вызов может вернуть и (THE SUM OF 5 2).]
> (parlor-trick 7)
(THE SUM OF 2 5)В случае простого поиска, встроенная функция find-if из Common Lisp
сработает не хуже. Где же преимущество недетерминированного выбора?
Почему не пройти просто в цикле по списку альтернатив в поиске
желаемого элемента? Ключевое отличие выбора от обыкновенной
итерации в том, что его область действия по отношению к неудаче не
ограничена. Недетерминированный выбор смотрит сколь угодно далеко в
будущее; если в будущем случится что-либо, аннулирующее прошлый
выбор, можно считать, что он и не совершался. Как было показано на
примере parlor-trick, оператор неудачи работает даже после возврата
из функции, содержащей выбор.
Такие же неудачи случаются и при поиске в Прологе. Недетерминированность в нём полезна, поскольку одна из характерных особенностей этого языка — возможность получать ответы на запросы по одному за раз. Не возвращая все удовлетворяющие ответы сразу, Пролог справляется с рекурсивными правилами, которые иначе бы выдавали бесконечное множество ответов.
Вашим первым впечатлением от descent, возможно, как и от сортировки
слиянием, был вопрос: где же выполняется работа? Как и при сортировке
слиянием, она происходит неявно, но всё же происходит. В разделе 22.3
описана реализация выбора, превращающая все вышеприведённые примеры
в рабочие программы.
Эти примеры иллюстрируют значение недетерминированности как абстракции. Лучшие абстракции программирования сокращают не только код, но и мысль. В теории автоматов некоторые доказательства затруднительно даже понять без обращения к недетерминированности. Язык, допускающий недетерминированность, вероятно, предоставляет программистам сравнимое преимущество.
Этот раздел объясняет, как имитировать недетерминированность с помощью
продолжений. Рисунок 22.4 содержит реализацию выбора и неудачи на
Scheme, задействующую отступления. Ищущая с отступлением программа
должна как-либо сохранять достаточно информации для следования по иным
альтернативам, если избранная заканчивается неудачей. Эта информация
хранится в виде продолжений в глобальном списке *paths*.
(define *paths* ())
(define failsym '@)
(define (choose choices)
(if (null? choices)
(fail)
(call-with-current-continuation
(lambda (cc)
(set! *paths*
(cons (lambda ()
(cc (choose (cdr choices))))
*paths*))
(car choices)))))
(define fail)
(call-with-current-continuation
(lambda (cc)
(set! fail
(lambda ()
(if (null? *paths*)
(cc failsym)
(let ((p1 (car *paths*)))
(set! *paths* (cdr *paths*))
(p1)))))))Функция choose принимает список альтернатив choices. Если он
пуст, вызывается fail, возвращающая вычисление обратно к последнему
выбору. Если он имеет вид (first . rest), choose добавляет в
*paths* продолжение, в котором choose вызывается с rest, и
возвращает first.
Функция fail проще, она всего лишь забирает продолжение из *paths*
и вызывает его. Если сохранённых путей больше нет, она возвращает
символ @. Однако недостаточно просто вернуть его, иначе он станет
результатом последнего вызова choose. Нужно вернуть его прямо на
верхний уровень. Мы достигаем этого, связывая cc с продолжением, в
котором определена fail — предположительно, на верхнем уровне.
Вызывая cc, fail возвращает прямо туда.
Реализация на рисунке 22.4 использует *paths* в качестве стека,
всегда возвращаясь обратно к последнему моменту выбора. Эта
стратегия, называемая хронологическим отступлением, осуществляет
поиск проблемной области в глубину. И слово «недетерминированность»
часто ассоциируют только с реализацией, ищущей в глубину. Так - и в
классической статье Флойда о недетерминированных алгоритмах, и
недетерминированных парсерах, и в Прологе. Однако, нужно отметить,
что реализация на рисунке 22.4 - не единственная возможная, и даже не
корректная. В принципе, выбор должен уметь возвращать объекты,
удовлетворяющие любой вычислимой спецификации, тогда как наш вариант
choose и fail может никогда не завершиться, если граф содержит
циклы.
С другой стороны, на практике недетерминированность часто означает именно поиск в глубину, эквивалентный нашему, оставляя на пользователе обязанность избегать циклов в области поиска. Однако заинтересованный читатель найдёт реализацию настоящих выбора и неудачи в последнем разделе этой главы.
В этом разделе говорится о том, как написать выбор и неудачу на
Common Lisp. Предыдущий раздел показал лёгкость имитации
недетерминированности на Scheme с использованием call/cc; ведь
продолжения - прямое воплощение нашей теоретической идеи
вычислительного будущего. На Common Lisp же вместо этого можно
применить передающие продолжения макросы из 20-ой главы. Вариант
выбора, полученный с их помощью, будет несколько безобразнее
написанного ранее на Scheme, но на деле эквивалентен ему.
(defparameter *paths* nil)
(defconstant failsym '@)
(defmacro choose (&rest choices)
(if choices
`(progn
,@(mapcar #'(lambda (c)
`(push #'(lambda () ,c) *paths*))
(reverse (cdr choices)))
,(car choices))
'(fail)))
(defmacro choose-bind (var choices &body body)
`(cb #'(lambda (,var) ,@body) ,choices))
(defun cb (fn choices)
(if choices
(progn
(if (cdr choices)
(push #'(lambda () (cb fn (cdr choices)))
*paths*))
(funcall fn (car choices)))
(fail)))
(defun fail ()
(if *paths*
(funcall (pop *paths*))
failsym))Рисунок 22.5 демонстрирует реализацию неудачи и двух вариантов
выбора на Common Lisp. Синтаксис этого choose немного отличен от
предыдущего. Тот принимал один параметр: список вариантов выбора.
Этот же совпадает по синтаксису с progn. За ним может следовать
любое число выражений, из которых для вычисления выбирается только
одно:
> (defun do2 (x)
(choose (+ x 2) (* x 2) (expt x 2)))
DO2
> (do2 3)
5
> (fail)
6
На верхнем уровне работа отступления, лежащего в основе
недетерминированного поиска, заметнее. Переменная *paths* содержит
ещё не пройденные пути. Когда вычисление достигает вызова choose с
несколькими альтернативами, первая из них вычисляется, а остальные
сохраняются в *paths*. Если программа в дальнейшем достигает
fail, последнее сохранённое значение извлекается из *paths* и
перезапускается. Когда список исчерпывается, fail возвращает
специальное значение:
> (fail) 9 > (fail) @
На рисунке 22.5 константа failsym, обозначающая неудачу, определена
как символ @. При желании использовать его в качестве обычного
возвращаемого значения, можно в качестве failsym использовать
(gensym).
Второй оператор недетерминированного выбора, choose-bind, отличен по
форме, принимая символ, список вариантов выбора и блок кода. Он
выберет одну из альтернатив, свяжет с ней символ и выполнит код.
> (choose-bind x '(marrakesh strasbourg vegas)
(format nil "Let's go to ~A." x))
"Let's go to MARRAKESH."
> (fail)
"Let's go to STRASBOURG."
То, что на Common Lisp целых два оператора выбора - лишь вопрос
удобства. Эффекта choose можно было бы добиться, всякий раз заменяя
(choose (foo) (bar))
на
(choose-bind x '(1 2)
(case x
(1 (foo))
(2 (bar))))
но программы более читаемы, когда на этот случай имеется особый
оператор. [fn:: Более того, внешний интерфейс мог бы состоять всего
из одного оператора, потому что (fail) эквивалентен (choose).]
Операторы выбора на Common Lisp сохраняют связи соответствующих
переменных в замыканиях с захватом переменных. Будучи макросами,
choose и choose-bind раскрываются в лексической среде содержащих
их выражений. Заметьте, что в *paths* помещается замыкание вокруг
сохраняемой альтернативы, включающее в себя все связи имеющихся
лексических переменных. К примеру, в выражении
(let ((x 2))
(choose
(+ x 1)
(+ x 100)))при перезапуске замыкания понадобится значение x. Вот почему
choose оборачивает свои аргументы в лямбды. Выражение выше
макрорасширяется до
(let ((x 2))
(progn
(push #'(lambda () (+ x 100))
*paths*)
(+ x 1)))В *paths* сохраняется замыкание с указателем на x. Именно
необходимость хранить переменные в замыканиях диктует различие
синтаксиса между операторами выбора на Scheme и Common Lisp.
Если использовать choose и fail вместе с передающими продолжения
макросами из главы 20, указатель на переменную продолжения *cont*
тоже сохраняется. Определяя функции с помощью =defun, вызывая с
=bind, получая возвращаемые значения с =values, можно применять
недетерминированность во всякой программе на Common Lisp.
С этими макросами можно успешно запустить примеры с недетерминированным
выбором в подпрограммах. Рисунок 22.6 показывает версию
parlor-trick на Common Lisp, работающую так же, как в Scheme:
(=defun two-numbers ()
(choose-bind n1 '(0 1 2 3 4 5)
(choose-bind n2 '(0 1 2 3 4 5)
(=values n1 n2))))
(=defun parlor-trick (sum)
(=bind (n1 n2) (two-numbers)
(if (= (+ n1 n2) sum)
‘(the sum of ,n1 ,n2)
(fail))))
> (parlor-trick 7) (THE SUM OF 2 5)
Это работает, потому что выражение
(= values n1 n2)
макрорасширяется до
(funcall *cont* n1 n2)
внутри choose-bind. Каждый choose-bind в свою очередь расширяется
в замыкание, сохраняющее указатели на все переменные в теле кода,
включая *cont*.
Ограничения применимости choose, choose-bind и fail совпадают с
данными на рисунке 20.5 для кода с передающими продолжения макросами.
Встречающееся выражение выбора должно вычисляться последним. Поэтому
для последовательных выборов операторы выбора на Common Lisp должны
быть вложены друг в друга:
> (choose-bind first-name '(henry william)
(choose-bind last-name '(james higgins)
(=values (list first-name last-name))))
(HENRY JAMES)
> (fail)
(HENRY HIGGINS)
> (fail)
(WILLIAM JAMES)
что приведёт, как обычно, к поиску в глубину.
Операторы, определённые в главе 20, нуждались в том, чтобы вычисляться
последними. Это право теперь унаследовано новым слоем макросов;
=values должно встречаться в choose, а не наоборот. То есть,
(choose (=values 1) (=values 2))
будет работать, а
(=values (choose 1 2))
нет. (В последнем случае расширение choose не захватит употребление
*cont* в расширении =values.)
До тех пор, пока эти требования, как и указанные на рисунке 20.5,
будут соблюдаться, недетерминированный выбор на Common Lisp будет
работать как и на Scheme. Рисунок 22.7 показывает вариант
недетерминированного поиска по дереву с рисунка 22.2 на Common Lisp.
Функция descent - результат прямого преобразования, правда, чуть
более длинный и неприятный.
> (=defun descent (n1 n2)
(cond ((eq n1 n2) (=values (list n2)))
((kids n1) (choose-bind n (kids n1)
(=bind (p) (descent n n2)
(=values (cons n1 p)))))
(t (fail))))
DESCENT
> (defun kids (n)
(case n
(a '(b c))
(b '(d e))
(c '(d f))
(f '(g))))
KIDS
> (descent 'a 'g)
(A C F G)
> (fail)
@
> (descent 'a 'd)
(A B D)
> (fail)
(A C D)
> (fail)
@
> (descent 'a 'h)
@Теперь мы располагаем в Common Lisp средствами для недетерминированного поиска без явного отступления. Озаботившись написанием этого кода, теперь можно пожинать плоды, несколькими строками описывая в противном случае большие и спутанные программы. Построив ещё один уровень макросов над этими, можно будет написать ATN-компилятор на одной странице кода (глава 23) и набросок Пролога на двух (глава 24).
Программы с использованием выбора на Common Lisp стоит компилировать с оптимизацией хвостовой рекурсии - не только ради ускорения, но и чтобы предотвратить исчерпание места на стеке. Программы, «возвращающие» значения вызовом продолжений, в действительности не возвращаются до последней неудачи. Без хвостовой оптимизации стек будет расти и расти.
Этот раздел рассказывает про использование отсечений в недетерминированных программах на Scheme. Хотя слово отсечение пришло из Пролога, сама идея принадлежит недетерминированности вообще. Она может пригодиться во всякой программе с недетерминированным выбором.
Отсечения легче понять независимо от Пролога. Представим жизненный пример. Производитель шоколадных конфет решает провести рекламную кампанию. Небольшое число коробок будут содержать жетоны, обмениваемые на ценные призы. Ради справедливости, никакие две выигрышные коробки не отправляются в один город.
После начала рекламной кампании выясняется, что жетоны достаточно малы, чтобы быть проглочены детьми. Преследуемые видениями грядущих исков, юристы компании начинают неистово выискивать все выигрышные коробки. В каждом городе их продают во многих магазинах, в каждом магазине - много коробок. Но юристам может не понадобиться открывать каждую: как только они найдут нужную в каком-либо городе, им не придётся больше в нём искать, потому что таких в каждом городе — не более одной. Осознать это значит сделать отсечение.
Отсекается часть исследуемого дерева. Для нашей компании это дерево существует физически: его корень - в главном офисе; дочерние узлы - магазины в каждом городе; от них - коробки в соответствующих магазинах. Когда юристы находят одну из коробок с жетоном, они отрезают все неисследованные ветви в том же городе.
Отсечение в действительности совершается в две операции: да, требуется знать бесполезную часть дерева, но сначала нужно отметить точку дерева, в которой можно произвести отсечение. В примере с шоколадной компанией здравый смысл подсказывает, что дерево отмечается по приходу в город. В абстрактных понятиях сложно объяснить, как работает отсечение в Прологе, потому что отметки расставляются неявно. С явным же отмечающим оператором действие отсечения понять будет легче.
(define (find-boxes)
(set! *paths* ())
(let ((city (choose '(la ny bos))))
(newline)
(let* ((store (choose '(1 2)))
(box (choose '(1 2))))
(let ((triple (list city store box)))
(display triple)
(if (coin? triple)
(display 'c))
(fail)))))
(define (coin? x)
(member x '((la 1 2) (ny 1 1) (bos 2 2))))Программа на рисунке 22.8 недетерминированно ищет в уменьшенном
подобии дерева шоколадной компании. При открывании каждой коробки она
отображает список (город магазин коробка). Если в коробке
оказывается жетон, выводится c:
> (find-boxes) (LA 1 1)(LA 1 2)C(LA 2 1)(LA 2 2) (NY 1 1)C(NY 1 2)(NY 2 1)(NY 2 2) (BOS 1 1)(BOS 1 2)(BOS 2 1)(BOS 2 2)C @
Для реализации техники оптимизированного поиска, открытой юристами,
нужны два новых оператора: mark и cut. Одна из возможных
реализаций представлена на рисунке 22.9. Тогда как
недетерминированность сама по себе не зависит от реализации,
сокращение дерева поиска, будучи приёмом оптимизации, определяется
способом реализации choose. Данные операторы mark и cut
подходят для choose, ищущего в глубину (рисунок 22.4).
(define (mark) (set! *paths* (cons fail *paths*)))
(define (cut)
(cond ((null? *paths*))
((equal? (car *paths*) fail)
(set! *paths* (cdr *paths*)))
(else
(set! *paths* (cdr *paths*))
(cut))))Общая идея в том, что mark сохраняет маркеры в списке
неисследованных точек выбора *paths*. Вызов cut вынимает из
*paths* элементы вплоть до маркера, положенного туда последним. Что
бы использовать в качестве маркера? Скажем, символ m; но тогда
пришлось бы переписать fail, чтобы он игнорировал встречающиеся
символы m. К счастью, поскольку функции — тоже объекты данных, один
маркер позволит использовать fail без изменений: это сама функция
fail. Тогда, если fail натолкнётся на маркер, она просто вызовет
саму себя.
Рисунок 22.10 показывает использование этих операторов для сокращения
дерева поиска в случае шоколадной компании. (Изменённые строки
отмечены точкой с запятой.) mark вызывается по выбору города. К
этому моменту *paths* содержит одно продолжение, соответствующее
поиску в оставшихся городах.
(define (find-boxes)
(set! *paths* ())
(let ((city (choose '(la ny bos))))
(mark) ;
(newline)
(let* ((store (choose '(1 2)))
(box (choose '(1 2))))
(let ((triple (list city store box)))
(display triple)
(if (coin? triple)
(begin (cut) (display 'c))) ;
(fail)))))
Когда находится коробка с жетоном, вызывается cut, возвращающий
*paths* к состоянию до вызова mark. Результат отсечения не
проявляется до следующего вызова fail. Но когда он, после вызова
display, наконец обнаруживает себя, следующий fail отбрасывает
поиск вплоть до самого первого choose, даже если ниже по дереву ещё
остались неисчерпанные точки выбора. В результате, как только
находится коробка с жетоном, поиск продолжается со следующего города:
> (find-boxes) (LA 1 1)(LA 1 2)C (NY 1 1)C (BOS 1 1)(BOS 1 2)(BOS 2 1)(BOS 2 2)C @
Так, открытыми оказались семь коробок вместо двенадцати.
b *-- a --* e \ * \ * * / * / c --* d
Детерминированной программе поиска по графу пришлось бы предпринимать
явные шаги, чтобы не застрять в циклическом пути. Рисунок 22.11
изображает направленный граф, содержащий цикл. Поиск пути между a и
e рискует попасться в круг <a b c>. Без рандомизации, поиска в
ширину или отмечания циклических путей, детерминированная программа
может и не завершиться. Реализация path на рисунке 22.12 избегает
зацикливания поиском в ширину.
(define (path node1 node2)
(bf-path node2 (list (list node1))))
(define (bf-path dest queue)
(if (null? queue)
'@
(let* ((path (car queue))
(node (car path)))
(if (eq? node dest)
(cdr (reverse path))
(bf-path dest
(append (cdr queue)
(map (lambda (n)
(cons n path))
(neighbors node))))))))В принципе, недетерминированность избавляет от всякого беспокойства о
циклических путях. Да, реализация выбора и неудачи поиском в
глубину из раздела 22.3 уязвима для циклических путей, но, будучи
более требовательным, можно было бы ожидать, чтобы недетерминированный
выбор отбирал объект, удовлетворяющей всякой вычислимой
спецификации, без исключения и в этом случае. Корректный выбор
позволил бы написать path короче и яснее, как показано на рисунке
22.13.
(define (path node1 node2)
(cond ((null? (neighbors node1)) (fail))
((memq node2 (neighbors node1)) (list node2))
(else (let ((n (true-choose (neighbors node1))))
(cons n (path n node2))))))Этот раздел показывает, как реализовать выбор и неудачу, безопасные от циклических путей. По-настоящему недетерминированная версия на Scheme показана на рисунке 22.14. Программы, использующие её, найдут решение для всякого недетерминированного алгоритма, лишь бы хватило аппаратных ресурсов.
(define *paths* ())
(define failsym '@)
(define (true-choose choices)
(call-with-current-continuation
(lambda (cc)
(set! *paths* (append *paths*
(map (lambda (choice)
(lambda () (cc choice)))
choices)))
(fail))))
(define fail)
(call-with-current-continuation
(lambda (cc)
(set! fail
(lambda ()
(if (null? *paths*)
(cc failsym)
(let ((p1 (car *paths*)))
(set! *paths* (cdr *paths*))
(p1)))))))Реализация true-choose на рисунке 22.14 работает со список
сохранённых путей как с очередью. Программы, использующие
true-choose, будут искать свои пространства состояний в ширину. При
достижении точки выбора, продолжения каждой альтернативы добавляются в
конец списка сохранённых путей. (map в Scheme возвращает то же, что
и mapcar в Common Lisp.) После этого вызывается fail, определение
которой осталось тем же.
Эта версия выбора позволит реализации path на рисунке 22.13 найти
путь (причём кратчайший) от a до e на графе на рисунке 22.11.
Хотя ради полноты здесь и была приведена корректная реализация выбора и неудачи, исходной обычно будет достаточно. Ценность языковой абстракции не уменьшается уже от того лишь, что её реализация не является формально корректной: в некоторых языках мы поступаем так, будто нам доступны все целые числа, тогда как наибольшим может быть всего лишь 32767. До тех, пока мы отдаём себе отчёт в том, сколь долго можно предаваться иллюзии, в ней мало опасности; во всяком случае, достаточно мало, чтобы абстракция оставалась выгодной. Краткость программ в следующих двух главах в значительной мере обусловлена использованием недетерминированных выбора и неудачи.