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

Специальный курс «Функциональное программирование на языке Scheme» (Functional programming in Scheme)


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

Оглавление


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

Новости


• Лекции по курсу запланированы с 13 февраля по вторникам и пятницам на 5й (16-20) паре в аудитории 637. На обеих парах даётся один и тот же материал. Посещать можно ту пару, которая удобнее. Слушателям следует, не откладывая, присоединиться к telegram-чату курса.

Аннотация


В рамках специального курса «Функциональное программирование на языке 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. Программирование с потоками. Функции работы с потоками: 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]


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


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

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

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


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

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


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

  

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

Обновлено: 12.II.2024