Современные системы логического программирования

Размещено на http://www.allbest.ru/

Введение

Почти все современные компьютеры основаны на ранних, разработанных в 40-х годах идеях фон Неймана и его коллег. Машина фон Неймана содержит большую память и процессор, снабженный локальной памятью, ячейки которой называются регистрами. Процессор может загружать данные из памяти в регистры, выполнять арифметические и логические операции над содержимым регистров и отсылать значения регистров в память. Программа машины фон Неймана представляет собой последовательность команд выполнения перечисленных операций вместе с дополнительным множеством команд управления, влияющих на выбор очередной команды. Хотя компьютеры предназначены для использования людьми, возникающие при их создании трудности были столь значительны, что язык описания проблемы и инструкций для их решения на компьютере разрабатывался применительно к инженерным решениям, заложенным в конструкцию компьютера.

Чистый Пролог

Взаимосвязь логического программирования и языка Пролог напоминает взаимосвязь лямбда-исчисления и языка Лисп. Оба этих языка являются конкретной реализацией абстрактных вычислительных моделей. Логические программы, исполняемые с помощью вычислительной модели Пролога, называются программами на чистом Прологе. Чистый Пролог представляет собой приближённую реализацию вычислительной модели логического программирования на последовательной машине. Конечно, данная реализация не является единственно возможной. Она является, однако, одной из наилучших с практической точки зрения - совмещения свойств абстрактного интерпретатора с возможностью эффективного выполнения.

При построении на основе абстрактного интерпретатора некоторого интерпретатора для конкретного языка программирования необходимо принять два решения. Во-первых, следует ограничить произвол в выборе редуцируемой цели в резольвенте, т.е. уточнить метод расписания. Во-вторых, нужно реализовать недетерминированный выбор предложения программы, используемого в редукции.

Существуют разные языки программирования, использующие различные способы выбора. Грубо говоря, они делятся на два класса. Пролог и его расширения основаны на последовательном выполнении. Другие языки, такие, как Parlog, Параллельный Пролог и GHC, основаны на параллельном выполнении. Последовательные языки отличаются от параллельных методом реализации недетерминизма. Отличие Пролога от его версий состоит в методе выбора редуцируемой цели.

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

Другими словами, в Прологе используется стековый метод расписания. В Прологе резольвента используется как стек - для редукции выбирается верхняя цель, производные цели помещаются в стек резольвенты.

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

Язык логического программирования KL0

KL0 (от англ. “kernel-language version 0” - ядро-язык версии 0) - язык, в основу которого положено расширение языка логического программирования Пролог. Среди особенностей, новых в KL0 по отношению к Прологу, можно выделить:

· более гибкую структуру управления.

· многопроцессовость

· операции с побочным эффектом

· машинно-ориентированные операции.

К наиболее существенным механизмам Пролога, не поддерживаемым в KL0, относятся:

· средства управления базой данных

· средства управления таблицей имён.

Так как KL0 мало чем отличается от Пролога, ограничимся лишь рассмотрением типов данных.

Типы данных KL0

Рассмотрим в общих чертах некоторые базовые типы данных языка. К ним относятся символы, целые и действительные числа, строки и др.

Символы в основном предназначены для представления символьных атомов Пролога и, как правило, никак не связаны ни со строками символов, используемыми для текстуального представления программ, ни с определениями предикатов, в которых символы задают имена предикатов. Такие атрибуты при необходимости могут быть приписаны символам средствами ESP . KL0 более прост и не поддерживает подобных механизмов. В этом отношении он только обеспечивает структуры данных прямого доступа и стандартную функцию хеширования для доступа к определениям атрибутов в хеш-таблице. Символы в KL0можно проверять только на идентичность.

Целые и действительные числа введены для эффективного выполнения арифметических операций. Арифметические операции в KL0 не обладают свойством двойственности: сложение и вычитание здесь различные предикаты. Аппаратно поддерживаются только числа фиксированной длины, определяемой разрядной сеткой. Целые числа произвольной длины (bignums), действительные числа произвольной точности и, возможно, рациональные числа могут быть реализованы с помощью обработчика исключений. Исключение возбуждается, если операндами встроенных арифметических предикатов (машинных инструкций в традиционном смысле) являются, например, нечисловые данные. Обработчик исключения может проверить аргументы и, если они соответствуют ожидаемым, выполнить предписанные операции; в противном случае вызывается обработчик ошибок. После обработки исключения дальнейшее выполнение программы может быть возобновлено.

Строки представляются одномерными массивами небольших положительных целых. Размер элементов массива зависит от диапазона значений элементов строки и может изменяться от одной строки к другой. Для представления битовых массивов, используемых для хранения образов графических изображений в памяти, введены строки с однобитовыми элементами. Для представления символов в коде ASCII используются строки с размером элемента 8 бит.

Логическое программирование на Лиспе

язык логическое программирование лисп

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

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

Чтобы в декларативном языке можно было выполнять разумные вычисления, для него наряду с декларативным смыслом определяется интерпретация в виде действий, или процедурная семантика.

При необходимости добиться от Лиспа возможности логического программирования необходимо запрограммировать алгоритм доказательства.

Построим такой алгоритм доказательства. Для этого доказываемый в настоящий момент предикат-теорему назовём целью. Цель можно доказать следующим алгоритмом:

1. Найти для доказательства цели первое предложение, значение которого унифицируется с целью.

2. Если предложение с таким заключением не найдено, то доказательство не удалось. Если предложение найдено и его тело пусто, то цель доказана. Если у предложения не пустое тело, то надо доказать его предикаты в качестве новых целей рекурсивно слева направо.

3. Если алгоритм зашёл в тупик, т.е. доказательство не удалось, то надо вернуться (backtrack) в предыдущее место, где можно выбрать другую цель (если такая имеется) и продолжить доказательство.

Подбор связей переменных основан на методе проб и ошибок и на поиске. Доказываемый в настоящий момент предикат пытаются унифицировать первым возможным способом. Если решение окажется неверным, т.е. некоторый предикат позже не удастся унифицировать, то происходит возврат к предыдущей унификации, выбирается следующая из ещё имеющихся возможностей, и делается попытка унифицировать оставшиеся предикаты другим способом.

Реализовав описанный алгоритм на Лиспе можно добиться возможности логического программирования на этом языке.

Так как возможное в Прологе реляционное и логическое программирование завоёвывало всё большее количество сторонников, многие Лисп-системы стали оснащаться встроенным интерпретатором Пролога. Основанное на логике программирование с помощью правил в будущем может таким же образом войти в Лисп, как, например, вошло объектно-ориентированное программирование Смолтолка.

Заключение

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

Однако логическое программирование с использованием лишь хорновских предложений было бы слишком узконаправленным. Поэтому, кроме этого, используются другие методы программирования. Некоторые задачи по своему характеру процедурные, и программировать их чисто декларативными языками непрактично. Нужны более развитые типы данных. Пролог и логическое программирование непрерывно расширяются, охватывая все новые методы программирования и формы изображения именно в направлении процедурного и объектно-ориентированного программирования, а также в направлении параллельных вычислений.

Размещено на Allbest.ru