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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

* '''Аудиозапись:''' 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) --- добавлять куда попало.

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

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

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

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%B8%D0%B3%D0%BC%D1%8B_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%2C_08_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_12_%D0%BD%D0%BE%D1%8F%D0%B1%D1%80%D1%8F%29

@@ Строка 212: / Строка 212: @@
 След. лекция будет посв. языку рефал.
-<gallery widths="240" heights="150" perrow="3">
-Image:Paradigm 091112 01.jpg|del_any, del_all.
-Image:Paradigm 091112 02.jpg|del_all, вариант с отсечением.
-Image:Paradigm 091112 03.jpg|Реверсивность append.
-Image:Paradigm 091112 04.jpg|Реверсивность append.
-Image:Paradigm 091112 05.jpg|Гипотеза о замкнутости универсума в Прологе.
-Image:Paradigm 091112 06.jpg|not.
-Image:Paradigm 091112 07.jpg|Вычисление длины списка.
-Image:Paradigm 091112 08.jpg|Вычисление длины списка: результат вызова.
-Image:Paradigm 091112 09.jpg|Вычисление длины списка, исправленная версия.
-Image:Paradigm 091112 10.jpg|Вычисление длины списка, исправленная версия: результат вызова.
-Image:Paradigm 091112 11.jpg|ten, первый вариант.
-Image:Paradigm 091112 12.jpg|naturals.
-Image:Paradigm 091112 13.jpg|ten, второй вариант.
-Image:Paradigm 091112 14.jpg|ten, финальный вариант.
-Image:Paradigm 091112 15.jpg|between.
-Image:Paradigm 091112 16.jpg|queens, часть первая.
-Image:Paradigm 091112 17.jpg|queens, часть вторая.
-Image:Paradigm 091112 18.jpg|queens, часть третья.
-Image:Paradigm 091112 19.jpg|queens, часть четвёртая.
-Image:Paradigm 091112 20.jpg|queens.
-Image:Paradigm 091112 21.jpg|assert, retract.
-</gallery>
 {{Парадигмы программирования}}
 {{Lection-stub}}

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты