ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Направление – Программная инженерия, 7 семестр Ст. преподаватель каф. ВТ НГТУ Юлия Вадимовна Новицкая Web: ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Направление – Информатика и ВТ, 7 семестр

ПРЕДМЕТ ИЗУЧЕНИЯ ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ язык программирования Lisp (LISt Processing) ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ язык программирования Prolog (PROgramming in LOGic)

ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (ФЛП) Лекции – 34 часа (17 лекций) Лабораторные работы (ЛР) – 17 часов (4 лаб. работы) Расчетно-графическое задание (РГЗ) (получение задания на 2-й лаб. работе) Экзамен

ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ (ФП) Лекции – 34 часа (17 лекций) Лабораторные работы (ЛР) – 17 часов (4 лаб. работы) Расчетно-графическое задание (РГЗ) (получение задания на 2-й лаб. работе) Диф. зачет

ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (ЛП) Лекции – 17 часов (8 лекций) Лабораторные работы (ЛР) – 17 часов (4 лаб. работы) Расчетно-графическое задание (РГЗ) (получение задания на 2-й лаб. работе) Диф. зачет

БАЛЛЬНО-РЕЙТИНГОВАЯ СИСТЕМА ФЛП Дисциплина в целом – 100 баллов – 60 баллов в семестре – 40 баллов на экзамене Лабораторные работы с 1 по 4 – 6 12 баллов Расчетно-графическое задание – 6 12 баллов Срок защиты ЛР без потери баллов – одна неделя после лабораторной работы по расписанию Срок защиты РГЗ без потери баллов – ФЛП – 17 неделя

БАЛЛЬНО-РЕЙТИНГОВАЯ СИСТЕМА ФП и ЛП Дисциплина в целом – 100 баллов – 80 баллов в семестре – 20 баллов на зачете Лабораторные работы с 1 по 4 – 8 16 баллов Расчетно-графическое задание – 8 16 баллов Срок защиты ЛР без потери баллов – одна неделя после лабораторной работы по расписанию Срок защиты РГЗ без потери баллов – ФП – 16 неделя, ЛП – 16 неделя

ОТЧЕТНОСТЬ Отчеты по лабораторным работам представляются в электронном виде одним файлом в конце семестра Отчет по расчетно-графическому заданию представляется в распечатанном виде в конце семестра

УЧЕБНЫЕ МАТЕРИАЛЫ

ИСТОЧНИКИ (ОСНОВНЫЕ) Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. - СПб.: БХВ-Петербург, С. Братко И. Алгоритмы искусственного интеллекта на языке Prolog. – М. : Вильямс, – 637 с. Городняя Л.В. Основы функционального программирования. – М. : ИНТУИТ.РУ, – 272 с. Ин Ц., Соломон Д. Использование Турбо-Пролога. - М.: Мир, С. Непейвода Н.Н. Стили и методы программирования. – М.: Интернет- университет информационных технологий, – 316 с.

ИСТОЧНИКИ (ОСНОВНЫЕ) Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. - М.: Мир, С. Хювёнен Э., Сеппянен Й. Мир Лиспа. М.: Мир, С. Цуканова Н.И., Дмитриева Т.А. Логическое программирование на языке Visual Prolog. - М.: Горячая Линия - Телеком, С. Чанышев О.Г. ПРОграммирование в ЛОГике. – Омск : Изд-во ОмГУ, – 63 с. Шрайнер П.А. Основы программирования на языке Пролог. Курс лекций. - М.: Интернет-университет информационных технологий, С.

ИСТОЧНИКИ (ДОПОЛНИТЕЛЬНЫЕ) Доорс Дж., Рейблейн А.Р., Вадера С. Пролог язык программирования будущего. - М.: ФиС, С. Клоксин У., Меллиш Д. Программирование на языке Пролог. - М.: Мир, С. Маурер У. Введение в программирование на языке ЛИСП. - М.: Мир, С. Полещук Н., Лоскутов П. AutoLISP и Visual LISP в среде AutoCAD. - СПб.: БХВ-Петербург, С. Стобо Дж. Язык программирования Пролог. - М.: Мир, С. Хендерсон П. Функциональное программирование: применение и реализация. М.: Мир, С. Янсон А. Турбо-Пролог в сжатом изложении. - М.: Мир, С.

ИНТЕРНЕТ-РЕСУРСЫ Программирование на языке ПРОЛОГ [Электронный ресурс]. – Электрон. дан. – USAM SRL, cop – Режим доступа : Русскоязычное сообщество липскеров [Электронный ресурс]. – Электрон. дан. – Lisp.ru, cop – Режим доступа : Lisper.ru [Электронный ресурс]. – Электрон. дан. – lisper.ru, cop – Режим доступа : Home Lisp [Электронный ресурс]. – Электрон. дан. – Режим доступа : XLISP Home Page [Electronic resource]. – Electronic data. – Mode acess : Amzi! inc. [Electronic resource]. – Electronic data. – Mode acess :

ИНТЕРНЕТ-РЕСУРСЫ Association of Lisp Users [Electronic resource]. – Electronic data. – Mode acess : LispWorks [Electronic resource]. – Electronic data. – LispWorks Ltd., cop – Mode acess : Prolog Development Center [Electronic resource]. – Electronic data. – Copenhagen, cop – Mode acess : SWI-Prolog [Electronic resource]. – Electronic data. – Mode acess : Visual Prolog [Electronic resource]. – Electronic data. – Mode acess :

ПАРАДИГМА Парадигма – это система взглядов на явления окружающего мира и представлений о возможных взаимодействиях с ними Парадигма программирования – система идей и понятий, определяющих фундаментальный стиль программирования

ПАРАДИГМЫ ПРОГРАММИРОВАНИЯ декларативная – логическая – функциональная императивная объектно-ориентированная параллельная процедурная …

ПАРАДИГМЫ ПРОГРАММИРОВАНИЯ Некоторый язык программирования не обязательно использует только одну парадигму, многие языки поддерживают несколько парадигм Ни одна парадигма не может быть одинаково эффективной для всех задач, и программисту следует выбирать лучший стиль программирования для решения каждой отдельной задачи

КЛАССИФИКАЦИЯ Языки программирования Алгоритмические (процедурные) языки (C, С++, Pascal, Basic, …) Декларативные (неалгоритмические) языки Языки логического программирования (Prolog, …) Языки функционального программирования (Lisp, Haskell, Erlang…)

ОТЛИЧИЯ Алгоритмический (процедурный) способ программирования соответствует вопросу «как» (необходимо описать, как решается задача), декларативный способ – вопросу «что» (достаточно описать, что должно быть решено) Программа на декларативном языке состоит из двух компонент: условия задачи (которую иногда называют «базой данных») и целевого запроса Для декларативного программирования необходимо наличие «решателя» (называемого обычно интерпретатором), который «знает» как выполнить целевой запрос, исходя из условий, представленных в «базе данных»

ОБЛАСТИ ПРИМЕНЕНИЯ ДЕКЛАРАТИВНЫХ ЯЗЫКОВ Реализация обработки типов данных, имеющих рекурсивную природу: списков, деревьев, графов и сводящихся к ним структур Такого рода задачи характерны для обработки символьной информации, то есть для создания трансляторов и решения задач искусственного интеллекта: обработки естественного языка, трансформации и автоматического синтеза программ, аналитического преобразования формальных текстов и др. Создание систем искусственного интеллекта Разработка экспертных систем и оболочек экспертных систем Создание систем помощи принятия решений Разработка систем обработки естественного языка Построение планов действий роботов …

Современное состояние ЛП Visual Prolog 7.5 Разработкой языка занимается фирма PDC Prolog Development Center

Современное состояние ФП

ЯЗЫК ЛП PROLOG Особенности языка – Описание проблемы и правил ее решения – Нахождение всех возможных решений с помощью механизма поиска с возвратом (backtracking) – Простой синтаксис

ПЕРВАЯ ПРОГРАММА Факты – Воробей – это птица. Воробей – родитель птенца. Правило вывода – Некто является птицей при условии, что у него есть родитель – птица. Программа – птица(воробей). – птица(X):– родитель(Y, X), птица (Y). – родитель(воробей, птенец). Запрос – птица(Z) Все возможные решения: – Z = воробей – Z = птенец

ПЕРВАЯ ПРОГРАММА bird(sparrow). bird(X):– parent(Y, X), bird(Y). parent(sparrow, nestling). ? – bird(Z) Z = sparrow Z = nestling Факт Правило вывода Запрос

ОСНОВНЫЕ СПОСОБЫ РЕШЕНИЯ Поиск с возвратом (backtracking) Рекурсия Вход

ПОИСК С ВОЗВРАТОМ Для работы поиска с возвратом необходимо выполнение двух условий – Недоказательство некоторой цели – Возврат (откат) к цели, которую можно передоказать

РЕКУРСИЯ Нахождение значения факториала 0! = 1 n! = 1 * 2 * 3 * … * (n – 1) * n Рекурсивная формула для расчета факториала 0! = 1 n! = (n – 1)! * n

РЕКУРСИЯ factorial (0, 1). factorial (N, RES) :- M = N – 1, factorial (M, TMP), RES = TMP * N. ? – factorial (3, RES) RES = 6

ЯЗЫК ФП LISP Особенности языка – Одинаковая форма представления данных и программ – в виде списка – Функциональный образ мышления – Не требуется явное описание типов данных, используемых в программе – Основной способ решения – рекурсия

ПЕРВАЯ ПРОГРАММА > (+ 2 3) программа данные > (+ 2 3) 5 > (+ 2 3) (+ 2 3) > (quote (+ 2 3)) (+ 2 3)

ОСНОВЫ LISPА