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

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


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

Оглавление


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

Новости


• Начиная с 22 марта лекции проводятся по четвергам в 18-00. Сбор возле 727 (у кафедры СП).

• Первая лекция в понедельник 5 марта в 18-00. Сбор возле 727 (у кафедры СП). Потенциальным слушателям следует связаться с лектором по 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]


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


• Для успешной сдачи спецкурса предлагается выполнить практические задания. Весной 2018 года для программирования используется среда Dr. Racket [html].

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

Упражнения по «Доктору» делятся на 3 блока:
1-й блок -- упражнения с 1 по 3. Максимальный балл -- 5.
2-й блок -- упражнения 4 и 5. Максимальный балл -- 7.
3-й блок -- упражнение 6. Максимальный балл -- 8.
4-й блок -- дополнительный, по желанию. Максимальный балл -- 10.

Рекомендуется сдавать упражнения блоками. Датой сдачи блока считается дата последнего сданного упражнения из блока, при условии что код прислан вовремя. Во время сдачи программы будьте готовы ответить на вопросы по коду, а также по материалам лекций. Например, какой процесс порождает та или иная функция: итеративный или рекурсивный, и т. п.. Вам могут предложить оценить эффективность фрагмента Вашего кода и улучшить её, переписав фрагмент.

Для сдачи любого из блоков «Доктора» следует прислать код лектору. Программы 1-3 блоков следует составлять на версии языка scheme/base (начинайте свой код с директивы #lang scheme/base). В них использование мутаторов (присваиваний и т. п.), мутируемых структур данных Racket, запрещено. При переходе от начальных упражнений к последующим код следует дописывать так, чтобы функциональность программы расширялась (то, что было раньше, не портить). Не следует сдавать несколько разных версий программы, каждая из которых решает только одно из упражений.

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

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


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

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


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

  

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

Обновлено: 24.3.2018