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

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


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

Оглавление


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

Новости


• Семестр закончен. Всё сдано в архив.

Аннотация


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

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


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

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

3. Функции высшего порядка. Функции в роли аргументов других функций. Функции как обобщённые схемы вычислений (map, filter, foldl, foldr). Функции как возвращаемые значения.

4. Структуры данных. Проектирование структур данных. Типовые операции структуры данных: конструкторы и селекторы. Построение слоистых систем с помощью структур данных. Точечные пары как основа реализации структур данных. Функции работы с точечными парами (cons, car, cdr). Стрелочные диаграммы. Деревья и бинарные деревья поиска в Scheme.

5. Остаточные вычисления. Программирование в стиле передачи остаточных вычислений.

6. Присваивание. Модель вычислений с окружениями. Внутренние переменные состояния. Специальная форма set!. Преимущества и издержки присваивания. Мутаторы и точечные пары (set-car!, set-cdr!). Связывание, кадры, окружения. Правила вычисления в модели с окружениями. Стрелочные диаграммы окружений. Тождественность и эквивалентность (eq?, equal?). Реализация в Scheme стека, таблиц. Мемоизация. Векторы в Scheme. Реализация xеш-таблиц.

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

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

9. Объектно-ориентированное программирование в Scheme. Обобщённые операции. Объекты данных как альтернатива обобщённым операциям. Базовые понятия объектно-ориентированного программирования: класс, экземпляр класса, механизм передачи сообщений, наследование, множественное наследование, ассоциация. Три точки зрения на ООП: модель, использование, реализация. Диаграммы классов и диаграммы объектов. Объектная система в Scheme и её элементы (функции create-instance, ask, get-method; схема реализации обработчика сообщений). Структура экземпляра класса, self. Описание объектной системы моделью окружений.

10. Математические основы функционального программирования. Основные сведения о λ-исчислении. λ-Нотация. Классическое λ-исчисление. λ-Выражения. Свободные и связанные переменные. Подстановки. β-Редукция и α-редукция. Эквивалентность и λ-редукция. Нормальная форма. Стратегии редукции при поиске нормальной формы. Теорема Черча-Россера и её следствия. Комбинаторы I, S, K, B, S, W, Y.

Литература
1. Абельсон Х., Сассман Дж. и др. Структура и интерпретация компьютерных программ. М.: Добросвет. 2010. 608 с.
2. Харрисон Дж. Введение в функциональное программирование. Перевод с английского. Новосибирск. 2009.
3. Чернов А. В. «Доктор». Задание практикума по функциональному программированию. М.: Издательский отдел ВМК МГУ. 2006. [pdf].
4. Brown J. H. Advanced Scheme: Some Naughty Bits. Scheme Macros. MIT. 2003.

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


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


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

• Первое задание общее для всех -- «Доктор». Методичка по «Доктору» доступна онлайн [pdf].

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

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

4й дополнительный блок можно сдать тем, кто желает заработать добавочные баллы. Блок посвящён дальнейшему "совершенствованию" "Доктора". Одним из путей совершенствования является добавление, так называемого, метауровня. Выполняя блок 3, мы реализовали один из способов выбора стратегии построения ответов. Этот способ заключался в том, что среди всех применимых стратегий с учётом их весов случайно применяется одна. Обозначим этот способ выбора как управляющую стратегию №1. Мы могли бы использовать другой способ выбора (другую управляющую стратегию). Например, можно упорядочить стратегии по весу, проверять сначала применимость более "тяжёлых" и, как только какая-то стратегия применима, останавливать проверку и использовать её (управляющая cond-стратегия с весами). Другие управляющие стратегии могли бы учитывать "историю" (предыдущие использования стратегий построения ответов), сложность выполняемых проверок. На "метауровне" "Доктор" перед тем как выбирать стратегию построения ответа, анализирует, какие управляющие стратегии применимы в текущий момент. Из применимых управляющих стратегий "Доктор" выбирает одну (случайно, с учётом веса). Выбрав, он запускает её для выбора стратегии построения ответа. Второй путь совершенствования "Доктора" -- это учёт "истории" в стратегии ответов по ключевым словам. "Доктор" мог бы запоминать, какое ключевое слово было использовано и к какой группе ключевых слов относилась выбранная реплика (ведь одно слово может входить в несколько групп). В последующем "Доктор" мог бы, с одной стороны "поддерживать тему", выбирая реплики-ответы из предыдущей группы, если есть такая возможность, с другой стороны, "избегать повторов", заменяя * в заготовке реплики не на использованное ранее ключевое слово, а на родственные ключевые слова из одной группы с ним. Например, если предыдущий обмен репликами, касался матери пациента, "Доктор" мог бы "поддержать" тему семьи, но переключить разговор на других родственников пациента.

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

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

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


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

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


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

  

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

Обновлено: 19.5.2017