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

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

Версия от 21:56, 8 декабря 2009; 212.192.251.38 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Отсечение --- чи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) --- добавлять куда попало.

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

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

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


Введение в парадигмы программирования


01 02 03 04 05 06 07 08 09 10 11


Календарь

Сентябрь
24
Октябрь
01 08 15 22 29
Ноябрь
05 12 19 26
Декабрь
03

Экзамен по курсу пройдёт 10 декабря 2009 года в 18:00 в аудитории 524. | Список экзаменационных вопросов


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы