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

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

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

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

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

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

Оценка отлично выставляется тем, кто наберет 90% баллов (160) и более за выполнение домашних заданий, курсовой работы и тестирования. Оценка хорошо - тем, кто наберет 75% баллов (133). Оценка удовлетворительно (зачет) - тем, кто наберет 50% баллов (89). Большая часть баллов набирается слушателями в процессе прохождения приватного курса на платформе Stepik, разработанного специально для этого курса.

Литература

Основная:

• 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 (русский перевод)

• Simon Peyton Jones, The Implementation of Functional Programming Languages,Prentice Hall, 1987

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

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

• Sorensen M. H., Urzyczyn P. Lectures on the Curry-Howard Isomorphism. — Elsevier, 2006.

• 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

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

Видео

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