Федеральное агентство по образованию 

    Государственное образовательное учреждение

    высшего профессионального образования

«САНКТ  – ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ» 
 

Кафедра информатики 
 
 

Реферат на тему:

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

Выполнил  студент 

107 группы:

Тютюшкина А.В.

Руководитель:     
 
 
 
 
 
 

Санкт-Петербург, 2010 
Содержание 

 

Введение

 

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 1. Что же представляют собой языки логического  программирования?

1. Чистый  Полог.

 

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

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

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

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

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

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

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

 

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

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

    Procedure A

          Call B₁

                 Call B₂

          .

          .

          .

          Call B_n

    End. 

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

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

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

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

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

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

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

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

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