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

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


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

Оглавление


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

Новости


• Весенний семестр 2017-го года закончен. Всё сдано в архив.

Аннотация


В рамках специального курса «Функциональное программирование на языке 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. Описание объектной системы моделью окружений.

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

Литература
1. Абельсон Х., Сассман Дж. и др. Структура и интерпретация компьютерных программ. М.: Добросвет. 2010. 608 с.
2. Харрисон Дж. Введение в функциональное программирование. Перевод с английского. Новосибирск. 2009. [pdf].
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, запрещено. Составленная в ходе выполнения упражнений программа должна быть показана лектору в ходе офлайновой сдачи. При переходе от начальных упражнений к последующим код следует дописывать так, чтобы функциональность программы расширялась (то, что было раньше, не портить).

Рекомендации, на которые следует обратить внимание для получения полного балла по «Доктору»:

  1. В упражнении 2 следует переписать many-replace, реализовав корректный алгоритм. Попытки заплатками лечить неверный алгоритм не рассматриваются.

  2. В упражнении 3 (стр. 5 методички) на самом деле имеется в виду, что при построении ответной реплики фраза пользователя, взятая из истории, подвергается тому же преобразованию, что и в упражнении 2, только вместо результата qualifier к фразе приписывается префикс "earlier you said that". Например, если из истории выбрана реплика (you are not being very helpful to me), то по ней будет построен ответ (earlier you said that i am not being very helpful to you).

  3. В упражнении 5 следует пополнить набор ключевых слов и ответов и использовать гибкую (со *) структуру данных. Построение реплик должно быть реализовано так, чтобы можно было вносить изменения только в структуру данных, не исправляя код функции, составляющей реплику. Реализуйте случайный выбор ключевого слова для построения реплики, если этих слов несколько во фразе пользователя. Предусмотрите учёт ситуации, когда одно и то же ключевое слово относится к разным группам.

  4. В упражнении 6 следует переписать reply, добавив ему параметр — список стратегий построения реплики, в этом списке для каждой стратегии есть предикат — функция, определяющая применима ли стратегия, тело — функция, строящая реплику, вес — число, помогающее выбрать одну стратегию из нескольких применимых. Функция reply проверяет предикаты всех стратегий, составляет список применимых стратегий, случайно с учётом веса выбирает одну стратегию из этого списка, запускает её тело. Все стратегии ответов, имеющиеся в программе должны быть представлены в списке. Каких-либо способов построения ответов вне списка стратегий быть не должно.

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

Второй путь совершенствования «Доктора» -- это учёт истории в стратегии ответов по ключевым словам. «Доктор» мог бы запоминать, какое ключевое слово было использовано и к какой группе ключевых слов относилась выбранная реплика (ведь одно слово может входить в несколько групп). В последующем «Доктор» мог бы, с одной стороны поддерживать тему, выбирая реплики-ответы из предыдущей группы, если есть такая возможность, с другой стороны, избегать повторов, заменяя * в заготовке реплики не на использованное ранее ключевое слово, а на родственные ключевые слова из одной группы с ним. Например, если предыдущий обмен репликами, касался матери пациента, «Доктор» мог бы поддержать тему семьи, но переключить разговор на других родственников пациента.

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

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


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

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


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

  

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

Обновлено: 14.8.2017