1. Вводные сведения о языке Scheme. Имена, связывания, окружения. Выражения и правила их вычисления. Внешнее представление значений. Функции и специальная форма define. Анонимные функции и специальная форма lambda. Специальные формы: cond, if, case, and, or, begin, let, quote. Базовые типы данных: числа, литеры, строки, списки, векторы. Блоки и блочная структура программы. Подстановочная модель вычислений. Аппликативный и нормальный порядки вычислений.
2. Рекурсивные и итеративные процессы. Функции и процессы, которые они порождают. Различия между процессами разных типов. Характеристики сложности процесса: количество шагов и размер памяти. Хвостовая рекурсия. Примеры реализации функций, порождающих рекурсивные и итеративные процессы. Именнованный let как инструмент реализации итеративных процессов.
3. Функции первого порядка и функции высшего порядка, различия между ними. Типовые обобщённые схемы вычислений и функции высшего порядка, реализующие их (map, filter, foldl, foldr и проч.). Функции как возвращаемые значения.
4. Структуры данных в языке Scheme. Проектирование структур данных. Типовые операции структуры данных: конструкторы и селекторы. Построение слоистых систем с помощью структур данных. Точечные пары как база для реализации структур данных. Функции работы с точечными парами (cons, car, cdr и проч.). Стрелочные диаграммы. Тождественность и эквивалентность (eq?, eqv?, equal?). Двоичные деревья, деревья поиска, деревья-кучи.
5. Остаточные вычисления. Программирование в стиле передачи остаточных вычислений. Преобразование программы, порождающей рекурсивный процесс, в программу с явной передачей остаточных вычислений. Продолжения как нелокальные возвраты.
6. Присваивание в языке Scheme. Специальная форма set!. Преимущества и издержки присваивания. Мутируемые точечные пары и мутаторы (mcons, mcar, mcdr, set-mcar!, set-mcdr!). Модель вычислений с окружениями. Связывание, кадры, окружения. Правила вычислений в модели с окружениями. Стрелочные диаграммы окружений. Мемоизация. Реализация мутируемых динамических структур данных.
7. Макросы syntax-rules в языке Scheme. Причины для использования макросов в функциональной программе. Характеристики системы syntax-rules: гигиеничность, прозрачность ссылок, закрытость. Язык образцов. Язык шаблонов. Спецсимволы в образцах. Специальные формы и макросы.
8. Программирование с потоками. Функции работы с потоками: stream-cons, stream-first, stream-rest, stream, stream-empty?. Ленивые вычисления, строгая/нестрогая функция по параметру. Задержанные объекты и работа с ними: delay и force. Санки как средство реализации задержанных объектов. Мемоизация задержанных объектов. Поисковое поведение на базе оператора Маккарти.
9. Объектно-ориентированное программирование в Scheme. Обобщённые операции. Объекты данных как альтернатива обобщённым операциям. Базовые понятия объектно-ориентированного программирования: класс, экземпляр класса, механизм передачи сообщений, наследование, множественное наследование, ассоциация. Три точки зрения на ООП: модель, использование, реализация. UML-Диаграммы классов и UML-диаграммы объектов. Объектная система в Scheme и её элементы (функции create-instance, ask, get-method; схема реализации обработчика сообщений). Структура экземпляра класса, self. Описание объектной системы моделью окружений. Средства ООП в Racket.
10. Математические основы функционального программирования. Основные сведения о λ-исчислении. λ-Нотация. Классическое λ-исчисление. λ-Выражения. Свободные и связанные переменные. Подстановки. β-Редукция и α-редукция. Эквивалентность и λ-редукция. Нормальная форма. Стратегии редукции при поиске нормальной формы. Теорема Черча-Россера и её следствия. Комбинаторы: I, S, K, B, S, W, Y.
Литература
1. Абельсон Х., Сассман Дж. и др. Структура и интерпретация компьютерных программ. М.: Добросвет. 2006. [pdf]
2. Харрисон Дж. Введение в функциональное программирование. Перевод с английского. Новосибирск. 2009. [pdf]
3. Чернов А. В. «Доктор». Задание практикума по функциональному программированию. М.: Издательский отдел ВМК МГУ. 2006. [pdf]
4. Хансон К., Сассман Дж. Дж. Проектирование гибких программ. М.: ДМК-Пресс, 2022.
5. Brown J. H. Advanced Scheme: Some Naughty Bits. Scheme Macros. MIT. 2003.
6. Пирс Б. Типы в языках программирования М.: Лямбда-Пресс, Добросвет. 2011. [pdf]
Ссылки:
1. Сайт среды программирования Racket [html]
|