Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 93
Текст из файла (страница 93)
Имеются, однако, совсемдругие языки программирования, в которых этот уклон ослаблен. Пример такого языкамы видели в разделе 3.3.5, где объектами вычисления были арифметические ограничения. В системе ограничений направление и порядок вычислений определены не стольчетко; стало быть, чтобы провести вычисление, система должна содержать в себе болеедетальное знание «как сделать», чем в случае с обычным арифметическим вычислением.Однако это не значит, что пользователь вовсе не отвечает за то, чтобы обеспечить систему императивным знанием. Существует множество сетей, которые задают одно и то жемножество ограничений, и пользователю нужно выбрать из множества математическиэквивалентных сетей одну подходящую, чтобы описать нужное вычисление.Недетерминистский интерпретатор программ из раздела 4.3 тоже представляет собойотход от представления, что программирование связано с построением алгоритмов для4.4.
Логическое программирование405вычисления однонаправленных функций. В недетерминистском языке у выражений может быть более одного значения, и оттого вычисление работает с отношениями, а не сфункциями, у которых значение только одно. Логическое программирование расширяетэту идею, сочетая реляционный взгляд на программирование с мощной разновидностьюсимвольного сопоставления с образцом, которую называют унификация (unification)58 .Когда этот подход работает, он служит весьма мощным способом написания программ. Отчасти эта мощь проистекает из того, что один факт вида «что такое» можноиспользовать для решения нескольких различных задач с разными компонентами «каксделать». Для примера рассмотрим операцию append, которая в качестве аргументовпринимает два списка и объединяет их элементы в один список.
В процедурном языкевроде Лиспа можно определить append через базовый конструктор списков cons, какв разделе 2.2.1:(define (append x y)(if (null? x)y(cons (car x) (append (cdr x) y))))Эту процедуру можно рассматривать как перевод на Лисп следующих двух правил;первое покрывает случай, когда первый список пуст, а второе — случай непустого списка,представляющего собой cons двух частей:• Для любого списка y, append пустого списка и y дает y.• Для любых u, v, y и z, append от (cons u v) и y дает (cons u z), еслиappend от v и y дает z59 .С помощью процедуры append мы можем решать задачи типаНайти append от (a b) и (c d).58 Логическое программирование выросло из долгой традиции исследований по автоматическому доказательству теорем.
Ранние программы доказательства теорем достигали лишь скромных результатов, так как ониполностью перебирали пространство возможных доказательств. Крупный прорыв, который сделал такой поиск осмысленным, случился в начале 1960х годов, когда были открыты алгоритм унификации (unificationalgorithm) и принцип резолюции (resolution principle) (Robinson 1965). Резолюцию использовали, например,Грин и Рафаэль (Green and Raphael 1968, см.
также Green 1969) как основу дедуктивной системы вопросответ. Большую часть этого периода исследователи сосредотачивались на алгоритмах, которые гарантированнонаходят решение, если оно существует. Такими алгоритмами было трудно управлять, и трудно было указатьим направление доказательства. Хьюитт (Hewitt 1969) нашел возможность сочетать управляющую структуруязыка программирования с операциями системы логического манипулирования, и это привело к появлению работы по автоматическому поиску, упомянутой в разделе 4.3.1 (примечание 47). В то же самое время в МарселеКольмероэ разрабатывал системы обработки естественного языка, основанные на правилах (см.
Colmerauer etal. 1973). Для представления этих правил он изобрел язык Пролог. Ковальски (Kowalski 1973; Kowalski 1979)в Эдинбурге обнаружил, что выполнение программы на Прологе можно интерпретировать как доказательствотеорем (с использованием метода доказательства, называемого линейной резолюцией Хорновских форм). Слияние этих двух линий привело к возникновению традиции логического программирования. Таким образом,в споре о приоритетах в области логического программирования французы могут указать на корни Пролога в Марсельском университете, а британцы на работы, сделанные в университете Эдинбурга.
А по мнениюисследователей из MIT, обе эти группы разработали логическое программирование, когда пытались понять,что же хотел сказать Хьюитт в своей блистательной, но трудночитаемой диссертации. Историю логическогопрограммирования можно найти в Robinson 1983.59 Соответствие между правилами и процедурой такое: пусть x из процедуры (когда x непустой) соответствует (cons u v) из правила.
Тогда z из правила соответствует append от (cdr x) и y.406Глава 4. Метаязыковая абстракцияОднако тех же двух правил достаточно для решения следующих типов вопросов, накоторые процедура ответить не может:Найти список y, такой, что append (a b) и y дает (a b c d).Найти все такие x и y, что append от них дает (a b c d).В языке логического программирования, когда программист пишет «процедуру» append,он формулирует два правила, приведенные выше. Знание «как сделать» автоматическиобеспечивается интерпретатором, что позволяет использовать одну эту пару правил дляответа на все три типа вопросов об append60 .У современных языков логического программирования (включая тот, который мысейчас реализуем) есть существенные недостатки, а именно: их общие методы «каксделать» порой заводят в ненужные бесконечные циклы или вызывают нежелательноеповедение другого рода.
Логическое программирование сейчас активно исследуется винформатике61.Ранее в этой главе мы изучили технологию реализации интерпретаторов и описали теее элементы, которые необходимы в интерпретаторе Лисп-подобного языка (в сущности,любого традиционного языка). Теперь мы воспользуемся этими идеями при рассмотрении интерпретатора для языка логического программирования. Мы называем этот языкязыком запросов (query language), поскольку он весьма удобен для извлечения информации из баз данных при помощи запросов (queries), то есть выраженных на нашемязыке вопросов. Несмотря на то, что язык запросов сильно отличается от Лиспа, егоудобно обсуждать в терминах той же самой общей схемы, которую мы использовалидо сих пор: как набор элементарных составляющих, дополненных средствами комбинирования, которые позволяют нам сочетать простые составляющие и получать при этомсложные, и средствами абстракции, которые позволяют нам рассматривать сложные составляющие как единые концептуальные единицы.
Интерпретатор языка логическогопрограммирования существенно сложнее, чем интерпретатор языка типа Лиспа. Тем неменее, нам предстоит убедиться, что наш интерпретатор языка запросов содержит многие из тех же элементов, которые были в интерпретаторе из раздела 4.1. В частности,у нас будет часть «eval», которая классифицирует выражения в соответствии с типом,и часть «apply», которая реализует механизм абстракции языка (процедуры в случае60 Это ни в коем случае не освобождает программиста полностью от решения задачи, как вычислить ответ.Существует множество математически эквивалентных наборов правил для отношения append, и только некоторые из них можно превратить в эффективное средство для вычисления в каком-либо направлении. Вдобавок,иногда информация «что такое» ничего не говорит о том, как вычислить ответ, — возьмем, например, задачунайти такое y, что y 2 = x.61 Пик интереса к логическому программированию пришелся на начало 80-х, когда японское правительствоинициировало амбициозный проект, целью которого было построение сверхбыстрых компьютеров, оптимизированных для логических языков программирования.
Скорость таких компьютеров предполагалось измерять вLIPS (Logical Inferences Per Second — число логических выводов в секунду), а не в обычных FLOPS (FLoatingpoint Operations Per Second — число операций с плавающей точкой в секунду). Несмотря на то, что в рамкахпроекта удалось создать аппаратное и программное обеспечение, которое изначально планировалось, интересымеждународной компьютерной промышленности сместились в другом направлении.
Обзор и оценку японскогопроекта можно найти в Feigenbaum and Shrobe 1993. К тому же и в сообществе логических программистоввозник интерес к реляционному программированию на основе других методов, помимо простого сопоставленияс образцом, например, к работе с численными ограничениями — вроде тех, которые присутствуют в системераспространения ограничений из раздела 3.3.5.4.4. Логическое программирование407Лиспа и правила (rules) в случае логического программирования).
Кроме того, в реализации центральную роль будет играть структура данных, построенная из кадров иопределяющая соотношение между символами и связанными с ними значениями. Ещеодна интересная сторона нашей реализации языка запросов — то, что мы существеннымобразом используем потоки, введенные в главе 3.4.4.1. Дедуктивный поиск информацииЛогическое программирование хорошо приспособлено для построения интерфейсов кбазам данных, служащих для поиска информации. Язык запросов, который мы реализуемв этой главе, спроектирован именно для такого использования.Чтобы показать, чем занимается система запросов, мы покажем, как с ее помощью управлять базой данных персонала для «Микрошафт», процветающей компаниииз окрестностей Бостона со специализацией в области высоких технологий. Язык предоставляет возможность поиска информации о сотрудниках, производимого с помощьюобразцов; он также может осуществлять логический вывод на основании общих правил.База данныхБаза данных персонала «Микрошафт» содержит утверждения (assertions) о сотрудниках компании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
