Обзор языков логического программирования

СОДЕРЖАНИЕ. 1. Введение. 2. 2. Что же представляют собой языки логического программирования 1. Чистый Полог. 2. Сравнение с традиционными языками программирования. 3. Программирование на чистом Прологе. 1. Порядок правил. 2. Проблема завершения программ. 3. Порядок целей. 4. Избыточные решения. 4.Практические рекомендации. 1. Эффективность программ на Прологе. 2. Разработка программ. 5. Другие языки логического программирования. 1. Язык логического программирования KL2. Типы данных KL3. Язык программирования ShapeUp. 3. Lisp язык функционального программирования. 1. Лисп в истории программирования. 3.2 Логическое программирование на Лиспе. 4. Заключение. 5. Используемая литература. 1.Введение. Почти все современные компьютеры основаны на ранних, разработанных в 40-х годах идеях фон Неймана и его коллег.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чистый Полог

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

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

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

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

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

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

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

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

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

Практические рекомендации

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

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

Этот параметр связан с временем работы программы. Для указанных алгоритмов применимы обычные методы анализа сложности вы... Анализ сложности таких программ представляет собой трудную задачу и тр... Единицей измерения скорости выполнения программы на языке логического ... 2.4.2.

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

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

Другие языки логического программирования

Другие языки логического программирования. Пролог не единственный язык логического программирования.

Кроме него существует ряд других языков, не получивших такого широкого признания в кругах программистов. Рассмотрим два таких языка. 2.5.1

Язык логического программирования KL

многопроцессовость операции с побочным эффектом машинно-ориентированны... Среди особенностей, новых в KL0 по отношению к Прологу, можно выделить... 2.5.2 . Язык логического программирования KL. Так как KL0 мало чем отличается от Пролога, ограничимся лишь рассмотре...

Типы данных KL

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

Язык программирования ShapeUp

Прологу присущи недетерминированность и сопоставление с образцом. Эти свойства очень полезны для разработки систем обработки информацион... К таким система можно отнести системы понимания естественного языка и ... В результате ShapeUp-программы проще и имеют более прозрачную семантик... Lisp list processing обработка списков.

Lisp язык функционального программирования

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

Лисп в истории программирования

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

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

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

Используемая литература

2. Язык Пролог в пятом поколении ЭВМ. Клоксин, Меллиш Программирование на языке Пролог. Сеппянен Мир Лиспа в 2-х томах. Стерлинг, Э.