Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Функциональное программирование
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299) 

1. Место дисциплины (модуля) в структуре ОПОП ВО - относится к вариативной части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля), предварительные условия:
Логически и содержательно данная дисциплина связана с базовыми курсами: «Алгоритмы и алгоритмические языки», «Системы программирования», «Дискретная математика».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, формируемые (полностью или частично) при реализации дисциплины (модуля):
«Функциональное программирование»
ОПК-1.Б. Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики.
ПК-3.Б. Способность в составе производственного коллектива участвовать в разработке и реализации в современных программных комплексах актуальных алгоритмов компьютерной математики.
ПК-4.Б. Способность применять в профессиональной деятельности современные средства разработки программного обеспечения и методы параллельной обработки данных, реализовывать отдельные этапы разработки системного и прикладного программного обеспечения, систем обработки и анализа данных, сетевых технологий.

Планируемые результаты обучения по дисциплине (модулю):  «Функциональное программирование»
Знать: 
1.	особенности функционального программирования, 
2.	основные понятия лямбда-исчисления, 
3.	синтаксис и семантику базовых средств языка Хаскель и средств функционального ядра языка Лисп;
Понимать: 
1.	принципы и ключевые абстракции функциональной парадигмы программирования;
Уметь: 
1.	программировать алгоритмы обработки базовых структур данных на базе средств функциональной парадигмы программирования; 
Владеть: 
1.	навыками составления функциональных программ на языках Лисп и Хаскель, 
2.	навыками анализа функциональных программ с целью повышения эффективности вычислений;
Иметь опыт: построения рекурсивных функциональных программ, а также программ на базе функционалов.

4. Формат обучения: лекции, семинары, письменные проверочные и контрольные работы, письменный экзамен.

5. Объем дисциплины (модуля) составляет 4 з.е., в том числе 72 академических часов, отведенных на контактную работу обучающихся с преподавателем (лекции, семинары), а также 72 академических часов на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий 
Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
Тема 1. Введение:  особенности функционального программирования. 
Основные парадигмы (модели) вычислений Функциональная парадигма и функциональные языки. Свойства функциональных языков: модульность, чистота (отсутствие побочных эффектов), прозрачность вычислений. Роль переменной в функциональном программировании. Достоинства и недостатки функциональной парадигмы.	4	2		2	2	
Тема 2. Основные понятия лямбда-исчисления.  Синтаксис функциональных выражений в лямбда-исчислении. Операции абстракции и аппликации. Связанные и свободные переменные выражения. Понятие абстрактного синтаксиса. Правила вывода (редукции) в чистом лямбда-исчислении. Нормальный и аппликативный порядок редукции, их связь с энергичным и ленивым вычислением в функциональных языках. Реализация рекурсивных функций в лямбда-исчислении.	12	4	4	8	4	

Тема 3. Функциональные средства языка Лисп. Основные структуры данных языка Лисп: атомы и списки. Синтаксис функциональных выражений. Обычные и особые функции. Встроенные функции базового набора, средства определения новых функций, анонимные функции. Представление атомов и списков в памяти компьютера, понятие S-выражения. Виды рекурсивной обработки списков. Понятие функционала (функции высшего порядка). Основные встроенные функционалы. Проблема функционального аргумента, способы ее решения. Замыкание функционального аргумента. Функционалы с функциональным значением. Лисп: динамическое связывание и типизация.	44	14	16	30	14 

Контрольная работа* № 1- 3 часа	
Тема 4. Доказательство свойств рекурсивных функций. Простая и обобщенная математическая индукция. Вполне- и обоснованно-упорядоченные множества. Способы введения порядка на множествах списочных выражений. Структурная индукция. Примеры доказательства правильности рекурсивных функций обработки списков.	10	4	2	6	4	
Тема 5.   Базовые средства языка Хаскель. Особенности языка Хаскель: встроенное каррирование функций, ленивые вычисления, полиморфизм, статическая типизация и автоматический вывод типов. Особенности синтаксиса выражений. Встроенные типы данных и операций: числовые, булевский, символьный, кортежи, списки. Охранные выражения. Конструкции LET и WHERE. Встроенные функционалы: отображения, фильтрация, левая и правая свертка. Анонимные функции. Полиморфные функции и типы. Классы типов. Синонимы типов. Конструкторы данных и конструкторы типов. Рекурсивные типы: списки, деревья. Списочные выражения, бесконечные списки.	40	12	14	26	14
Контрольная работа* № 2 - 3 часа	
Промежуточная аттестация:  Письменный экзамен 	34				34**	
Итого	144	36	36	72	72	
7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине
7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.
      Контрольные работы проводятся после завершения изучения тем 1-3 и 5 соответственно.
Контрольная работа  № 1: состоит из 5-6 задач на составление рекурсивных функций на языке Лисп, включая разные виды рекурсии. 
	Типовые задачи контрольной:
1.	Определить функцию-предикат Double, которая в заданном списке дублирует каждый второй элемент верхнего уровня, например: 
(Double '(K(9)(45 G)()(W))=> (K(9)(9)(45 G)NIL NIL(W))
2.	Написать функцию-предикат Subset с двумя аргументами – множествами, записанными как списки из неповторяющихся атомов. Предикат определяет, является ли первое множество-аргумент подмножеством второго множества. 
Например:  (Subset ‘(q r) ‘(p q s r))=> t .
3.	Определить функцию Subst0, заменяющую на всех уровнях заданного списочного выражения S все символьные (нечисловые) атомы, отличные от атома * , на число 0:   (Subst0 ‘((4 (Z(1))*)()Y))=> ‘((4 (0(1))*)()0)).
Контрольная работа  № 2: состоит из 5-6 задач на определение функций на языке Хаскель.		
	Типовые задачи контрольной:
1.	Объявить синоним типа для представления точки на плоскости и реализовать на языке Хаскель функцию, которая по четырем заданным точкам определяет, образуют ли они квадрат. Определить вспомогательные функции, если их использование улучшает наглядность решения.
2.	Используя функционалы, определить на Хаскеле функцию joinLetters, которая в заданном списке из кортежей-пар букв оставляет только пары с разными буквами, и преобразует эти пары в строки, вставляя между ними точку:	   
joinLetters [('A','S'),('S','S'),('N','V')] == ["A.S", "N.V"]
7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации..
 	Промежуточная аттестация проводится в виде экзамена. Экзамен по дисциплине "Функциональное программирование" проводится в письменной форме и включает 9-10 заданий: вопросов на понимание теоретического материала и задач на программирование функций на языке Лисп и Хаскель.
	Типовые задания письменного экзамена:
1.	Для следующих функций, записанных в синтаксисе Лиспа, определить значение F(7):   a) при статическом связывании;   б) при динамическом связывании. Ответ обосновать. 
(defun G (Farg z) (let ((x 2)) (Farg (+ z x)) ))	(defun F (x) (G '(lambda (y) (+ x y)) 5)
2.	Реализовать на языке Лисп и доказать правильность функции с двумя аргументами – множествами, представленными как одноуровневые списки из атомов, без повторений. Функция вычисляет разность этих множеств, т.е. формирует список-множество из элементов первого множества, не входящих во второе.  	
3.	На основе функционалов определить на языке Хаскель полиморфную функцию concatMap, применяющую заданную функцию к каждому элементу исходного списка, а затем  конкатенирующую полученные результаты (списки):
	concatMap (replicate 2) ['a', 'c', 'b'] == "aaccbb"

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Проверочные работы, экзамен	Отсутствие знаний	Фрагментарные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Контрольные работы, экзамен	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципиального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	

8. Ресурсное обеспечение:
	Литература и Web-источники
Литература
1.	Большакова Е.И., Груздева Н.В. Основы программирования на языке Лисп: Учебное пособие. – М.: МАКС Пресс, 2010.
	[PDF] (http://www.recyclebin.ru/BMK/LISP/lisp.html)
2.	Филд А., Харрисон П. Функциональное программирование: Пер. с англ. – М.: Мир, 1993.
3.	Душкин Р.В. Функциональное программирование на языке Haskell  – М.: ДМК Пресс, 2006.
4.	Хювенен Э., Сеппянен Й. Мир Лиспа, Т.1. – М.: Наука, 1990.
	Программное обеспечение и Интернет-ресурсы
На сайте кафедры алгоритмических языков факультета ВМК МГУ содержатся  учебно-методические материалы по языку Хаскель:
	http://al.cs.msu.ru/node/60 .
Учебные материалы по языкам Лисп  и  Хаскель есть также на сайтах
 	http://www.recyclebin.ru/BMK/LISP/lisp.html  и   http://cmc-msu-ai.github.io/haskell-course/  .
Для интерактивной проверки лисп-программ доступны браузеры:  https://www.jdoodle.com/execute-clisp-online    и    https://tio.run
Для проверки хаскель-программ доступны браузеры:  https://www.fpcomplete.com	    и	  http://tryhaskell.org/  .
Оперативная информация (методические указания, результаты контрольных и др.) рассылается студентам.
	Материально-техническое обеспечение дисциплины: Наличие литературы в библиотеке, общедоступные образовательные интернет-ресурсов по тематике дисциплины, маркерная или меловая доска.
9. Язык преподавания - русский.
10. Преподаватели:  Доцент, к.ф.-м.н.  Е.И. Большакова;  н.с., к.ф.-м.н. Н.В. Груздева 
11. Авторы программы:  Доцент, к.ф.-м.н.  Е.И. Большакова;  н.с., к.ф.-м.н. Н.В. Груздева