учебники, программирование, основы, введение в,

 

Общие вопросы сентенциального программирования

Введение
Начнем с краткого сравнения путей развития двух ветвей сентенциального программирования.
Развитие языка Prolog
Британско-канадская группа, создававшая Prolog, первоначально ориентировалась на задачи математической лингвистики, где сложные преобразования данных сопряжены с проверкой гипотез.
Это естественно навело их на ортогональный Рефалу подход, формально мотивированный математической логикой. Наличие именно формальной мотивировки оказало медвежью услугу языку Prolog и всему направлению. Его сущность оказалась замаскирована примитивным методологически-теоретическим анализом и неадекватным названием: логическое программирование.
Prolog вдохновлялся ограничением классического исчисления предикатов, предложенным Хорном. Как известно, в классической логике в любой достаточно богатой теории появляются чистые теоремы существования, когда из доказательства невозможно выделить построение требуемого объекта. Если ограничиться конъюнкциями импликаций вида
http://localhost:3232/img/symbols/forall.gifx1, . . . , xnhttp://localhost:3232/img/symbols/exist.gify1, . . . , yk . . . (A1&· · ·&An http://localhost:3232/img/symbols/rArr.gifB),
где каждая составляющая является элементарной формулой и само доказанное утверждение имеет такой же вид, то получить построение из доказательства возможно, поскольку у нас не остается даже косвенных способов сформулировать и нетривиально использовать что-либо похожее на A http://localhost:3232/img/symbols/or.gif¬A. Такие формулы называются хорновыми.
От лишних кванторов можно избавиться при помощи сколемизации, когда кванторы существования заменяются на функцию, аргументами которой являются все переменные, связанные ранее стоящими кванторами всеобщности. Таким образом, мы приходим к простейшему виду хорновых формул (хорновы импликации):
http://localhost:3232/img/symbols/forall.gifx1, . . . , xn (A1&· · ·&An http://localhost:3232/img/symbols/rArr.gifB).
Применив к последней формуле преобразование, выполненное лишь в классической логике, мы приходим к хорновым дизъюнктам:
http://localhost:3232/img/symbols/forall.gifx1, . . . , xn (¬A1 http://localhost:3232/img/symbols/or.gif· · · http://localhost:3232/img/symbols/or.gif¬An http://localhost:3232/img/symbols/rArr.gifB).
Именно от последней формы представления хорновых утверждений получила имя основная структура данных языка Prolog. Но тот факт, что импликация преобразована в дизъюнкцию, на самом деле нигде в этом языке не используется, он послужил лишь для установления взаимосвязей с алгоритмом метода резолюций, который в тот момент был последним криком моды в автоматическом доказательстве теорем (и действительно громадным концептуальным продвижением). Метод резолюций до сих пор остается одним из нескольких наиболее часто применяемых методов автоматического доказательства, и единственным, известным широкой публике. Этот метод поставил три идеи (унификация, стандартизация цели, стандартизация порядка вывода), красивой программистской реализацией которых явился Prolog. Но находки языка Prolog не исчерпываются реализацией идей, взятых из теории. Они внесли существенный вклад в теорию и методологию программирования.
Именно на примере языка Prolog западное программистское сообщество четко осознало, что могут быть совсем другие модели исполнения программы, не являющиеся ни традиционными, ни их расширением. Был реабилитирован и стал порою успешно использоваться метод динамического порождения программы. Стала актуальной идея косвенного управления вычислениями. Этих достоинств с лихвой хватит для того, чтобы Prolog мог считаться важным принципиальным достижением.
Развитию языка Prolog мешает, прежде всего, слишком большая привязка к конкретной модели вычислений, которая в погоне за мнимой эффективностью была зафиксирована слишком рано. Совершенно извращено понимание его места и роли. На самом деле Prolog представляет собой великолепную заготовку для языка моделирования идей, а никакое не логическое программирование.
Рассмотрим, что именно этой заготовке мешает в реальности стать таким языком. Как мы уже неоднократно видели, главное препятствие — потеря целостности, вызванная лишними возможностями. В первую очередь, это эклектичные добавки операционных средств, которые провоцируют программиста к операционному мышлению и хакерскому стилю. Так, в задаче о лабиринте было бы естественно не зацикливание исполнения, когда не предусмотрены ограничивающие условия, заставляющие программу продвигаться вперед, а указание того, что в процессе выполнения не хватает условий, что возможны определенные варианты ограничений, делающие программу корректной. В результате разработчикам языка пришлось искать дополнительные средства выражения требуемых, а не предлагаемых, действий. Ничего лучшего по сравнению с известными операционными методами они не нашли и включили соответствующие средства в язык, полностью потеряв первоначальную концепцию.
Одним из классических примеров применения первоуровневых моделей и плоских, неадекватных практике, но привлекательно звучащих и просто объясняемых, выводов, которые делаются на их основе, является утверждение: «Логика Хорна достаточна для спецификации вычислений, поскольку, как было доказано, она эквивалентна машине Тьюринга». С этим утверждением можно было бы согласиться, если бы решения реальных задач, которые апеллируют к базам данных-фактов и должны решаться с использованием баз знаний-утверждений, являющихся следствиями из имеющихся фактов, всегда можно было бы формулировать в такой разделенной манере: сначала задаются факты, затем предложения-соотношения и далее идет манипулирование информацией. На самом деле таким образом формулируемые решения пригодны только для узкого класса задач, которые характеризуются стабильностью фактов, и только в том случае, когда не принимается в расчет эффективность.

http://localhost:3232/img/empty.gifhttp://localhost:3232/img/empty.gifРазвитие языка Рефал и его диалекты

Язык Рефал был создан В. Ф. Турчиным для аналитических вычислений в физике. Первоначально Турчин продумал саму идею конкретизации и представил ее в виде языка, демонстративно записанного в не слишком прямо представимой форме. Например, не было понятия детерминатива, предложения имели вид, подобный
§1.1.2 E1 + (E2 * E3)= (K E1 + E2 .)* (K E1 + E3 .)
Конкретно-синтаксическая форма языка, данная в теоретической работе Турчина сразу же была изменена для удобства представления и работы. Уже при первой реализации был продуман и проверен приведенный выше алгоритм отождествления, были выброшены иерархические комментарии в начале предложений, а вместо них появились понятия детерминатива и функции.
Дальнейшая доработка потребовала процедур ввода-вывода и механизма хранения глобальных данных, что было реализовано через стеки закопанных данных. Получившийся язык Рефал-2 длительное время был практическим стандартом Рефал-систем.
В языке Рефал-4 были сделаны две попытки расширения языка. Во-первых, как и во множестве других систем, к Рефалу были достаточно механически добавлены нарождавшиеся модные объектно-ориентированные средства. Эта попытка быстро зашла в тупик и была оставлена. Во-вторых, были определены метаоперации. Это нововведение доказало свою жизнеспособность и выжило. В языке Рефал-5, который сейчас является фактическим стандартом, объекты были отброшены, зато последовательно была проведена как стандартная надстройка над языком идея метакодирования. В нем получили свое окончательное оформление вложенные процедуры и дополнительные условия.
Из других существующих версий языка стоит отметить Рефал-6 и Рефал+, которые развивают одну и ту же линию. В реализации Рефал+ отошли от представления, принятого в, с тем чтобы воспользоваться современными алгоритмами сборки мусора. Вместо стеков закопанных значений в этих языках предлагаются объекты, которые имеют лишь одно значение. В частности, такие объекты используются для описания графического ввода и вывода, что полностью игнорируется в стандартном Рефале. В этих версиях позволяется объявить функцию откатной и пытаться при невозможности отождествлений обработать неудачу. Но автор этих версий проигнорировал концептуальную несовместимость неудач с общей структурой управления в языке Рефал. Из находок Рефал+, помимо новой структуры данных, стоит отметить концепцию упорядочения возможных отождествлений и возможность до некоторой степени управлять этим упорядочением (правда, в языке предусмотрен лишь переход от прямого порядка к его обращению, но уже это дает в некоторых случаях большой выигрыш в выразительности).
Наиболее заметным недостатком новых версий языка Рефал явилось отсутствие различения абстрактного и конкретного синтаксиса. Можно было бы просто отказаться от фиксации оформления в определении языка и дать возможность определять синтаксические расширения и представления самим разработчикам.
Стоит заметить, что нынешний язык Рефал находится в мягком концептуальном противоречии со столь блестяще реализованной в нем же идеей динамического вычисления программ. Решение исполнять ту функциональную скобку, внутри которой нет других таких скобок, было оправдано и логично при создании Рефала, а теперь оно уже мешает эффективно использовать аппарат метапреобразований. Необходимо заметить, что Рефал созрел для настоящего представления мультииерархической структуры, что позволит языку выйти на новые классы приложений. Таким образом, в ближайшее время можно ожидать появления нового сентенциального языка, реализующего идею конкретизации. Будет просто беда, если под красивой оберткой кто-нибудь подсунет в эту область концептуально непродуманное 'прагматическое' решение. Выигрыш от прагматизма будет минимальным, временным и локальным, а потери — длительными, на порядок превосходящими аналогичные для традиционных языков, и к тому же глобальными.
Именно в языке Рефал было четко показано, как выбирать структуры данных и алгоритм работы абстрактной машины для нетрадиционных вычислений и насколько это важно. В нем впервые избавились от жесткой привязки к конкретному синтаксису. Он продемонстрировал советскому программистcкому сообществу возможность альтернативных моделей вычислений, выполнив на востоке ту же роль, что Prolog на западе. В нем впервые была реализована концепция встроенных частичных вычислений программ. Он не поддался давлению моды, и этим способствовал осознанию наличия альтернатив даже в том случае, когда подходы в принципе близки. Всего этого достаточно для признания пионерской роли этого языка.
Сравнение версий сентенциального программирования
Прежде всего, методы управления языка Prolog и языка Рефал принципиально отличаются. В Prolog'е неудача глобальна, но исправима, а в Рефале — локальна, но фатальна.
Унификация в Prolog и конкретизация в Рефале являются операциями примерно одного и того же уровня общности. Но направления унификации и конкретизации ортогональны.

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

Внимание!
Модели унификации и конкретизации формально несовместимы, поскольку, соединив их, мы получаем алгоритмически неразрешимое понятие отождествления (Н. К. Косовский и др., 1990).
Это — глубочайший теоретический результат и одно из редких прямых предупреждений, сделанных теорией практике. Поэтому при сходстве многих идей, положенных в их основу, эти модели развиваются и должны дальше развиваться независимо (что не исключает творческого заимствования идей из одной ипостаси подхода в другую). Обратите внимание, что мы столкнулись с той же самой ситуацией, которая имеет место для циклической и рекурсивной ипостасей структурного программирования.
Точно так же, как циклическая ипостась структурного программирования, Рефал приспособлен для работы с данными, развернутыми в основном вширь и для развертывания процесса в ширину. Точно так же, как рекурсивная ипостась, Prolog приспособлен для развертывания процесса в глубину и для работы с данными, имеющими ограниченную ширину, но зато большую глубину.
Даже машинная реализация этих языков сродни двум ипостасям структурного программирования. В Рефале вызовы, которые выглядят как рекурсивные, на самом деле рекурсией не являются, поскольку мы заканчиваем породивший вызов, и лишь после этого переходим к отработке порожденных. Prolog больше похож на рекурсию, поскольку после вызова внутреннего предиката мы можем возвратиться к внешнему и продолжить попытки его унификации. В Рефале достаточно общего поля памяти, а в Prolog вынуждены запоминать также управляющие данные ( точки возврата).
Стоит заметить, что сентенциальное программирование, и особенно его разновидность, базирующаяся на модели отождествления-замены, великолепно сочетается с идеей ассоциативной памяти (см. стр. 31), и здесь возможен прорыв одновременно на аппаратном и программном уровнях.
Вариант сентенциального программирования, базирующийся на возвратах и унификации, отлично сочетается с идеей машины потоков данных. Японцы попытались использовать его в своем проекте ЭВМ пятого поколения. Провал данного проекта надолго дискредитировал направление соединения сентенциального программирования с потоками данных, но к нему придется вернуться в будущем на другой технической и, видимо, на гораздо более концептуально выверенной программистской основе.
Концепция унификации и возвратов после неудач исключительно хорошо подходит для выражения http://localhost:3232/img/symbols/or.gif-параллелизма (см. § 15.2). Более того, уже имеются системы (в частности, Muse), реализующие этот вариант параллелизма в языке Prolog.
Рефал, в свою очередь, великолепно подходит для &-параллелизма. Подстановки значений переменных в результирующее выражение можно осуществлять независимо друг от друга. Более того, в принципе можно было бы даже в нынешнем варианте Рефала вычислять различные функциональные скобки в параллель, помешать этому могут лишь значения, передаваемые через аппарат закапывания-выкапывания. Но это — стандартная проблема синхронизации для параллельных вычислений, с которой можно справляться хорошо разработанными средствами, тем более что аппарат для соответствующей разметки программы еще в ходе ее составления концептуально подготовлен в языке.
Таким образом, две ветви сентенциального программирования ориентированы даже на разные классы параллельных вычислений. Именно на примере сентенциального программирования нами был сделан вывод о том, что и для других стилей должны быть альтернативные реализации. Их выявлению мешал прежде всего закон экологической ниши.
При создании и развитии языков PROLOG и Рефал ярко проявились сильные и слабые стороны русской и англо-американской школ науки.
В. Ф. Турчин проделал адекватный анализ, не устаревший за 40 лет, но он не стремился к общепонятности и слишком большой популяризации (может быть, потому, что ему не нужно было выбивать гранты). Его последователи четко восприняли идею и развивали ее, практически полностью избегая концептуально противоречащих ей возможностей. Но популяризация языка и внешняя сторона работы с ним (удобные системы, интерфейсы и т. п.) оказались практически полностью проигнорированными, и поэтому язык остается достоянием узкой группы приверженцев.
Создатели Prolog с самого начала в значительной мере использовали теорию и методологию как заклинания либо молитвы, не имеющие отношения к сути дела и произносимые для его освящения. Тем самым теоретическая база сразу же оказалась неадекватной, что и привело к быстрому расползанию системы и потере концептуального единства. Язык в значительно большей мере, чем Рефал, оказался загрязнен чужеродными элементами.
Неадекватность теории практике помешала осознанию реальных достижений подхода, основанного на унификации, поскольку они часто противоречили мифам и саморекламе. Зато развитие внешнего оформления и удобных (с точки зрения дизайна) средств работы с языком шло адекватными темпами, а реклама его действительных и мнимых достижений далеко опережающими. Язык вошел в практику обучения многих университетов мира и попал даже в стандарты программ обучения специалистов IFAC.
Если говорить о практических задачах, то Prolog значительно лучше подходит для поиска, а Рефал — для синтаксических преобразований. Стоит также помнить, что в нынешнем состоянии Prolog не может служить даже для прототипирования, это язык лишь для моделирования решений и логики поведения программы.Но это — особенность нынешних конкретных реализаций идеи унификации и возвратов, она связана с тем, что примитивный концептуальный механизм пришел в противоречие с выявившимися богатейшими потенциальными возможностями подхода.
Рефал делает символьные преобразования столь же эффективно, как и программа на традиционном языке, и поэтому может быть использован на всех уровнях: и для создания прототипа программы, и для написания надпрограммы, и для написания подпрограммы.
Таким образом, Рефал по эффективности и ясности представления уже сейчас может служить языком прототипирования, и, если бы его снабдить удовлетворительными интерфейсами, вполне мог бы служить и для окончательных решений, работающих в многоязыковой среде. В момент написания книги существует единственный имеющийся надежно работающий интерфейс Рефала: с языком PHP преобразования HTML-текстов.
В особенности Рефал хорош в тех случаях, когда нужно произвести нетривиальное преобразование символьных входных либо выходных файлов. Его использование, как показала практика автора и студентов в многоязыковом программировании, зачастую оправдывается даже тогда, когда ведется передача данных через файл.
У Prolog ныне интерфейсы имеются, но они, как правило, ориентированы лишь на C++ и LISP и совершенно не стандартизованы. Каждая реализация имеет свой интерфейс.
Мы затронули общий недостаток нынешних систем сентенциального программирования. Это — плохая проработка связей с другими языками. При создании средств высших уровней необходимо с самого начала продумать вопросы связи с другими языками и использования языка в многоязыковой и многостилевой методологии программирования.
http://localhost:3232/img/empty.gif

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика