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

Специальный курс «Структура и выполнение функциональных программ» (Structure and execution of functional programs)


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

Оглавление


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

Новости


• Первая лекция состоится в понедельник 5 марта в 18-00. Сбор возле 726 (у кафедры СП). Потенциальным слушателям следует связаться с лектором по email.

Аннотация


Специальный курс «Структура и выполнение функциональных программ» посвящён знакомству студентов бакалавриата с функциональным программированием на примере языка 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: гигиеничность, прозрачность ссылок, закрытость. Язык образцов системы syntax-rules. Язык шаблонов системы 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]. Новая методичка по «Доктору» отличается от старой (под номером 4 в списке литературы). • Второе задание -- добавление в «Доктор» дополнительной стратегии ответов, в которой он предлагает пациенту сыграть с ним в игру (варианты: 4 в ряд, калах, реверси, шашки, уголки и т. п.). Максимальный балл -- 30. Второе задание индивидуально. Выбранные для реализации игры не должны совпадать у разных студентов. При решении второго задания можно использовать обычные библиотеки racket, мутируемые структуры, присваивание там, где это уместно. Использование этих средств должно быть обосновано. При оценке задания учитывается «сила» игры доктора, сложность выбранной игры, сложность реализации. Код второго задания должен содержать комментарии. В них следует указать, как представлена игровая ситуация, какой способ решения игры (поиска хода) реализован, каковы его параметры. Как отправную точку в написании кода можно рассматривать реализацию крестиков-ноликов на Racket. По соседству лежит реализация игры Ним. Сдавать реализации этих двух игр нельзя.

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


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

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


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

  

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

Обновлено: 1.3.2018