Главная страница « Информация « Спецкурсы «

Специальный курс «Структура и выполнение функциональных программ» (Structure and execution of functional programs)


Лектор: доц. кафедры СП, канд. физ.-мат. наук Малышко Виктор Васильевич
Продолжительность: 36 часов лекции.
Аудитория: для студентов бакалавриата (3-4 курс), не обучающихся на кафедре СП. Курс не может быть зачтён студентам, сдавшим или имеющим в учебном плане курс «Введение в функциональное программирование». Курс не предлагается студентам бакалавриата с кафедры СП, поскольку его материал все они осваивают в рамках обязательного курса «Введение в функциональное программирование».
Формы отчётности: экзамен/зачёт в зависимости от учебного плана слушателя.
Автор программы: канд. физ.-мат. наук Малышко В. В.
Программа составлена по материалам канд. физ.-мат. наук Чернова А. В.
Группа Вконтакте: [sp_scheme].
Telegram-чат: [Scheme @ВМК].
Гугль-таблица: [html].

Оглавление


Новости
Аннотация
Программа курса
Практические задания
Материалы по курсу

Новости


• Вторая лекция состоится не 23 февраля, а 22 февраля в 10:30 (дублирующей второй лекции в этот день не будет).

• Первая лекция состоится на 16 февраля в 14:30, а также в 18:00. Далее планируется читать по две лекции, совпадающие по материалу, еженедельно по вторникам. Потенциальным слушателям следует, не откладывая, присоединиться к ВК-группе и/или telegram-чату для получения сведений о подключении в Zoom.

Аннотация


В рамках специального курса «Функциональное программирование на языке Scheme» слушатели знакомятся с парадигмой функционального программирования на примере языка Scheme. Рассматриваются как базовые средства языка, относящиеся к «чистому» функциональному программированию, так и дополнительные его возможности: мутаторы, ленивые вычисления, потоки, макросы, средства объектно-ориентированного программирования. Также даётся короткий обзор математических основ функционального программирования. Для успешного прохождения курса слушателям необходимо будет написать две контрольные работы: промежуточную и итоговую. Для получения дополнительных баллов и высокой итоговой оценки слушателям предлагается набор факультативных упражнений по написанию программ на Scheme. Курс не может быть зачтён студентам, сдавшим или имеющим в учебном плане курс «Введение в функциональное программирование», поэтому он не предлагается студентам бакалавриата с кафедры СП.

Программа курса


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. Программирование с потоками. Ленивые вычисления, строгая/нестрогая функция по параметру. Санк, функции работы с санками: delay и force. Мемоизация санков. Реализация потоков как «ленивых списков». Функции работы с потоками: stream-cons, stream-first, stream-rest, stream, stream-empty?.

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. Пирс Б. Типы в языках программирования М.: Лямбда-Пресс, Добросвет. 2011. [pdf]
4. Чернов А. В. «Доктор». Задание практикума по функциональному программированию. М.: Издательский отдел ВМК МГУ. 2006. [pdf]
5. Brown J. H. Advanced Scheme: Some Naughty Bits. Scheme Macros. MIT. 2003.

Ссылки:
1. Сайт среды программирования DrRacket [html]


Факультативные упражнения


• По желанию, для зарабатывания дополнительных баллов предлагается выполнить факультативные упражнения. Весной 2021 года для программирования используется среда Dr. Racket [html].

• Общий набор упражнений по программированию на Scheme называется «Доктор». Обновлённая методичка по «Доктору» доступна онлайн: [html]. Старая методичка по «Доктору» доступна онлайн [pdf]. В обновлённой методичке материал старой существенно переработан. Следует использовать самую свежую версию методички, опубликованную здесь, а не в каких-либо сторонних ресурсах.

Материалы по курсу


• Ссылку на Moodle-версию курса с учебными материалами ищите в ВК-группе и/или в telegram-чате. Если Вы испытываете затруднения с доступом в группу или telegram, то запросите материалы по e-mail    у лектора. Все предоставленные материалы (в том числе задания анкет/контрольных/итоговых работ) должны быть использованы только лично Вами для учёбы во время изучения курса. Пожалуйста, не распространяйте их как-либо и где-либо.

Предупреждение


Размещение на других ресурсах, а также коммерческое использование материалов, опубликованных в данном разделе, возможно только с разрешения авторов. По всем вопросам пишите:   

  

© Кафедра системного программирования ВМК МГУ.

Обновлено: 16.II.2021