Функциональное программирование
Санкт-Петербург, весна 2021
Описание
Курс знакомит слушателей с функциональными языками программирования и техниками написания программ на этих языках. Рассматриваются отличия функционального подхода к программированию от традиционного императивного, сравниваются их сильные и слабые стороны.
Курс разделен на теоретическую и практическую части. В теоретической части слушатели знакомятся с синтаксисом и семантикой лямбда-исчисления в бестиповом и просто типизированном вариантах. Обсуждается устройство систем типов функциональных языков и, в частности, алгоритм вывода типов Хиндли-Милнера.
Практическая часть курса ориентирована на изучении языка программирования Haskell. Студенты знакомятся с ленивой и энергичной версиями операционной семантики, алгебраическими типами данных и их использованием для реализации механизма сопоставления с образцом. При изучении системы типов языка Haskell будут обсуждаться параметрический и специальный полиморфизм и, в частности, механизм классов типов, в том числе многопараметрических.
Подробно рассматриваются основные классы типов из стандартной библиотеки Haskell, в том числе полугруппы и моноиды с одной стороны, и функторы, аппликативные функторы и монады с другой. Также обсуждаются различные стратегии свертки и обхода списков, деревьев и обобщение этих стратегий в классах типов Foldable и Traversable.
Слушатели приобретут навык программирования с использованием стандартных монад. В частности будут рассмотрены проблемы ввода-вывода в чистых языках и их решение с помощью монады IO, а также работа с изменяемым состоянием с помощью монады State и родственных ей монад. Изучение трансформеров монад познакомит студентов с решением проблемы композиции монадических эффектов.
Критерии и методы выставления оценок за курс
Оценка отлично
выставляется тем, кто наберет 90% баллов и более за выполнение домашних заданий, курсовой работы и тестирования. Оценка хорошо
- тем, кто наберет 75% баллов. Оценка удовлетворительно
(зачет
) - тем, кто наберет 50% баллов. Всего можно набрать 172 балла (30 за первые три задания и 142 на Stepik). Таким образом для оценки отлично
нужно набрать 154 балла, для оценки хорошо
- 129 баллов, для зачета - 86 баллов. Финальный дедлайн - 13.05.2021 в 20:00, в этот день я выставлю формальные оценки. Если кому-то будет не хватать небольшого числа баллов до следующего рубежа, то в рассмотрение пойдут задания, выполненные после дедлайна. Эту процедуру вы должны инициировать сами, связавшись со мной в слэке или по почте в течении следующих суток. В пятницу 14.05.2021 в 20:00 оценки станут итоговыми.
Литература
Основная:
Miran Lipovača, Learn You a Haskell for Great Good! A Beginner’s Guide 2011 (русский перевод: Миран Липовача, Изучай Haskell во имя добра! Издательство: ДМК Пресс, 2012)
Уилл Курт, Программируй на Haskell, М.:ДМК Пресс, 2019
Vitaly Bragilevsky, Haskell in Depth, Manning Publications, 2020
Дополнительная:
Х. Барендрегт, Ламбда-исчисление, его синтаксис и семантика, М.:Мир, 1985
Филд А., Харрисон П., Функциональное программирование, М.:Мир, 1993
John Harrison, Introduction to Functional Programming (русский перевод)
Bryan O’Sullivan, Don Stewart, and John Goerzen, Real World Haskell, O’Reilly Media, 2008
Simon Peyton Jones, The Implementation of Functional Programming Languages,Prentice Hall, 1987
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.
Видео
Видео всех лекций версии курса 2015 года можно смотреть на канале CS центра на YouTube.