Существуют разные языки программирования, использующие различные способы выбора. Грубо говоря, они делятся на два класса. Пролог и его расширения основаны на последовательном выполнении. Другие языки, такие, как Parlog, Параллельный Пролог и GHC, основаны на параллельном выполнении. Последовательные языки отличаются от параллельных методом реализации недетерминизма. Отличие Пролога от его версий состоит в методе выбора редуцируемой цели.
Выполнение программ на Прологе заключается в работе абстрактного интерпретатора, при которой вместо произвольной цели выбирается самая левая цель, а недетерминированный выбор предложения заменяется последовательным поиском унифицируемого правила и механизма возврата.
Другими словами, в Прологе используется стековый метод расписания. В Прологе резольвента используется как стек – для редукции выбирается верхняя цель, производные цели помещаются в стек резольвенты.
В дополнение к методу стека Пролог моделирует недетерминированный выбор редуцирующего правила с помощью последовательного поиска и механизма возврата. При попытке редуцировать цель выбирается первое предложение, заголовок которого унифицируем с данной целью. Если не существует правила, унифицируемого с выбранной целью, то вычисление восстанавливается на стадии последнего сделанного выбора и выбирается следующее унифицируемое предложение.
1.2. Сравнение с традиционными языками программирования.
Язык программирования характеризуется присущими ему механизмами управления и обработки данных. Пролог как универсальный язык программирования можно рассматривать и с этих точек зрения.
При успешном выполнении вычисления средства управления программ на языке Пролог подобны средствам управления в обычных процедурных языках. Обращение к некоторой цели соответствует вызову процедуры, порядок целей в теле правила соответствует последовательности операторов. Точнее, правило А = В1,В2,…,Вn можно рассматривать как определение процедуры:
Procedure A
Call B1
Call B2
.
.
.
Call Bn
End.
Рекурсивный вызов цели в Прологе в последовательности действий и в реализации подобен тому же вызову в обычных рекурсивных языках. Различие возникает при реализации возврата. В обычных языках, если вычисление не может быть продолжено (например, все ветви в операторе case ложны), возникает ошибка выполнения. В Прологе вычисление просто возвращается к последнему выбору и делается попытка продолжить вычисления по новому пути.
Структуры данных, которыми оперируют логические программы, - термы – соответствуют общим структурам записей в обычных языках программирования. Пролог использует очень гибкую систему организации структур данных. Подобно языку Лисп, Пролог является бестиповым языком, не содержащим объявления данных.
Другие особенности использования структур данных в языке Пролог связаны с природой логических переменных. Логические переменные соотносятся с объектами, а не с ячейками памяти. Если переменной сопоставлен конкретный объект, то эта переменная уже никогда не может ссылаться на другой объект. Иными словами, логическое программирование не поддерживает механизм деструктивного присваивания, позволяющий изменять значение инициализированной переменной.
В логическом программировании обработка данных полностью заключена в алгоритме унификации. В унификации реализованы:
• однократное присваивание,
• передача параметров,
• размещение записей,
• доступ к полям записей для одновременных чтения/записи.
Традиционные языки, как правило, содержат различной степени сложности средства обработки ошибочных и исключительных ситуаций. Чистый Пролог не содержит механизма обработки ошибок и исключительных ситуаций, встроенного в описание языка. В отличие от традиционных языков ситуации, приводящие к ошибке (например, отсутствие нужной ветви в операторе case, деление на нуль), в чистом Прологе приводят к “отказу”.
1.3 Программирование на чистом Прологе.
Основная цель логического программирования – создать возможность разработки программ на языке высокого уровня. В идеале программист должен записать аксиомы, определяющие требуемые отношения, полностью игнорируя, каким образом эти аксиомы будут использоваться в процессе выполнения. Имеющиеся языки логического программирования, и, в частности Пролог, всё ещё далеки от этого идеала декларативного программирования. Нельзя игнорировать конкретный, четко определённый способ моделирования абстрактного оператора в реализации каждого языка. Эффективное логическое программирование требует знания и использования этого способа.
Два синтаксических понятия, несущественные в логических программах, важны при создании программ на Прологе. В каждой процедуре должен быть принят порядок правил, или порядок предложений. Кроме того, в теле каждого предложения должен быть определён порядок целей. Последствия этих решений могут оказаться колоссальными: эффективность программирования на Прологе может измениться в десятки раз. В крайних и тем не менее распространённых случаях корректные логические программы вообще не приведут к решению вследствие не завершающегося вычисления.
Порядок правил определяет порядок поиска решений.
Изменение порядка правил в процедуре приводит к перестановке ветвей в любом дереве поиска цели, использующей данную процедуру. Обход дерева поиска происходит в глубину. Поэтому перестановка ветвей дерева изменяет порядок обхода дерева и порядок нахождения решений. Этот эффект очевиден при использовании фактов для нахождения ответов на экзистенциальный вопрос.
Порядок, в котором находятся ответы на вопросы при работе рекурсивной программы, определяется порядком предложений.
Порядок предложений в программах на общепринятом Прологе важнее, чем порядок предложений в программах на чистом Прологе.
1.3.2. Проблема завершения программ.
Используемый в Прологе принцип обхода дерева в глубину приводит к серьёзным проблемам. Если дерево поиска цели относительно некоторой программы содержит бесконечную ветвь, то вычисление не завершится. Пролог может не найти решение цели, даже если существует конечное вычисление, решающее вопрос.
Бесконечные вычисления появляются при использовании рекурсивных правил. Рекурсивные правила, в которых рекурсивная цель является первой целью в теле правила, называются левыми рекурсивными правилами. Левые рекурсивные правила в Прологе приносят немало хлопот. В случае несоответствующих аргументов использование этих правил приводит к бесконечным вычислениям.
Лучшее решение этой проблемы – отказаться от использования левой рекурсии. В общем случае невозможно избавиться от всех появлений левой рекурсии. Однако соответствующий анализ позволяет определить вопросы, решение которых относительно рекурсивных программ приводит к результату. Другой, не всегда замечаемый случай, который заведомо приводит к не завершающимся вычислениям – это порочный круг. Ввиду порочного круга дерево поиска обязательно содержит бесконечную ветвь.
Порядок целей более существен, чем порядок предложений. Порядок целей имеет решающее значение при определении последовательности действий в программе на Прологе.
Причина, по которой порядок целей в предложении влияет на порядок решений, отличается от причины, по которой порядок правил в процедуре влияет на порядок решений. Изменение порядка правил не изменяет дерево поиска, которое используется при решении данной цели. Просто обход дерева производится в ином порядке. Изменение порядка целей приводит к изменению дерева поиска.
Порядок целей определяет дерево поиска. По этой причине порядок целей влияет на количество проверок, выполняемых программой при решении.
Существенен не порядок правил, а порядок целей. Программа будет завершающейся, если первый аргумент цели – полный список. Цели, у которых первый аргумент – неполный список приводят к бесконечным вычислениям.
При построении программ на Прологе следует обратить внимание на важную характеристику программы, не имеющую аналогов в логическом программировании, - отсутствие избыточных решений. Значением логической программы является множество выводимых из программы основных целей. Здесь не существенно, выводится ли цель единственным образом или существует несколько различных выводов; однако это существенно в Прологе, поскольку от этого зависит эффективность поиска решений. Каждый возможный вывод означает дополнительную ветвь в дереве поиска, чем больше дерево поиска, тем дольше продолжается вычисление. В общем случае желательно сохранить размер дерева поиска по возможности минимальным.
Наличие избыточных решений из-за возвратов может вызвать в предельном случае экспоненциальный рост времени работы программы. При решении конъюнкции n целей, каждая из которых имеет одно избыточное решение, в случае возвратов может быть порождено 2n решений, что приводит к изменению оценки времени работы программы от полиноминальной (или даже линейной) к экспоненциальной.
Одна из причин появления избыточных решений в программах на Прологе состоит в наличии различных правил, пригодных для одного и того же случая.
Другая причина, приводящая к избыточным решениям, состоит в рассмотрении слишком большого числа специальных случаев. Иногда подобное рассмотрение мотивируется стремлением к эффективности.
Для исключения избыточных решений можно добавить дополнительный факт, что позволит сократить рекурсивные вычисления, когда существует аргумент – пустой список. Каждое предложение должно применяться лишь к спискам с ненулевым вторым аргументом.