| МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторным работам
по дисциплине «Функциональное и логическое программирование»
Лабораторная работа №1. Знакомство с основами логического программирования (Prolog)..... 1
Лабораторная работа №2. Поиск с возвратом и рекурсия (Prolog)................................................. 3
Лабораторная работа №3. Рекурсивные структуры данных (списки и деревья) (Prolog)............. 9
Лабораторная работа №4. Знакомство с основами функционального программирования (Lisp) 12
Лабораторная работа №1. Знакомство с основами логического программирования (
Prolog)
Тема:
Знакомство с основами логического программирования.
Задание:
При отладке программы использовать возможности трассировки.
Используя предикаты parent(symbol,symbol), man(symbol), woman(symbol), married(symbol,symbol), записать факты, описывающие Вашу семью. Записать 8 правил вывода для любых родственных отношений в Вашей семье (например: мать, отец, сестра, брат, племянница, племянник, тетя, дядя, внучка, внук, бабушка, дедушка, двоюродная сестра, двоюродный брат и т.д.).
Содержание отчета:
- титульный лист;
- задание;
- описание родственных связей (в виде дерева);
- исходный текст;
- выводы по работе.
Методические указания:
Как правило, программа на Прологе состоит из двух программных секций: секции предикатов PREDICATES и секции предложений CLAUSES.
В секции PREDICATES описываются собственные предикаты. Описание предикатов заключается в их перечислении с указанием доменов (типов) их аргументов. Встроенные предикаты объявлять не требуется. Формат объявления предиката:
predicate_name(argument_domain_1, argument_domain_2, …, argument_domain_n)
В секции CLAUSES помещаются предложения – факты и правила, составляющие программу. Все предложения для одного предиката должны быть сгруппированы. Каждое предложение заканчивается точкой. Формат записи предложений:
fact(object_1, object_2, …, object_n).
rule(Var_1, Var_2, …,Var_m):–subgoal_1, subgoal_2, …, subgoal_k.
Пример программы на Прологе:
PREDICATES
bird(symbol)
parent(symbol,symbol)
CLAUSES
bird(sparrow). % Воробей – это птица.
bird(X):–parent(Y,X), bird(Y). % X – это птица, если у него есть родитель,
% который является птицей.
parent(sparrow,nestling). % Воробей – родитель птенца.
Для отладки программы можно использовать возможности трассировки. Трассировка позволяет в пошаговом режиме проследить процесс нахождения решения.
Для того чтобы включить трассировку, можно воспользоваться одним из двух способов:
- в первой строке программы поместить директиву trace;
- выбрать Trace из меню Options/Compiler Directives/Trace.
При работе в режиме трассировки вся текущая информация появляется в окне трассировки Trace. Для пошагового выполнения программы в режиме трассировки используется клавиша F10.
Сообщения в окне трассировки могут быть следующими:
- CALL – вывод имени предиката и значений его параметров;
- FAIL – вывод имени неудачно завершившегося предиката;
- REDO – вывод сообщения о том, произведен поиск с возвратом;
- RETURN – вывод имени удачно завершившегося предиката и значений его параметров (символ * показывает, что существуют другие решения).
Лабораторная работа №2. Поиск с возвратом и рекурсия (
Prolog)
Тема:
Поиск с возвратом и рекурсия.
Задание:
При отладке программы использовать возможности трассировки.
Вариант 1
- Написать программу, реализующую телефонный справочник. В справочнике содержится следующая информация о каждом абоненте: имя и телефон. Реализовать вывод всей информации из справочника, поиск телефона по имени, поиск имени по телефону. Для удобства работы реализовать меню с соответствующими пунктами.
- Подсчитать, сколько раз встречается некоторая буква в строке. Строка и буква должны вводиться с клавиатуры. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 2
- Написать программу, реализующую географический справочник. В справочнике содержится следующая информация: названия страны и площади страны, названия рек и длины рек, названия озер и глубины озер. Реализовать вывод всей информации из справочника, поиск по названию. Реализовать поиск по площади, длине или глубине, при этом должна быть возможность ввести некоторое пороговое значение (например, вывести названия всех рек, длина которых не менее 3000 км). Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1,
f(n)=f(n-1)+f(n-2). Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 3
- Написать программу, реализующую словарь. В словаре содержится следующая информация: слово и его несколько переводов. Реализовать вывод всего словаря, перевод с русского на английский, с английского на русский. Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить произведение двух целых положительных чисел (используя суммирование). Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 4
- Написать программу, реализующую калькулятор на четыре арифметических действия (без скобок).
- Подсчитать, сколько раз встречается некоторое слово в строке. Строка и слово должны вводиться с клавиатуры. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 5
- Написать программу, реализующую авиасправочник. В справочнике содержится следующая информация о каждом рейсе: номер рейса, пункт назначения, цена билета. Реализовать вывод всей информации из справочника, поиск пункта назначения по номеру рейса. Реализовать поиск по пункту назначения с указанием максимально возможной цены билета (должны быть выведены все рейсы, цена билета на которые ниже указанного значения) Для удобства работы реализовать меню с соответствующими пунктами.
- Поменять порядок следования букв в слове на противоположный. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 6
- Написать программу для продажи театральных билетов. Должна быть представлена следующая информация: спектакль, свободные места, цена билета. Реализовать вывод всей информации о билетах, поиск билета по ряду. Реализовать поиск по цене с указанием максимально возможной цены (должна быть выведена информация о билетах, цены на которые ниже указанного значения). Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить сумму ряда целых нечетных чисел от 1 до n. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 7
- Написать программу, реализующую автомагазин. Должна быть представлена следующая информация о каждом автомобиле: модель, мощность двигателя, цвет, цена. Реализовать вывод всей информации по автомобилям, поиск по цвету. Реализовать поиск по мощности с указанием минимальной мощности (должна быть выведена информация обо всех моделях, мощность которых выше указанного значения). Для удобства работы реализовать меню с соответствующими пунктами.
- Поменять порядок следования слов в предложении на противоположный. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 8
- Написать программу, реализующую книжный магазин. Должна быть представлена следующая информация: название книги, количество экземпляров, цена. Реализовать вывод всей информации о книгах, поиск книги по названию. Реализовать поиск по цене с указанием интервала возможной цены (должна быть выведена информация о книгах, цены которых попадают в указанный интервал). Для удобства работы реализовать меню с соответствующими пунктами.
- Вычислить сумму ряда целых четных чисел от 2 до n. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 9
- Написать программу для продажи туристических туров. Должна быть представлена следующая информация: название тура, страна, продолжительность, цена. Реализовать вывод информации обо всех турах, поиск тура по стране. Реализовать поиск по продолжительности с указанием интервала возможной продолжительности (должна быть выведена информация о турах, продолжительность которых попадает в указанный интервал). Для удобства работы реализовать меню с соответствующими пунктами.
- Организовать ввод целых положительных чисел и их суммирование до тех пор, пока сумма не превысит некоторого порогового значения. Введенные отрицательные целые числа суммироваться не должны. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Вариант 10
- Написать программу для заказа мест в отеле. Должна быть представлена следующая информация: название отеля, класс отеля, свободные места, цена номера. Реализовать вывод информации обо всех свободных номерах, поиск отеля по классу. Реализовать поиск по цене с указанием максимально возможной цены (должна быть выведена информация о номерах, цены на которые ниже указанного значения) Для удобства работы реализовать меню с соответствующими пунктами.
- Организовать ввод букв и их соединение в строку до тех пор, не будет введен символ #. Для присоединения символа к строке использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий присоединять символ Char к строке StringRest и получать строку String. Написать два варианта программы, без хвостовой рекурсии и с хвостовой рекурсией.
Содержание отчета:
- титульный лист;
- задание;
- исходные тексты;
- выводы по работе.
Методические указания:
Поиск с возвратом
Одной из важнейших особенностей языка Пролог является возможность поиска всех решений. Поиск всех решений достигается использованием механизма поиска с возвратом.
Можно сформулировать четыре основных правила поиска с возвратом:
- Правило 1: подцели должны быть согласованы по порядку, слева направо (сверху вниз);
- Правило 2: предикатные предложения проверяются в том порядке, в котором они появляются в программе, сверху вниз;
- Правило 3: когда подцель сопоставляется с заголовком правила, тело этого правила должно быть доказано (тело правила состоит, в свою очередь, из новых подцелей, которые должны быть доказаны);
- Правило 4: целевое утверждение считается согласованным, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.
Пример:
DOMAINS
name, thing=symbol
PREDICATES
hobby (name, thing)
reads (name)
is_inquisitive (name)
CLAUSES
hobby (“Ян”, “теннис”).
hobby (“Лена”, “лыжи”).
hobby (X, “книги”):- reads (X), is_inquisitive (X).
hobby (“Лена”, “книги”).
reads (“Ян”).
is_inquisitive (“Ян”).
Goal: hobby (Y, “теннис”), hobby (Y, “книги”).
Y=“Ян”
Для управления поиском решений существует два стандартных предиката:
- предикат fail, использующийся для поддержания поиска с возвратом;
- предикат !, использующийся для предотвращения поиска с возвратом.
Предикат fail всегда дает неудачу в доказательстве и, таким образом, поддерживает поиск с возвратом.
Пример.
DOMAINS
name=symbol
PREDICATES
father (name, name)
everybody
CLAUSES
father (“Павел”, “Петр”).
father (“Петр”, “Михаил”).
father (“Петр”, “Иван”).
everybody:- father (X, Y), write (X, “это отец ”, Y, “а”), nl, fail.
GOAL
everybody.
Результатом работы будет вывод следующих сообщений и работа программы завершится с неуспехом:
Павел это отец Петра
Петр это отец Михаила
Петр это отец Ивана
Предикат ! убирает все точки возврата, то есть через отсечение нельзя совершить поиск с возвратом.
Пример.
r(1):- !, a, b, c.
r(2):- !, d.
r(3):- !, e.
r(_):- write (“Это предложение-ловушка”).
Рекурсия
Рекурсивная процедура – это процедура, которая вызывает сама себя. Рекурсия – хороший способ для решения задач, содержащих в себе подзадачу такого же типа.
Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.
PREDICATES
factorial (integer, real)
CLAUSES
factorial (0, 1):-!. %факториал 0! равен 1 (граничное условие,
%останавливающее рекурсию)
factorial (N, FactN):-M=N-1, factorial (M, FactM), FactN= FactM*N.
%факториал n! равен (n-1)!*n (рекурсивное условие)
Goal: factorial (3, FactN)
FactN=6
Для наглядного представления нахождения решения удобно использовать дерево целей:
У рекурсии есть большой недостаток, она требует памяти. Избежать этого недостатка позволяет хвостовая рекурсия.
Рекурсия является хвостовой, если выполняются следующие условия:
- рекурсивный вызов является самой последней подцелью выражения;
- ранее в предложении не было возвратных точек.
Пример хвостовой рекурсии:
PREDICATES
count (real)
CLAUSES
count (N):- write (N), nl, NewN=N+1, count (NewN).
GOAL
count (1).
Примеры нехвостовой рекурсии:
PREDICATES
badcount1 (real)
badcount2 (real)
badcount3 (real)
CLAUSES
% рекурсивный вызов ‑ не последняя подцель в предложении
badcount1 (N):- write (N), NewN=N+1, count (NewN), nl.
% перед рекурсивным вызовом в предложении есть точка возврата
badcount2 (N):- N>=0, write (N), nl, NewN=N-1, badcount2 (NewN).
badcount2 (N):- write (“N – отрицательное число”).
% перед рекурсивным вызовом в предложении есть точка возврата
badcount3 (N):- write (N), nl, NewN=N+1, check(NewN), badcount3 (NewN).
check (M):-M>=0.
check (M):-M<0.
Для преобразования рекурсии в хвостовую для предикатов badcount2 и badcount3 достаточно воспользоваться отсечением, которое уберет все точки возврата перед рекурсивным вызовом.
badcount2 (N):- N>=0, !, write (N), nl, NewN=N-1, badcount2 (NewN).
badcount2 (N):- write (“N – отрицательное число”).
badcount3 (N):- write (N), nl, NewN=N+1, check(NewN), !, badcount3 (NewN).
check (M):-M>=0.
check (M):-M<0.
Лабораторная работа №3. Рекурсивные структуры данных (списки и деревья) (
Prolog)
Тема:
Рекурсивные структуры данных (списки и деревья).
Задание:
При отладке программы использовать возможности трассировки.
Вариант 1
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка найти среднее арифметическое листьевых вершин, из полученных результатов сформировать список (без использования стандартного предиката findall). Выполнить реверс для полученного списка.
Вариант 2
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка проверить упорядоченность, из полученных результатов сформировать список (без использования стандартного предиката findall). Получить n-й элемент списка-результата.
Вариант 3
- Имеется список, элементы которого – бинарные деревья, пустые и непустые. Удалить из списка все пустые бинарные деревья, затем вывести на экран все элементы полученного списка в виде деревьев.
Вариант 4
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка найти глубину дерева, из полученных результатов сформировать список (без использования стандартного предиката findall). Для полученного списка выполнить циклический сдвиг вправо на заданное число элементов.
Вариант 5
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка найти число вершин, значения которых лежат в определенном диапазоне, из полученных результатов сформировать список (без использования стандартного предиката findall). Из полученного списка удалить 2-ой, 4-ой и т.д. элементы.
Вариант 6
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка выполнить преобразование дерева в список. В полученных списках заменить все элементы, равные 0, на -1.
Вариант 7
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка найти количество отрицательных узлов дерева, из полученных результатов сформировать список (без использования стандартного предиката findall). Преобразовать полученный список арабских чисел (максимальное значение 10) в список римских чисел.
Вариант 8
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка найти количество вершин бинарного дерева, значения которых не равны 0, из полученных результатов сформировать список (без использования стандартного предиката findall). Для полученного списка подсчитать количество заданных элементов в списке.
Вариант 9
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка найти среднее арифметическое положительных узлов дерева, из полученных результатов сформировать список (без использования стандартного предиката findall). Для полученного списка подсчитать количество элементов списка без какого-либо указываемого элемента.
Вариант 10
- Имеется список, элементы которого – непустые бинарные деревья. Для каждого элемента списка найти количество вершин бинарного дерева, значения которых равны 0, из полученных результатов сформировать список (без использования стандартного предиката findall). Для полученного списка подсчитать количество элементов списка, значения которых лежат в определенном диапазоне.
Содержание отчета:
- титульный лист;
- задание;
- исходные тексты;
- выводы по работе.
Методические указания:
Списки
Список – это объект данных, содержащий конечное число других объектов (элементов списка). Список, содержащий числа 1, 2 и 3, записывается следующим образом:
[1, 2, 3]
Для объявления списка используется следующее описание домена:
DOMAINS
integerlist=integer*
Список является рекурсивным составным объектом, он состоит из двух частей:
- головы списка – первого элемента списка;
- хвоста списка – списка, включающего все последующие элементы.
[1| [2, 3]]
голова списка 1
хвост списка [2, 3]
Так как список имеет рекурсивную составную структуру, для работы со списками используется рекурсия.
Пример: печать элементов списка.
DOMAINS
integerlist=integer*
PREDICATES
printlist (integerlist)
CLAUSES
printlist ([]):-!. %для пустого списка ничего не делать
printlist ([H|T]):-write (H), nl, printlist (T). %для непустого списка отделить голову,
%напечатать ее, продолжить печать для
%хвоста списка
Деревья
Пролог позволяет определить рекурсивные типы данных. Например, можно определить дерево следующим образом:
DOMAINS
treetype=tree(integer, treetype, treetype); empty()
Такое определение позволяет записать следующую структуру данных:
tree(5,
tree(3,
tree(6, empty, empty),
tree(4, empty, empty)),
tree(10,
tree(2, empty, empty),
tree(8, empty, empty)))
Одной из наиболее частых операций с деревом является обход узлов дерева и выполнение некоторых действий с ними. Например, вывод значений всех узлов дерева:
DOMAINS
treetype =tree(integer, treetype, treetype); empty()
PREDICATES
print_tree(treetype)
CLAUSES
print_tree(empty):-!.
print_tree(tree(Root, Left, Right)):-write(Root), nl, print_tree(Left), print_tree(Right).
GOAL
print_tree(tree(5,tree(3,tree(6, empty, empty),tree(4, empty, empty)),tree(10,tree(2, empty, empty),tree(8, empty, empty)))).
Лабораторная работа №4. Знакомство с основами функционального программирования (
Lisp)
Тема:
Знакомство с основами функционального программирования.
Задание:
Вариант 1
- Определить рекурсивную функцию, возвращающую значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).
- Определить функцию, вычисляющую, сколько всего атомов в списке (списочной структуре).
- Определить функцию для нахождения среднего арифметического листьевых вершин бинарного дерева.
Вариант 2
- Определить рекурсивную функцию для удаления последнего элемента списка.
- Определить функцию, вычисляющую глубину списка (самой глубокой ветви).
- Определить функцию для проверки упорядоченности бинарного дерева.
Вариант 3
- Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование).
- Определить функцию, реализующую головоломку «Ханойские башни».
- Определить функцию для вывода бинарного дерева на экран в виде дерева.
Вариант 4
- Определить рекурсивную функцию, возвращающую последний элемент списка.
- Определить функцию, подсчитывающую число элементов списка без какого-либо указываемого элемента.
- Определить функцию для вычисления глубины бинарного дерева (глубина пустого дерева равна 0, глубина одноузлового дерева равна 1).
Вариант 5
- Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n.
- Определить функцию (first_elem x y), которая возвращает первый элемент, входящий в оба списка x и y, в противном случае nil.
- Определить функцию для подсчета количества вершин бинарного дерева, значения которых лежат в определенном диапазоне.
Вариант 6
- Определить рекурсивную функцию, возвращающую значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).
- Определить функцию, вычисляющую, сколько всего атомов в списке (списочной структуре).
- Определить функцию для нахождения среднего арифметического листьевых вершин бинарного дерева.
Вариант 7
- Определить рекурсивную функцию для удаления последнего элемента списка.
- Определить функцию, вычисляющую глубину списка (самой глубокой ветви).
- Определить функцию для проверки упорядоченности бинарного дерева.
Вариант 8
- Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование).
- Определить функцию, реализующую головоломку «Ханойские башни».
- Определить функцию для вывода бинарного дерева на экран в виде дерева.
Вариант 9
- Определить рекурсивную функцию, возвращающую последний элемент списка.
- Определить функцию, подсчитывающую число элементов списка без какого-либо указываемого элемента.
- Определить функцию для вычисления глубины бинарного дерева (глубина пустого дерева равна 0, глубина одноузлового дерева равна 1).
Вариант 10
- Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n.
- Определить функцию (first_elem x y), которая возвращает первый элемент, входящий в оба списка x и y, в противном случае nil.
- Определить функцию для подсчета количества вершин бинарного дерева, значения которых лежат в определенном диапазоне.
Содержание отчета:
- титульный лист;
- задание;
- исходный текст;
- выводы по работе.
Методические указания:
Предложения
prog1,
prog2,
progN
(progX form1 form2 … formN)
Назначение: выполнение последовательных вычислений.
Пример:
>(progn (setq x 2) (setq y (* 3 x)))
6
Предложение
cond
(cond (predicate1 form1) (predicate2 form2) … (predicateN formN))
Назначение: выполнение ветвления.
Пример: функция, определяющая тип выражения (пустой список, атом или список).
>(defun deftype(arg)
(cond ((null arg) ‘empty) ((atom arg) ‘atom) (t ‘list)))
DEFTYPE
>(deftype ‘(a b c))
LIST
>(deftype (atom ‘(a t o m)))
EMPTY
Предложение
if
(if (condition) thenform elseform)
Назначение: выполнение ветвления.
Пример:
>(setq x ‘(a b c))
(A B C)
>(if (atom x) ‘atom ‘list)
LIST
Предложение
do
(do ((var1 value1) (var1 value1) … (var1 value1))
(endcondition form11 form12)
form 21 form 22)
Назначение: выполнение циклических вычислений.
Пример: вычисление суммы целых чисел от n до 0.
>(defun count (n)
(do ((result n)) ;;начальное значение
((= n 0) result) ;;условие окончания цикла
(setq n (- n 1))
(setq result (+ result n))
)
)
COUNT
>(count 5)
15
Простая рекурсия
Функция является рекурсивной, если в ее определении содержится вызов этой же функции. Рекурсия является простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл.
Пример: построение копии списка.
>(defun listcopy (list)
(cond ((null list) nil) ;;граничное условие
(t (cons (car list) (listcopy (cdr list)))))) ;;рекурсия
LISTCOPY
>(listcopy ‘(a b c))
(A B C)
Трассировка программы
Для отладки программы можно использовать возможности трассировки. Трассировка позволяет проследить процесс нахождения решения.
Для того, чтобы включить трассировку, можно воспользоваться следующей директивой:
(trace function)
Назначение: включает режим трассировки.
Пример:
>(trace listcopy)
(LISTCOPY)
>(listcopy '(a b))
Entering: LISTCOPY, Argument list: ((A B))
Entering: LISTCOPY, Argument list: ((B))
Entering: LISTCOPY, Argument list: (NIL)
Exiting: LISTCOPY, Value: NIL
Exiting: LISTCOPY, Value: (B)
Exiting: LISTCOPY, Value: (A B)
(A B)
(untrace function)
Назначение: отключает режим трассировки.
Пример:
>(untrace listcopy)
NIL
|