Курс «Введение в функциональное программирование»

Читается в осенне-весеннем семестре 2011 года УНК «ИПСА» НТУУ «КПИ» в рамках факультативного цикла «Программная инженерия».

В последнее время функциональное программирование из предмета академических исследований превратилось в инструмент для эффективного решения промышленных задач. Задача курса — познакомить слушателей c основными идиомами функционального подхода и примерами их применения на практике. Будут рассмотрены верификация программ, абстракция данных и параллельное программирование в стиле MapReduce. Рабочие языки курса — F# и Haskell.

Программа основана на курсах «15-150: Functional Programming» Университета Карнеги—Меллон и «CS61A: Structure and Interpretation of Computer Programs» Университета Беркли.

Лекторы:

Второй семестр

Расписание

Дата Тема Лектор Аудитория
8.02 Лекция 4-1 В. Дёмкин 210-35
15.02 Лекция 4-2 А. Полозов 210-35
7.03 Лекция 4-3 А. Полозов 210-35
14.03 Лекция 4-4 А. Полозов 210-35
TBA Лекция 4-5 О. Смирнов 210-35

Конспект лекций

Модуль 4. Сочетание различных подходов
  1. Концепция изменяемого состояния. Проблемы, связанные с присваиванием и способы избавления от них в практической разработке — гостевая лекция Всеволода Дёмкина (Grammarly)
  2. Чисто функциональные структуры данных. Понятие перситентности. Семейство структур данных Zipper
  3. Понятие потока и его связь со списками. Ленивые вычисления. Язык программирования Haskell
  4. Продолжения. Основы Continuation Passing Style. Применения: реализация исключений и сопрограмм. Трансформация рекурсии в цикл
  5. Проблема побочных эффектов. Монада как абстракция последовательного вычисления. Примеры монад: List, Maybe, IO. F# computational workflows. Асинхронные вычисления
  6. Монады State и Parser. Пример использование библиотек Parsec/FParsec для реализации DSL; профессиональный синтаксический разбор
  7. Классы типов. Моноиды, монады, монады со сложением (MonadPlus), «сворачиваемые» данные (Foldable)
  8. Функторы и аппликативные функторы. Классы Applicative, Alternative, Traversable — гостевая лекция Романа Чепляка (Barclays Capital)
Модуль 5. Дополнительные темы
  1. Математические основы функционального программирования.
  2. Бестиповое лямбда-исчисление. Порядок редукций и теорема Черча-Россера. Теорема о неподвижной точке. Y-комбинатор. Применение: мемоизация
  3. Введение в теорию типов. Обзор систем типов и алгоритмов вывода типов, особенности типизированного лямбда-исчисления

Задачи

Первый семестр

Расписание

Дата Тема Лектор Аудитория
16.09 Лекции 1-1 и 1-2 О. Смирнов 02-13
23.09 Лекция 1-3 А. Полозов 02-13
30.09 Лекция 2-1 О. Смирнов 62-14
7.10 Лекция 2-2 А. Полозов 147A-16
14.10 Лекция 2-3 О. Смирнов 147A-16
21.10 Лаба №1: Практика ФП. А. Полозов 147A-16
28.10 Лекция 3-1 И. Веселов 147A-16
4.11 Лекция 3-2 А. Полозов 147А-16
11.11 Лекция 3-3 А. Полозов 147А-16
18.11 Лекция 3-4 О. Смирнов 147А-16
2.12 Лаба №2: Параллельное программирование О. Смирнов 147A-16
9.12 Консультация А. Полозов 147A-16
16.12 Экзамен О. Смирнов 147A-16

Конспект лекций

Модуль 1. Основы функционального программирования
  1. Обзор курса. Функциональный подход к программированию. Применения ФП: верификация, парсинг, параллелизация, «безошибочность»
  2. Вводная лекция. Язык программирования F#. Порядок применения функции
  3. Рекурсивные и итеративные процессы, их отличие и особенности. Вычисление с аккумулятором. Хвостовая рекурсия. Процесс декомпозиции задачи
Модуль 2. Практика функционального программирования
  1. Функция как объект манипулирования. Функции высших порядков. Абстракция вычисления. Часто используемые операторы над функциями. Каррирование и разрезы
  2. Замыкания. Проблемы реализации замыканий и их эмуляция в императивных языках. Работа со списками, списочные комбинаторы. Пример: LINQ
  3. Абстракция данных. Алгебраические типы данных. Сопоставление с образцом. Список как алгебраический тип данных. Деревья и операции над ними. Пример: примитивный синтаксический разбор
Модуль 3. Параллельное программирование
  1. Списочная свёртка и её применения. Свёртка деревьев. Обобщение свёртки на алгебраические типы данных и понятие катаморфизма — гостевая лекция Ивана Веселова (Barclays Capital)
  2. Моноиды. Сбалансированные деревья и дерево отрезков. Моноидальные вычисления в деревьях
  3. Сканирующие пробеги и их применения в параллельном программировании. Сегментированные пробеги. Примеры: алгоритмы параллельного программирования, использующие идиому пробега — выпуклая оболочка, максимальный поток в графе, численные методы
  4. Списочные гомоморфизмы. Третья теорема о гомоморфизмах. Пример: технология MapReduce и её открытая реализация Apache Hadoop. Применения MapReduce: индекс цитирования Web, байесовские классификаторы, пути в графе

Задачи

  1. Темы 1.1-1.3, 2.1-2.3
  2. Темы 3.1-3.4

Лабораторные работы

  1. Практика функционального программирования
  2. Параллельное программирование(шаблоны кода, данные )

Экзамен

  1. Билеты