🗊Презентация Логическое программирование

Факультет Прикладной математики и физики Факультет Прикладной математики и физики Кафедра Вычислительной математики и программирования Московский авиационный институт (государственный технический университет)

Майкрософт Россия, академический евангелист Майкрософт Россия, академический евангелист Кандидат физ.-мат. наук Распределенные интеллектуальные системы с явным представлением знаний Интеллектуальная реструктуризация социальных сетей на основе онтологий Семантически-ориентированые системы (Semantic Wiki) Кафедра Вычислительной математики и программирования МАИ (доцент) Логическое программирование Искусственный интеллект Студенческая лаборатория MAILabs (www.mailabs.ru) ФИВТ

Что такое логическое программирование? Что такое логическое программирование?

Тест Тьюринга – подробнее в курсе ИИ Тест Тьюринга – подробнее в курсе ИИ Проблемы: Неоднозначность человеческого языка При коммуникации мы полагаемся на картину мира, которая есть у нас в голове (common knowledge)

Assembler (x86, …) Assembler (x86, …) C, C++, C#, Java Pascal … Brainfuck? FORTH? LISP, FP, ML, Haskell, OCaml, F#, … Prolog, Mercury, Datalog, …

Первый язык программирования высокого уровня – ФОРТРАН – был создан Дж.Бэкусом, чтобы математики могли программировать на уровне формул. Первый язык программирования высокого уровня – ФОРТРАН – был создан Дж.Бэкусом, чтобы математики могли программировать на уровне формул.

Позже Дж.Бэкус пошел дальше и предложил язык FP, в котором формулы более соответствовали математическому понятию функции Позже Дж.Бэкус пошел дальше и предложил язык FP, в котором формулы более соответствовали математическому понятию функции

Надо пытаться формализовать человеческий язык! Надо пытаться формализовать человеческий язык! Основной инструмент формализации: Формальные аксиоматические системы Логика!

При декларативном программировании мы (на некотором формальном языке) описываем результат (его свойства), а не способ его достижения При декларативном программировании мы (на некотором формальном языке) описываем результат (его свойства), а не способ его достижения Описание факториала HTML – описание расположения объектов SQL LINQ Функциональные, логические языки

Императивное – мы говорим компьютеру, как решать задачу (что делать) Императивное – мы говорим компьютеру, как решать задачу (что делать) Основной акцент – манипулирование ячейками памяти Оператор присваивания Явные операторы передачи управления Циклы, условный оператор

Это не «чистая» императивная программа. Это не «чистая» императивная программа. В «чистых» императивных языках (ФОРТРАН) нет рекурсии Нет операторов присваивания «:= » -это возврат результата из функции, а не присваивание

Парадигма декларативного программирования, в которой Парадигма декларативного программирования, в которой программа представляет собой описание требуемого решения в терминах определенной логики решение задачи строится в процессе логического вывода по заданному описанию Различные разновидности логического программирования: индуктивное, в ограничениях, ... Подход к программированию Языки программирования Prolog, Datalog, Mercury, Oz, …

Найдем все комбинации <a,b,c> чисел от 1 до 10, что a2+b2=c2 Найдем все комбинации <a,b,c> чисел от 1 до 10, что a2+b2=c2

Функциональные языки Функциональные языки Компактный синтаксис для списков, n-ок (tuples), вариантных типов Логические языки Компактный синтаксис для списков, n-ок (tuples), вариантных типов Возможность перебора и поиска различных решений, заложенная в язык

studied(petya,mathematics). studied(vasya,german). studied(petya,mathematics). studied(vasya,german). studied(petya,compscience). studied(vasya,literature). studied(petya,english). studied_technical(X) :- studied(X,mathematics). studied_technical(X) :- studied(X,compscience). studied_languages(X) :- studied(X,english). studied_languages(X) :- studied(X,german). speciality(X,tech_translator) :- studied_languages(X),studied_technical(X). speciality(X,programmer) :- studied(X,mathematics),studied(X, compscience). speciality(X,lit_translator) :- studied_languages(X),studied(X,literature). ?-specialty(vasya,X). ?- specialty(X,lit_translator).

Определения на логическом языке похожи на предложения математической логики Определения на логическом языке похожи на предложения математической логики Логическое программирование имеет очень четкую математическую основу Возможны рассуждения о программах: доказательство корректности, … Отсутствует оператор присваивания Есть знак = , но он имеет другую семантику – унификация, связывание имен Переменные связываются неявно, в процессе логического вывода Будучи один раз связанным, имя может менять свое значение только в процессе пересмотра решения (возврата) А это значит – нет побочных эффектов!

C# - императивный (ОО) + элементы функциональности C# - императивный (ОО) + элементы функциональности F# - функциональный с элементами императивности Mercury – функционально-логический Oz Python …

Придется ли нам программировать на Прологе в реальной жизни? Придется ли нам программировать на Прологе в реальной жизни?

Задачи искусственного интеллекта Задачи искусственного интеллекта Экспертные системы Лингвистика, обработка естественного языка Задачи с неопределенностью Задачи, связанные с поиском решений Мета-программирование, построение специализированных языков

Отсутствие операторов присваивания и побочных эффектов Отсутствие операторов присваивания и побочных эффектов Декларативное программирование Естественная математическая модель вычислений Заложенная в язык возможность возвратов и перебора Заложенные в язык возможности по представлению списков, деревьев Развитые возможности мета-программирования и построения проблемно-ориентированных языков