вы 3.5.4 и «более ленивыми» списками, описанными в этом разделе. Как можно воспользоваться этой дополнительной ленивостью?

Упражнение 4.33.

Бен Битобор проверяет вышеописанную реализацию при помощи выражения (car (a b c))

К его большому удивлению, в ответ выдается ошибка. После некоторого размышления он понимает, что «списки». которые получаются при чтении кавычек, отличаются от списков, управляемых новыми определениями cons, car и cdr. Измените работу интерпретатора с закавыченными выражениями так, чтобы при вводе списковых выражений в цикле управления получались настоящие ленивые списки.

Упражнение 4.34.

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

4.3 Scheme с вариациями - недетерминистское вычисление

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

Подобно обработке потоков, недетерминистское вычисление полезно в задачах типа «порождение и проверка». Рассмотрим такую задачу: даются два списка натуральных чисел, и требуется найти пару чисел - одно из первого списка, другое из второго, - сумма которых есть простое число. В разделе 2.2.3 мы уже рассмотрели, как это можно сделать при помощи операций над конечными последовательностями, а в разделе 3.5.3 - при помощи бесконечных потоков. Наш подход состоял в том, чтобы породить последовательность всех возможных пар и отфильтровать ее, выбирая пары, в которых сумма есть простое число. Порождаем ли мы на самом деле сначала всю последовательность, как в главе 2, или чередуем порождение и фильтрацию, как в главе 3, несущественно для общей картины того, как организовано вычисление.

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

(define (prime-sum-pair list1 list2) (let ((a (an-element-of list1)) (b (an-element-of list2))) (require (prime? (+ a b)))

(list a b)))

Может показаться, что эта процедура просто переформулирует задачу, а не указывает способ ее решить. Однако это законная недетерминистская програм-

42

ма.

Основная идея здесь состоит в том, что выражениям в недетерминистском языке разрешается иметь более одного возможного значения. Например, an-element-of может вернуть любой элемент данного списка. Наш интерпретатор недетерминистских программ будет автоматически выбирать возможное значение и запоминать, что он выбрал. Если впоследствии какое-либо требование не будет выполнено, интерпретатор попробует другой вариант выбора и будет перебирать варианты, пока вычисление не закончится успешно или пока варианты не иссякнут. Подобно тому, как ленивый интерпретатор освобождал программиста от заботы о деталях задержки и вынуждения значений, недетерминистский интерпретатор позволяет ему не заботиться о том, как происходит выбор.

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

Описываемый в этом разделе интерпретатор недетерминистских программ называется amb-интерпретатор, потому что он основан на новой особой форме amb. Мы можем ввести вышеприведенное определение prime-sum-pair в управляющем цикле amb-интерпретатора (наряду с определениями prime?, an-element-of и require) и запустить процедуру:

;;; Ввод Amb-Eval:

(prime-sum-pair (1358) (20 35 110)) ;;; Начало новой задачи ;;; Значение Amb-Eval: (3 20)

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

В разделе 4.3.1 вводится форма amb и показывается, как она поддерживает недетерминизм через механизм поиска, встроенный в интерпретатор. В

42Мы предполагаем, что уже заранее определена процедура prime?, которая проверяет числа на простоту. Даже если такая процедура определена, prime-sum-pair может подозрительно напоминать бестолковую попытку определения квадратного корня на псевдо-Лиспе из начала раздела 1.1.7. На самом деле, подобного рода процедура вычисления квадратного корня может быть сформулирована в виде недетерминистской программы. Вводя в интерпретатор механизм поиска, мы размываем границу между чисто декларативными описаниями и императивными спецификациями способов вычислить ответ. В разделе 4.4 мы пойдем еще дальше в этом направлении.

разделе 4.3.2 приводятся примеры недетерминистских программ, а раздел 4.3.3 содержит подробности того, как реализовать amb-интерпретатор путем модификации обычного интерпретатора Scheme.

4.3.1 Amb и search

Чтобы расширить Scheme и поддержать недетерминистское программирование, мы вводим новую особую форму amb.43 Выражение (amb (e) (в2) ••• (en)) возвращает «произвольным образом» значение одного из n выражений ( ei). Например, выражение

(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))))

Это похоже на потоковую процедуру integers-starting-from, описанную в разделе 3.5.2, но есть важное различие: потоковая процедура возвращает поток, который представляет последовательность всех целых чисел, начиная с n, а процедура, написанная через amb, выдает одно целое число. 44

43Идея недетерминистского программирования с помощью amb-выражений впервые была описана Джоном Маккарти в 1961 году (см. McCarthy 1967).

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