Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 95
Текст из файла (страница 95)
Это правила (rules). Правило63 Это описание not верно только для простых случаев. На самом деле поведение этой конструкции болеесложное. Мы исследуем тонкости not в разделах 4.4.2 и 4.4.3.64 Lisp-value имеет смысл использовать только для тех операций, которых нет в языке запросов.
В частности, с его помощью не следует проверять равенство (так как для этого предназначено сопоставление в языкезапросов) и неравенство (так как это можно сделать посредством правила same, приведенного ниже).4.4. Логическое программирование413(rule (живет-около ?person-1 ?person-2)(and (адрес ?person-1 (?town . ?rest-1))(адрес ?person-1 (?town . ?rest-2))(not (same ?person-1 ?person-2))))говорит, что двое людей живут рядом друг с другом, если они живут в одном городе.Выражение not в конце необходимо для того, чтобы правило не говорило про всехлюдей, что они живут сами около себя.
Отношение same (тот же самый) определяетсяочень простым правилом65 :(rule (same ?x ?x))Следующее правило объявляет, что сотрудник является «шишкой», если он начальствует над кем-нибудь, кто сам является начальником:(rule (шишка ?person)(and (начальник ?middle-manager ?person)(начальник ?x ?middle-manager)))В общем случае правило выглядит как(rule hзаключениеi hтелоi)где hзаключениеi — это образец, а hтелоi — произвольный запрос66 .
Можно считать,что правило представляет собой большое (даже бесконечное) множество утверждений, аименно, все конкретизации заключения при помощи присваиваний переменным, удовлетворяющих телу правила. Когда мы описывали простые запросы (образцы), мы сказали,что присваивание переменным удовлетворяет образцу в том случае, когда конкретизированный образец имеется в базе данных. Однако образец не обязательно должен явноприсутствовать в базе данных как утверждение.
Это может быть неявное утверждение,следующее из правила. Например, запрос(живет-около ?x (Битобор Бен))выдает(живет-около (Дум Хьюго) (Битобор Бен))(живет-около (Фиден Кон) (Битобор Бен))Чтобы найти всех программистов, живущих около Бена Битобора, можно спросить65 Заметим, что правило same не нужно для того, чтобы сделать два объекта одинаковыми: достаточно просто использовать одну и ту же переменную образца — тогда у нас с самого начала будет иметься только одинобъект, а не два. Например, обратите внимание на ?town в правиле живет-около или ?middle-managerв правиле шишка ниже.
Same оказывается полезным, когда нам хочется, чтобы два объекта различались, как?person-1 и ?person-2 в правиле живет-около. При том, что использование одной переменной в двухместах в запросе требует, чтобы в обоих местах присутствовало одно значение, использование разных переменных не означает, что значения различаются. (Значения, присваиваемые различным переменным образца,могут быть как разными, так и одинаковыми.)66 Кроме того, мы разрешаем иметь правила без тела, вроде same, и будем полагать, что такое правилоозначает, что заключение удовлетворяется любыми значениями переменных.Глава 4. Метаязыковая абстракция414(and (должность ?x (компьютеры программист))(живет-около ?x (Битобор Бен)))Как и в случае с составными процедурами, правила можно использовать внутридругих правил (как мы видели в живет-около), и они даже могут быть рекурсивными.Например, правило(rule (одчиняется ?staff-person ?boss)(or (начальник ?staff-prerson ?boss)(and (начальник ?staff-person ?middle-manager)(подчиняется ?middle-manager ?boss))))говорит, что служащий подчиняется руководителю, если руководитель командует имнепосредственно или (рекурсивно) непосредственный начальник служащего подчиняетсяруководителю.Упражнение 4.57.Определите правило, которое говорит, что служащий 1 может заменить служащего 2, если либослужащий 1 имеет ту же должность, что и служащий 2, либо человек с должностью служащего1 может выполнять работу служащего 2, и при этом служащие 1 и 2 — разные люди.
Используяэто правило, составьте запросы, которые находят следующую информацию:а. все служащие, которые могут заменить П.Э. Фекта.б. все служащие, которые могут заменить кого-то, кто получает больше их самих, с указаниемдвух зарплат.Упражнение 4.58.Определите правило, которое говорит, что человек «независим» в своем отделе, если он работаетв этом отделе, но у него нет начальника, который работает в том же отделе.Упражнение 4.59.Бен Битобор пропускает слишком много совещаний.
Опасаясь потерять из-за этой глупой привычки работу, он решает, что с ней надо что-то делать. Он добавляет данные обо всех еженедельныхсовещаниях в базу данных «Микрошафт» в виде следующих утверждений:(совещание(совещание(совещание(совещаниебухгалтерия (понедельник 9))администрация (понедельник 10))компьютеры (среда 15))администрация (пятница 13))Все эти утверждения сообщают о совещаниях отделов. Кроме того, Бен вводит утверждение осовещании всей компании, которое относится ко всем отделам. Все сотрудники компании должныходить на это совещание.(совещание вся-компания (среда 16))а. В пятницу утром Бен хочет спросить у базы данных, какие совещания происходят в этотдень.
Как ему надо составить запрос?б. Лиза П. Хакер недовольна. Она считает, что намного полезнее было бы, если бы можно былоспрашивать о совещаниях, указывая свое имя. Она пишет правило, гласящее, что совещания,куда служащему надо ходить, это совещания всей компании и совещания отдела, где он работает.Допишите тело Лизиного правила.4.4. Логическое программирование415(rule (время-совещания ?person ?day-and-time)hтелоi)в. Лиза приходит на работу в среду и хочет узнать, на какие совещания ей нужно идти в этотдень. Если имеется правило время-совещания, то какой запрос ей надо подать?Упражнение 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 от двух списков:416Глава 4. Метаязыковая абстракция;;; Ввод запроса:(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.4. Логическое программирование417Упражнение 4.63.Следующая база данных (см. книгу Бытия, 4) содержит генеалогию сыновей Ады вплоть до Адама,через Каина:(сын Адам Каин)(сын Каин Енох)(сын Енох Ирад)(сын Ирад Мехиаель)(сын Мехиаель Мафусал)(сын Мафусал Ламех)(жена Ламех Ада)(сын Ада Иавал)(сын Ада Иувал)Сформулируйте правила, такие как «Если S сын F , а F сын G, то S внук G» и «Если W женаM , а S сын W , то S также сын M » (предполагается, что в библейские времена это в большейстепени соответствовало истине, чем теперь). Эти правила должны позволить системе найти внукаКаина; сыновей Ламеха; внуков Мафусала.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
