четверг, 4 февраля 2010, Александр Краковецкий

Любителям функционального программирования посвящается...

Дмитрий Сошников (Academic Developer Evangelist, shwars) выложены слайды по курсу “Функциональное программирование на языке F#”, который , были прочитаны на ФИВТ МФТИ.

В курс на текущий момент входят следующие лекции:

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

Скачать материалы:

• Скачать лекции 1-3
• Скачать лекции 4-5
• Скачать лекции 6-7
• Скачать лекции 8-9

P.S. Если у вас есть вопросы либо предложения к автору, пишите на почту dmitryso(sobaka)microsoft(dot)com.

---