Письменный экзамен

ВОПРОСЫ К ЭКЗАМЕНУ

1. Понятие о функциональном стиле программирования. Отличительные особенности этого стиля.
2. Язык Haskell: типы, функции и задание определяющих уравнений для функций. Образцы и сопоставление с ними.
3. Рекурсия и накапливающие параметры. Эффективность рекурсивных функций. Концевая рекурсия. Примеры.
4. Язык Haskell: списки и операции над ними. Способы задания списков.
5. Задание синонимов для типов данных. Определение новых типов данных, конструкторы. Параметризация типов данных.
6. Сложные типы данных. Определение деревьев и функций их обработки. Сортировка с помощью двоичного дерева.
7. Функции высших порядков. Отображение (map) и свертка (foldr) списков. Определение функций с помощью лямбда-выражений в Haskell.
8. Свертка деревьев. Примеры программирования с помощью свертки сложных структур данных - деревьев и списков.
9. Частичное применение функций. Карринг и сечение. Каррирование и декаррирование функций.
10. Функциональное представление конечных и бесконечных множеств. Фильтрация списков.
11. Понятие об энергичном и ленивом вычислениях. Конъюнкция и дизъюнкция по МакКарти. Бесконечные структуры данных.
12. Встроенные в язык операции над бесконечными списками. Программа вычисления списка простых чисел способом решета Эратосфена.
13. Графическое представление бесконечных списков как потоков. Программирование с помощью завязывания узлов. Построение списка из чисел Фибоначчи.
14. Определение анализатора для регулярных языков с помощью функций высших порядков.
15. Определение классов и их реализации. Расширение классов. Стандартные классы Eq, Ord и Show.
16. Основные черты и особенности языка ЛИСП.
17. Комбинаторное программирование. Система программирования FP Дж.Бэкуса. Примеры программ.
18. Лямбда-исчисление: базовые понятия и правила редукций. Нормальная форма и ее единственность.
19. Различные порядки редукций в лямбда-исчислении. Проблема конфликта имен переменных. Слабая заголовочная нормальная форма.
20. Прямая и косвенная рекурсия в лямбда-исчислении. Комбинатор неподвижной точки. Y-комбинатор Карри.
21. Представление констант и основных функций в чистом лямбда-исчислении: логические функции и значения, списки.
22. Чистое лямбда-исчисление: способы представления арифметических значений и функций.
23. Интерпретаторы и компиляторы. Перевод конструкций языков функционального программирования в расширенное лямбда-исчисление.
24. Представление программ расширенного лямбда-исчисления в виде объектов языка Haskell. Схема интерпретации в Eval / Apply интерпретаторе.
25. Реализация Eval / Apply интерпретатора программ. Вопрос об энергичной и ленивой схемах интерпретации.
26. Архитектура и представление SECD-машины. Интерпретация работы энергичной SECD-машины.
27. Функциональные эквиваленты императивных программ: представление императивной программы в виде функции состояния.
28. Представление выражений в виде графов. Редукция графов. Решение проблемы разделения переменных. Фиктивные ссылочные узлы.
29. Комбинаторная редукция. Основные комбинаторы и функция абстрагирования от переменных.
30. Комбинаторная редукция: оптимизации Карри.
31. Комбинаторная редукция: сохранение аппликативных подвыражений.
32. Комбинаторная редукция графов.