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

Содержание 

Введение.

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

По мере преодоления  технических проблем построения компьютеров накапливались проблемы, связанные с их использованием. Трудности сместились из области выполнения программ компьютера в область создания программ для компьютера. Начались поиски языков программирования, пригодных для человека. Начиная с языка, воспринимаемого компьютером (машинного языка), стали появляться более удобные формализмы и системы обозначений. И хотя степень абстракции языков возрастала, начиная с языка ассемблера и далее к Фортрану, Алголу, Паскалю и Аде, все они несут печать машины с архитектурой фон Неймана.  Характерные особенности программирования на компьютерах фон Неймана приводят к разделению труда: есть люди, которые думают, как решить задачу, и разрабатывают соответствующие методы, а есть люди-кодировщики, которые пишут тексты программ, т.е. выполняют прозаическую и утомительную работу по переводу инструкций разработчиков в команды, воспринимаемые компьютером.

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

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

  Основание  символьной логики были заложены  Булем, Де Морганом и другими  в прошлом столетии. Современную,  систематическую формулировку логики  первого порядка изложил Фреге.  В течение длительного времени  семантика (или "значение”) логики оставалось запутанным предметом, но в конце концов значительная ясность в него была внесена Тарским.

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

Конечно, логика давно используется  и при проектировании компьютеров, и при анализе компьютерных программ. Однако непосредственное использование логики в качестве языка программирования, называемого логическим программированием, возникло сравнительно недавно.

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

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

        А, если В1 и В2 и … и  Вn 

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

  Логическое  программирование возникло главным  образом благодаря успехам в  автоматическом доказательстве  теорем, в частности благодаря разработке принципа резолюции. Одно из первых исследований, связывающих резолюцию с программированием для ЭВМ, было предпринято Грином. Общая идея, состоящая в рассмотрении логических предложений как операторов в программах,  а управляемого вывода – как исполнения программ, была исследована Хайсом, Сандвеллом и другими. Однако осознанию того, что логика является исполняемым языком программирования, в особенности способствовала указанная выше процедурная интерпретация Ковальского.

  Успехи в  технологии реализации также в значительной мере способствовали представлению логики как практической формальной системы программирования. Первый экспериментальный интерпретатор был реализован Русселом и Колмероэ и другими в университете Экс – Марсель в 1972 году. Ему было дано имя Пролог ("программирование на языке логики” – PROgramming in LOGic), и он оказал сильное влияние на разработку последующих систем.

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

  Возникновение  Пролога покрыто тайной. Известно  только то, что два создателя  языка – Роберт Ковальский, в то время работавший в Эдинбурге, и Алан Колмероэ из Марселя – разрабатывали в начале 70-х сходные идеи и даже работали вместе в течение одного лета. В результате были сформулированы основные положения логического программирования и вычислительная модель, описан и реализован первый язык логического программирования – Пролог.

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

  Несмотря  на обилие теоретических работ  и волнующих идей, концепция логического программирования казалась нереалистичной. В этот период в результате исследования, проведённого в США, были обнаружены серьёзные недостатки "языков искусственного интеллекта следующего поколения”. Основные претензии к таким языкам программирования заключались в следующем: они были неэффективны и очень трудны в реализации.

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

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

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

Глава 1. Общие сведения.

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

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

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

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

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

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

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

1.2. Сравнение с традиционными языками

программирования

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

При успешном выполнении вычисления средства управления программ на языке Пролог подобны средствам  управления в обычных процедурных  языках. Обращение к некоторой  цели соответствует вызову процедуры, порядок целей в теле правила соответствует последовательности операторов. Точнее, правило А = В1,В2,…,Вn можно рассматривать как определение процедуры:

Procedure A

      Call B1

      Call B2

      .

      .

      .

      Call Bn

End. 

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

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

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

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

•    однократное  присваивание,

•    передача параметров,

•    размещение записей,

• доступ к полям  записей для одновременных чтения/записи.

  Традиционные  языки, как правило, содержат  различной степени сложности  средства обработки ошибочных и исключительных ситуаций. Чистый Пролог не содержит механизма обработки ошибок и исключительных ситуаций, встроенного в описание языка. В отличие от традиционных языков ситуации, приводящие к ошибке (например, отсутствие нужной ветви в операторе case, деление на нуль), в чистом Прологе приводят к "отказу”.

Глава 2. Программирование на чистом Прологе.

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

2.1 Порядок правил.

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

  Порядок  правил определяет порядок поиска  решений.

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

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

  Порядок  предложений в программах на  общепринятом Прологе важнее, чем  порядок предложений в программах  на чистом Прологе.

2.2. Проблема завершения программ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 3. Практические рекомендации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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