Лекция 7

	*Лекция 7*
	*Встроенные предикаты обработки термов.*

Cодержание

7.1 Встроенные предикаты

7.1.1 repeat.

7.1.2 Проверка типа терма

7.2 Метапредикаты. (Встроенные предикаты обработки термов.)

7.2.1 Создание и декомпозиция термов

7.2.1.1 Т=..L

7.2.1.2 functor

7.2.1.3 arg

7.2.2 Предикаты работы с базой данных

7.3 Поиск в лабиринте

7.4 Сравнительная характеристика языков программирования.

repeat- цель, которая всегда успешна.
Ее особое свойство состоит в том, что она всегда находит альтернативу.
Поэтому всякий раз, когда до нее доходит перебор, она порождает новую ветвь
вычислений.
Хотя repeat встроенный предикат, он может быть определен следующим образом:

		repeat. repeat:- repeat.

Применение repeat можно посмотреть на примере процедуры sq,которая читает
последовательность чисел и выдает их квадраты.
Последовательность чисел заканчивается атомом stop.

sq:-repeat,read(X),( X=stop,!;

          Y is X*X, write(Y), fail).

7.1.2 Проверка типа терма

atom(X) - да, если X-атом.
integer(X) - да, если X-целое.
atomic(X) - да, если X-целое или атом.
var(X) - да, если X-не конкретизированная переменная.
nonvar(X) - да, если X- терм, отличный от переменной, или уже конкретизированная
переменная.

Пример универсального предиката суммирования:

plus(X,Y,Z):-integer(X),integer(Y),integer(Z),

             S is X + Y, S=Z.

plus(X,Y,Z):-integer(X),integer(Y),var(Z),

             Z is X + Y.

plus(X,Y,Z):-var(X),integer(Y),integer(Z),

             X is Z - Y.

plus(X,Y,Z):-integer(X),var(Y),integer(Z),

             Y is Z - X.

Примеры :

		?-plus(1,2,Z). Z=3. ?-plus(X,2,4). X=2. ?-plus(1,Y,2). Y=1. ?-plus(1,2,3). no.

7.2 Метапредикаты.(Встроенные предикаты обработки термов.)

7.2.1 Создание и декомпозиция термов.

7.2.1.1 Т=..L

	Т=..L (читается "univ") истина, если L - список, начинающийся с главного функтора терма T, вслед за которым идут его аргументы.

Примеры:

		?-f(a,b)=..L. L=[f,a,b]

Иллюстрация запроса :

		?-T=..(like,tom,mary). T=like(tom,mary).

Иллюстрация запроса :

Позволяет из списка получать структуру и наоборот.

7.2.1.2 functor

functor(Term,F,N) Будет истиной, если F- главный функтор терма Term,a N-количество его аргументов.

Примеры:

		?-functor(f(a,S),F,G). F=f G=2 ?-functor(b,F,G). F=b G=0 ?-functor(F,d,4). F=d(_,_,_,_).

Иллюстрации примеров:

7.2.1.3 arg

arg(N,T,A) - обеспечивает доступ
к конкретному аргументу структуры.

N - номер аргумента,
T - терм,
A - значение аргумента.

Пример:

?-arg(2,f(a,b),X)
X=b

?-F=..[a,2,3,4,5],arg(4,F,X).
X=5

7.2.2 Предикаты работы с базой данных

Программа в прологе - база данных. Можно добавлять к базе данных новые предложения и удалять предложения.
Аналогично, в ходе выполнения программы ее можно изменять.
Для этого используются специальные предикаты.

assert(C) - добавляет к базе данных предложение С.

?-assert(a(b)).
?-listing.
a(b).

?-asserta(a(a)).
?-assertz(a(c)).
?-listing.
a(a).
a(b).
a(c).

· Можно добавлять предложения:

assert((a(X):-X>0))

?-F=..[a,b,c],assert(F).
a(b,c).

		Иллюстрация примеров

· assert используется иногда для сохранения промежуточных результатов.
Может служить для передачи значений переменных между предложениями.
Использование лучше ограничивать из-за усложнения понимания программы.

retract(C) - удаляет предложения, согласуемые с C.

7.3 Поиск в лабиринте

Рассмотрим следующую задачу:
Существует дом с комнатами b,c,d,e,f,g. Между некоторыми комнатами есть двери. В одной из комнат (g) находится клад. Требуется пройти через комнаты к кладу.

Запишем информацию о дверях:

			door(a,b). door(b,c). door(b,e). door(d,e). door(d,c). door(e,g). door(e,f).

Переход из комнаты в комнату производится через предикат:

path(X,Y,T)

X - исходная комната;
Y - конечная комната;
T - список пройденных комнат. Он необходим, чтобы не проходить дважды через одну комнату.

Терминальное условие

path(Y,Y,T)

Т.е. мы находимся в нужной комнате.

Рекурсивное правило перехода:

path(X,Y,T):-door(X,Z),not(member(Z,T)),

             path(Z,Y,[Z|T]).

		Иллюстрация действия правила

Характер рекурсии другой. Один аргумент всегда увеличивается. В этой программе каждая дверь в одну сторону. Чтобы избежать этого, есть два варианта:

добавить к door(b,c) факт door(c,b)
ввести еще одно правило:

path(X,Y,T):-door(Z,X),not(member(Z,T)),

             path(Z,Y,[Z|T]).

		Иллюстрация действия правила

Можно записать, используя

дизъюнкцию

path(X,Y,T):-(door(Z,X);door(X,Z)),

              not(member(Z,T)),

              path(Z,Y,[Z|T]).

Поиск пути в комнату f

		?-path(a,f,[]).

Добавим факт о кладе:

money(g).

Тогда найдем путь к комнате с кладом.

Запрос

		?-path(a,X,[]), money(X).

Это вопрос типа "создать и проверить" находит достижимые комнаты, а затем проверяет наличие в них клада.

Запрос

		?-money(X),path(a,X,[]).

Здесь требуется сначала найти комнату, а затем путь к ней.

Интересные задачи:

Как вывести путь T?
Как найти самый короткий путь?

7.4 Сравнительная характеристика языков программирования.

Характеристика	PASCAL	LISP	PROLOG
тип языка	процедурный	функциональный	логический
типы данных	скаляры,структуры	атомы,списки	атомы,структуры
обработка данных	присвоение, передача по значению, передача по ссылке	значение функции, передача по значению	связь переменных через унификацию
управление программой	последовательное, ветвление,циклы рекурсия	вычисление функций, условные вычисления, рекурсии, циклы	рекурсия, бэктрекинг, !
структуры программы	блоки, процедуры	функции, LET-блоки	правила, факты
действия переменных	глобальные, локальные	локальные, свободные, предложение	область, одно
транслятор	компилятор, компилятор	интерпретатор, компилятор	интерпретатор
длина программы	5	3	1
скорость	1	2	5
Область	программы общего назначения	символная обработка, ИИ	ЭС, ИИ, прототипы

(c) M.N.Morozov, 1999.

информация	проекты	публикации
материалы	друзья	студенты
	связи