Письменный экзамен
Пятница, 18 мая 2012
ФМЛ 239, Актовый зал
Описание
ВОПРОСЫ К ЭКЗАМЕНУ
- Понятие о функциональном стиле программирования. Отличительные особенности этого стиля.
- Язык Haskell: типы, функции и задание определяющих уравнений для функций. Образцы и сопоставление с ними.
- Рекурсия и накапливающие параметры. Эффективность рекурсивных функций. Концевая рекурсия. Примеры.
- Язык Haskell: списки и операции над ними. Способы задания списков.
- Задание синонимов для типов данных. Определение новых типов данных, конструкторы. Параметризация типов данных.
- Сложные типы данных. Определение деревьев и функций их обработки. Сортировка с помощью двоичного дерева.
- Функции высших порядков. Отображение (map) и свертка (foldr) списков. Определение функций с помощью лямбда-выражений в Haskell.
- Свертка деревьев. Примеры программирования с помощью свертки сложных структур данных - деревьев и списков.
- Частичное применение функций. Карринг и сечение. Каррирование и декаррирование функций.
- Функциональное представление конечных и бесконечных множеств. Фильтрация списков.
- Понятие об энергичном и ленивом вычислениях. Конъюнкция и дизъюнкция
по МакКарти
. Бесконечные
структуры данных.
- Встроенные в язык операции над бесконечными списками. Программа вычисления списка простых чисел способом
решета Эратосфена
.
- Графическое представление бесконечных списков как потоков. Программирование с помощью
завязывания узлов
. Построение списка из чисел Фибоначчи.
- Определение анализатора для регулярных языков с помощью функций высших порядков.
- Определение классов и их реализации. Расширение классов. Стандартные классы Eq, Ord и Show.
- Основные черты и особенности языка ЛИСП.
- Комбинаторное программирование. Система программирования FP Дж.Бэкуса. Примеры программ.
- Лямбда-исчисление: базовые понятия и правила редукций. Нормальная форма и ее единственность.
- Различные порядки редукций в лямбда-исчислении. Проблема конфликта имен переменных. Слабая заголовочная нормальная форма.
- Прямая и косвенная рекурсия в лямбда-исчислении. Комбинатор неподвижной точки. Y-комбинатор Карри.
- Представление констант и основных функций в чистом лямбда-исчислении: логические функции и значения, списки.
- Чистое лямбда-исчисление: способы представления арифметических значений и функций.
- Интерпретаторы и компиляторы. Перевод конструкций языков функционального программирования в расширенное лямбда-исчисление.
- Представление программ расширенного лямбда-исчисления в виде объектов языка Haskell. Схема интерпретации в Eval / Apply интерпретаторе.
- Реализация Eval / Apply интерпретатора программ. Вопрос об энергичной и ленивой схемах интерпретации.
- Архитектура и представление SECD-машины. Интерпретация работы энергичной SECD-машины.
- Функциональные эквиваленты императивных программ: представление императивной программы в виде функции состояния.
- Представление выражений в виде графов. Редукция графов. Решение проблемы разделения переменных. Фиктивные ссылочные узлы.
- Комбинаторная редукция. Основные комбинаторы и функция абстрагирования от переменных.
- Комбинаторная редукция: оптимизации Карри.
- Комбинаторная редукция: сохранение аппликативных подвыражений.
- Комбинаторная редукция графов.