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

Реализуйте новую особую форму ramb, которая подобна amb, однако перебирает варианты не слева направо, а в случайном порядке. Покажите, как такая форма может пригодиться в Лизиной задаче из упражнения 4.49

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

Реализуйте новую разновидность присваивания permanent-set! - присваивание, которое не отменяется при неудачах. Например, можно выбрать два различных элемента в списке и посчитать, сколько для этого потребовалось попыток, следующим образом:

(define count 0)

(let ((x (an-element-of (a b c))) (y (an-element-of (a b c))))

(permanent-set! count (+ count 1))

(require (not (eq? x y)))

(list x y count)) ;;; Начало новой задачи ;;; Значение Amb-Eval: (a b 2)

;;; Ввод Amb-Eval: try-again

;;; Значение Amb-Eval: (a c 3)

Какие значения были бы напечатаны, если бы мы вместо permanent-set! использовали здесь обычный set! ?

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

Реализуйте новую конструкцию if-fail, которая позволяет пользователю перехватить неудачу при выполнении выражения. If-fail принимает два выражения. Первое она выполняет как обычно и, если вычисление успешно, возвращает его результат. Однако если вычисление неудачно, то возвращается значение второго выражения, как в следующем примере:

;;; Ввод Amb-Eval:

(if-fail (let ((x (an-element-of (1 3 5)))) (require (even? x))

x)

all-odd)

;;; Начало новой задачи ;;; Значение Amb-Eval: all-odd

;;; Ввод Amb-Eval:

(if-fail (let ((x (an-element-of (1 3 5 8)))) (require (even? x))

x)

all-odd)

;;; Начало новой задачи ;;; Значение Amb-Eval: 8

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

Если у нас есть permanent-set!, описанное в упражнении 4.51, и if-fail из упражнения 4.52, то каков будет результат вычисления

(let ((pairs ()))

(if-fail (let ((p (prime-sum-pair (1358) (20 35 110)))) (permanent-set! pairs (cons p pairs))

(amb))

pairs))

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

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

(define (require? exp) (tagged-list? exp require))

(define (require-predicate exp) (cadr exp))

новая ветвь разбора в analyze:

((require? exp) (analyze-require exp))

а также процедура analyze-require, которая обрабатывает выражения require. Допишите следующее определение analyze-require:

(define (analyze-require exp)

(let ((pproc (analyze (require-predicate exp)))) (lambda (env succeed fail) (pproc env

(lambda (pred-value fail2) (if {??) (??)

(succeed ok fail2)))

fail))))

4.4 Логическое программирование

В главе 1 мы подчеркивали, что информатика имеет дело с императивным знанием («как сделать»), в то время как математика имеет дело с декларативным знанием («что такое»). Действительно, языки программирования требуют, чтобы программист, выражая свои знания, указывал методы пошагового решения определенных задач. С другой стороны, языки высокого уровня обеспечивают в рамках своих реализаций существенный объем методологических знаний, которые освобождает пользователя от забот о многих деталях того, как проходит описываемое вычисление.

Большинство языков программирования, включая Лисп, построены вокруг вычисления значений математических функций. Языки, ориентированные на выражения, (такие, как Лисп, Фортран и Алгол) пользуются тем, что выражение, описывающее значение функции, можно интерпретировать и как способ вычислить это значение. По этой причине большинство языков программирования имеют уклон в однонаправленные вычисления (вычисления со строго определенными входом и выходом). Имеются, однако, совсем другие языки программирования, в которых этот уклон ослаблен. Пример такого языка мы видели

в разделе 3.3.5, где объектами вычисления были арифметические ограничения. В системе ограничений направление и порядок вычислений определены не столь четко; стало быть, чтобы провести вычисление, система должна содержать в себе более детальное знание «как сделать», чем в случае с обычным арифметическим вычислением. Однако это не значит, что пользователь вовсе не отвечает за то, чтобы обеспечить систему императивным знанием. Существует множество сетей, которые задают одно и то же множество ограничений, и пользователю нужно выбрать из множества математически эквивалентных сетей одну подходящую, чтобы описать нужное вычисление.

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

Когда этот подход работает, он служит весьма мощным способом написания программ. Отчасти эта мощь проистекает из того, что один факт вида «что такое» можно использовать для решения нескольких различных задач с разными компонентами «как сделать». Для примера рассмотрим операцию append, которая в качестве аргументов принимает два списка и объединяет их элементы в один список. В процедурном языке вроде Лиспа можно определить append через базовый конструктор списков cons, как в разделе 2.2.1:

(define (append x y)

(if (null? x) y

(cons (car x) (append (cdr x) y))))

Эту процедуру можно рассматривать как перевод на Лисп следующих двух правил; первое покрывает случай, когда первый список пуст, а второе - случай

58Логическое программирование выросло из долгой традиции исследований по автоматическому доказательству теорем. Ранние программы доказательства теорем достигали лишь скромных результатов, так как они полностью перебирали пространство возможных доказательств. Крупный прорыв, который сделал такой поиск осмысленным, случился в начале 1960х годов, когда были открыты алгоритм унификации (unification algorithm) и принцип резолюции (resolution principle) (Robinson 1965). Резолюцию использовали, например, Грин и Рафаэль (Green and Raphael 1968, см. также Green 1969) как основу дедуктивной системы вопрос-ответ. Большую часть этого периода исследователи сосредотачивались на алгоритмах, которые гарантированно находят решение, если оно существует. Такими алгоритмами было трудно управлять, и трудно было указать им направление доказательства. Хьюитт (Hewitt 1969) нашел возможность сочетать управляющую структуру языка программирования с операциями системы логического манипулирования, и это привело к появлению работы по автоматическому поиску, упомянутой в разделе 4.3.1 (примечание 47). В то же самое время в Марселе Кольмероэ разрабатывал системы обработки естественного языка, основанные на правилах (см. Colmerauer et al. 1973). Для представления этих правил он изобрел язык Пролог. Ковальски (Kowalski 1973; Kowalski 1979) в Эдинбурге обнаружил, что выполнение программы на Прологе можно интерпретировать как доказательство теорем (с использованием метода доказательства, называемого линейной резолюцией Хорновских форм). Слияние этих двух линий привело к возникновению традиции логического программирования. Таким образом, в споре о приоритетах в области логического программирования французы могут указать на корни Пролога в Марсельском университете, а британцы на работы, сделанные в университете Эдинбурга. А по мнению исследователей из MIT, обе эти группы разработали логическое программирование, когда пытались понять, что же хотел сказать Хьюитт в своей блистательной, но трудночитаемой диссертации. Историю логического программирования можно найти в Robinson 1983.