Лекция 22: Формальная семантика языков функционального программирования, и 21 |
Академия Microsoft: Функциональное программирование: Информация
Автор: Дмитрий Сошников
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 25 студентам
Уровень:
Специалист
Длительность:
2:12:00
Студентов:
1870
Выпускников:
155
Качество курса:
4.17 | 4.42
Курс знакомит слушателей с парадигмой функционального программирования, в которой решение задач сводится к описанию функций, перерабатывающих некоторые входные данные в выходные и строящихся из более простых функций на основе принципов функциональной абстракции и аппликации. Рассматриваются теоретические основы функционального программирования (лямбда-исчисление, комбинаторная логика, вопросы вычислимости), на примере функционального подхода дается представление о некоторых теоретических разделах компьютерных наук (семантика языков программирования, доказательство программ). С другой стороны курс содержит значительную практическую составляющую, основанную на промышленном языке программирования F# (входит в состав Microsoft Visual Studio 2010), рассматриваются вопросы использования функциональных языков для построения компиляторов, грамматического разбора и т.д.
Курс будет интересен как практикующим программистам и студентам, изучившим основы компьютерных наук, так и математикам. Для программистов на императивных языках знакомство с функциональным подходом позволит расширить сознание, перейти на более чистый (свободный от побочных эффектов) стиль программирования с более высоким уровнем абстракции, научиться эффективно использовать новые возможности современных императивных языков (LINQ, лямбда-выражения и т.д.). Для математиков, функциональное программирование может служить безболезненным введением в компьютерные науки, поскольку в рамках курса мы практически «с нуля» строим (начиная от математических основ, вплоть до реализации интерпретатора/компилятора и описания формальной семантики) язык программирования на базе лямбда-исчисления – раздела дискретной математики.
Темы: Программирование
Специальности: Программист
Теги: 2d, анализ, вычисления, графика, история, логика, поиск, программирование, структуры данных, функциональное программирование
План занятий
Занятие
Заголовок <<
Дата изучения
Определение и краткая история функционального программирования
Знакомство. Определение функционального программирования и его история.
-
Абстракция и декомпозиция. Декларативное программирование
Абстракция и декомпозиция при функциональном подходе. Декларативное программирование. Плюсы и минусы.
-
Парадигмы программирования
Зачем надо изучать функциональное программирование.
-
Функциональное программирование в реальной жизни
Построение множества Мандельброта. Функциональное программирование в реальной жизни. Пример визуализации на F#. Рекомендуемая литература. Информация о курсе.
-
Основные принципы функционального программирования
Введение в лямбда-исчисление. Редукция. Язык функционального программирования как лямбда-редуктор. Функции нескольких аргументов. Каррирование. Условное выражение. Определение имен. Области видимости.
Оглавление
-
Сопоставление с образцом. Рекурсия. Циклы
Циклические конструкции. Виды рекурсии.
-
Пример: построение графика 2D-функции
Пример: построение графика 2D-функции и построение графика трехмерной функции
-
Рекурсивные структуры данных. Списки
Рекурсивные структуры данных. Основные операции работы со списками.
-
Примеры работы со списками
Примеры работы со списками. Перестановки. Вычисление простых чисел. Работа с изображениями. Синтаксис порождения списка list comprehension.
-
Хвостовая рекурсия. Порядковое представление списков и матриц
Хвостовая рекурсия. Порядковое представление списков и матриц.
-
Функциональные структуры данных
Функциональные структуры данных. Представление очереди. Многомерные массивы.
-
Деревья
Деревья общего вида и двоичные деревья. Обход дерева. Реализация обхода с помощью функции с отложенным вычислением.
-
Деревья выражений и деревья поиска. Продолжения
Деревья поиска. Деревья выражений. Хвостовая рекурсия для деревьев. Продолжения (continuations).
Оглавление
-
Введение в л-исчисление
Основные модели вычислений. Синтаксис л-исчисления. Чистое и прикладное л-исчисление. Преобразования л-выражений. Редукция. Бетта-редукция и замена переменной.
-
Нормальный и аппликативный порядок редукции. Теорема Чёрча-Россера
Нормальный и аппликативный порядок редукции. Ленивые и энергичные вычисления. Механизмы вызова и проблема разделения. Теорема Чёрча-Россера и теорема стандартизации. Экстенсиональность. Слабая заголовочная нормальная форма.
-
Описание рекурсивных функций. Комбинаторы и комбинаторная логика
Описание рекурсивных функций. Оператор неподвижной точки. Комбинаторы и комбинаторная логика.
-
От л-исчисления к языку программирования
Представление условных выражений, списков и натуральных чисел в лямбда исчислении.Вычислимость.Эквивалентность алгоритмических моделей.
-
Замыкания, генераторы и отложенные вычисления
Переопределение имен. Замыкания. Генераторы - как способ работы с бесконечными последовательностями, отложенные вычисления.
-
Последовательности и ленивые вычисления в F#. Мемоизация
F# sequences. Примеры. Ленивые вычисления. Мемоизация.
-
Пример: реализация машины Тьюринга
Определение. Пример. Реализация на F#. Зиппер.
-
Типизация в языках функционального программирования
Классификация языков программирования по видам типизации. Типизированное лямбда исчисление. Вывод типов.
-
Формальная семантика языков функционального программирования
Классификация формальных семантик.Теория доменов. Теорема о неподвижной точке. Семантика для простейшего языка.
-
Доказательство свойств программ
Доказательство корректности программ на примерах. Проблема самопременимости.
-
Реализация функциональных языков. Eval-Apply-интерпретаторы
Реализация функциональных языков. Eval-Apply-интерпретаторы.
-
Реализация функциональных языков: интерпретаторы и абстрактные машины
Обработка рекурсии и ленивые вычисления в Eval-Apply модели. SECD-машина.
-
Реализация функциональных языков: редукция графов, потоковые реализации
Редукция графов. Эффект разделения. Пара слов о потоковых графах.
-
Анализ искусственных и естественных языков
Языки и грамматики. Лексический анализ. Синтаксический разбор. Специализированные утилиты.
-
Метапрограммирование: Quotations
Метапрограммирование. Quotations. Примеры. DLinq технология.
-
Императивное ядро в функциональных языках. Монады. Computational Workflows
Императивное ядро в функциональных языках. Монады. Примеры.
Оглавление
-
Асинхронные и параллельные вычисления
Подходы к параллельным вычислениям. Asychrnous Workflows. Примеры.
-