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

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


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

Оглавление


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

Новости


• Во вторник 19 февраля в 16-20 в ауд. 624 запланирована первая лекция.

• Потенциальным слушателям следует связаться с лектором по email.

Аннотация


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

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


1. Вводные сведения о языке Scheme. Имена, связывания, окружения. Выражения и правила их вычисления. Внешнее представление значений. Функции и специальная форма define. Анонимные функции и специальная форма lambda. Специальные формы: cond, if, case, and, or, begin, let, quote. Базовые типы данных: числа, литеры, строки, списки, векторы. Блоки и блочная структура программы. Подстановочная модель вычислений. Аппликативный и нормальный порядки вычислений.

2. Рекурсивные и итеративные процессы. Функции и процессы, которые они порождают. Различия между процессами разных типов. Характеристики сложности процесса: количество шагов и размер памяти. Хвостовая рекурсия. Примеры реализации функций, порождающих рекурсивные и итеративные процессы.

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

8. Макросы syntax-rules в языке Scheme. Причины для использования макросов в функциональной программе. Характеристики системы syntax-rules: гигиеничность, прозрачность ссылок, закрытость. Язык образцов. Язык шаблонов. Спецсимволы в образцах. Специальные формы и макросы.

9. Объектно-ориентированное программирование в Scheme. Обобщённые операции. Объекты данных как альтернатива обобщённым операциям. Базовые понятия объектно-ориентированного программирования: класс, экземпляр класса, механизм передачи сообщений, наследование, множественное наследование, ассоциация. Три точки зрения на ООП: модель, использование, реализация. Диаграммы классов и диаграммы объектов. Объектная система в 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]


Практические задания


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

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

• Второе задание -- добавление в «Доктор» дополнительной стратегии ответов, в которой он предлагает пациенту сыграть с ним в игру (варианты). Максимальный балл -- 35. Второе задание индивидуально. Выбранные для реализации игры не должны совпадать у разных студентов. При решении второго задания можно использовать обычные библиотеки racket, мутируемые структуры, присваивание там, где это уместно. Использование этих средств должно быть обосновано. При оценке задания учитывается «сила» игры доктора, сложность выбранной игры, сложность реализации. Код второго задания должен содержать комментарии. В них следует указать, как представлена игровая ситуация, какой способ решения игры (поиска хода) реализован, каковы его параметры. Как отправную точку в написании кода можно рассматривать реализацию крестиков-ноликов на Racket (код, приспособленный под Racket, выложен в ВК-группу). По соседству лежит реализация игры Ним. Сдавать реализации этих двух игр нельзя.

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


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

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


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

  

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

Обновлено: 19.II.2019