Развитие языка Prolog
Британско-канадская группа, создававшая Prolog, первоначально ориентировалась на задачи математической лингвистики, где сложные преобразования данных сопряжены с проверкой гипотез.
Это естественно навело их на ортогональный Рефалу подход1), формально мотивированный математической логикой. Наличие именно формальной мотивировки оказало медвежью услугу языку Prolog и всему направлению. Его сущность оказалась замаскирована примитивным методологически-теоретическим анализом и неадекватным названием: логическое программирование.
Prolog вдохновлялся ограничением классического исчисления предикатов, предложенным Хорном. Как известно (см., например, книгу [20]), в классической логике в любой достаточно богатой теории появляются чистые теоремы существования, когда из доказательства невозможно выделить построение требуемого объекта. Если ограничиться конъюнкциями импликаций вида
где каждая составляющая является элементарной формулой и само доказанное утверждение имеет такой же вид, то получить построение из доказательства возможно, поскольку у нас не остается даже косвенных способов сформулировать и нетривиально использовать что-либо похожее на A
От лишних кванторов можно избавиться при помощи сколемизации, когда кванторы существования заменяются на функцию, аргументами которой являются все переменные, связанные ранее стоящими кванторами всеобщности2). Таким образом, мы приходим к простейшему виду хорновых формул (хорновы импликации):
Применив к последней формуле преобразование, выполненное лишь в классической логике, мы приходим к хорновым дизъюнктам:
Именно от последней формы представления хорновых утверждений получила имя основная структура данных языка Prolog. Но тот факт, что импликация преобразована в дизъюнкцию, на самом деле нигде в этом языке не используется, он послужил лишь для установления взаимосвязей с алгоритмом метода резолюций [30], который в тот момент был последним криком моды в автоматическом доказательстве теорем (и действительно громадным концептуальным продвижением).
Метод резолюций до сих пор остается одним из нескольких наиболее часто применяемых методов автоматического доказательства, и единственным, известным широкой публике. Этот метод поставил три идеи (унификация, стандартизация цели, стандартизация порядка вывода), красивой программистской реализацией которых явился Prolog. Но находки языка Prolog не исчерпываются реализацией идей, взятых из теории. Они внесли существенный вклад в теорию и методологию программирования3).
Именно на примере языка Prolog западное программистское сообщество четко осознало, что могут быть совсем другие модели исполнения программы, не являющиеся ни традиционными, ни их расширением. Был реабилитирован и стал порою успешно использоваться метод динамического порождения программы. Стала актуальной идея косвенного управления вычислениями. Этих достоинств с лихвой хватит для того, чтобы Prolog мог считаться важным принципиальным достижением.
Развитию языка Prolog мешает, прежде всего, слишком большая привязка к конкретной модели вычислений, которая в погоне за мнимой эффективностью была зафиксирована слишком рано. Совершенно извращено понимание его места и роли. На самом деле Prolog представляет собой великолепную заготовку для языка моделирования идей, а никакое не логическое программирование.
Рассмотрим, что именно этой заготовке мешает в реальности стать таким языком. Как мы уже неоднократно видели, главное препятствие — потеря целостности, вызванная лишними возможностями. В первую очередь, это эклектичные добавки операционных средств, которые провоцируют программиста к операционному мышлению и хакерскому стилю. Так, в задаче о лабиринте было бы естественно не зацикливание исполнения, когда не предусмотрены ограничивающие условия, заставляющие программу продвигаться вперед, а указание того, что в процессе выполнения не хватает условий, что возможны определенные варианты ограничений, делающие программу корректной. В результате разработчикам языка пришлось искать дополнительные средства выражения требуемых, а не предлагаемых, действий.
Ничего лучшего по сравнению с известными операционными методами они не нашли и включили соответствующие средства в язык, полностью потеряв первоначальную концепцию.
Одним из классических примеров применения первоуровневых моделей и плоских, неадекватных практике, но привлекательно звучащих и просто объясняемых, выводов, которые делаются на их основе, является утверждение: "Логика Хорна достаточна для спецификации вычислений, поскольку, как было доказано, она эквивалентна машине Тьюринга4)". С этим утверждением можно было бы согласиться, если бы решения реальных задач, которые апеллируют к базам данных-фактов и должны решаться с использованием баз знаний-утверждений, являющихся следствиями из имеющихся фактов, всегда можно было бы формулировать в такой разделенной манере: сначала задаются факты, затем предложения-соотношения и далее идет манипулирование информацией. На самом деле таким образом формулируемые решения пригодны только для узкого класса задач, которые характеризуются стабильностью фактов, и только в том случае, когда не принимается в расчет эффективность.
