Темы лекций по дисциплине «Функциональное и логическое программирование»

Раздел пополняется по мере проведения лекций.

Лекция №1. Введение в функциональное программирование.

Понятие императивного и декларативного программирования.

Tim Sweeney (Epic Games) о недостатках современных языков программирования.

Сильные стороны функционального программирования.

Развитие многоядерных процессоров и языки функционального программирования.

Области и примеры применения функциональных языков.

Онлайн-системы (Viaweb: Robert Morris, Paul Graham).

Сильные стороны языка Haskell.

Выводы. Условия проведения и результаты IСFP Programming Contest.

Основные типы и конструкции языка Haskell.

Литература:

Н.Н. Непейвода. Стили и методы программирования. Л. 1, 8, 17.

Л.В. Городняя. Основы функционального программирования. Л. 1, 15.

С.В. Зыков. Введение в теорию программирования. Функциональный подход. Л. 1, 3.

Д. Хьюз. Сильные стороны функционального программирования.

С. Сильван. Сильные стороны языка Haskell.

В. Ахмечет. Функциональное программирование для всех.

И.А. Дехтяренко. Декларативное программирование.

Ф. Вадлер. Почему никто не использует функциональные языки.

H. Sutter. The Free Lunch Is Over.

T. Sweeney. The Next Mainstream Programming Language» (PPT).

P. Graham. Beating the Averages (внешняя ссылка).

P. Graham. What Languages Fix (внешняя ссылка).

P. Graham. The Hundred-Year Language (внешняя ссылка).

Локальная копия избранных статей П. Грэма (статья The Hundred-Year Language с переводом).

Лекция №2. Рекурсивные функции. Абстракции списков.

Определение функций с помощью шаблонов.

Определение функций с помощью сопоставления с образцом.

Образцы на списках.

Основные принципы использования рекурсии.

Пример: решение задачи о ханойских башнях.

Пример: тривиальное и оптимизированное рекурсивное представление степени.

Хвостовая рекурсия. Использование накапливающих параметров.

Рекурсивные функции на списках.

Примеры рекурсивных алгоритмов: сортировка вставками, быстрая обменная, слиянием.

Рекурсия по нескольким аргументам.

Пример: определение функции zip. Применение функции для нумерации списков.

Взаимная рекурсия.

Пример: функции получения элементов списка, стоящих на четных и нечетных местах.

Абстракции списков. Методы построения абстракций.

Пример: база данных библиотеки.

Литература:

G. Hutton. Programming in Haskell. Ch. 6.

Н. Роганова. Функциональное программирование. Гл. II-3, VI-2.

Лекция №3. Определение типов.

Пониятие типа данных. Множества значений и допустимых операций.

Полиморфизм и перегрузка типов функций.

Основные классы типов: Eq, Ord, Show, Read, Num, Integral, Fractional, Enum.

Определение синонимов типов с помощью декларации type.

Определение новых типов данных с помощью декларации data.

Наследование методов класса типов с помощью декларации deriving.

Определение новых методов класса типов с помощью декларации instance.

Определение параметризованных (полиморфных) типов.

Определение рекурсивных типов.

Пример: определение типов структуры данных типа «дерево» различной конфигурации.

Пример: таблица поиска с отображением на двоичное дерево. Операции поиска и вставки элемента.

Пример: определение типа и реализация функций работы с арифметическими выражениями.

Литература:

G. Hutton. Programming in Haskell. Ch. 3 — 5, 10.

Н. Роганова. Функциональное программирование. Гл. VII-2 - VII-4.

Л. Карделли. О понимании типов, абстракций данных и полиморфизма.

Текст примера арифметических выражений (win).

Лекция №4. Функции высшего порядка.

Понятите функции высшего порядка. Примеры типичных шаблонов программирования.

Функция map. Примеры использования.

Функция filter. Примеры использования.

Карринг, частичная параметризация и операторные секции.

Функции curry и uncurry. Пример использования.

Функция $. Примеры использования.

Функции takeWhile и dropWhile.

Функция zipWith. Пример: вычисление длины ломаной и периметра многоугольника.

Композиция функций. Примеры использования.

Литература:

Н. Роганова. Функциональное программирование. Гл. III-3, IV, VI-1.4

Описание библиотечных функций Prelude.hs. Краткий обзор синтаксиса, стандартных функций и сообщений об ошибках.

Лекция №5. Функции высшего порядка. Окончание.

Группа функций свертки fold*. Особенности и применение каждой функции. Примеры использования.

Универсальность функции foldr. Запись map, filter, length с помощью foldr.

Расширенный пример использования функций высшего порядка: шифр Цезаря.

Общий подход построения программ на функциональных языках «снизу вверх».

Пример: формирование чека для супермаркета по списку штрих-кодов товаров.

Литература:

Н. Роганова. Функциональное программирование. Гл. III-3, IV, VI-1.4

Текст примера шифра Цезаря (win).

Текст примера формирования чека для супермаркета (win).

Лекция №6. Средства ввода-вывода.

Принципиальные трудности реализации в функциональных программах ввода-вывода, параллельных процессов, хранения состояния, взаимодействия с программами на других языках.

Отличие функций и действий. Тип IO.

Внутренняя организция команды do. Операции >>= и >>.

Организация императивной последовательности выполнения команд с помощью do.

Действия (Actions) для консольного ввода-вывода и генерации случайных чисел.

Пример программы для угадывания чисел.

Организация ветвлений и циклов. Принципиальное отличие императивных циклов и циклов в языке Haskell.

Действия для файлового ввода-вывода.

Особенности ленивых вычислений при работе с файлами.

Обработка ошибок ввода-вывода.

Литература:

Н. Роганова. Функциональное программирование. Гл. VIII.

S. Thompson. The Craft of Functional Programming. Ch. 18.1-18.6.

H. Daume. Yet Another Haskell Tutorial. Ch. 3.8, 5.

Лекция №7. Монады.

Подход с передачей состояния как переменной World.

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

Использование монад для реализации хранения изменяемого состояния (IORef).

Использование unsafePerformIO для ввода-вывода из функционального ядра.

Синхронизация параллельных процессов (forkIO, MVar, организация каналов).

Обработка исключительных ситуаций. Синхронные и асинхронные исключения.

Взаимодействие с программами на других языках. Импорт и экспорт функций. Маршаллинг.

Управление памятью. Указатели и внешние объекты.

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

Литература:

S.P. Jones. Tackling the Awkward Squad.

S. Thompson. The Craft of Functional Programming. Ch. 18.7-18.9.

H. Daume. Yet Another Haskell Tutorial. Ch. 9.

Ф. Уодлер. Монады в функциональном программировании.

Д. Ньюберн. Всё о монадах.

Лекция №8. Примеры использования языка Haskell. Распознавание и трансляция выражений.

Понятие и определение типа функции-парсера.

Три основных парсера: return, failure, item.

Организация последовательного и выборочного применения парсеров.

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

Парсеры для лексем.

Построение упрощенной грамматики арифметических выражений.

Реализация парсера упрощенной грамматики арифметических выражений.

Литература:

G. Hutton. Programming in Haskell. Ch. 8.

S. Thompson. The Craft of Functional Programming. Ch. 17.5.

Текст примера распознавания и трансляции арифметических выражений (win).

Лекция №9. Примеры использования языка Haskell. Работа с арифметическими выражениями. Средства тестирования.

Постановка олимпиадной задачи генерации арифметических выражений с заданным ответом.

Функции генерации подмножеств, перестановок, сочетаний, размещений и разбиений.

Решение задачи методом полного перебора.

Способы повышения эффективности решения.

Сравнение алгоритмической и низкоуровневой оптимизации.

Понятие автоматизированного тестирования.

Обзор возможностей средства автоматизированного тестирования QuickCheck.

Создание свойств для автоматизированной проверки.

Ограничение множества генерируемых входных данных.

Литература:

G. Hutton. Programming in Haskell. Ch. 11.

Текст примера генерации арифметических выражений (win).

K. Claessen, J. Hughes. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs.

K. Claessen, J. Hughes. Testing Monadic Code with QuickCheck.

Лекция №10. Введение в логическое программирование. Основы языка Пролог.

Понятие и основные особенности логического программирования.

История возникновения и развития Пролога. Проект ЭВМ пятого поколения.

Области использования Пролога. Перспектива применения в качестве языка запросов к базам данных.

Основные понятия Пролога. Предложения, цели, факты и правила.

Факты. Хранение данных в программах на примере квеста.

Механизм поиска и достижения цели в программе на языке Пролог.

Запросы. Понятие унификации и работа механизма вывода пролог-машины.

Внутренняя структура подцели в механизме логического вывода. Понятие и назначение CALL, EXIT, REDO, FAIL.

Работа механизма логического вывода. Обработка правил в подцелях. Предикаты специального вида: I/O, fail.

Правила. Передача управления внутри подцелей.

Особенности использования арифметических операторов.

Литература:

П. Шрайнер. Основы программирования на языке Пролог. Л. 1, 3.

У. Клоксин, К. Меллиш. Программирование на языке Пролог. Гл. 1, 2.

И. Братко. Программирование на языке Пролог для искусственного интеллекта. Гл. 1.

D. Merritt. Adventures in Prolog. Ch. 1 — 3.

Лекция №11-12. Обзор основных возможностей языка Пролог. Управление исполнением программ. Списки.

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

Предикаты специального вида: repeat, !.

Предикат отсечения и особенности логического вывода.

Особенности использования арифметических операторов.

Представление предикатов в виде операторов.

Рекурсия. Практические аспекты применения рекурсии и оптимизация выполнения.

Рекурсия. Влияние порядка правил и предикатов на эффективность работы программы.

Пример: вычисление факториала. Различные варианты с оптимизацией.

Пример: вычисление числа Фибоначчи. Различные варианты с оптимизацией.

Использование динамических баз данных для повышения эффективности выполнения программ.

Пример: эффективное вычисление последовательности Фибоначчи.

Списки. Особенности работы со списками.

Неоднозначное использование предикатов и особенности механизма вывода на примере проверки вхождения элемента в список и конкатенации.

Пример: множество возможных способов использования append.

Литература:

П. Шрайнер. Основы программирования на языке Пролог. Л. 4, 6.

D. Merritt. Adventures in Prolog. Ch. 14.

У. Клоксин, К. Меллиш. Программирование на языке Пролог. Гл. 9.

Лекция №13. Представление и обработка деревьев в языке Пролог. Обработка грамматики, разностные списки.

Представление бинарных деревьев и двоичных справочников в языке Пролог.

Примеры базовых процедур работы с бинарными деревьями.

Разбор структуры естественного языка средствами языка Пролог. Запись правил грамматики.

Разностные списки. Пример реализации интерфейса пользователя на естественном языке.

Литература:

П. Шрайнер. Основы программирования на языке Пролог. Л. 10.

D. Merritt. Adventures in Prolog. Ch. 15.

У. Клоксин, К. Меллиш. Программирование на языке Пролог. Гл. 9.

Лекция №14-15. Применение функционального и логического программирования. Искусственный интеллект.

Понятие и основные области исследования искусственного интеллекта.

Основные вехи исторического развития искусственного интеллекта.

Понятие теста Тьюринга.

Логические игры. Игры для двух лиц с полной информацией. Методы обхода пространства состояний.

Минимаксный принцип в логических играх.

Алгоритм альфа-бета отсечения для эффективной реализации минимаксного принципа.

Методы улучшения эффективности альфа-бета алгоритма: эвристическое отсечение, последовательное углубление просмотра дерева игры, просмотр до спокойных позиций, экспертная система особых ситуаций (эндшпилей).

Понятие, виды, структура и функциональность экспертных систем.

Принципы реализации экспертных систем средствами языка Пролог.

Реализация ответов на вопросы «как» и «почему».

Литература:

Википедия. Поиск по словам Artificial Intelligence, History of Artificial Intelligence (внешняя ссылка).

Association for the Advancement of Artificial Intelligence (внешняя ссылка).

И. Братко. Программирование на языке Пролог для искусственного интеллекта. Гл. 14, 15.