Темы (окончательные) к экзамену по ФП 2023-2024
Вопросы-автоматы на оценку F обозначены ‡.
- Функции в программировании и функции в математике. Сходства и отличия. ‡ Понятие чистой функции
- ‡ Алгебраические типы данных. Что такое и в чем их алгебраичность?
- Boolean blindness
- ‡ Хвостовая рекурсия. Уметь объяснять, чем хвостовая лучше обычной обычной рекурсии примерах. CPS
- Переход к хвостовой рекурсии. (Переписать функцию, что дал экзаменатор)
- Continuation passing style. Преобразование функций из стандартного (direct) стиля в CPS
- ‡ Быть готовыми переписать функцию в CPS (функция выбирается экзаменатором)
- Лямбда-исчисление
- ‡ Привести (подготовить заранее) трассу вычисления факториала (или фибоначчи) для каждой из стратегий (CBN, CBV, NO, AO) для "голого" лямбда исчисления. (Функцию и стратегию выбирает экзаменатор.) Демонстрировать понимание того, как проходят редукции в указанной стратегии
- Понятие исчисления. Аксиомы, правила вывода, посылки и заключения. Доказательства
- ‡ Определение языка лямбда-выражений. Три правила (α, β, η) преобразования лямбда-выражений.
- Лямбда исчисление как универсальный язык программирования. Числа Чёрча, арифметика, ветвления
- Редексы. Стратегии вычисления лямбда-термов: CBN, CBV, CBNeeded, NO, AO. Достоинства и недостатки
- Написание рекурсивных функций без использования рекурсии. Комбинаторы неподвижной точки для разных стратегий. Примеры
- Проблема останова
- Capture avoiding substitution. Индексы и уровни де Брёйна
- SKI
- ‡ Определение монады. Стандартные монады: Maybe/Option, Result, List, Identity, Parser, Concurrency.
- Как в использовании отличаются монады и исключения?
- Аппликативные функторы. Чем отличаются от монад, и когда их стоит предпочитать монадам?
- Парсер-комбинаторы.
- ‡ Пример: синтаксический анализатор языка a^n b^n c^n (где а,b,c -- символы алфавита, ^n -- n вхождений подряд). Плохой вход должен детектироваться максимально рано.
- Унификация и подстановки. Occurs check.
- Уметь демонстрировать преимущества и недостатки включения/выключения occurs check.
- ‡ Уметь проунифицировать на примере экзаменатора.
- ‡ STLC. Понятие схемы типов.
- Вывод типов в системе Хиндли-Милнера. Правила, которые отличают от STLC.
- ‡ Понятие мемоизации
- Пример: эффективное вычисление чисел Фибоначчи
- Ленивые списки (потоки)
- Стандартные задачи: фибоначчи
- PFDS. ‡ Понятие неизменяемых и устойчивых (persistent) типов данных.
- PFDS. Чисто функциональные очереди. Три реализации и их асимптотики.
- PFDS. Понятие префиксных деревьев и HAMT.
- Схемы рекурсии. На примере списков и деревьев. Ката- и анаморфизмы.
- Схемы рекурсии. Хиломорфизм. Решения задач: фибоначчи, binary partition, LCS, merge sort.
- ‡ Идея реализации динамического программирования через схемы рекурсии