Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 88
Текст из файла (страница 88)
Мы можемввести вышеприведенное определение prime-sum-pair в управляющем цикле ambинтерпретатора (наряду с определениями prime?, an-element-of и require) и запустить процедуру:;;; Ввод Amb-Eval:(prime-sum-pair ’(1 3 5 8) ’(20 35 110))42 Мы предполагаем, что уже заранее определена процедура prime?, которая проверяет числа на простоту.Даже если такая процедура определена, prime-sum-pair может подозрительно напоминать бестолковую попытку определения квадратного корня на псевдо-Лиспе из начала раздела 1.1.7.
На самом деле, подобного родапроцедура вычисления квадратного корня может быть сформулирована в виде недетерминистской программы.Вводя в интерпретатор механизм поиска, мы размываем границу между чисто декларативными описаниямии императивными спецификациями способов вычислить ответ. В разделе 4.4 мы пойдем еще дальше в этомнаправлении.4.3. SCHEME с вариациями —недетерминистское вычисление383;;; Начало новой задачи;;; Значение Amb-Eval:(3 20)Возвращенное значение было получено после того, как интерпретатор сделал несколькопопыток выбора из каждого списка, последняя из которых оказалась успешной.В разделе 4.3.1 вводится форма amb и показывается, как она поддерживает недетерминизм через механизм поиска, встроенный в интерпретатор.
В разделе 4.3.2 приводятсяпримеры недетерминистских программ, а раздел 4.3.3 содержит подробности того, какреализовать amb-интерпретатор путем модификации обычного интерпретатора Scheme.4.3.1. Amb и searchЧтобы расширить Scheme и поддержать недетерминистское программирование, мывводим новую особую форму amb43 . Выражение (amb he1 i he2 i ... hen i) возвращает «произвольным образом» значение одного из n выражений hei i. Например, выражение(list (amb 1 2 3) (amb ’a ’b))имеет шесть возможных значений:(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)Amb с одним вариантом возвращает обыкновенное (одно) значение.Amb без вариантов — выражение (amb) — является выражением без приемлемыхзначений. С операционной точки зрения, выполнение выражения (amb) приводит к«неудаче» в вычислении: выполнение обрывается, и никакого значения не возвращается.
При помощи этого выражения можно следующим образом выразить требование,чтобы выполнялось предикатное выражение p:(define (require p)(if (not p) (amb)))Через amb и require можно реализовать процедуру an-element-of, используемую выше:(define (an-element-of items)(require (not (null? items)))(amb (car items) (an-element-of (cdr items))))Если список пуст, an-element-of терпит неудачу. В противном случае он произвольным образом возвращает либо первый элемент списка, либо элемент, выбранный изхвоста списка.Можно также выразить выбор из бесконечного множества.
Следующая процедурапроизвольным образом возвращает целое число, большее или равное некоторому данному n:(define (an-integer-starting-from n)(amb n (an-integer-starting-from (+ n 1))))43 Идея недетерминистского программирования с помощью amb-выражений впервые была описана ДжономМаккарти в 1961 году (см. McCarthy 1967).384Глава 4.
Метаязыковая абстракцияЭто похоже на потоковую процедуру integers-starting-from, описанную в разделе 3.5.2, но есть важное различие: потоковая процедура возвращает поток, которыйпредставляет последовательность всех целых чисел, начиная с n, а процедура, написанная через amb, выдает одно целое число44 .Мысля абстрактно, мы можем представить, что выполнение выражения amb заставляет время разветвиться, и на каждой ветке оно продолжается с одним из возможныхзначений выбора.
Мы говорим, что amb представляет собой точку недетерминистского выбора (nondeterministic choice point). Если бы у нас была машина с достаточнымчислом процессоров, которые можно было бы динамически выделять, то поиск можнобыло бы реализовать напрямую. Выполнение происходило бы, как в последовательноймашине, пока не встретится выражение amb. В этот момент выделялись и инициализировались бы дополнительные процессоры, которые продолжали бы все параллельныепотоки выполнения, обусловленные выбором.
Каждый процессор продолжал бы последовательное выполнение одного из потоков, как если бы он был единственным, пока потокне оборвется, потерпев неудачу, не разделится сам или не завершится45 .С другой стороны, если у нас есть машина, которая способна выполнять толькоодин процесс (или небольшое число параллельных процессов), альтернативы приходится рассматривать последовательно.
Можно представить себе интерпретатор, который вкаждой точке выбора произвольным образом выбирает, по какой ветке продолжить выполнение. Однако случайный выбор может легко привести к неудачам. Можно было бызапускать такой интерпретатор многократно, делая случайный выбор и надеясь, что вконце концов мы получим требуемое значение, но лучше проводить систематическийпоиск (systematic search) среди всех возможных путей выполнения.
Amb-интерпретатор,который мы разработаем в этом разделе, реализует систематический поиск следующимобразом: когда интерпретатор встречает выражение amb, он сначала выбирает первыйвариант. Такой выбор может в дальнейшем привести к другим точкам выбора. В каждойточке выбора интерпретатор сначала будет выбирать первый вариант. Если выбор приводит к неудаче, интерпретатор автомагически46 возвращается (backtracks) к последнейточке выбора и пробует следующий вариант. Если в какой-то точке выбора варианты исчерпаны, интерпретатор возвращается к предыдущей точке выбора и продолжает оттуда.Такой процесс реализует стратегию поиска, которую называют поиск в глубину (depthfirst search) или хронологический поиск с возвратом (chronological backtracking)47 .44 На самом деле, различие между произвольным выбором с возвратом единственного значения и возвратомвсех возможных значений выбора определяется в некоторой степени точкой зрения.
С точки зрения того кода,который использует значение, недетерминистский выбор возвращает одно значение. С точки зрения программиста, проектирующего код, недетерминистский выбор потенциально возвращает все возможные значения, авычисление разветвляется, вследствие чего каждое значение исследуется отдельно.45 Можно возразить, что этот механизм безнадежно неэффективен.
Чтобы решить какую-нибудь просто сформулированную задачу таким образом, могут потребоваться миллионы процессоров, и бо́льшую часть временибо́льшая часть этих процессоров будет ничем не занята. Это возражение нужно воспринимать в контексте истории. Память раньше точно так же считалась дорогим ресурсом. В 1964 году мегабайт памяти стоил 400 000долларов.
Сейчас в каждом персональном компьютере имеется много мегабайтов памяти, и бо́льшую часть времени бо́льшая часть этой памяти не используется. Трудно недооценить стоимость электроники при массовомпроизводстве.46 Автомагически: «Автоматически, но при этом таким способом, который говорящий почему-либо (обычнолибо из-за его сложности, либо уродливости, или даже тривиальности) не склонен объяснять».
(Steele 1983;Raymond 1993)47 У встраивания стратегий автоматического поиска в языки программирования долгая и пестрая история.Первые предположения, что недетерминистские алгоритмы можно изящно реализовать в языке программиро-4.3. SCHEME с вариациями —недетерминистское вычисление385Управляющий циклУправляющий цикл amb-интерпретатора не совсем обычен. Он считывает выражениеи печатает значение первого успешного вычисления, как в примере с prime-sum-pairв начале раздела. Если нам хочется увидеть значение следующего успешного выполнения, мы можем попросить интерпретатор вернуться и попробовать породить значениеследующего успешного выполнения.
Для этого нужно ввести символ try-again. Есливводится какое-то другое выражение, а не try-again, интерпретатор начнет решатьновую задачу, отбрасывая неисследованные варианты предыдущей. Вот пример работы синтерпретатором:;;; Ввод Amb-Eval:(prime-sum-pair ’(1 3 5 8) ’(20 35 110));;; Начало новой задачи;;; Значение Amb-Eval:(3 20);;; Ввод Amb-Eval:try-again;;; Значение Amb-Eval:(3 110);;; Ввод Amb-Eval:try-again;;; Значение Amb-Eval:(8 35);;; Ввод Amb-Eval:try-againвания с поиском и автоматическим возвратом, высказывались Робертом Флойдом (Floyd 1967). Карл Хьюитт(Hewitt 1969) изобрел язык программирования Плэнер (Planner), который явным образом поддерживал автоматический хронологический поиск в возвратом, обеспечивая встроенную стратегию поиска в глубину.
Сассман,Виноград и Чарняк (Sussman, Winograd, and Charniak 1971) реализовали подмножество этого языка, названное ими МикроПлэнер (MicroPlanner), которое использовалось в работе по автоматическому решению задачи планированию действий роботов.
Похожие идеи, основанные на логике и доказательстве теорем, привелик созданию в Эдинбурге и Марселе изящного языка Пролог (Prolog) (который мы обсудим в разделе 4.4).Разочаровавшись в автоматическом поиске, Макдермот и Сассман (McDermott and Sussman 1972) разработалиязык Коннивер (Conniver), в котором имелись механизмы, позволявшие программисту управлять стратегиейпоиска. Однако это оказалось слишком громоздким, и Сассман и Столлман (Sussman and Stallman 1975) нашли более удобный в обращении подход, когда исследовали методы символьного анализа электрических цепей.Они разработали схему нехронологического поиска с возвратом, которая была основана на отслеживании логических зависимостей, связывающих факты, и стала известна как метод поиска с возвратом, управляемогозависимостями (dependency-directed backtracking). При всей своей сложности, их метод позволял строитьдостаточно эффективные программы, так как почти не проводилось излишнего поиска.
Дойл (Doyle 1979) иМакаллестер (McAllester 1978; McAllester 1980) обобщили и сделали более ясными идеи Столлмана и Сассмана, разработав новую парадигму для формулирования поиска, называемую сейчас поддержание истины (truthmaintenance). Все современные системы решения задач основаны на какой-либо форме поддержания истины. УФорбуса и де Клеера (Forbus and deKleer 1993) можно найти обсуждение изящных способов строить системыс поддержанием истины и приложения, в которых используется поддержание истины. Заби, Макаллестер иЧепман (Zabih, McAllester, and Chapman 1987) описывают недетерминистское расширение Scheme, основанноена amb; оно похоже на интерпретатор, обсуждаемый в этом разделе, но более сложно, поскольку используетпоиск с возвратом, управляемый зависимостями, а не хронологический.
Уинстон (Winston 1992) дает введениев обе разновидности поиска с возвратом.Глава 4. Метаязыковая абстракция386;;; Нет больше значений(prime-sum-pair (quote (1 3 5 8))(quote (20 35 110)));;; Ввод Amb-Eval:(prime-sum-pair ’(19 27 30) ’(11 36 58));;; Начало новой задачи;;; Значение Amb-Eval:(30 11)Упражнение 4.35.Напишите процедуру an-integer-between, которая возвращает целое число, лежащее междудвумя заданными границами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
