Парадигмы программирования, 08 лекция (от 12 ноября)

Материал из eSyr's wiki.

• Аудиозапись: http://esyr.org/lections/audio/paradigms_2009_winter/paradigms_09_11_12.manmachine.ogg

Отсечение --- отсекает все развилки выше.

Отсечение --- чиcто процедурная штука.

Отсечение позв. с одной стороны экономить время. С другой стороны... отсечение, в принципе, что такое: if then else, ... с другой стороны, отсечение штука нехорошая, поскольку убивает реверсивность предикатов --- не позв. исп. функция в разных предикатах. Вот, у нас был предикат member:

member(E, [E|_]).
member(E, [_|L]) :- member(E, L).

Что с этим можно сдлеать? Молжно спросить:

?- member(a, [b,a,c])
Yes

но можно сделать и так:

?- member(X, [b,a,c])
X=a
X=b
X=c
No

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

Есть предикат append. Он явл. истинным, если L есть конкатенация M и N.

append([], L, L).
append([X|L], M, [X|R]) :- append(L, M, R).

С этим предикатом интересная история --- он реверсится со страшной силой во все направления. Можно задать все три аргумента. Можно здаать первые два, а третий не дать.

? append([a,b], [1,2], X)
X=[a,b,1,2]
No

Можно не указать второе и третье:

? append([a,b], X, [a,b,c,d])
X=[1,2]
? append(X, Y, [a,b,c,d])
X=[], Y=[a,b,c,d]
X=[a], Y=[b,c,d]
X=[a,b], Y=[c,d]
X=[a,b,c], Y=[d]
X=[a,b,c,d], Y=[]

Мы получили это бесплатно, хотя изначально мы этого не хотели.

Так вот, как правило, если мы при написании предиката не ис.п вещи, которые с точки зрения считаются нехорошими, то предикат будет реверсивным. Если же такие вещи есть, то они реверсивность убивают. Среди них отсечение.

Так вот, del_all будет работать при первых трёх или первых двух прототипах, но никак иначе. А вот del_any работать будет. Не для всех трёх output, но, например, при отсутствии списка или элемента:

? del_any(X, L, [a,b,c])

Мы получим беск. последовательность списком. Работать он будет плохонько, но будет.

? del_any(1, L, [a,b,c])
L=[1,a,b,c]
L=[a,1,b,c]
...

Какие бывают ещё нехорошие вещи, Отрицание. not(...). Такое вот будет истинно в том и только в том случае, если не сущ. таких переменных, которые обр. в истину то, что внутри.

Тут есть ещё одна такая вещь: пролог действует из гипотезы о замкнутостим мира. Объяснять это долго, проще показать на примере:

human(vasya)
human(petya)
human(ivan)

При этом, если написать

?- not(human(sidor))
YES

Так как пролог считает, что всех людей знает.

not() не может стать причиной новых связей в контексте. Как раз таки наоборот: если какая-то значения получит решение, то дальше оно скорее всего не пойдёт, т. к. если получено знач, то найдено решение.

Вот есть у нас список людей, но мы не сможем перечислить всех, кто не явл. человеком:

? not(human(X))
...

Если not появлися в предикате, то реверсия он если и будет, то плохо и/или неправильно.

Что есть ещё: =\=, неравенство. Означает, что два терма неунифицируются.

Есть ещё одна интересная штука. Напишем предикат, вычисл. длину списка. Для этого нам пот. ввести ещё одну вещь.

len([], 0).
len([X|L], N) :- len(:, M), N=M+1.

Так мы получим не то, что хотели. Будет ли оно работать? Да, и вот как:

?- len([a,b,c],X)
X=0+1+1+1

В каком-то смысле правильно, но не то, чот мы хотели. (некоторые системы могут вообще посчитать ("((0+1)+1)+1"). Пролог не станет сам вычислять выражение.

Как же сделать так, чтобы пролог это вычислил --- написать is

len([], 0).
len([X|L], N) :- len(:, M), N is M+1.

Что такое is --- это предикат, который выч. правое выр. в ариф. смысле и сопост. с левым.

Тогда мы получим то, что хотели:

?- len([a,b,c],X)
X=3

Rfrbt tcnm juhfybxtybz e is? Попробуем сделать так:

len([], 0).
len([X|L], N) :- len(:, M), M is N-1.

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

Аналогичным свойствам обл. предикаты >, <, >=, <=. Только тут ещё хуже --- тут должны быть обе части вычислимы в ариф. смысле. И все перем. должны уже иметь знач. Соотв., как только какая-то из этих вещей появилась, реферса можно уже не ждать.

Интересно, в свой время лектор попытался написать простой одноместный предикат:

ten(X)

Что лектор хотел сделать --- чтобы он был истинен для 1..10. Простейший способ его написать — сделать так:

ten(1).
ten(2).
...
ten(10).

Но захотялось сделать без этого, что оказалось не так просто. Точнее, в случае, если аргумент дан, то просто:

ten(x) :- X < 11, X > 0.

Но хотелось, чтобы он реверсился:

? ten(N).

Первое, что лектор попробовал сделать:

naturals(1).
naturals(X) :- naturals(Y), X is Y+1.

Работает. Единственное, что при больших X работает долго, n^2/2 от аргумента.

ten(1).
ten(X) :- ten(Y), X is Y+1, Y<10.

Вроде работает, но есть один эффект: мы получим 1..10, после чего она уходит в беск. цикл., съедает весь стек и вываливается.

Поэтому такое решение не проходит, оно не делает то, что хочется лектору.

Следующее решение имело такой вид:

ten(1).
ten(X) :- ten(Y), !, X is Y+1, Y<10.

Рещение --- 1,2,No. Потому что нужные ошибки тоже пришиблись.

Наконец, лектор написал правильное решение, лектор сейчас покажет, как.

Есть такая вещь в прологе --- ";", дизъюнкция. Т. к. конъюнкция имеет более высокий приоритет, то ...:=...;... это всё равно что два правила с одной головой. Понятно, что можно ставить скобки и на этом как-то сыграть. Что получилось у лектора:

ten(1).
tex(X) :- teny(Y), X is Y+1, ((Y>=10,!fail);true).

Понятно, что происходит: если Y>=10, то оно отсекает все развилки и fail.

Можно написать чуть лучше. Есть предикат between, он истинен в случае, если третий арг. нах. между первым и вторым.

between(A,B,_) :- A>B, !, fail.
between(A,_,A).
between(A,B,C) :- A1 is A+1, between(A1, B, C).

Работает замечательно. На основе неё можно написать ten:

ten(X) :- beween(1,10,X).

Такие вот это бывают вещи, наруш. семантику. Значит ли это, что продог плохой? Отнюдь, он хорош для решения переборных задач. Например, задача ферзей. (в данном решении считается, что доска квадратная и каждый ферзь на своей линии)

queens(N, Result) :- do_queens(N, 0, [], Result).
do_queens(N,N,Res,Res).
do_queens(N,X,Cur,Res) :- X1 is X+1, next_queen(N,X1, Cur,Q), do_queens(N, X1, [Q|Cur], Rs).
no_attack(_, []).
no_attack(Q,[X|L]) :- not(attacks(Q,X)), no_attack(Q,L).
attacks(q(X,_),q(X,_)).
attacks(q(_,Y),q(_,Y)).
attacks(q(X1,Y1),q(X2,Y2)) :- D1 is X2-X1, D2 is Y2-Y1, (D1 is D2; D1 is 0-D2).
next_queen(N,X,AL,Q) :- between(1,N,Y), Q=q(X,Y), no_attack(Q, AL).

Теперь немного про непрологовские средства. Есть возм. изменять БД во время работы программы. Что такое БД --- набор фактов, то есть предложений, у которых нет из головы и есть только опред. пар.

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

Работа с файлами в прологе есть, сделана чёрте как.

Единственный вариант сделать так, чтобы вываливались только наши сообщения --- сделать посимв. воод-вывод.

• get(X) --- читает посимвольно, пропуская проеблы
• get0(X) --- не пропускает
• name( , ) --- gjpd/ cnhjre gthtltkfnm d fnjv/

• assert(F) --- добавить факт F в БД.
• assertA(F) --- добавить факт F в БД.
• assertZ(F) --- добавить факт F в БД.

В чём разница? Факты в предикате могут стоять в разном порядке имеет значение. assertA добавляет в начало, assertZ --- в конец, assert --- куда попало.

• retract(F) --- добавлять куда попало.

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

По прологу, наверное, всё.

След. лекция будет посв. языку рефал.

del_any, del_all.	del_all, вариант с отсечением.	Реверсивность append.
Реверсивность append.	Гипотеза о замкнутости универсума в Прологе.	not.
Вычисление длины списка.	Вычисление длины списка: результат вызова.	Вычисление длины списка, исправленная версия.
Вычисление длины списка, исправленная версия: результат вызова.	ten, первый вариант.	naturals.
ten, второй вариант.	ten, финальный вариант.	between.
queens, часть первая.	queens, часть вторая.	queens, часть третья.
queens, часть четвёртая.	queens.	assert, retract.