1. Что такое функциональный стиль программирования и в чем его отличие от традиционного.
2. Почему традиционные языки программирования не подходят для программирования в функциональном стиле.
3. Введение в язык Haskell: основные типы данных, определение функций.
4. Интерпретаторы языка Haskell: Hugs-системы.

• Эффективность рекурсивных функций. Концевая рекурсия и накапливающие аргументы.
• Списки в Haskell.
• Определение новых типов данных в Haskell.
• Функции высших порядков. Лямбда-выражения.

• Частичная параметризация функций. Карринг и сечения.
• Функциональное представление множеств.
• Ленивые вычисления и бесконечные списки.

• Завязывание узлов. Потоки.
• Пример: программирование регулярных выражений.
• Пример: функциональное представление графов.
• Классы в Haskell.

• Другие стили функционального программирования: ЛИСП.
• Другие стили функционального программирования: FP.
• Основы λ-исчисления. λ-выражения и редукции. Нормальная форма.
• Проблема конфликта имен и СЗНФ.

• Рекурсия в λ-исчислении. Y-комбинатор.
• Чистое λ-исчисление. Представление логических значений и функций, списков, арифметики целых чисел.
• Интерпретаторы функциональных программ. Представление функциональных программ на языке Haskell.

• Eval / Apply -интерпретатор.
• Эффективная и ленивая интерпретация.
• SECD-машина. Эффективная и ленивая версии.

• Представление последовательных процессов в функциональном программировании.
• Введение в редукцию графов. Основной алгоритм редукции.
• Использование вершин-синонимов при редукции графов.

• Введение в комбинаторную редукцию. Функция абстрагирования от переменных.
• Оптимизация Карри и аппликативные подвыражения.
• Комбинаторная редукция графов.
• Редукция рекурсивных выражений в графах.

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

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. Комбинаторная редукция графов.