1.5.1 Язык логического программирования KL0.
KL0 (от англ. “kernel-language version 0” – ядро-язык версии 0) – язык, в основу которого положено расширение языка логического программирования Пролог. Среди особенностей, новых в KL0 по отношению к Прологу, можно выделить:
· более гибкую структуру управления.
· многопроцессовость
· операции с побочным эффектом
· машинно-ориентированные операции.
К наиболее существенным механизмам Пролога, не поддерживаемым в KL0, относятся:
· средства управления базой данных
· средства управления таблицей имён.
Так как KL0 мало, чем отличается от Пролога, ограничимся лишь рассмотрением типов данных.
Рассмотрим в общих чертах некоторые базовые типы данных языка. К ним относятся символы, целые и действительные числа, строки и др.
Символы в основном предназначены для представления символьных атомов Пролога и, как правило, никак не связаны ни со строками символов, используемыми для текстуального представления программ, ни с определениями предикатов, в которых символы задают имена предикатов. Такие атрибуты при необходимости могут быть приписаны символам средствами ESP[1] . KL0 более прост и не поддерживает подобных механизмов. В этом отношении он только обеспечивает структуры данных прямого доступа и стандартную функцию хеширования для доступа к определениям атрибутов в хеш-таблице. Символы в KL0 можно проверять только на идентичность.
Целые и действительные числа введены для эффективного выполнения арифметических операций. Арифметические операции в KL0 не обладают свойством двойственности: сложение и вычитание, здесь различные предикаты. Аппаратно поддерживаются только числа фиксированной длины, определяемой разрядной сеткой. Целые числа произвольной длины (bignums), действительные числа произвольной точности и, возможно, рациональные числа могут быть реализованы с помощью обработчика исключений. Исключение возбуждается, если операндами встроенных арифметических предикатов (машинных инструкций в традиционном смысле) являются, например, нечисловые данные. Обработчик исключения может проверить аргументы и, если они соответствуют ожидаемым, выполнить предписанные операции; в противном случае вызывается обработчик ошибок. После обработки исключения дальнейшее выполнение программы может быть возобновлено.
Строки представляются одномерными массивами небольших положительных целых. Размер элементов массива зависит от диапазона значений элементов строки и может изменяться от одной строки к другой. Для представления битовых массивов, используемых для хранения образов графических изображений в памяти, введены строки с однобитовыми элементами. Для представления символов в коде ASCII используются строки с размером элемента 8 бит.
1.5.3. Язык программирования ShapeUp.
ShapeUp - ещё один язык логического программирования, в основу которого положен Пролог, расширенный средствами сопоставления строк.
В ShapeUp образцы строк рассматриваются так же, как и термы Пролога, и их сопоставление возложено на процесс унификацию. Таким образом, программы на ShapeUp значительно проще, чем аналогичные программы на Прологе, их легче писать и понимать. Сокращается значительно и размер программ.
Прологу присущи недетерминированность и сопоставление с образцом. Эти свойства очень полезны для разработки систем обработки информационных знаний. К таким системам можно отнести системы понимания естественного языка и другие системы интеллектуальной обработки текстов. Для подобных приложений очень важна операция сопоставления строк. Однако механизм сопоставления с образцом в таком виде, как он существует в Прологе, недостаточен для сопоставления строк. Причина заключена в “терм-терм” механизме сопоставления. ShapeUp – попытка разработать более практический, свободный от присущего Прологу недостатка инструмент программирования. Характерной чертой ShapeUp, отличающей его от традиционных Пролог-систем, является выполняемая при унификации функция сопоставления строк. В ShapeUp включено несколько операторов сопоставления строк. Язык позволяет конструировать образцы строк, представляемые как термы Пролога. Образцы могут унифицироваться с различными строковыми объектами: расширена унификация для выполнения сопоставления строк. В результате ShapeUp-программы проще и имеют более прозрачную семантику, их легче писать.
Список языков логического программирования можно продолжать ещё долго. Кроме перечисленных выше, к языкам логического программирования относятся также: Дейталог, LogLisp и множество других. Но хотелось бы ещё остановиться на таком языке, как Лисп (от англ. Lisp – list processing – обработка списков).
Глава 2. Lisp – язык функционального программирования.
Дело в том, что кроме функционального программирования (которое является основным в Лиспе) в этом языке можно использовать программирование, основанное на обычном последовательном исполнении операторов с присваиваниями, передачами управления и специальными операторами цикла. С помощью макропрограммирования можно запрограммировать новые структуры языка или реализовать совершенно новые языки. Кроме того, в Лиспе можно применять множество методов программирования, известных из традиционных языков. В зависимости от системы в Лиспе можно использовать методы программирования более высокого уровня, например такие, как объектно-ориентированное программирование, ситуационное программирование, продукционное программирование и логическое программирование. Именно на последнем методе мы и остановимся.
2.1. Лисп в истории программирования.
Лисп является наиболее важным языком программирования, используемым в исследованиях по искусственному интеллекту и в математической лингвистике.
Лисп, ни в каком смысле не является младенцем в программировании. Скорее, он старик среди языков программирования. Лисп был разработан в 50-х годах и является вслед за Фортраном старейшим ещё используемым языком программирования. Но в отличие, от Фортрана будущее Лиспа ещё впереди.
Как уже упоминалось выше, Лисп представляет собой язык так называемого функционального программирования. Он основан на алгебре списочных структур, лямбда-исчислений и теории рекурсивных функций. Благодаря неразвитости традиционной вычислительной техники, отличающемуся от других языков программирования характеру и из-за наличия элементарных средств обработки списков Лисп долгое время являлся основным инструментом исследования искусственного интеллекта и средством теоретического подхода к анализу программирования. Однако в 80-х годах Лисп, наконец, вышел из лабораторий и нашел применение в прикладных проблемах.
Обычно языки не изобретают, а проектируют. Однако по отношению к Лиспу можно говорить об изобретении. Первоначальная версия языка, в частности, содержала множество понятий и принципов, которые сначала казались очень странными, но многие из которых позже оказались существенным нововведением. Кроме этого, возможность добавления в Лисп в течение десятилетий многих новых черт подтвердила свойство расширяемости этого языка. Вокруг Лиспа возникла широкая культура, охватывающая многочисленные школы и разнообразные диалекты языка, различные системы и методы программирования, программные среды и Лисп-машины.
2.2. Логическое программирование на Лиспе.
Лисповские функции, как и написанные на традиционных языках программы, обрабатывают данные в порядке, задаваемом описанием алгоритма, несмотря на то, что эту последовательность можно в Лиспе отобразить весьма гибкими и общими формами. Такие языки назовём процедурными.
В процедурных языках и формализмах программирование сводиться к разработке алгоритма, выполняющего действия. В логических языках алгоритмы в таком смысле не используются. Если функциональные и операторные языки описывают, каким образом решается некоторая задача, то в логических языках для её решения достаточно точного логического описания. Языки, в которых решение задачи получают из описания структуры и условий задачи, называют декларативными.
Чтобы в декларативном языке можно было выполнять разумные вычисления, для него наряду с декларативным смыслом определяется интерпретация в виде действий, или процедурная семантика.
При необходимости добиться от Лиспа возможности логического программирования необходимо запрограммировать алгоритм доказательства.
Построим такой алгоритм доказательства. Для этого доказываемый в настоящий момент предикат-теорему назовём целью. Цель можно доказать следующим алгоритмом:
1. Найти для доказательства цели первое предложение, значение которого унифицируется с целью.
2. Если предложение с таким заключением не найдено, то доказательство не удалось. Если предложение найдено и его тело пусто, то цель доказана. Если у предложения не пустое тело, то надо доказать его предикаты в качестве новых целей рекурсивно слева направо.
3. Если алгоритм зашёл в тупик, т.е. доказательство не удалось, то надо вернуться (backtrack) в предыдущее место, где можно выбрать другую цель (если такая имеется) и продолжить доказательство.
Подбор связей переменных основан на методе проб и ошибок и на поиске. Доказываемый в настоящий момент предикат пытаются унифицировать первым возможным способом. Если решение окажется неверным, т.е. некоторый предикат позже не удастся унифицировать, то происходит возврат к предыдущей унификации, выбирается следующая из ещё имеющихся возможностей, и делается попытка унифицировать оставшиеся предикаты другим способом.
Реализовав описанный алгоритм на Лиспе можно добиться возможности логического программирования на этом языке.