Методические указания к лабораторным работам по дисциплине «Функциональное и логическое программирование» (стр. 2 из 3)

Содержание отчета:

- титульный лист;

- задание;

- исходные тексты;

- выводы по работе.

Методические указания:

Поиск с возвратом

Одной из важнейших особенностей языка Пролог является возможность поиска всех решений. Поиск всех решений достигается использованием механизма поиска с возвратом.

Можно сформулировать четыре основных правила поиска с возвратом:

- Правило 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

- Определить рекурсивную функцию для удаления последнего элемента списка.