City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Functional programming
Novosibirsk / spring 2020, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

Мы рассмотрим отличия функционального подхода к программированию от традиционного императивного, познакомимся с лямбда-исчислением, как теоретической основой функционального программирования, изучим системы типов функциональных языков и алгоритм вывода типов Хиндли-Дамаса-Милнера.

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

Мы изучим основные классы типов из стандартной библиотеки Haskell, в том числе функторы, аппликативные функторы и монады. Мы обсудим различные стратегии свертки и обхода списков, деревьев и познакомимся с обобщением этих операций в классах типов Foldable и Traversable.

Мы научимся программировать, используя стандартные монады, в частности обсудим проблему ввода-вывода в чистых языках и его реализацию в Haskell с помощью монады IO, а также работу с изменяемым состоянием с помощью монады State и родственных ей монад.

Формат курса

Курс проводится в интенсивном формате и разделён на две неравные части. Первая часть (7 занятий по 4 академических часа в вечернее время) пройдёт с 31 января по 7 февраля, воскресенье выходной. Вторая часть курса (еще 6 занятий) запланирована на март.

Критерии выставления оценок за курс

Оценка отлично выставляется тем, кто наберет 90% баллов и более за выполнение домашних заданий, курсовой работы и тестирования. Оценка хорошо - тем, кто наберет 75% баллов. Оценка удовлетворительно (зачет) - тем, кто наберет 50% баллов.

Литература

Основная

  • Miran Lipovača, Learn You a Haskell for Great Good! A Beginner’s Guide, 2011 (русский перевод: Миран Липовача, Изучай Haskell во имя добра! Издательство: ДМК Пресс, 2012)

  • Vitaly Bragilevsky, Haskell in Depth, Manning Publications, 2020

Дополнительная

общетеоретические книги по ФП:

книги о языке Haskell:

  • Will Kurt, Get Programming with Haskell, Manning Publications, 2018, 616 pages (русский перевод: Уилл Курт, Программируй на Haskell, М.:ДМК Пресс, 2019)

  • Richard Bird, Thinking Functionally with Haskell, Cambridge University Press, 2014, 344 pages

  • Bryan O’Sullivan, Don Stewart, and John Goerzen, Real World Haskell O’Reilly Media, 2008

книги про типы:

  • Benjamin C. Pierce, Types and Programming Languages, MIT Press, 2002 (русский перевод: Бенджамин Пирс, Типы в языках программирования, Издательство: Лямбда пресс, Добросвет, 2012)

  • Henk Barendregt, Lambda calculi with types, Handbook of logic in computer science (vol. 2), Oxford University Press, 1993

  • Henk Barendregt, Wil Dekkers, Richard Statman, Lambda Calculus with Types, Cambridge University Press, 2013

прочие книги:

  • Саймон Марлоу. Параллельное и конкурентное программирование на языке Haskell. Издательство: ДМК Пресс, 2014

  • Simon Marlow and Simon Peyton-Jones. The Glasgow Haskell Compiler.

Хороший обзор самых новых англоязычных книг про Haskell сделал Виталий Николаевич Брагилевский. Общие итоги доступны здесь и далее по ссылкам на обзоры конкретных книг.

Видео

Видео всех лекций курса версии 2015 года можно смотреть на канале CS центра на YouTube.

Date and time Class|Name Venue|short Materials
31 January
18:10–19:45
Лямбда-исчисление, Lecture НГУ, ауд. 2128, НГУ, ауд. 2128 slides,  video
31 January
20:00–21:35
Чистое лямбда-исчисление как язык программирования, Seminar НГУ, ауд. 2128, НГУ, ауд. 2128 files
01 February
18:10–19:45
Рекурсия и редукция, Lecture НГУ, ауд. 2128, НГУ, ауд. 2128 slides,  video
01 February
20:00–21:35
Рекурсия и редукция, Seminar НГУ, ауд. 2128, НГУ, ауд. 2128 files
03 February
18:10–19:45
Просто типизированное лямбда-исчисление, Lecture НГУ, ауд. 2128, НГУ, ауд. 2128 slides,  video
03 February
20:00–21:35
Просто типизированное лямбда-исчисление, Seminar НГУ, ауд. 2128, НГУ, ауд. 2128 files
04 February
18:10–19:45
Введение в Haskell, Lecture НГУ, ауд. 2128, НГУ, ауд. 2128 slides,  video
04 February
20:00–21:35
Введение в Haskell, Seminar НГУ, ауд. 2128, НГУ, ауд. 2128 files
05 February
18:10–19:45
Типы данных, Lecture НГУ, ауд. 2128, НГУ, ауд. 2128 slides,  video
05 February
20:00–21:35
Стандартные списки, Seminar НГУ, ауд. 2128, НГУ, ауд. 2128 files
06 February
18:10–19:45
Классы типов, Lecture НГУ, ауд. 2128, НГУ, ауд. 2128 slides,  video
06 February
20:00–21:35
Реализация представителей стандартных классов типов, Seminar НГУ, ауд. 2128, НГУ, ауд. 2128 files
07 February
18:10–19:45
Свертки, Lecture НГУ, ауд. 2128, НГУ, ауд. 2128 slides,  video
07 February
20:00–21:35
Моноиды и свертки, Seminar НГУ, ауд. 2128, НГУ, ауд. 2128 files
25 March
18:10–19:45
Аппликативные функторы, Lecture Заочный просмотр slides,  videofiles
01 April
20:00–21:35
Аппликативные функторы, Seminar Онлайн, Онлайн
02 April
18:10–19:45
Использование аппликативных функторов, Lecture Заочный просмотр slides,  videofiles
02 April
20:00–21:35
Использование аппликативных функторов, Seminar Онлайн, Онлайн
09 April
18:10–19:45
Монады, Lecture Заочный просмотр slides,  videofiles
09 April
20:00–21:35
Монады, Seminar Онлайн, Онлайн
15 April
18:10–19:45
Использование монад, Lecture Заочный просмотр slides,  videofiles
15 April
20:00–21:35
Использование монад, Seminar Онлайн, Онлайн video,  files
22 April
18:10–19:45
Трансформеры монад, Lecture Заочный просмотр slides,  videofiles
22 April
20:00–21:35
Трансформеры монад, Seminar Онлайн, Онлайн video,  files
29 April
18:10–19:45
Вывод типов, Lecture Заочный просмотр slides,  video
29 April
20:00–21:35
Итоговое тестирование, Seminar Онлайн, Онлайн No