Слайд 1Логические языки программирования
Канарейкин А. И.
Слайд 2Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем, а
также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.
Самым известным языком логического программирования является Prolog.
Слайд 3История
Первым языком логического программирования был язык Planner, в котором была заложена
возможность автоматического вывода результата из данных и заданных правил перебора вариантов (совокупность которых называлась планом). Planner использовался для того, чтобы понизить требования к вычислительным ресурсам (с помощью бэктрекинга — поиска с возвратом) и обеспечить возможность вывода фактов, без активного использования стека. Затем был разработан язык Prolog, который не требовал плана перебора вариантов и был, в этом смысле, упрощением языка Planner.
От языка Planner также произошли логические языки программирования QA-4, Popler, Conniver и QLISP. Языки программирования Mercury, Visual Prolog, Oz и Fril произошли уже от языка Prolog. На базе языка Planner было разработано также несколько альтернативных языков логического программирования, не основанных на методе поиска с возвратами, например, Ether.
Слайд 4Что такое Пролог
Prolog (Programming in Logic, в оригинале: programmation en logique)
был разработан в Марселе в начале 70-х Аленом Колмероэ. В основу языка легла процедурная интерпретация логических выражений Хорна (т.е., как именно можно машинно выполнить) утверждений вида:
a :- b, c, d,...,z.
Что может быть прочитано как: "если условия b, c, d, ..., z — выполнены, тогда и "a" должно быть верно.
И, упрощенно говоря (вот тут мы опускаем все технические детали), может быть переписано в виде логического следования:
По сути Сэр Боб Ковальски — -- придумал такую вещь: утверждение "a" верно, если мы докажем, что все предпосылки к нему верны. (Кстати, отличный и веселый мужик — еще здоров и сыпет шутками и байками, год назад на конференции в Королевском сообществе в Лондоне он прочитал отличную и временами смешную лекцию по истории Пролога и логического программирования.)
В чём соль, Ковальски? Если взять выражение "a :- b,c,d", то его можно прочитать так:
"a" — верно, если я могу: доказать "b", доказать "c" и доказать "d".
Тогда каждая программа — это набор теорем для вывода утверждений, а каждое выражение "доказывается".
Задача становится чуть веселее, если добавить сюда отрицание. В Прологе оно называется negation as failure и отличается от классического отрицания в логике. В теории это звучит так: если я не смог доказать утверждение "a", то значит оно неверно. В логике такое предположение называется closed world assumption и иногда оно очень даже осмысленно.
Слайд 5Базы Знаний
Под Базами знаний в информатике понимают совокупность фактов и правил
вывода, допускающих логический вывод и осмысленную обработку информации. В языке Пролог базы знаний описываются в форме конкретных фактов и правил логического вывода над базами данных и процедурами обработки информации, представляющих сведения и знания о людях, предметах, фактах событиях и процессах в логической форме.
Наиболее важным свойством информации, хранящейся в базах знаний, является достоверность конкретных и обобщенных сведений в базе данных и релевантности информации, получаемой с использованием правил вывода, заложенных в базу знаний.
В ответах на простейшие запросы к базам знаний системы логического программирования Пролог, выдает значения «истина» и «ложь» в зависимости от наличия соответствующих фактов. Истинность и ложность ответов существенно зависит от наполнения баз знаний фактической информацией и ее непротиворечивостью.
Обобщенные сведения в базах знаний на языке Пролог задаются с помощью правил логического вывода, выполняющих роль определения понятий, а также логических процедур, состоящих из наборов правил логического вывода. Достоверность обобщенных сведений зависит от наличия необходимых фактов и достоверности данных в базах знаний.
Слайд 6Mercury
Mercury — язык логического программирования, призванный решить следующие две проблемы, которые
возникают при использовании классического языка логического программирования Prolog:
проблема производительности. Современные реализации языков логического программирования по производительности уступают реализациям языков программирования императивного типа.
проблема отладки. Реализации языков логического программирования осуществляют меньше проверок во время компиляции, чем реализации языков программирования императивного типа. Это вынуждает программиста находить ошибки самому и без какой-либо существенной помощи со стороны отладчика.
Компилятор языка Mercury написан на самом языке. До того как компилятор Mercury смог скомпилировать себя сам, был использован язык Prolog.
Mercury – это новый функционально-логический язык программирования со строгой типизацией, системой режимов аргументов и детерминизмом предикатов. Синтаксис частично унаследован от Пролога, система типов похожа на Haskell. Mercury - является эволюционным продолжением логического подхода, принятого в языке Пролог, но при этом лишенным многих недостатков классического Пролога. Исторически сложилось, что гегемоном в логическом программировании является язык Пролог с классическим, так называемым, эдинбургским синтаксисом.
Слайд 7ShapeUp
ShapeUp - ещё один язык логического программирования, в основу которого положен
Пролог, расширенный средствами сопоставления строк.
В ShapeUp образцы строк рассматриваются так же, как и термы Пролога, и их сопоставление возложено на процесс
унификацию. Таким образом, программы на ShapeUp значительно проще, чем аналогичные программы на Прологе,
их легче писать и понимать. Сокращается значительно и размер программ.
Прологу присущи недетерминированность и сопоставление с образцом. Эти свойства очень полезны для разработки систем обработки информационных знаний. К таким система можно отнести системы понимания естественного языка и другие системы интеллектуальной обработки текстов. Для подобных приложений очень важна операция сопоставления строк. Однако механизм сопоставления с образцом в таком виде, как он существует в Прологе, недостаточен для сопоставления строк. Причина заключена в “терм-терм” механизме сопоставления.
ShapeUp – попытка разработать более практический, свободный от присущего Прологу недостатка инструмент программирования. Характерной чертой ShapeUp, отличающей его от традиционных Пролог-систем, является выполняемая при унификации функция сопоставления строк. В ShapeUp включено несколько операторов сопоставления строк. Язык позволяет конструировать образцы строк, представляемые как термы Пролога. Образцы могут унифицироваться с различными строковыми объектами: расширена унификация для выполнения сопоставления строк. В результате ShapeUp-программы проще и имеют более прозрачную семантику, их легче писать.
Слайд 8Достоинства и недостатки
Достоинства:
- Операции, совершаемые в логическом программировании всегда понятны;
- Результат
практически всегда не зависит от выбранного пути реализации;
- Может быть использован в качестве невычислительного языка используя только выражения и факты.
Недостатки:
- Если брать за пример логического языка программирования Prolog, то на лицо невозможность создания комплексных задач. То есть в реальности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко;
- Из-за недостатка в инвестициях и простом внимании, логические языки слабо развиваются;
- Если предстоит иметь дело с вычислительными операциями, то логические языки программирования - не лучший выбор.