Information
C# (личная):
Functional Programming
: Information
Created: 08.02.2010 | Level: specialist | Access: free
Курс знакомит слушателей с парадигмой функционального программирования, в которой решение задач сводится к описанию функций, перерабатывающих некоторые входные данные в выходные и строящихся из более простых функций на основе принципов функциональной абстракции и аппликации. Рассматриваются теоретические основы функционального программирования (лямбда-исчисление, комбинаторная логика, вопросы вычислимости), на примере функционального подхода дается представление о некоторых теоретических разделах компьютерных наук (семантика языков программирования, доказательство программ). С другой стороны курс содержит значительную практическую составляющую, основанную на промышленном языке программирования F# (входит в состав Microsoft Visual Studio 2010), рассматриваются вопросы использования функциональных языков для построения компиляторов, грамматического разбора и т.д.
Курс будет интересен как практикующим программистам и студентам, изучившим основы компьютерных наук, так и математикам. Для программистов на императивных языках знакомство с функциональным подходом позволит расширить сознание, перейти на более чистый (свободный от побочных эффектов) стиль программирования с более высоким уровнем абстракции, научиться эффективно использовать новые возможности современных императивных языков (LINQ, лямбда-выражения и т.д.). Для математиков, функциональное программирование может служить безболезненным введением в компьютерные науки, поскольку в рамках курса мы практически «с нуля» строим (начиная от математических основ, вплоть до реализации интерпретатора/компилятора и описания формальной семантики) язык программирования на базе лямбда-исчисления – раздела дискретной математики.
Goal: Познакомить слушателя с основами функционального программирования как дисциплины, находящейся на стыке программирования и дискретной математики; дать, с одной стороны, практические навыки функционального программирования на используемом на практике языке F#, а с другой – показать связь между теоретическими главами computer science и программированием, осветив некоторые теоретические проблемы информатики (вычислимость, семантика языков программирования, доказательство программ) и показав, как они решаются в функциональном подходе.
Prerequisites: Строго говоря, предварительных знаний для курса не требуется – возможно изучение программирования, начиная с функционального подхода. Однако более традиционным подходом является изучение основ программирования на базе императивного языка, и затем изучение функционального программирования как альтернативной парадигмы. Курс в большей степени ориентирован именно на такой подход.
План занятий
| Lesson | Title << | Date |
|---|---|---|
| - | ||
Lecture 1 | Определение и краткая история функционального программирования
Знакомство. Определение функционального программирования и его история.
| - |
Lecture 2 | Абстракция и декомпозиция. Декларативное программирование
Абстракция и декомпозиция при функциональном подходе. Декларативное программирование. Плюсы и минусы.
| - |
Lecture 3 | Парадигмы программирования
Зачем надо изучать функциональное программирование.
| - |
Lecture 4 | Функциональное программирование в реальной жизни
Построение множества Мандельброта. Функциональное программирование в реальной жизни. Пример визуализации на F#. Рекомендуемая литература. Информация о курсе.
| - |
Тест 112 minutes | - | |
Lecture 5 | Основные принципы функционального программирования
Введение в лямбда-исчисление. Редукция. Язык функционального программирования как лямбда-редуктор. Функции нескольких аргументов. Каррирование. Условное выражение. Определение имен. Области видимости.
Contents | - |
Lecture 6 | Сопоставление с образцом. Рекурсия. Циклы
Циклические конструкции. Виды рекурсии.
| - |
Lecture 7 | Пример: построение графика 2D-функции
Пример: построение графика 2D-функции и построение графика трехмерной функции
| - |
Тест 212 minutes | - | |
Lecture 8 | Рекурсивные структуры данных. Списки
Рекурсивные структуры данных. Основные операции работы со списками.
| - |
Lecture 9 | Примеры работы со списками
Примеры работы со списками. Перестановки. Вычисление простых чисел. Работа с изображениями. Синтаксис порождения списка list comprehension.
| - |
Lecture 10 | Хвостовая рекурсия. Порядковое представление списков и матриц
Хвостовая рекурсия. Порядковое представление списков и матриц.
| - |
Lecture 11 | Функциональные структуры данных
Функциональные структуры данных. Представление очереди. Многомерные массивы.
| - |
Тест 321 minute | - | |
Lecture 12 | Деревья
Деревья общего вида и двоичные деревья. Обход дерева. Реализация обхода с помощью функции с отложенным вычислением.
| - |
Lecture 13 | Деревья выражений и деревья поиска. Продолжения
Деревья поиска. Деревья выражений. Хвостовая рекурсия для деревьев. Продолжения (continuations).
| - |
Тест 412 minutes | - | |
Lecture 14 | Введение в л-исчисление
Основные модели вычислений. Синтаксис л-исчисления. Чистое и прикладное л-исчисление. Преобразования л-выражений. Редукция. Бетта-редукция и замена переменной.
| - |
Lecture 15 | Нормальный и аппликативный порядок редукции. Теорема Чёрча-Россера
Нормальный и аппликативный порядок редукции. Ленивые и энергичные вычисления. Механизмы вызова и проблема разделения. Теорема Чёрча-Россера и теорема стандартизации. Экстенсиональность. Слабая заголовочная нормальная форма.
| - |
Lecture 16 | Описание рекурсивных функций. Комбинаторы и комбинаторная логика
Описание рекурсивных функций. Оператор неподвижной точки. Комбинаторы и комбинаторная логика.
| - |
Тест 524 minutes | - | |
Lecture 17 | От л-исчисления к языку программирования
Представление условных выражений, списков и натуральных чисел в лямбда исчислении.Вычислимость.Эквивалентность алгоритмических моделей.
| - |
Lecture 18 | Замыкания, генераторы и отложенные вычисления
Переопределение имен. Замыкания. Генераторы - как способ работы с бесконечными последовательностями, отложенные вычисления.
| - |
Lecture 19 | Последовательности и ленивые вычисления в F#. Мемоизация
F# sequences. Примеры. Ленивые вычисления. Мемоизация.
| - |
Lecture 20 | Пример: реализация машины Тьюринга
Определение. Пример. Реализация на F#. Зиппер.
| - |
Тест 612 minutes | - | |
Lecture 21 | Типизация в языках функционального программирования
Классификация языков программирования по видам типизации. Типизированное лямбда исчисление. Вывод типов.
| - |
Lecture 22 | Формальная семантика языков функционального программирования
Классификация формальных семантик.Теория доменов. Теорема о неподвижной точке. Семантика для простейшего языка.
| - |
Lecture 23 | Доказательство свойств программ
Доказательство корректности программ на примерах. Проблема самопременимости.
| - |
Тест 718 minutes | - | |
Lecture 24 | Реализация функциональных языков. Eval-Apply-интерпретаторы
Реализация функциональных языков. Eval-Apply-интерпретаторы.
| - |
Lecture 25 | Реализация функциональных языков: интерпретаторы и абстрактные машины
Обработка рекурсии и ленивые вычисления в Eval-Apply модели. SECD-машина.
| - |
Lecture 26 | Реализация функциональных языков: редукция графов, потоковые реализации
Редукция графов. Эффект разделения. Пара слов о потоковых графах.
| - |
Lecture 27 | Анализ искусственных и естественных языков
Языки и грамматики. Лексический анализ. Синтаксический разбор. Специализированные утилиты.
| - |
Тест 89 minutes | - | |
Lecture 28 | Метапрограммирование: Quotations
Метапрограммирование. Quotations. Примеры. DLinq технология.
| - |
Lecture 29 | Императивное ядро в функциональных языках. Монады. Computational Workflows
Императивное ядро в функциональных языках. Монады. Примеры.
Contents | - |
Lecture 30 | Асинхронные и параллельные вычисления
Подходы к параллельным вычислениям. Asychrnous Workflows. Примеры.
| - |
Тест 912 minutes | - | |
5 hours | - |