Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 94
Текст из файла (страница 94)
Вот информация о Бене Битоборе, местном компьютерном гуру:(адрес (Битобор Бен) (Сламервилл (Ридж Роуд) 10))(должность (Битобор Бен) (компьютеры гуру))(зарплата (Битобор Бен) 60000)Каждое утверждение представляет собой список (в данном случае тройку). элементыкоторого сами могут быть списками.В качестве местного гуру Бен отвечает за компьютерный отдел компании и руководитдвумя программистами и одним техником. Вот информация о них:(адрес (Хакер Лиза П) (Кембридж (Массачусетс Авеню) 78))(должность (Хакер Лиза П) (компьютеры программист))(зарплата (Хакер Лиза П) 40000)(начальник (Хакер Лиза П) (Битобор Бен))(адрес (Фект Пабло Э) (Кембридж (Эймс Стрит) 3))(должность (Фект Пабло Э) (компьютеры программист))(зарплата (Фект Пабло Э) 35000)(начальник (Фект Пабло Э) (Битобор Бен))(адрес (Поправич Дайко) (Бостон (Бэй Стейт Роуд) 22))(должность (Поправич Дайко) (компьютеры техник))(зарплата (Поправич Дайко) 25000)(начальник (Поправич Дайко) (Битобор Бен))Имеется также программист-стажер, над которым начальствует Лиза:(адрес (Дум Хьюго) (Сламервилл (Пайн Три Роуд) 80))(должность (Дум Хьюго) (компьютеры программист стажер))408Глава 4.
Метаязыковая абстракция(зарплата (Дум Хьюго) 30000)(начальник (Дум Хьюго) (Хакер Лиза П))Все эти служащие работают в компьютерном отделе, на что указывает слово компьютеры в начале описания их должностей.Бен — служащий высокого ранга. Его начальник — сам глава компании:(начальник (Битобор Бен) (Уорбак Оливер))(адрес (Уорбак Оливер) (Суэлсли (Топ Хип Роуд)))(должность (Уорбак Оливер) (администрация большая шишка))(зарплата (Уорбак Оливер) 150000)Помимо компьютерного отдела, руководимого Беном, в компании имеется бухгалтерия, где работает главный бухгалтер со своим помощником:(адрес (Скрудж Эбин) (Уэстон (Шейди Лейн) 10))(должность (Скрудж Эбин) (бухгалтерия главный бухгалтер))(зарплата (Скрудж Эбин) 75000)(начальник (Скрудж Эбин) (Уорбак Оливер))(адрес (Крэтчит Роберт) (Олстон (Норт Гарвард Стрит) 16))(должность (Крэтчит Роберт) (бухгалтерия писец))(зарплата (Крэтчит Роберт) 18000)(начальник (Крэтчит Роберт) (Скрудж Эбин))Есть еще секретарь главы компании:(адрес (Фиден Кон) (Сламервилл (Онион Сквер) 5))(должность (Фиден Кон) (администрация секретарь))(зарплата (Фиден Кон) 25000)(начальник (Фиден Кон) (Уорбак Оливер))Данные содержат также утверждения о том, какой род работы могут выполнять сотрудники, имеющие другую должность.
Например, компьютерный гуру способен выполнять работу как компьютерного программиста, так и компьютерного техника:(может-замещать (компьютеры гуру) (компьютеры программист))(может-замещать (компьютеры гуру) (компьютеры техник))Программист может выполнять работу стажера:(может-замещать (компьютеры программист)(компьютеры программист стажер))Кроме того, как всем известно,(может-замещать (администрация секретарь)(администрация большая шишка))4.4.
Логическое программирование409Простые запросыЯзык запросов дает пользователям возможность извлекать информацию из базы данных, формулируя запросы в ответ на приглашение системы. Например, чтобы найти всехпрограммистов, можно сказать;;; Ввод запроса:(должность ?x (компьютеры программист))Система выведет следующие результаты:;;; Результаты запроса:(должность (Хакер Лиза П) (компьютеры программист))(должность (Фект Пабло Э) (компьютеры программист))Входной запрос указывает, что мы ищем в базе данных записи, соответствующиенекоторому образцу (pattern). В этом примере образец указывает, что запись должнасостоять из трех элементов, из которых первый является символом должность, второй может быть чем угодно, а третий представляет собой список (компьютеры программист).
«Что угодно», которое может стоять на второй позиции в искомом списке,изображается переменной образца (pattern variable) ?x. В общем случае переменнаяобразца — это символ, который мы считаем именем переменной, предваряемый знакомвопроса. Несколько позже мы увидим, почему имеет смысл давать переменным образцаимена, а не просто ставить в образцы ?, означающее «что угодно». Система отвечает напростой запрос, выводя все записи в базе данных, соответствующие введенному образцу.В образце может содержаться более одной переменной. Например,(адрес ?x ?y)выводит адреса всех служащих.В образце может совсем не быть переменных.
В этом случае запрос просто проверяет,содержится ли запись в базе. Если да, будет одна подходящая под образец запись; еслинет, ни одной.Одна и та же переменная может встречаться в образце в нескольких местах, и этоозначает, что одинаковое «что угодно» должно встретиться в каждом из этих мест. Радиэтого переменным и даются имена. Например,(начальник ?x ?x)находит всех сотрудников, которые сами себе начальники (впрочем, в нашей пробнойбазе таковых не имеется).Запросу(должность ?x (компьютеры ?type))соответствуют все записи о должностях, в которых третий элемент является двухэлементным списком, а первый элемент в нем компьютеры:(должность(должность(должность(должность(Битобор Бен) (компьютеры гуру))(Хакер Лиза П) (компьютеры программист))(Фект Пабло Э) (компьютеры программист))(Поправич Дайко) (компьютеры техник))Глава 4.
Метаязыковая абстракция410Этому образцу не соответствует запись(должность (Дум Хьюго) (компьютеры программист стажер))поскольку третий элемент здесь является списком из трех элементов, а третий элементобразца указывает, что элементов должно быть два. Если бы нам захотелось изменитьобразец так, чтобы третий элемент мог быть любым списком, который начинается скомпьютеры, мы могли бы написать62(должность ?x (компьютеры .
?type))Например,(компьютеры . ?type)соответствуют данные(компьютеры программист стажер)причем ?type равняется списку (программист стажер). Тому же образцу соответствуют данные(компьютеры программист)где ?type равняется списку (программист), и данные(компьютеры)где ?type равняется пустому списку ().Можно следующим образом описать обработку простых запросов в нашем языке:• Система находит все присваивания переменным в образце запроса, которые удовлетворяют (satisfy) запросу — то есть, все наборы значений переменных, такие, что еслипеременные образца конкретизуются (are instantiated), то есть замещаются, своимизначениями, то результат находится в базе данных.• Система отвечает на запрос, перечисляя все конкретизации образца с удовлетворяющими ему присваиваниями переменным.Заметим, что в случае, когда образец не содержит переменных, запрос сводится квыяснению, находится ли образец в базе.
Если да, то нулевое присваивание, не сообщающее значений никаким переменным, удовлетворяет запросу к текущей базе данных.Упражнение 4.55.Постройте простые запросы, которые извлекают из базы данных следующую информацию:а. Все сотрудники, начальником которых является Бен Битобор.б. Имена и должности всех работников бухгалтерии.в. Имена и адреса всех сотрудников, живущих в Сламервилле.62 Здесьиспользуется точечная запись, введенная в упражнении 2.20.4.4.
Логическое программирование411Составные запросыПростые запросы являются элементарными операциями языка запросов. Чтобы порождать составные операции, язык предоставляет средства комбинирования. Один изэлементов, превращающих язык запросов в язык логического программирования — то,что средства комбинирования запросов отражают средства комбинирования, используемые при построении логических выражений: and (и), or (или) и not (не). (Здесь and,or и not — это не элементарные выражения Лиспа, а операции, встроенные в языкзапросов.)Мы можем найти адреса всех программистов с помощью and так:(and (должность ?person (компьютеры программист))(адрес ?person ?where))Получаем на выводе(and (должность (Хакер Лиза П) (компьютеры программист))(адрес (Хакер Лиза П) (Кембридж (Массачусетс Авеню) 78)))(and (должность (Фект Пабло Э) (компьютеры программист))(адрес (Фект Пабло Э) (Кембридж (Эймс Стрит) 3)))В общем случае, запросу(and hзапрос1 i ...
hзапросn i)удовлетворяют все наборы значений переменных образца, которые одновременно удовлетворяют hзапросу1i ... hзапросуni.Как и в случае с простыми запросами, система при обработке составного запросанаходит все присваивания переменным образца, удовлетворяющие запросу, и затем печатает все конкретизации запроса этими значениями.Другой метод построения составных запросов — через or. Например,(or (начальник ?x (Битобор Бен))(начальник ?x (Хакер Лиза П)))найдет всех сотрудников, над которыми начальствует Бен Битобор или Лиза П. Хакер:(or (начальник (Хакер Лиза П) (Битобор Бен))(начальник (Хакер Лиза П) (Хакер Лиза П)))(or (начальник (Фект Пабло Э) (Битобор Бен))(начальник (Фект Пабло Э) (Хакер Лиза П)))(or (начальник (Поправич Дайко) (Битобор Бен))(начальник (Поправич Дайко) (Хакер Лиза П)))(or (начальник (Дум Хьюго) (Битобор Бен))(начальник (Дум Хьюго) (Хакер Лиза П)))В общем случае, запросу412Глава 4.
Метаязыковая абстракция(or hзапрос1 i ... hзапросn i)удовлетворяют все наборы значений переменных образца, которые удовлетворяют покрайней мере одному из hзапроса1 i ... hзапросаni.Кроме того, составные запросы можно порождать при помощи not. Например,(and (начальник ?x (Битобор Бен))(not (должность ?x (компьютеры программист))))ищет всех сотрудников, для которых начальник Бен Битобор, не являющихся программистами. В общем случае, запросу(not hзапрос1 i)удовлетворяют все присваивания переменным образца, которые не удовлетворяют hзапросу1 i63 .Последняя комбинирующая форма называется lisp-value. Когда она стоит в началеобразца, она указывает, что следующий элемент является предикатом Лиспа, которыйтребуется применить к остальным (конкретизированным) элементам как к аргументам.В общем случае, образец(lisp-value hпредикатi hарг1 i ...
hаргn i)удовлетворяется теми присваиваниями переменным образца, для которых применениеhпредикатаi к конкретизированным hарг1 i . . . hаргn i дает истину. Например, чтобынайти всех сотрудников с зарплатой выше 30000 долларов, можно написать64(and (зарплата ?person ?amount)(lisp-value > ?amount 30000))Упражнение 4.56.Сформулируйте составные запросы для получения следующей информации:а.
имена всех сотрудников, у которых начальником Бен Битобор, и их адреса;б. все сотрудники, чья зарплата ниже, чем у Бена Битобора, вместе с их зарплатой и зарплатойБена;в. все сотрудники, у которых начальник не относится к компьютерному отделу, вместе с именеми должностью их начальника.ПравилаВ дополнение к элементарным и составным запросам, наш язык обладает средствомабстракции запросов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
