Функциональное программирование

Общая информация
ЛекторЕ. Р. Кирпичёв
Семестросень 2010
Дата начала12.09.2010
Количество пар12
Язык курсарусский
Видеоhttp://lektorium.tv/course/?id=22779
Аннотация

Курс знакомит слушателей с функциональным подходом к программированию, все более набирающим силу в последнее время (наблюдается взрывной рост популярности языков Erlang, Scala, F#). Ключевые свойства этого подхода - борьба со сложностью программ через использование мощных механизмов абстракции и акцент на важность математических свойств программ. Курс в значительной мере основан на знаменитейшем курсе и книге "Структура и интерпретация компьютерных программ" из MIT, однако адаптирован под ряд особенностей современного программирования и профессиональную подготовку слушателей: обсуждаемые идеи иллюстрируются как в "чистом" виде, так и в контексте типичных повседневных задач. В курсе рассматриваются следующие наиболее важные идеи из мира функционального программирования: лямбда-исчисление, рекурсивные и итеративные процессы, функции высшего порядка и замыкания, абстрактные типы данных, свёртки (данная тема особенно важна в контексте параллельного и распределенного программирования), мини-языки, модель окружений, а также дается введение в системы типов.

Страница курса и лекции с прошлого года: http://spbhug.folding-maps.org/wiki/SICP_Course.

Рассылка курса: http://groups.google.com/group/csclub-fprog.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Основы лямбда-исчисления
(12.09.2010 - 11:15 - 12:50)

В лекции рассматриваются основы нетипизированного лямбда-исчисления, порядки редукций и теорема Чёрча-Россера, понятия "дна" и "строгости" функции, а также важность отсутствия побочных эффектов ("чистоты") для выполнения теоремы Чёрча-Россера.

Текст и домашнее задание: http://tinyurl.com/1-lambda-calculus

2. Язык Scheme. Рекурсия и хвостовые вызовы.
(12.09.2010 - 13:00 - 14:35)

В лекции дается введение в язык Scheme на примере нескольких простых программ, а затем рассматривается явление рекурсии, хвостовые вызовы и связанные с ними техники построения и преобразования программ. Также кратко рассматривается "вполне обоснованная рекурсия" как метод доказательства завершаемости программ.

Материалы:

  • http://tinyurl.com/2-scheme-recursion
  • Номер 3 журнала "Практика функционального программирования" http://fprog.ru/2009/issue3/, статья "Элементы функциональных языков", главы "Хвостовой вызов" и "Структурная и вполне обоснованная рекурсия".

3. Функции высшего порядка и замыкания
(19.09.2010 - 15:35 - 17:10)

В лекции рассматривается на примерах идея абстрагирования вычислительных процессов с помощью функций высшего порядка и польза этого подхода, а также обсуждаются трудности использования замыканий и функций высшего порядка в языках без сборки мусора.

Текст и домашнее задание: http://tinyurl.com/3-higher-order-functions, http://fprog.ru/2009/issue3/ - статья "Элементы функциональных языков", разделы "Функция высшего порядка" и "Замыкание".

4. Абстракция данных
(10.10.2010 - 15:35 - 17:10)

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

Вторая часть обсуждает несколько ситуаций, когда полезно или необходимо необычное представление данных, а также многогранность самого понятия "данных".

Текст лекции и домашнее задание: http://tinyurl.com/4-data-abstraction

5. Свертки
(24.10.2010 - 15:35 - 17:10)

В лекции вводится понятие "свертки" над структурой данных как абстракции вычисления "снизу вверх" (по индукции), а также рассматривается ее частный случай - списочные свертки.

Материалы:

Текст лекции и домашнее задание

Глава "Свертки" в статье "Элементы функциональных языков" в номере 3 журнала "Практика функционального программирования".

6. Моноиды, векторный параллелизм, MapReduce
(31.10.2010 - 15:35 - 17:10)

В этой лекции продолжается разговор о свертках и их применениях - рассматриваются ассоциативные и коммутативные свертки, связанное с ними понятие моноида и основанные на них алгоритмы и структуры данных - агрегирующие деревья, векторный параллелизм (алгоритмы на основе префиксных сумм), MapReduce и некоторые другие.

Материалы:

Текст лекции и домашнее задание

Книга "Vector models for data-parallel computing"

7. DSL: Упрощалка выражений
(05.12.2010 - 11:15 - 12:50)

В этой лекции на примере программы для упрощения выражений иллюстрируется ряд идей, связанных с "предметными языками" (DSL):

  • Формулировка логики программы в терминах предметной области, а не в терминах целевого языка
  • Отделение правил от механизма их интерпретации
  • Использование средств целевого языка для оперирования самими правилами (например, использование макросов)
  • Пример декомпозиции интерпретатора правил для системы переписывания термов ("окружения", унификация, подстановка, основной цикл)

Текст лекции.

8. Изменяемое состояние и модель окружений
(05.12.2010 - 13:00 - 14:35)

В этой лекции вводится понятие изменяемого состояния и тождества объектов, а также показывается, как при этом разрушается подстановочная модель вычислений и взамен нее дается другая - модель окружений. Также обсуждаются общие вопросы, связанные с использованием изменяемых объектов в программах.

Текст лекции.

9. Системы типов (начало)
(19.12.2010 - 15:35 - 17:10)

В лекции вводится понятие системы типов и даются начальные сведения о системе типов языка Haskell и об одном из самых важных ее элементов - обобщенных алгебраических типах (GADT).

Материалы: устаревший текст лекции, номер 3 журнала "Практика функционального программирования" - статья "Элементы функциональных языков", главы "Алгебраический тип", "Класс типов", "Вывод типов".

10. Экзамен
(26.12.2010 - 11:15 - 17:00)

Ваша оценка: Пусто Средняя: 4.3 (6 votes)
Share |
Евгений Кирпичёв
Зал не всегда вмещает всех желающих
Евгений Кирпичёв на лекции в клубе
Первое занятие клуба в осеннем семестре
Лекция Евгения Кирпичёва
Студенты на лекции Евгения Кирпичёва