7344
.pdfМинистерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
«Нижегородский государственный архитектурно-строительный университет»
Н.Ю. Прокопенко
ЛОГИЧЕСКОЕ И ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ
Учебно-методическое пособие
по подготовке к лекционным и практическим занятиям (включая рекомендации по организации самостоятельной работы)
для обучающихся по дисциплине «Логическое и функциональное программирование»
по направлению подготовки 09.03.04 Программная инженерия профиль Разработка программно-информационных систем
Нижний Новгород
2018
УДК 004.9
Прокопенко Н.Ю. Логическое и функциональное программирование [Электронный ресурс]: учеб. - метод. пос. / Прокопенко Н.Ю.; Нижегор. гос. архитектур.
-строит. ун - т – Н. Новгород: ННГАСУ, 2018. – 60 с;
Вданном учебно-методическом пособии по дисциплине «Логическое и функциональное программирование» даются конкретные рекомендации учащимся для освоения как основного, так и дополнительного материала дисциплины и тем самым способствующие достижению целей, обозначенных в учебной программе дисциплины. Цель учебно-методического пособия — это помощь в усвоении лекций и подготовке к практическим занятиям.
Учебно-методическое пособие предназначено для обучающихся в ННГАСУ по дисциплине «Логическое и функциональное программирование» по направлению подготовки 09.03.04 Программная инженерия. Учебно-методическое пособие ориентировано на обучение в соответствии с календарным учебным графиком и учебным планом по основной профессиональной образовательной программе направления 09.03.04 Программная инженерия, утверждённым решением учёного совета ННГАСУ от 02.03.2018 г. (протокол № 3).
© Н.Ю., Прокопенко, 2018 © ННГАСУ, 2018
2
Оглавление
1. Общие положения…………………………………………………..……..4
1.1Цели изучения дисциплины и результаты обучения ……………..…..4
1.2Содержание дисциплины…………………………………………..……4
1.3Порядок освоения материала…………………….………………..…….5 2.Методические указания по подготовке к лекциям………...………….....6
2.1Общие рекомендации по работе на лекциях………….……………..…6
2.2Общие рекомендации при работе с конспектом лекций…….……...…6
2.3Общие рекомендации по изучению материала лекций………..............7
2.4Контрольные вопросы…………………………….…………………….21
3. Методические указания по подготовке к практическим занятиям…...24
3.1 Общие рекомендации по подготовке к практическим занятиям…….24
3.2 Примеры задач для практических занятий…………………..………..25
4. Методические указания по организации самостоятельной работы…..48
4.1Общие рекомендации для самостоятельной работы…………............48
4.2Темы для самостоятельного изучения………………...........................51
4.3Учебно-методическое обеспечение самостоятельной работы………52
4.4Задания для самостоятельной работы………………………...............52
3
1. Общие положения
1.1 Цели изучения дисциплины и результаты обучения
Целями освоения учебной дисциплины «Логическое и функциональное про-
граммирование» являются формирование и закрепление системного подхода при разработке программ с применением языков логического и функционального про-
граммирования.
В процессе освоения дисциплины студент должен
Знать: проблематику дисциплины «Функциональное и логическое программи-
рование» и ее основные разделы; базовые понятия и определения, используемые в логическом и функциональном программировании; основы технологии программи-
рования в программных средствах, используемых в современных декларативных языках.
Уметь: обосновать выбор методов обработки данных для решения поставлен-
ной задачи; разрабатывать и тестировать программы с применением программных средств, используемых в современных декларативных языках.
Владеть: методами построения программ на основе языков логического и функционального программирования.
Данная дисциплина позволит студентам не только систематизировать получен-
ные теоретические знания, укрепить исследовательские навыки, но и даст возмож-
ность ориентироваться в новом предметном поле информатики.
1.2 Содержание дисциплины
Материал дисциплины сгруппирован по следующим разделам:
1. Общие сведения о языках логического и функционального программирования.
Функциональное и логическое программирование как научная дисциплина.
Общие сведения о языках логического и функционального программирования.
Перспективы дальнейшего развития теории и практики функционального и логиче-
ского программирования. Языки искусственного интеллекта.
2. Основные элементы и приемы программирования языка ПРОЛОГ. Методы по-
4
строения программ в языке ПРОЛОГ.
Основные элементы и приемы программирования языка ПРОЛОГ. Предложе-
ния: факты и правила. Цели внутренние и внешние. Отношения (предикаты). Пере-
менные свободные и связанные. Анонимная переменная. Отсечение и способы его использования. Семантические модели. Использование конструкций языка ПРОЛОГ для реализации семантических моделей.
3. Основные конструкции языка LISP. Управляющие структуры языка LISP.
Основные особенности языка LISP. Основные понятия и базовые механизмы функционального языка программирования Лисп, ориентированного на решение за-
дач обработки символьных данных. Рассматриваются приемы рекурсивного про-
граммирования, в том числе с использованием функционалов.
1.3 Порядок освоения материала
Материал дисциплины изучается в соответствии с порядком, определённым в следующей таблице:
|
|
Таблица 1 |
|
Порядок освоения дисциплины |
|
|
|
|
№ |
Раздел дисциплины |
№№ предшествующих разделов |
|
|
|
1 |
Общие сведения о языках логического и функ- |
- |
|
ционального программирования. |
|
|
|
|
|
|
|
2 |
Основные элементы и приемы программиро- |
|
|
вания языка ПРОЛОГ. Методы построения |
1 |
|
программ в языке ПРОЛОГ. |
|
|
|
|
3 |
Основные конструкции языка LISP. Управля- |
1,2 |
|
ющие структуры языка LISP. |
|
|
|
|
|
|
|
2. Методические указания по подготовке к лекциям
5
2.1 Общие рекомендации по работе на лекциях
Лекция является главным звеном дидактического цикла обучения. Ее цель — формирование основы для последующего усвоения учебного материала. В ходе лек-
ции преподаватель в устной форме, а также с помощью презентаций передает обуча-
емым знания по основным, фундаментальным вопросам изучаемой дисциплины.
Назначение лекции состоит в том, чтобы доходчиво изложить основные поло-
жения изучаемой дисциплины, ориентировать на наиболее важные вопросы учебной дисциплины и оказать помощь в овладении необходимых знаний и применения их на практике.
Личное общение на лекции преподавателя со студентами предоставляет боль-
шие возможности для реализации образовательных и воспитательных целей.
При подготовке к лекционным занятиям студенты должны ознакомиться с пре-
зентаций, предлагаемой преподавателем, отметить непонятные термины и положе-
ния, подготовить вопросы с целью уточнения правильности понимания. Рекоменду-
ется приходить на лекцию подготовленным, так как в этом случае лекция может быть проведена в интерактивном режиме, что способствует повышению эффектив-
ности лекционных занятий.
2.2Общие рекомендации при работе с конспектом лекций
Входе лекционных занятий необходимо вести конспектирование учебного ма-
териала. Конспект помогает внимательно слушать, лучше запоминать в процессе осмысленного записывания, обеспечивает наличие опорных материалов при подго-
товке к семинару, зачету, экзамену.
Полезно оставить в рабочих конспектах поля, на которых делать пометки из ре-
комендованной литературы, дополняющие материал прослушанной лекции, а также подчеркивающие особую важность тех или иных теоретических положений.
В случае неясности по тем или иным вопросам необходимо задавать преподава-
телю уточняющие вопросы. Следует ясно понимать, что отсутствие вопросов без обсуждения означает в большинстве случаев непонимание материала дисциплины.
6
2.3 Общие рекомендации по изучению материала лекций
Раздел 1: Общие сведения о языках логического и функционального программиро-
вания.
Одними из наиболее универсальных понятий в математике являются поня-
тия функции и предиката, именно они легли в основу современных языков функционального и логического программирования.
При ФП задача специфицируется в виде набора определений функций, ко-
торый можно назвать библиотекой, или базой данных, и некоторого выражения с фактическими параметрами, которое можно назвать целевым выражением,
или запросом. Целью решения задачи является вычисление значения этого вы-
ражения, содержащего обычно обращения к встроенным и (или) определенным в базе данных функциям. В целях большей универсальности вид выражения за-
ранее не фиксируется, и пользователь может формулировать его произвольно.
При ЛП база данных описывается набором логических правил и фактов, ко-
торые можно рассматривать как аксиомы предметной области. Запрос пред-
ставляет собой некоторую логическую формулу, которая, в отличие от преды-
дущего случая может содержать переменные. Целью решения является попытка доказать, что эта формула есть логическое следствие аксиом с определением всех вариантов означивания переменных в запросе, либо получить сообщение,
что запрос не является логическим следствием.
Для практического применения данных подходов необходимо конкретизи-
ровать способы, с помощью которых строятся определения функций (в ФП) или логических формул (в ЛП). Понятно, что чем меньше ограничений накладыва-
ется на допустимые способы определения функций (или логических формул),
тем проще пользователю формализовать свою задачу. Однако тем менее эффек-
тивным будет алгоритм интерпретации. На сегодня в парадигме и функцио-
нального, и логического программирования выработаны общепринятые стан-
дарты таких определений, которые являются разумным компромиссом между выразительностью и эффективностью.
Функциональное программирование было задумано как альтернатива про-
цедурному программированию (в конце 50-х годов).
7
Функциональная программа представляет собой некоторое выражение (в
математическом смысле); выполнение программы означает вычисление значе-
ния этого выражения. Другими словами, функциональные программы соответ-
ствуют математическим объектам (позволяют производить строгие суждения – правильно/неправильно).
Результат работы императивной (процедурной) программы полностью и одно-
значно определен ее входом, можно сказать, что финальное состояние (или любое промежуточное) представляют собой некоторую функцию от начального состояния.
Языки функционального программирования:
-Lisp (Лисп) – базируется на -исчислении (определенная формализация поня-
тия функции): для обработки списков (используют в графических и тексто-
вых редакторах), для задач искусственного интеллекта;
-Рефал – базируется на нормальных алгорифмах Маркова;
-Миранда – комбинаторная логика Haskell.
Таблица. Сравнение функционального и императивного подхода
Программирование
|
Процедурное |
|
Функциональное |
1) переменные |
|
|
|
Именованные |
ячейки |
памяти, |
Настоящие переменные (в частности не |
изменяемые константы. |
|
используется оператор присваивания). |
|
2) циклы |
|
|
|
Циклы есть. |
|
|
Не может быть циклов (нет счетчика); |
|
|
|
используются рекурсивные функции |
|
|
|
вместо циклов. |
3) программа – это … |
|
|
|
Последовательное изменение памяти. |
Вычисление функции. Последовательное |
||
|
|
|
выполнение команд бессмысленно, по- |
|
|
|
скольку одна команда не может повлиять |
|
|
|
на выполнение следующей (т.к. негде |
|
|
|
сохранять промежуточные значения). |
|
|
|
|
4) функции |
|
|
|
|
|
||
При вызове функции возможны побоч- |
Функции используются широко, могут |
||
ные эффекты (два вызова одной о той же |
даже использоваться в качестве аргумен- |
||
функции с одними и теми же аргумента- |
тов для других функций и возвращать в |
||
ми могут дать разные результаты; изме- |
качестве результата; побочных эффектов |
||
нение значений глобальных перемен- |
нет. |
||
ных). |
|
|
|
|
|
8 |
|
Из этого следует, что вычисление любого выражения не может иметь никаких побочных эффектов, и значит, порядок выполнения его подвыражений не оказывает влияния на результат. Таким образом, функциональные программы легко поддаются распараллеливанию, поскольку отдельные компоненты выражений могут вычис-
ляться одновременно.
В логическом программировании используются логические функции. Обыч-
ная и логическая функции не отличаются аргументами.
f (х) (х 5) – функция в функциональном программировании;
f (х) (х 5) – функция в логическом программировании (возвращает значе-
ние истина или ложь).
В логике функции называются предикатами. Под предикатом понимают ло-
гическую функцию, аргументы которой могут принимать значения из некоторой предметной области, а сама функция принимать значения истина или ложь.
В практическом плане языки ФП и ЛП, как языки программирования особен-
но удобны для реализации обработки типов данных, которые сами имеют рекурсив-
ную природу: списков, деревьев, графов и сводящихся к ним структур. Такого рода задачи характерны для обработки символьной информации, т. е. для создания трансляторов и решения задач искусственного интеллекта: обработки естественного языка, трансформации и автоматического синтеза программ, аналитического преоб-
разования формальных текстов и др. В этих случаях программы, написанные на ФП
(ЛП), обычно в 5 – 10 раз короче программ, написанных в императивном стиле.
1. Процедурный способ программирования соответствует вопросу «как»
(необходимо описать, как решается задача), декларативный способ – вопросу
«что» (достаточно описать, что должно быть решено).
2. Программа на декларативном языке состоит из двух компонент: условия за-
дачи (которую иногда называют «базой данных») и целевого запроса.
3. Для декларативного программирования необходимо наличие «решателя»
(называемого обычно интерпретатором), который «знает» как выполнить це-
левой запрос, исходя из условий, представленных в «базе данных».
4. В каждом декларативном языке программирования можно выделить две се-
9
мантики: декларативную и процедурную. Декларативная семантика определя-
ется в соответствии с семантикой тех математических конструкций, которые положены в основу данного языка, а процедурная – с помощью принятого ме-
ханизма интерпретации этих конструкций.
5. Необходимым условием объявления некоторого декларативного языка яв-
ляется корректность предложенной для него процедурной семантики (правил интерпретации), т. е. совпадение результатов вычислений любой программы с результатами, имеющими место при восприятии этой программы как матема-
тического текста.
6. Корректность механизмов вычислений, используемых в современных ин-
терпретаторах ФП и ЛП, обоснована теоретическим аппаратом лямб-
да-исчисления для ФП и исчисления предикатов первого порядка для ФП.
7. Применение парадигм ФП и ЛП дает наибольший выигрыш при работе с данными, которые сами имеют рекурсивную природу: списками, деревьями,
графами и сводящимися к ним структурами.
8. Задачи такого рода характерны для обработки символьной информации: со-
здания трансляторов, обработки естественного языка, трансформации и авто-
матического синтеза программ, аналитических преобразований формальных текстов и др.
9.Существуют специальные технологии, с помощью которых при известном описании обрабатываемых данных написание программ из полуинтуитивного процесса превращается в достаточно строгую процедуру.
10.Программы ФП и ЛП являются гораздо более приспособленными для реа-
лизации параллельных вычислений, чем традиционные программы.
Раздел 2: Основные элементы и приемы программирования языка ПРОЛОГ.
Методы построения программ в языке ПРОЛОГ.
Пролог – один из языков логического программирования, позволяющий ис-
пользовать как традиционный процедурный подход, так и декларативный подход, то есть программировать не ход решения задачи, а ее постановку. Встроенная в Пролог машина вывода, реляционный характер языка, средства автоматического поиска
10