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

Подав запрос

(живет-около ?person (Хакер Лиза П))

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

(живет-около ?person-1 ?person-2)

она видит, что каждая подходящая пара людей попадается в выводе дважды, например

(живет-около (Хакер Лиза П) (Фект Пабло Э)) (живет-около (Фект Пабло Э) (Хакер Лиза П))

Почему так происходит? Можно ли получить список людей, живущих рядом друг с другом, в котором каждая пара появлялась бы по одному разу? Ответ объясните.

Логика как программы

Можно рассматривать правило как своего рода логическую импликацию: если присваивание значений переменным образца удовлетворяет телу, то оно удовлетворяет заключению. Следовательно, можно считать, что язык запросов способен производить логический вывод (logical deduction) на основании правил. В качестве примера рассмотрим операцию append, описанную в начале раздела 4.4. Как мы уже сказали, append характеризуется следующими двумя правилами:

•Для любого списка y, append пустого списка и y дает y

•Для любых u, v, y и z, append от (cons u v) и y дает (cons u z), если append от v и y дает z.

Чтобы выразить это в нашем языке запросов, мы определяем два правила для отношения

(append-to-form x y z)

которое можно интерпретировать как «append от x и y дает z»:

(rule (append-to-form () ?y ?y))

(rule (append-to-form (?u . ?v) ?y (?u . ?z)) (append-to-form ?v ?y ?z))

В первом правиле нет тела, и это означает, что следствие выполняется для любого значения ?y. Обратите также внимание, как во втором правиле car и cdr списка изображаются с использованием точечной записи.

При помощи этих двух правил мы можем формулировать запросы, которые вычисляют append от двух списков:

;;; Ввод запроса: (append-to-form (a b) (c d) ?z) ;;; Результаты запроса: (append-to-form (a b) (c d) (a b c d))

Удивительнее то, что мы с помощью тех же правил можем задать вопрос «Какой список, будучи добавлен к (a b), дает (a b c d)?» Это делается так:

;;; Ввод запроса:

(append-to-form (a b) ?y (a b c d)) ;;; Результаты запроса: (append-to-form (a b) (c d) (a b c d))

Можно также запросить все пары списков, append от которых дает (a b c

d) :

;;; Ввод запроса: (append-to-form ?x ?y (a b c d)) ;;; Результаты запроса:

(append-to-form () (a b c d) (a b c d)) (append-to-form (a) (b c d) (a b c d)) (append-to-form (a b) (c d) (a b c d)) (append-to-form (a b c) (d) (a b c d)) (append-to-form (a b c d) () (a b c d))

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

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

Следующие правила определяют отношение next-to, которое находит в списке соседние элементы:

(rule (?x next-to ?y in (?x ?y . ?u)))

(rule (?x next-to ?y in (?v . ?z)) (?x next-to ?y in ?z))

Каков будет ответ на следующие запросы?

(?x next-to ?y in (1 (2 3) 4))

(?x next-to 1 in (2 1 3 1))

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

Определите правила, которые реализуют операцию last-pair из упражнения 2.17, которая возвращает последнюю пару непустого списка. Проверьте Ваши правила на таких запросах, как (last-pair (3) ?x) , (last-pair (1 2 3) ?x) и (last-pair (2 ?x) (3)) . Правильно ли Ваши правила работают с запросами вида (last-pair ?x (3)) ?

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

Следующая база данных (см. книгу Бытия, 4) содержит генеалогию сыновей Ады вплоть до Адама, через Каина:

(сын Адам Каин) (сын Каин Енох) (сын Енох Ирад) (сын Ирад Мехиаель) (сын Мехиаель Мафусал) (сын Мафусал Ламех) (жена Ламех Ада) (сын Ада Иавал) (сын Ада Иувал)

Сформулируйте правила, такие как «Если S сын F, а F сын G, то S внук G» и «Если W жена M, а S сын W, то S также сын M» (предполагается, что в библейские времена это в большей степени соответствовало истине, чем теперь). Эти правила должны позволить системе найти внука Каина; сыновей Ламеха; внуков Мафусала. (В упражнении 4.69 можно найти правила, с помощью которых выводятся более сложные родственные связи.)

4.4.2 Как действует система обработки запросов

В разделе 4.4.4 мы представим реализацию интерпретатора запросов в виде набора процедур. В этом разделе дается обзор системы и объясняется ее общая структура, без низкоуровневых деталей реализации. После того, как мы опишем интерпретатор, нам легче будет понять его ограничения и некоторые тонкости, в которых логические операции языка запросов отличаются от операций математической логики.

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

Запросная система организована вокруг двух основных операций, которые называются сопоставление с образцом (pattern matching) и унификация (unification). Сначала мы опишем сопоставление с образцом и объясним, как эта операция, вместе с организацией информации в виде потоков кадров, позволяет нам реализовывать как простые, так и составные запросы. Затем мы обсудим унификацию - обобщение сопоставления с образцом, которое требуется для реализации правил. Наконец, мы покажем, как части интерпретатора связываются воедино процедурой, классифицирующей выражения, подобно тому, как eval разбирает выражения в интерпретаторе, описанном в разделе 4.1.

Сопоставление с образцом

Сопоставитель (pattern matcher) - это программа, которая проверяет, соответствует ли некоторая структура данных указанному образцу. Например, список ((a b) c (a b)) соответствует образцу (?x c ?x) при значении переменной ?x, равном (a b) . Этот же список соответствует образцу (?x ?y ?z) при значениях переменных ?x и ?z, равных (a b) и значении ?y, равном b. Однако он не соответствует образцу (?x a ?y) , поскольку этот образец требует, чтобы вторым элементом списка был символ a.