непустого списка, представляющего собой cons двух частей:

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

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

С помощью процедуры append мы можем решать задачи типа

Найти append от (a b) и (c d) .

Однако тех же двух правил достаточно для решения следующих типов вопросов, на которые процедура ответить не может:

Найти список y, такой, что append (a b) и y дает (a b c d) .

Найти все такие x и y, что append от них дает (a b c d) .

В языке логического программирования, когда программист пишет «процедуру» append, он формулирует два правила, приведенные выше. Знание «как сделать» автоматически обеспечивается интерпретатором, что позволяет использовать одну эту пару правил для ответа на все три типа вопросов об append.60

У современных языков логического программирования (включая тот, который мы сейчас реализуем) есть существенные недостатки, а именно: их общие методы «как сделать» порой заводят в ненужные бесконечные циклы или вызывают нежелательное поведение другого рода. Логическое программирование сейчас активно исследуется в информатике.61

Ранее в этой главе мы изучили технологию реализации интерпретаторов и описали те ее элементы, которые необходимы в интерпретаторе Лисп-подобного языка (в сущности, любого традиционного языка). Теперь мы воспользуемся этими идеями при рассмотрении интерпретатора для языка логического программирования. Мы называем этот язык языком запросов (query language), поскольку он весьма удобен для извлечения информации из баз данных при помощи запросов (queries), то есть выраженных на нашем языке вопросов. Несмотря на то, что язык запросов сильно отличается от Лиспа, его удобно обсуждать в терминах той же самой общей схемы, которую мы использовали

59Соответствие между правилами и процедурой такое: пусть x из процедуры (когда x непустой) соответствует (cons u v) из правила. Тогда z из правила соответствует append от (cdr x) и У.

60Это ни в коем случае не освобождает программиста полностью от решения задачи, как вычислить ответ. Существует множество математически эквивалентных наборов правил для отношения append, и только некоторые из них можно превратить в эффективное средство для вычисления в каком-либо направлении. Вдобавок, иногда информация «что такое» ничего не говорит о том, как вычислить ответ, - возьмем, например, задачу найти такое у, что y2 = x.

61 Пик интереса к логическому программированию пришелся на начало 80-х, когда японское правительство инициировало амбициозный проект, целью которого было построение сверхбыстрых компьютеров, оптимизированных для логических языков программирования. Скорость таких компьютеров предполагалось измерять в LIPS (Logical Inferences Per Second - число логических выводов в секунду), а не в обычных FLOPS (FLoating-point Operations Per Second - число операций с плавающей точкой в секунду). Несмотря на то, что в рамках проекта удалось создать аппаратное и программное обеспечение, которое изначально планировалось, интересы международной компьютерной промышленности сместились в другом направлении. Обзор и оценку японского проекта можно найти в Feigenbaum and Shrobe 1993. К тому же и в сообществе логических программистов возник интерес к реляционному программированию на основе других методов, помимо простого сопоставления с образцом, например, к работе с численными ограничениями - вроде тех, которые присутствуют в системе распространения ограничений из раздела 3.3.5.

до сих пор: как набор элементарных составляющих, дополненных средствами комбинирования, которые позволяют нам сочетать простые составляющие и получать при этом сложные, и средствами абстракции, которые позволяют нам рассматривать сложные составляющие как единые концептуальные единицы. Интерпретатор языка логического программирования существенно сложнее, чем интерпретатор языка типа Лиспа. Тем не менее, нам предстоит убедиться, что наш интерпретатор языка запросов содержит многие из тех же элементов, которые были в интерпретаторе из раздела 4.1. В частности, у нас будет часть «eval», которая классифицирует выражения в соответствии с типом, и часть «apply», которая реализует механизм абстракции языка (процедуры в случае Лиспа и правила (rules) в случае логического программирования). Кроме того, в реализации центральную роль будет играть структура данных, построенная из кадров и определяющая соотношение между символами и связанными с ними значениями. Еще одна интересная сторона нашей реализации языка запросов - то, что мы существенным образом используем потоки, введенные в главе 3.

4.4.1 Дедуктивный поиск информации

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

Чтобы показать, чем занимается система запросов, мы покажем, как с ее помощью управлять базой данных персонала для «Микрошафт», процветающей компании из окрестностей Бостона со специализацией в области высоких технологий. Язык предоставляет возможность поиска информации о сотрудниках, производимого с помощью образцов; он также может осуществлять логический вывод на основании общих правил.

База данных

База данных персонала «Микрошафт» содержит утверждения (assertions) о сотрудниках компании. Вот информация о Бене Битоборе, местном компьютерном гуру:

(адрес (Битобор Бен) (Сламервилл (Ридж Роуд) 10)) (должность (Битобор Бен) (компьютеры гуру)) (зарплата (Битобор Бен) 60000)

Каждое утверждение представляет собой список (в данном случае тройку). элементы которого сами могут быть списками.

В качестве местного гуру Бен отвечает за компьютерный отдел компании и руководит двумя программистами и одним техником. Вот информация о них:

(адрес (Хакер Лиза П) (Кембридж (Массачусетс Авеню) 78)) (должность (Хакер Лиза П) (компьютеры программист)) (зарплата (Хакер Лиза П) 40000) (начальник (Хакер Лиза П) (Битобор Бен))

(адрес (Фект Пабло Э) (Кембридж (Эймс Стрит) 3)) (должность (Фект Пабло Э) (компьютеры программист)) (зарплата (Фект Пабло Э) 35000)

(начальник (Фект Пабло Э) (Битобор Бен))

(адрес (Поправич Дайко) (Бостон (Бэй Стейт Роуд) 22)) (должность (Поправич Дайко) (компьютеры техник)) (зарплата (Поправич Дайко) 25000) (начальник (Поправич Дайко) (Битобор Бен))

Имеется также программист-стажер, над которым начальствует Лиза:

(адрес (Дум Хьюго) (Сламервилл (Пайн Три Роуд) 80)) (должность (Дум Хьюго) (компьютеры программист стажер)) (зарплата (Дум Хьюго) 30000) (начальник (Дум Хьюго) (Хакер Лиза П))

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

Бен - служащий высокого ранга. Его начальник - сам глава компании:

(начальник (Битобор Бен) (Уорбак Оливер))

(адрес (Уорбак Оливер) (Суэлсли (Топ Хип Роуд))) (должность (Уорбак Оливер) (администрация большая шишка)) (зарплата (Уорбак Оливер) 150000)

Помимо компьютерного отдела, руководимого Беном, в компании имеется бухгалтерия, где работает главный бухгалтер со своим помощником:

(адрес (Скрудж Эбин) (Уэстон (Шейди Лейн) 10)) (должность (Скрудж Эбин) (бухгалтерия главный бухгалтер)) (зарплата (Скрудж Эбин) 75000) (начальник (Скрудж Эбин) (Уорбак Оливер))

(адрес (Крэтчит Роберт) (Олстон (Норт Гарвард Стрит) 16)) (должность (Крэтчит Роберт) (бухгалтерия писец)) (зарплата (Крэтчит Роберт) 18000) (начальник (Крэтчит Роберт) (Скрудж Эбин))

Есть еще секретарь главы компании:

(адрес (Фиден Кон) (Сламервилл (Онион Сквер) 5)) (должность (Фиден Кон) (администрация секретарь)) (зарплата (Фиден Кон) 25000) (начальник (Фиден Кон) (Уорбак Оливер))

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

(может-замещать (компьютеры гуру) (компьютеры программист)) (может-замещать (компьютеры гуру) (компьютеры техник))

Программист может выполнять работу стажера:

(может-замещать (компьютеры программист)

(компьютеры программист стажер))