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

Порядок целей.

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

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

Порядок целей определяет дерево поиска. По этой причине порядок целей влияет на количество проверок, выполняемых программой при решении.

Существенен не порядок правил, а порядок целей. Программа будет завершающейся, если первый аргумент цели – полный список. Цели, у которых первый аргумент – неполный список приводят к бесконечным вычислениям.

Избыточные решения.

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

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

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

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

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

Практические рекомендации.

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

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

Эффективность программ на Прологе.

В практическом программировании на Прологе необходимо обращать внимание на эффективность программ. Установим критерии оценки программ. Основной оцениваемый параметр – число выполняемых унификаций и число попыток унификации в процессе вычисления. Этот параметр связан со временем работы программы. Ещё один параметр – глубина вложенной рекурсии. Если в процессе вычислений глубина станет больше максимально допустимой, то вычисления прервутся. На практике эта проблема является основной. Третий параметр – число порождённых структур данных. Рассмотрим последовательно эти параметры.

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

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

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

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

Один из основных способов повышения эффективности программ – совершенствование алгоритма. Хотя речь идёт о декларативном языке, понятие алгоритма в Прологе остаётся тем же, что и в других языках программирования.

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

Разработка программ.

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

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

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

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

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

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

Один из ответов на вопрос в чём разница в разработке программ на Прологе и на обычных языках программирования состоит в том, что, хотя, программирование на Прологе – это “просто” программирование, в случае Пролога имеется преимущество в простоте записи и скорости отладки по сравнению с формализмами более низкого уровня.

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

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

Имеющиеся средства и системы программирования не навязывают и не поддерживают, какую либо специфическую методику разработки программ. Однако, как и в других символьных языках программирования, наиболее естественной стратегией разработки программ является стратегия быстрой смены прототипов. При такой стратегии на каждой стадии разработки имеется лучше работающий прототип программы. Разработка происходит путём переделки или расширения прототипа. Другой подход к разработке программ, иногда комбинируемый с первым, состоит в “нисходящем анализе и восходящей реализации”. Хотя проектирование системы следует проводить нисходящим способом, основываясь на анализе цели, реализацию системы лучше всего строить “снизу вверх”. В процессе восходящего программирования каждый написанный фрагмент программы может быть немедленно отлажен. Глобальные проектные решения, такие, как представление, могут быть проверены на небольших сегментах системы, которые будут приведены в порядок и очищены от ошибок на начальной стадии программирования. Кроме того, эксперименты с одной подсистемой могут привести к изменению проектных решений, относящихся к другим подсистемам.

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

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

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

Пролог не единственный язык логического программирования. Кроме него существует ряд других языков, не получивших такого широкого признания в кругах программистов. Рассмотрим два таких языка.

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

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

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

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

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

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

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

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

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

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

Типы данных KL0.

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

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

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

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