Использование предикатов, анализирующих типы или структуру термов

Речь о встроенных в пролог предикатах, которые дают инфу о типе или структуре терма.

Integer /1

Предикат проверяет явл ли его аргумент целочисленным значением.

Мы можем представить его множеством фактов:

Integer(0).

Integer(-1).

Integer(1).

…

Аналогично real /1

Если число вещественное.

Atom /1

Истинен если аргумент явл атомом, переменная конкретизирована…

Compound /1

Истинен если аргумент его явл структурой.

Класс встроенный

Number(X) :- integer(X).

Number(X):- real(X).

Есть предикат

atomic(X):-atom(X).

atomic(X):- number(X).

Есть предикат, позв посмотреть состояние переменной, это предикат

Var /1

Он проверяет, явл ли переменная еще не конкретизированной.

Его уже фактами описать нельзя, он наруш логич смысл пролога, позв подсмотреть внутрь…

Есть nonvar /1. Он истинен если переменная конкретизирована.

Рассмотрим алгоритм который делает список плоским. Этот алг более общий по сравн с пред.

?- flatten([a,b,[c,[d]]], X).

X = [a,b,c,d]

?- flatten(.(a,.(b,c)), X).

X = [a,b,c]

1ый пример – вложенные списки и в рез – е получ плоский список у которого элементы в том же порядке.

2ой пример – элементы структурированы точечными парами произвольно. Тут более общее исп функтора точка. Такие структуры назыв S – выражениями.

Сам алгоритм:

flatten1([],[]):- !.

flatten1(X,[X]):- atomic(X),!.

flatten1([X|Xs],Ys) :-

flatten1(X,Ys1),

flatten1(Xs,Ys2),

append(Ys1,Ys2,Ys).

Имеет несколько альтернативных вариантов. Самый простой случай, когда первый список пуст, то результатом будет тоже пустой список.

2ой случай, если первый элемент атомарный.

И тогда результатом будет список, содерж этот атомарный объект X.

3ий случай общий, когда список имеет голову и хвост.

.(b,c)

[X|Xs]

X=b

Xs = c

Рассмотрим, как этот алгоритм можно сделать более эффективным, использовав накапливающий параметр, в котором мы будем хранить отложенную работу.

list([_|_]).

flatten2(Xs,Ys) :- flatten3(Xs,[],Ys).

flatten3([X|Xs],S,Ys) :-

list(X),!,

flatten3(X,[Xs|S],Ys).

flatten3([[]|Xs],S,Ys) :- !,

flatten3(Xs,S,Ys).

Определен предикат list, который истинен если его аргумент список. Здесь можно было бы исп и предикат compound, если учесть что для процедур будет перед список функтором точка.

flatten3([X|Xs],S,[X|Ys]) :-

atomic(X),!,

flatten3(Xs,S,Ys).

flatten3([],[X|S],Ys) :- !,

flatten3(X,S,Ys).

flatten3([],[],[]).

Процедура flatten2, вх Xs, вых Ys выз вспомогательную процедуру flatten3 с накапл параметром, который в начале пуст. В ней должны анализ все варианты списков.1 если вх список имеет голову X и хвост Xs при этот голова сама явл списком. Тогда алгоритм будет делать плоской голову, вызов рекурсивный… А хвост Xs заноситься в накаплив. параметр, это отложенная работа. Ys результат.

2ой случай, голова и хвост, но голова пустая, дальнейшая работа ведется с хвостом Xs.

След.вариант – голова Xи хвост Xs. Голова атомарная atomic, результатом будет список с головой X хвостом Ys, которая результат обработки Xs.

Если исходный список пуст а в накаплив параметре есть голова и хвост, то нужно перейти в отложенной работе, т.е. алгоритм работает над головой X, отложенный – хвост Xs, стремимся к Ys.

Последний случай – когда первые два аргумента пустые, то результат пустой список.

Лекция

Пролог – язык символных вычислений.

Как на прологе можно преобразовывать выражения, и вычислять их

Нужно уметь делать подстановку термов.

Символьные вычисления.

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

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

L = [f,a,b]

?- F =.. [f,a,b].

F = f(a,b)‏

Теперь мы можем выделить функтор и составляющую часть из структуры. Для этого есть оператор =..

Этот оператор – предикат, который истинен, если левый операнд структура, а правый – список, голова которого – функтор, а хвост – компоненты структуры.

Таким образом, мы получаем и компоненты и само имя структуры.

Т.к. предикаты могут работать и в одном и в другом направлении, оператор =.. позволяет собрать структуру.

! Мы можем теперь писать алгоритмы, работающие с любыми структурами.