По следам моего выступления на конференции “Современные технологии и IT-образование” в репозиторий учебных курсов Майкрософт выложены слайды по курсу “Функциональное программирование на языке F#”, который я прочитал в прошлом семестре на ФИВТ МФТИ. В курс на текущий момент входят следующие лекции:

1. Что такое функциональное программирование – дается определение и основные отличия функционального программирования от других парадигм, кратко обсуждается понятие парадигм программирования, применение функционального программирования в реальной жизни, перспективы использования функциональных языков в индустриальном программировании. Также в этой лекции приводится несколько увлекательных примеров на языке F#, в т.ч. построение множества Мандельброта.
2. Основы функционального программирования – рассматриваются основные понятия функционального программирования с примерами на F#: редукция, каррирование, функциональные типы, рекурсия. Приводится пример построения программы рисования графика функции в функциональном стиле.
3. Рекурсивные структуры данных – списки – рассматриваются основные операции над списками в функциональных языках на примере F#, обсуждается представление матриц и массивов.
   Скачать лекции 1-3
4. Рекурсивные структуры данных – деревья – обсуждаются вопросы представления двоичных деревьев и деревьев общего вида в функциональных языках на примере F#.
5. Аппликативная модель вычислений. Лямбда-исчисление и комбинаторная логика – рассматриваются теоретические основы функционального программирования: лямбда-исчисление и комбинаторная логика. Дается формулировка теоремы Чёрча-Россера и стандартизации (без доказательства), вводятся понятия нормального и аппликативного порядка редукции и комбинатора неподвижной точки.
   Скачать лекции 4-5
6. Лямбда-исчисление как язык программирования – рассматривается, как можно построить язык программирования на основе чистого лямбда-исчисления, введением чисел (нумералов), логических констант и условного оператора. Вводятся понятия ленивых и энергичных вычислений, мемоизации, замыканий, рассматриваются генераторы и последовательности. В заключении приводится пример реализации интерпретатора машины Тьюринга на F#.
7. Семантика языков функционального программирования и типизация – описывается построение систем типов для лямбда-исчисления. Вводится понятие семантики языка программирование и описывается денотационная семантика основных конструкций функционального языка. Приводятся примеры доказательства функциональных программ.
   Скачать лекции 6-7
8. Реализация языков функционального программирования – рассматриваются различные подходы к реализации функциональных языков: eval/apply-интерпретаторы, абстрактные машины (SECD, КАМ), редукция графов. Приводятся примеры реализации энергичного и ленивого eval/apply-интерпретатора на F# и реализация интерпретатора SECD-машины. Также кратко описываются подходы к лексическому и синтаксическому анализу с примерами синтаксического анализатора методом рекурсивного спуска и на базе fslex/fsyacc. После этой лекции должно придти понимание того, как можно реализовать свой собственный модельный функциональный язык (90% кода содержится в примерах).
9. Метапрограммирование и параллельное программирование – рассматриваются особенности языка F#, связанные с метопрограммированием: Quotations и Computational Expressions, даётся понятие монады и реализация монады недетерминированных вычислений через Computational Expressions с примерами её использования для решения логических задач с перебором. Рассматриваются параллельные и асинхронные вычисления на основе Asynchronous Workflows.
   Скачать лекции 8-9

В ближайшее время также планируется выход аналогичного видео-курса в рамках интернет-университета информационных технологий ИНТУИТ.РУ. Тем временем я буду признателен вам за возможные советы по улучшению курса, за замечания и обсуждения вопросов преподавания функционального программирования в целом. Пишите в комментарии к этой записи, на почту dmitryso(sobaka)microsoft(dot)com или в твиттер.