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

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

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

©2009 Сошников Д.В. 4

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

©2009 Сошников Д.В. 6 Формальный язык

©2009 Сошников Д.В. 7 Assembler (x86, …) C, C++, C#, Java Pascal … Brainfuck? FORTH? LISP, FP, ML, Haskell, OCaml, F#, … Prolog, Mercury, Datalog, …

©2009 Сошников Д.В. 8

FORTRAN LISP С, Pascal С++ Java Prolog F# Python Mercury

©2009 Сошников Д.В. 10 Первый язык программирования высокого уровня – ФОРТРАН – был создан Дж.Бэкусом, чтобы математики могли программировать на уровне формул. программирование переключателей машинные коды язык ассемблера FORTRAN г., Дж.Бэкус A 12 1F 4B C3 E0 EE F C3 1D F2 00 0C 0D 0010 … MOVAX, [ARG1] ADDAX, [ARG2] MOV[RES], AX JMPNEXT ARG1:DB10 ARG2:DB20 RES:DB0 NEXT:… S = 0 DO 10 I=1,10 S = S + I*I 10CONTINUE

©2009 Сошников Д.В. 11 Позже Дж.Бэкус пошел дальше и предложил язык FP, в котором формулы более соответствовали математическому понятию функции программирование переключателей машинные коды язык ассемблера FORTRAN 1977 г., Дж.Бэкус def fac = eq 0 1; * [id,fac ( - [id,1])] (defun factorial (n) (if (<= n 1) 1 (* n (factorial (- n 1))))) FP LISP 1958 г., Дж.Маккарти

©2009 Сошников Д.В. 12 Надо пытаться формализовать человеческий язык! Основной инструмент формализации: Формальные аксиоматические системы Логика!

©2009 Сошников Д.В. 13 программирование переключателей машинные коды язык ассемблера FORTRAN FP LISP С, Pascal С++ Java C# Haskell Prolog Mercury F# OCaml ML Miranda Python ? ? Datalog Oz

©2009 Сошников Д.В. 14 Вычисление факториала: function fact(x:integer):integer; var i, r : integer; begin r:=1; for i:=1 to x do r:=r*i; fact:=r end; Императивное программирование (Pascal) let rec fact = function 1 -> 1 | x -> x*fact(x-1);; Функциональное программирование (F#) fact(1,1). fact(N,F) :- N1 is N-1, fact(N1,F1), F is F1*N. Логическое программирование (Prolog) fact(1)=1. fact(N)=N*fact(N-1). Логическое программирование (Mercury)

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

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

©2009 Сошников Д.В. 17 Это не «чистая» императивная программа. В «чистых» императивных языках (ФОРТРАН) нет рекурсии Нет операторов присваивания «:= » -это возврат результата из функции, а не присваивание function fact(x:integer):integer; begin if x=1 then fact:=1 else fact:=x*fact(x-1) end;

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

©2009 Сошников Д.В. 19 Найдем все комбинации чисел от 1 до 10, что a 2 +b 2 =c 2 for a:=1 to 10 do for b:=1 to 10 do for c:=1 to 10 do if a*a+b*b=c*c then write(a,b,c);; [ for a in for b in for c in when a*a+b*b=c*c -> (a,b,c) ];; solve(A,B,C) :- for(A,1,10), for(B,1,10), for(C,1,10), A*A+B*B =:= C*C. zip3 [1..10] [1..10] [1..10] |> filter ( fun (a,b,c)->a*a+b*b=c*c );;

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

©2009 Сошников Д.В. 21 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).

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

23

©2009 Сошников Д.В. 24 Императивное (алгоритмическое) Машина Тьюринга, Машина фон Неймана Pascal, C и т.д. Аппликативное (функциональное) λ-исчисление, рекурсивные функции F#, LISP / Scheme, ML и друзья, Haskell Декларативное (логическое) Логика предикатов 1-го порядка Prolog, Mercury, Oz, … Объектное, компонентное, многоагентное (эмерджентное) Синергетика, теория сложных систем Ситуационное (продукционное) Нормальные алгоритмы Маркова Рефал

©2009 Сошников Д.В. 25 Императивные языки Оперируют состоянием памяти. Выполнение операторов изменяет состояние. Функциональные языки Оперируют данными. Применение функции к аргументам изменяет данные. Подход, ориентированный на данные. Логические языки Оперируют пространством поиска решений. Программа задаёт множество возможных переходов в пространстве поиска

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

27

©2009 Сошников Д.В. 28 Придется ли нам программировать на Прологе в реальной жизни? В лучшем случае – 1 человеку из группы Пролог удобен при быстром прототипировании определенного класса систем Принципы, заложенные в основу логического программирования, помогут при решении реальных задач

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

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