Functional Programming

2021/2022

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered at:

School of Data Analysis and Artificial Intelligence

Course type:

Elective course

When:

4 year, 1, 2 module

Instructors

Kuznetsov, Stepan

Рогозин Даниил Дмитриевич

Программа дисциплины

Аннотация

Настоящая дисциплина относится к профессиональному циклу, дисциплинам базовой части профиля. Для специализации «Распределенные системы» настоящая дисциплина является базовой. Изучение данной дисциплины базируется на знании курса “Сложность вычислений и логика в теоретической информатике”.

Цель освоения дисциплины

• Освоение теоретической базы функционального программирования (начала теории типов, лямбда-исчисление, начала теории категорий).
• Овладение техникой программирования на языке Haskell.

Планируемые результаты обучения

• Студент владеет общей информацией об императивном и функциональном стилях программирования, их сильных и слабых сторонах, умеет выбирать правильный стиль в зависимости от задачи.
• Студент знает теоретические основы функционального программирования (лямбда-исчисление, начала теории категорий и проч.).
• Студент разрабатывает новые библиотеки на языке Haskell.
• Студент решает задачи на программирование на языке Haskell.
• Студент создает код на функциональном языке, корректность которого формально доказана (верифицирована).

Содержание учебной дисциплины

• Типизованное лямбда-исчисление
• Нормализуемость и конфлюэнтность
• Императивное и функциональное программирование. Элементы функционального программирования в императивных языках
• Язык и среда разработки Haskell: установка и настройка
• Основы программирования на языке Haskell
• Типы данных в Haskell
• "Ленивые" и "ретивые" вычисления
• Монады и их использование для ввода-вывода
• Соответствие Карри - Говарда. Верификация программ и математических утверждений. Система Coq

Элементы контроля

• Домашние задания
  Программистские домашние задания (4-6 заданий в течение модуля). <br />Домашние задания могут раздаваться и приниматься по электронной почте, посредством системы Github или каким-либо иным удобным для преподавателя и студентов способом. В ходе текущего контроля (домашние задания) студент должен продемонстрировать владение техниками программирования, обсуждёнными к настоящему моменту.
• Контрольная работа
  Контрольная работа (60 мин) в середине курса.
• Экзамен
  Письменный экзамен (90 мин).<br />На итоговом экзамене студент должен показать владение теоретическими основами функционального программирования, посредством решения задач. Экзамен уже состоялся в 3 модуле.

Промежуточная аттестация

• 2021/2022 учебный год 2 модуль
  Итоговая оценка формируется следующим образом: <br />0,7*(накоп.) + 0,3*(экзамен), <br />где (экзамен) - оценка за итоговый экзамен, а (накоп.) - накопленная оценка за семестр, определяемая следующим образом: <br /> (накоп.) = 0,72*(прог.) + 0,28*(контр.), <br />где (прог.) - суммарная оценка за программистские домашние задания, (сам.) - оценка за контрольную работу.

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

Рекомендуемая основная литература

• Barendregt, H., Dekkers, W., Statman, R. Lambda calculus with types. – Cambridge University Press, 2013. – 856 pp.

Рекомендуемая дополнительная литература

• Lipovaca M. Learn you a Haskell for great good!: a beginner's guide. – No Starch Press, 2011. – 404 pp.