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

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

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

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

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

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

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

Отсечение позв. с одной стороны эконопить время. С другой стороны... отсечение, в принципе, что такое: 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) --- добавлять куда попало.

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

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

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

<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>

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

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

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

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

Получено с http://esyr.us/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

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

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

Просмотры

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

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 3: / Строка 3: @@
 Отсечение --- отсекает все развилки выше.
-Отсечение --- чиcто процедурная штука.
+Отсечение --- чито процедурная штука.
-Отсечение позв. с одной стороны экономить время. С другой стороны... отсечение, в принципе, что такое: if then else, ... с другой стороны, отсечение штука нехорошая, поскольку убивает реверсивность предикатов --- не позв. исп. функция в разных предикатах. Вот, у нас был предикат member:
+Отсечение позв. с одной стороны эконопить время. С другой стороны... отсечение, в принципе, что такое: if then else, ... с другой стороны, отсечение штука нехорошая, поскольку убивает реверсивность предикатов --- не позв. исп. функция в разных предикатах. Вот, у нас был предикат member:
  member(E, [E|_]).
@@ Строка 82: / Строка 82: @@
  ...
-Если not появлися в предикате, то реверсия он если и будет, то плохо и/или неправильно.
+Если not появлися в предикате, то реверсится он если и будет, то плохо и/или неправильно.
 Что есть ещё: =\=, неравенство. Означает, что два терма неунифицируются.