Темы (предварительные) к экзамену по ФП 2024-2025 для второго курса ПИ. Вопросы-автоматы на оценку F обозначены ☭.
Формат:
- Летучка на переписывание на листочке функции в CPS. (Проверка на минимальные навыки программирования.) Писать надо на OCaml, без ошибок, багов и со всеми скобками.
- Ответ принимающему. ☭ Привести (подготовить заранее) трассу вычисления факториала/фибоначчи для каждой из стратегий (CBN, CBV, NO, AO) для "голого" лямбда исчисления. (Функцию и стратегию выбирает экзаменатор.) Демонстрировать понимание того, как проходят редукции в указанной стратегии.
- Ответ принимающему. Демонстрация знания/понимания всего кода, за который вы получили допуск. (Чтобы проверить, что допуск писали Вы, а не напарник). Все конструкции и код, которые были нагуглены, должны быть осмыслены. В том числе, надо уметь отвечать, за что отвечают типовые параметры у типов данных, объявленных в вашем коде.
- Ответ принимающему. Вопросы из списка ниже без подготовки.
Список тем (не вопросов).
- Функции в программировании и функции в математике. Сходства и отличия. ☭ Понятия чистой функции, тотальной функции.
- ☭ Алгебраические типы данных. Что такое и в чем их алгебраичность? (Два объяснения)
- Boolean blindness
- Вывод zipperов для списков и деревьев.
- ☭ Хвостовая рекурсия. Уметь объяснять, чем хвостовая лучше обычной обычной рекурсии примерах.
- Переход к хвостовой рекурсии. (Переписать функцию, что дал экзаменатор)
- ☭ Понятие замыкания.
- Continuation passing style. Преобразование функций из стандартного (direct) стиля в CPS
- ☭ Быть готовыми переписать функцию в CPS (функция выбирается экзаменатором)
- Понятие дефункционализации. Пример
- Упражнение про: start, fin, push, add, mul
- Лямбда-исчисление
- Понятие исчисления. Аксиомы, правила вывода, посылки и заключения. Доказательства
- ☭ Определение языка лямбда-выражений. Три правила (α, β, η) преобразования лямбда-выражений.
- Лямбда исчисление как универсальный язык программирования. Числа Чёрча, арифметика, ветвления. Понятие каррирования.
- Упражнение: нарисовать AST.
- Редексы. Стратегии вычисления лямбда-термов: CBN, CBV, call-by-need, NO, AO. Достоинства и недостатки
- Упражнение: что будет если в составной стратегии NO везде писать no?
- Написание рекурсивных функций без использования рекурсии. Комбинаторы неподвижной точки для разных стратегий. Примеры
- Проблема останова
- Capture avoiding substitution. Индексы и уровни де Брёйна
- SKI
- ☭ Определение монады. Стандартные монады: Option, Result, List, Identity, Parser, Concurrency.
- Как в использовании отличаются монады и исключения?
- Задача про CPS
- Аппликативные функторы. Чем отличаются от монад, и когда их стоит предпочитать монадам?
- Модульная парадигма программирования. Модули и функторы OCaml. Структура и сигнатура.
- Понятие абстрактного типа данных
- Парсер-комбинаторы. Понятие AST.
- ☭ Пример: синтаксический анализатор языка a^n b^n c^n (где а,b,c --- символы алфавита, ^n -- n вхождений подряд). Плохой вход должен детектироваться максимально рано.
- Унификация и подстановки. Occurs check и его последствия. Связь понятия PFDS и подстановок.
- Уметь демонстрировать преимущества и недостатки включения/выключения occurs check.
- ☭ Уметь проунифицировать на примере экзаменатора.
- ☭ STLC. Понятие схемы типов. Правила вывода.
- Вывод типов в системе Хиндли-Милнера. Правила, которые отличают от STLC.
- Desugraing let в ULC.
- Let-полиморфизм
- “Well typed program can’t go wrong”. Контр-примеры к системе типов: ковариантные контейнеры, объекты на фазе создания.
- ☭ Понятие мемоизации
- Пример: эффективное вычисление факториала
- Ленивые списки (потоки)
- Пример: числа Фибоначчи
- Пример: решето Эратосфена
- SECD машина. Примеры. Интерпретатор большого шага и малого.
- PFDS. ☭ Понятие неизменяемых и устойчивых (persistent) типов данных.
- PFDS. Понятие префиксных деревьев и HAMT.
- PFDS. Чисто функциональные очереди. Три реализации и их асимптотики.
- История Mars Climate Orbiter. Понятия: zero-cost abstraction.
- Четыре вида полиморфизма (по Карделли). Полиморфные вариантны. Subtyping vs. inheritance.