Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
С.А.Cавушкин
ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ
Учебное пособие по курсам
«Функциональное программирование» и «Функциональное и логическое программирование»
Москва – 2012
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ПУТЕЙ СООБЩЕНИЯ»
Кафедра «Математическое обеспечение
Автоматизированных систем управления»
С.А.Cавушкин
ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ
Рекомендовано редакционно-издательским советом
университета в качестве учебного пособия для студентов, обучающихся по направлению 230100 «Информатика и вычислительная техника», профиль «Программное обеспечение вычислительной техники и автоматизированных систем», а также по направлению 231000 «Программная инженерия»
Москва – 2012
УДК 004
С 12
Cавушкин С.А. Функциональное программирование. Учебное пособие для студентов, обучающихся по направлению 230100 «Информатика и вычислительная техника», профиль «Программное обеспечение вычислительной техники и автоматизированных систем», а также по направлению 231000 «Программная инженерия». - М.: МИИТ, 2012. - 141 с.
В учебном пособии излагаются сведения по теории функционального программирования, в частности элементы лямбда-исчисления и алгебры комбинаторов, которые лежат в основе функционального программирования, приведена модель Бэкуса. Описаны синтаксис и семантика, а также основные приемы и примеры программирования на языках LISP и HASKELL. Сформулированы варианты заданий и методические указания для выполнения лабораторных работ.
Учебное пособие предназначено для студентов, обучающихся по направлению 230100 «Информатика и вычислительная техника», профиль «Программное обеспечение вычислительной техники и автоматизированных систем», а также по направлению 231000 «Программная инженерия»
Рецензенты:
зав. кафедрой ВСС МИИТа к. т. н., доцент В. Н. Нагинаев;
профессор Российской международной академии туризма,
к.т.н В. Г. Шапошников
© МИИТ, 2012
СОДЕРЖАНИЕ
1. Парадигмы программирования.. 7
2. Лисп (LISP) – как язык функционального программирования 9
2.1. Атомы и списки. Функции. 10
2.2. Функции работы со списками. 13
2.3. Основные функции. 15
2.4. Функции ввода/вывода. 17
2.5. Другие функции. 20
2.6. Порядок вычислений в LISP'е. 22
2.7. Определение новых функций. 26
2.7.1. Безымянные вычисляемые функции. 26
2.7.2. Невычисляющие функции. 27
2.7.3. Поименованные функции. 29
2.7.4. Функции с нефиксированным числом аргументов. 36
2.7.5. Фунарг-проблема. Замыкание. 36
2.8. Функции высших порядков. Функционалы. 39
2.9. Макросы.. 48
3. Теоретические основы функционального программирования 51
3.1. Функции, функциональные выражения. 51
3.2. Рекурсивные определения функции. 52
3.3. Функции высших порядков, функционалы.. 55
3.4. Исчисление функциональных типов. 57
3.4.1. Параметрический тип и полиморфизм.. 58
3.5. Карринг. 59
3.6. λ-исчисления и алгебра комбинаторов. 61
3.6.1. λ–термы.. 61
3.6.2. Подстановки. 62
3.6.3. Конверсии. 62
3.6.4. Неподвижная точка. 63
3.6.5. Редукции. 63
3.6.6. Нормальная форма λ-термов. 66
3.6.7. Стратегии применения редукций. Аппликативный и нормальный порядок редукций 67
3.6.8. Алгебра комбинаторов. 68
3.7. Функциональный язык Бэкуса. 71
3.7.1. Состав системы FP. 72
3.7.2. Функции FP. 73
3.7.3. Функциональные формы.. 75
3.7.4. Определение пользовательских функций. 77
3.7.5. Семантика. 77
3.7.6. Примеры функциональных программ. 78
3.7.7. Элементы алгебры программ.. 79
4. HASKELL – язык функционального программирования.. 83
4.1. Типы.. 83
4.1.1. Основные типы.. 83
4.1.2. Арифметика. 84
4.1.3. Кортежи. 85
4.1.4. Списки. 86
4.1.5. Строки. 87
4.2. Определение функций. 88
4.2.1. Условные выражения. 90
4.2.2. Функции многих переменных и порядок определения функций. 91
4.2.3. Операция выбора и правила выравнивания. 91
4.2.4. Кусочное задание функций. 92
4.2.5. Сопоставление с образцом.. 92
4.2.6. let-связывание. 94
4.2.7. Охраняющие условия. 96
4.2.8. Полиморфизм.. 97
4.3. Пользовательские типы.. 97
4.3.1. Синонимы типов. 98
4.3.2. Пары.. 98
4.3.3. Множественные конструкторы.. 99
4.3.4. Классы типов. 101
4.4. Рекурсивные типы.. 102
4.4.1. Списки как рекурсивные типы.. 103
4.4.2. Синтаксические деревья. 104
4.5. Функции высшего порядка. 106
4.5.1. λ–абстракции. 109
4.6. Определение операторов. 110
4.6.1. Секции. 111
4.7. Модули. 111
4.8. Абстрактные типы данных. 112
4.9. Операции ввода-вывода. 114
4.9.1. Базовые операции ввода-вывода. 114
4.9.2. Стандартные операции ввода-вывода. 115
4.10. Создание исполняемых программ.. 117
4.11. Монады.. 117
4.11.1. Последовательные вычисления (монада IO) 117
4.11.2. Вычисления с обработкой отсутствующих значений (монада Maybe) 118
4.11.3. Вычисления с несколькими результатами (монада List) 119
4.11.4. Операции «>>=» и return. 121
4.11.5. Законы монад. 122
4.11.6. Стандартные монады.. 123
5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЛАБОРАТОРНОЙ РАБОТЫ ПО ЛОГИЧЕСКОМУ ПРОГРАММИРОВАНИЮ... 126
5.1. ЗАДАНИЕ N1. Работа со списками (на LISP’е и HASKELL’е) 126
5.1.1. Методические указания. 126
5.1.2. Варианты.. 127
5.2. ЗАДАНИЕ N2. Графы и деревья (на LISP’е и HASKELL’е) 130
5.2.1. Методические указания. 130
5.2.2. Варианты.. 130
5.3. ЗАДАНИЕ N3. Разные задачи (на LISP’е и HASKELL’е) 135
5.3.1. Методические указания. 135
5.3.2. Варианты.. 135
5.4. Упражнения. 137
5.5. Содержание отчета. 138
Парадигмы программирования
Парадигма (от греч. παράδειγμα, «пример, модель, образец») — осмысление мира на основе идей, взглядов и понятий. Современное значение этого термина в философии науки используется для обозначения исходной концептуальной схемы, модели постановки проблем и их решения, методов исследования.
Под парадигмой программирования будем понимать систему взгляд, подходов, позиций, определяющую стиль программирования на концептуальном уровне. Парадигма программирования представляет (и определяет) то, как программист видит процесс выполнения программы и, в конечном счете, саму программу.
В литературе формулируется большое число парадигм программирования. Мы выделим следующие:
Императивное программирование — процесс вычисления описывается в виде последовательности команд, изменяющих состояние вычислительной среды. Этот стиль программирования является традиционным и связывается с именем фон Неймана, который разработал основные архитектурно-функциональные принципы построения вычислительных машин (управления выполнением программы, хранимой в памяти программы, счетчик команд), которые легли в основу понятия фон-Неймановской архитектуры вычислительных устройств и фон-Неймановского стиля программирования.
Процедурное программирование — часто используется как синоним императивного программирования. При этом команды реализуются вызовами процедур.
Объектно-ориентированное программирование — программа – это набор взаимодействующих объектов. Каждый объект обладает набором свойств, а также набором методов - программ, которые связывают значения свойств данного объекта и других объектов друг с другом.
Функциональное программирование — программа представляется в виде композиции и суперпозиции функций. Программы не представляют собой последовательности инструкций и не имеют глобального состояния.
Логическое программирование — программа обычно определяет, что надо вычислить, а не то, как это надо делать. Выполнение программы основано на выводе новых утверждений из набора исходных утверждений, согласно заданным логическим правилам вывода.
Структурное программирование — в настоящее время общепринятая методология, в основе которой лежит представление программы в виде иерархии структур управления (последовательное исполнение операций, ветвление в зависимости от выполнения некоторого заданного условия, цикл, вызов подпрограмм). Разработка программы ведётся пошагово, методом «сверху вниз». Исторически возникло из традиционного императивного программирования путем ограничения применения «неструктурных» операторов, таких как оператор GOTO (безусловного перехода). Использование произвольных переходов в тексте программы приводило к получению запутанных, программ, по тексту которых практически невозможно понять порядок исполнения и взаимозависимость фрагментов.
Программа, управляемая данными — программа представляется в виде графа с вершинами двух видов – процедуры и данные. Данные могут быть входами и выходами процедур. Программа запускается посредством запроса вида «ДАНО-НАЙТИ».
Из выбранных парадигм нас интересуют императивное программирование и его разновидности, как представляющие традиционный стиль программирования, а также функциональное программирование, которое является темой данного пособия. Остальные парадигмы приведены в качестве примеров.
Дата: 2016-10-02, просмотров: 169.