Логич-кое и функ-ное программ-ние_УМП. Учебные пособия по логическому и функциональ ному программированию В. М. Зюзькова. В пособие внесены изменения в 2020 г
 Скачать 2.34 Mb.
|
|
Министерство образования Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Кафедра автоматизированных систем управления (АСУ) В. М. Зюзьков ЛОГИЧЕСКОЕ И ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ Учебное методическое пособие 2000 Зюзьков В. М. Логическое и функциональное программирование : учебное пособие. - Томск: Томский межвузовский центр дистанционного образования, 2000. - 72 с. Учебное методические пособие содержит учебные программы, описания ин- сталляций интерпретаторов с Пролога и Лиспа, требования к выполнению контрольных заданий и курсовой работы, варианты заданий, темы курсовых работ, экзаменационные вопросы. В качестве источников для получения теоретических знаний студенту необ- ходимо и достаточно использовать учебные пособия по логическому и функциональ- ному программированию В. М. Зюзькова. В пособие внесены изменения в 2020 г. Зюзьков В. М., 2000 Томский межвузовский центр дистанционного образования, 2000 3 СОДЕРЖАНИЕ 1. Учебные программы ……………………………………………………... 4 1.1. Программа по дисциплине "Функциональное программирование" ... 4 1.2. Программа по дисциплине "Логическое программирование" ………. 5 2. Функциональное программирование …………………………………… 6 2.1. Контроль обучения ……………………………………………………... 6 2.2. Инсталляция XLisp'а …………………………………………………… 6 2.3. Первое контрольное задание …………………………………………... 7 2.4. Второе контрольное задание …………………………………………... 9 3. Логическое программирование ………………………………………….. 14 3.1. Контроль обучения ……………………………………………………... 14 3.2. Инсталляция SWI-Prolog'а ……………………………………………... 14 3.3. Первое контрольное задание …………………………………………... 15 3.4. Второе контрольное задание …………………………………………... 19 3.5. Третье контрольное задание …………………………………………… 23 4. Курсовые работы …………………………………………………………. 28 5. Как выполнять курсовую работу и оформлять пояснительную записку 36 6. Экзаменационные вопросы ……………………………………………… 40 7. Рекомендуемая литература ………………………………………………. 69 Приложение 1. Форма титульного листа к курсовой работе …………….. 70 Приложение 2. Форма задания для курсовой работы …………………….. 71 Приложение 3. Пример оформления содержания ………………………… 72 Приложения 4. Примеры библиографических описаний источников, помещаемых в список литературы ……………………….. 72 4 1. УЧЕБНЫЕ ПРОГРАММЫ 1.1. Программа по дисциплине "Функциональное программирование" Введение в функции.Чистые функции. Функциональность. Введение в функциональное программирование. О языке Лисп. Приме- ры на Лиспе. Символьная обработка. Лисп опередил свое время. Одинаковая форма данных и программы. Автоматическое и динамическое управление па- мятью. Лисп - безтиповой язык программирования. Заблуждения и предрас- судки. Основы языка Лисп. Символы и списки. Символы используются для представления других объектов. Символы в языке Коммон Лисп. Числа явля- ются константами. Логические значения T и NIL. Константы и переменные. Атомы = Символы + Числа. Построение списков из атомов и подсписков. Пу- стой список = NIL. Список как средство представления знаний. Значение способа записи. Различные интерпретации списка. Понятие функции. Едино- образная префиксная нотация. Диалог с интерпретатором Лиспа. Иерархия вызовов. QUOTE блокирует вычисление выражения. Основные функции об- работки списков. First, rest, cons. Предикаты atom, =, eq, eql, equal, equalp, null. Функции second, third, (nth n список) , last, list. Имя и значение символа. Зна- чением константы является сама константа. Символ может обозначать произ- вольное выражение. Set вычисляет имя и связывает его. Setq связывает имя, не вычисляя его. Побочный эффект псевдофункции. Определение функций. Defun, if, let. Использование квалифицирован- ного выражения. Накапливающие параметры. Локальные функции. Програм- ма: сортировка списка с помощью дерева. Математические основы. Лямбда-исчисление. Введение в синтаксис. Вычисление -выражений. Порядок редукций и нормальные формы. -редукция и проблема конфликта имен. Рекурсивные выражения. Чистое -исчисление. Ламбда- выражения в Лиспе. -вызов. Внутреннее представление списков. Лисповская память состоит из ссы- лочных ячеек. Значение представляется указателем. First и rest выбирают по- ля указателя. Cons создает ячейку и возвращает на нее указатель. У списков могут быть общие части. Логическое и физическое равенство не одно и то же. Примеры. Рекурсия. Простая рекурсия. Простая рекурсия соответствует циклу. Member проверяет, принадлежит ли элемент списку. Использование трасси- ровки. Append объединяет два списка. Remove удаляет элемент из списка. Reverse обращает список. Другие формы рекурсии. Параллельное ветвление рекурсии. Взаимная рекурсия. Рекурсия более высокого порядка. Функции более высокого порядка. Функционал имеет функциональный аргумент. 5 Функциональное значение функции. Способы композиции функций. Функции более высокого порядка. Применяющие функционалы. Apply применяет функцию к списку ар- гументов. Funcall вызывает функцию с аргументами. Отображающие функ- ционалы. Отображающие функции повторяют применение функций. Компо- зиция функционалов. Замыкания. Function блокирует вычисление функции. Замыкание - это функция и контекст ее определения. Связи свободных пере- менных замыкаются. Замыкание позволяет осуществлять частичное вычисле- ние. Абстрактный подход. Обобщение функций, имеющих одинаковый вид. Параметризованное определение функций. Автоаппликация и автореплика- ция. 1.2. Программа по дисциплине "Логическое программирование" Логическое программирование. Логический вывод. Метод резолюций. Унификация. Применение метода резолюций для ответа на вопросы. Введе- ние в Пролог. Особенности языка Пролог. Пример программы: родственные отношения. Фразы Хорна как способ представления знаний. Алгоритм работы интерпретатора Пролога. Порядок предложений и целей. Процедурная и декларативная семанти- ка Пролога. Синтаксис языка Пролог. Арифметические выражения, арифме- тические функции, арифметические предикаты. Составные термы (структу- ры), пример программы “Упрощение цепей” Списки. Предикаты со списками member, append, select. Примеры про- грамм “Сортировка с помощью дерева”, “Дифференцирование”. Ограничение перебора. Примеры, использующие отсечение. Отрицание как неудача. Трудности с отсечением и отрицанием. Программирование по- вторяющихся операций. Метапрограммирование. Предположение об открытости мира. Внело- гические предикаты: доступ к программам и обработка программ. Ввод и вы- вод . Работа с базой данных “Достопримечательности” (программа, которая учится у пользователя). Программирование второго порядка. Запоминающие функции. Операторная запись. Примеры программ. 6 2. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ 2.1. Контроль обучения В процессе дистантного обучения дисциплине "Функциональное программи- рование" студент должен выполнить два контрольных задания и обучение за- канчивается выполнением компьютерной экзаменационной работы. Кон- трольные задания представлены ниже и состоят каждое из трех задач, требу- ющих составить программы на Лиспе. Составленные и отлаженные програм- мы (обязательно с комментариями) студент по мере освоения функциональ- ного программирования периодически пересылает по электронной почте дис- петчеру центра дистантного обучения, который в свою очередь пересылает их лектору. Лектор проверяет программы и при правильном выполнении про- граммы студент получает подтверждение о том, что они зачтены. Если про- грамма составлена неправильно, студент получает от лектора текстовый файл, в котором содержится описание ошибок программы. 2.2. Инсталляция XLisp'а Интерпретатор с языка XLisp представлен в виде упакованного файла XLisp.arj. XLisp работает в среде Windows (3.11 или 95); для его установки на компьютере достаточно распаковать файл XLisp.arj вместе со всеми храня- щимися в этом файле каталогами. Запустите файл XLisp.exe из каталога XLisp\bin и вы войдете в интерпретатор. Лисп выдает приглашение ">" и ждет вашего ввода. Программы вы можете набирать в окне интерпретатора, но это неудоб- но. Лучше воспользоваться каким-либо внешним текстовым редактором (XLisp не имеет собственного редактора). Например, вы можете пользоваться стандартной программой Notepad ("блокнот"). Набранные программы сохра- няйте в виде текстовых файлов с расширением lsp (но можно и расширение txt) в рабочем каталоге. По умолчанию рабочим каталогом будет XLisp\bin, но вы можете это изменить: для этого создайте ярлык для XLisp.exe и изме- ните рабочий каталог в свойствах этого ярлыка. Загрузить программу, нахо- дясь в среде интерпретатора, вы можете, если выберите пункт меню File | Load Lisp source… . Отметим следующую особенность работы в Лиспе с блокнотом. После набора текста программы обязательно перейдите курсором на новую строчку, иначе XLisp при загрузке файла с программой выдаст ошибку "неожиданный конец файла". 7 2.3. Первое контрольное задание Задание состоит из трех задач, в которых требуется составить программы на Лиспе. В первой задаче не требуется рекурсия, остальные две задачи требуют применения простой рекурсии. При составлении программ (если не оговорено противное) можно использовать все встроенные функции Лиспа. Тексты всех программ, если вы мыслите в духе функционального программирования, бук- вально состоят из нескольких строчек. Отладку программ можно осуществлять с помощью функции трасси- ровки (trace <имя функции>), трассировка функции отключается - (untrace <имя функции>). Пример задания с решением Задача 1 Пусть l1 и l2 -списки. Напишите функцию, которая возвращала бы t, если первые два элемента этих списков соответственно равны друг другу, и nil в противном случае (например, если длина одного из списков меньше 2). Задача 2 Напишите функцию, зависящую от двух аргументов x и u, удаляющую все вхождения x в список u на всех уровнях. Задача 3 Сортировка слиянием. Даны два упорядоченных по возрастанию списка чи- сел x и y. Написать функцию (merge x y), которая в качестве значения выдает общий упорядоченный список элементов x и y. Например, merge('(1 3 5 7 8) '(2 3 5 7)) => (1 2 3 3 5 5 7 7 8). Решение Задача 1 (defun f (l1 l2) (and (> (length l1) 1) (> (length l2) 1) (equal (first l1) (first l2)) (equal (second l1) (second l2)))) Задача 2 (defun f (x u) (if (null u) nil (let ((c (first u)) (r (rest u))) (cond ((and (atom c) (equal x c)) (f x r )) ((atom c) (cons c (f x r))) ( t (cons (f x c) (f x r)))) )) ) 8 Задача 3 (defun merge (x y) (cond ((null x) y) ((null y) x) ((> (first x) (first y)) (cons (first y) (merge x (rest y)))) (t (cons (first x) (merge (rest x) y)))) ) Варианты заданий Вариант 1 1. Напишите функцию трех аргументов (list3 x y z) такую, что (list3 x y z) =(x y z) для любых символьных выражений; не используйте функцию list. 2. Последовательность чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13… строится по сле- дующему закону: первые два числа - единицы; любое следующее число есть сумма двух предыдущих f(n)=f(n-1)+f(n-2). Напишите функцию (f n f1 f2) c накапливающимися параметрами f1 и f2, которая вычисляет n-ое число Фибоначчи. 3. Определите умножение целых чисел (*2 x y) через сложение и вычитание. Вариант 2 1. Напишите функцию, которая выдает истину, если ее аргумент удовлетво- ряет хотя бы одному из следующих условий: а) является списком из двух элементов; б) является списком из двух атомов; в) является списком из трех элементов. 2. Определите возведение в целую степень (^ x n) через умножение и деление. 3. Напишите функцию (fullength x), считающую полное количество атомов (не равных nil) в списке x. Вариант 3 1. Напишите с помощью композиции условных выражений функции от че- тырех аргументов (and4 x1 x2 x3 x4) и (or4 x1 x2 x3 x4), совпадающие с встроенными функциями and и or от четырех аргументов. 2. Напишите функцию, вычисляющую последний элемент списка. 3. Напишите функцию от двух аргументов x и n , которая создает список из n раз повторенных элементов x. Вариант 4 1. Напишите функцию, осуществляющую циклическую перестановку элементов в списке, т.е. (f g h j) -> (g h j f). 9 2. Напишите функцию, которая из данного одноуровнего списка строит спи- сок списков его элементов, например, (a b) -> ((a) (b)). 3. Определите функцию, зависящую от двух аргументов u и v, являющихся списками, которая вычисляет список всех элементов u, не содержащихся в v. Вариант 5 1. Определите функцию (f a b c), которая равна истине тогда и только тогда, когда из отрезков с длинами a,b и c можно построить треугольник. 2. Определите функцию, зависящую от двух аргументов u и v, являющихся списками, которая вычисляет список всех элементов, содержащихся либо в u, либо в v, но не одновременно в u и v. 3. Напишите функцию, осуществляющую замену элементов списка y на соот- ветствующие элементы списка x в списке w, например, y=(a b), x=(1 2), w=((a b) a (c (a (a d)))) -> ((1 2) 1 (c (1 (1 d)))). Вариант 6 1. Определите функцию (f a b c), которая вычисляет список корней квадрат- ного уравнения a*x^2+b*x+c=0 (если корней нет, то список пустой). 2. Напишите функцию, аналогичную встроенной функции замены subst в списке s выражения x на y, но производящую взаимную замену x на y, т.е. x- >y, y->x. 3. Определите функцию (f s), результатом которой является список, получа- ющийся после удаления на всех уровнях всех положительных элементов списка чисел s. Вариант 7 1. Определите функцию, которая меняет местами первый и последний эле- менты списка, оставляя остальные на своих местах. 2. Определите функцию (summa_digits n), результатом которой является сум- ма цифр натурального числа n. 3. Определите функцию (f s), которая из данного списка s удаляет последний элемент. 2.4. Второе контрольное задание Задание состоит из трех задач, в которых требуется составить программы на Лиспе. В первых двух задачах требуется для программирования использовать локальные или вспомогательные функции. В третьей задаче требуется ис- пользовать функционалы. При составлении программ (если не оговорено про- тивное) можно использовать все встроенные функции Лиспа. Тексты всех программ, если вы мыслите в духе функционального программирования, бук- вально состоят из нескольких строчек. 10 Пример задания с решением Задача 1 Напишите функцию, вычисляющую полное число подсписков, входящих в данный список на любом уровне. Для списка (a b ((a) d) e) оно равно двум. Задача 2 Напишите функцию, удаляющую повторные вхождения элементов в список, например, (a b c d d a) -> (a b c d) Задача 3 Напишите функцию, строящую список всех подмножеств данного множества. Решение Задача 1 ; Предикат (p x) выясняет является ли список одноуровневым (defun p (x) (cond ((null x) t) ((listp (first x)) nil) ( t (p (rest x)))) ) (defun f (x) (cond ((atom x) 0) ((p x) 0) ( t (if (listp (first x)) (+ 1 (f (first x)) (f (rest x))) (f (rest x))))) ) Задача 2 (defun f (x) (labels (( f1 (y z) (cond ((null y) z) ((member (first y) z) (f1 (rest y) z)) ( t (f1 (rest y) (append z (list (first y)))))))) (f1 x nil)) ) Задача 3 Следующее решение принадлежит Клыкову Виктору, студенту кафедры АСУ группы 437-1. ; встроенная функция (union list1 list2) создает список всех элементов, входя- щих в список list1 или в list2 (объединение множеств): 11 ; (union '(1 2 3) '(2 5 7 1)) => ( 7 5 1 2 3) (defun f(s) (if (null s) (list s) (union (mapcar '(lambda (x) (cons (car s) x)) (f (cdr s))) (f (cdr s))) ) ) Варианты заданий Вариант 1 1. Определите функцию, зависящую от одного аргумента, которая по данному списку вычисляет список его элементов, встречающихся в нем более одного раза. Проверьте, как она будет работать на примере '(a a a a b a). 2. Определите функцию, зависящую от двух аргументов u и n, которая по данному списку строит список его элементов, встречающихся в нем не менее n раз. Проверьте работу этой функции на примере (a a b a c b c a b b d a b) для n=1,2,5,0. 3. Используя функционалы, напишите функцию, которая из данного списка строит список списков его элементов, например, (a b) -> ((a) (b)). Вариант 2 1. Определите функцию, обращающую список и все его подсписки на любом уровне, например, (a b (c d) e) -> (e (d c) b a). 2. Напишите функцию, заменяющую Y на число, равное глубине вложения Y в W, например, Y=a, W=((a b) a (c (a (a d)))) -> ((2 b) 1 (c (3 (4 d)))). 3. Напишите функцию, единственным аргументом которой являлся бы список списков, объединяющую все эти списки в один. Вариант 3 1. Напишите функцию, определяющую глубину первого вхождения элемента y в список w. 2. Напишите функцию, которая делает из списка множество, т.е. удаляет все повторяющиеся элементы. 3. Напишите функцию (exists p x), которая проверяет "Существует ли элемент списка x, удовлетворяющий предикату p?" (p - функция или функциональное имя ). 12 Вариант 4 1. Напишите функцию, которая определяет является ли данное натуральное число простым. Воспользуйтесь более общей задачей: (ispr n m) - "Число n не делится ни на одно число большее или равное m и меньшее n". Имеем (ispr n m) -истинно, во-первых, если n = m, и, во-вторых, если истинно (ispr n m+1) и n не делится на m. 2. Напишите функцию, которая сортирует список чисел, используя алгоритм простой вставки. 3. Напишите функцию (all p x), которая проверяет "Для всех ли элементов списка x выполняется предикат p? " (p - функция или функциональное имя ). Вариант 5 1. Напишите функцию, которая сортирует список чисел, используя алгоритм простого выбора. 2. Определите функцию (f s), результатом которой является список, получа- ющийся из списка списков s после удаления всех подсписков, содержащих числа. 3. Напишите функцию (filter p x), которая "фильтрует" (создает список) эле- менты списка x, удовлетворяющие предикату p (p - функция или функциональное имя ). Вариант 6 1. Определите функцию (f a n), которая от двух числовых аргументов вычисляет величину a+a*(a+1)+a*(a+1)*(a+2)+...+a*(a+1)*...*(a+n). 2. Определите функцию (f s), которая вычисляет список (m1 m2 m3), состоящий из трех наибольших элементов списка s: m1 >= m2 >= m3. Исходный список содержит не менее трех элементов. 3. Определите функцию (f s n), которая из списка чисел s создает новый спи- сок, прибавляя к каждому атому число n. Исходный список не предполагается одноуровневым. Вариант 7 1. Определите функцию (f n), n кратное 3, вычисляющую сумму: 1*2*3+4*5*6+...+(n-2)*(n-1)*n. 2. Определите функцию (f s), которая в одноуровневом списке чисел s переставляет все отрицательные элементы в начало списка, например, (f '(4 -8 6 -9 -7)) -> (-8 -9 -7 4 6). 13 3. Определите функцию (f s), которая из списка чисел s создает новый список, меняя знак у каждого атома. Исходный список не предполагается одноуров- невым. Вариант 8 1. Определите функцию (f s), вычисляющую знакочередующую сумму a1-a2+a3-a4+...+ak*(-1)^(k+1) для списка s, имеющего вид (a1 a2 a3 ... ak). 2. Определите функцию (f n), которая для натурального числа n вычисляет 1!+2!+3!+...+n!. 3. Напишите функцию (count p x), которая подсчитывает, сколько атомов в списке x удовлетворяет предикату p (p -функция или функциональное имя). Список x не предполагается одноуровневым. 14 |