Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 105
Блин, вроде и статья классная.
Но названия функций глаз режут
Но названия функций глаз режут
formula(X1, X2, X3, X4, X5, X6, Sign1, Sign2, Sign3, Sign4, Sign5, Result):-
operacia(X1, X2, Sign1, PartialResult1),
Джин в контексте логического программирования напомнил об Акинаторе. Убилось полчаса рабочего времени.
На самом Prolog в правила можно встраивать стратегии обхода графа. Выставлять «флаги», чтобы не зацикливаться. Можно использовать оператор отсечения "!". Есть такая книжка 1980г (?) гуглится «братко пролог». В ней много чего рассматривалось. Да и в мануалах Visual Prolog чего-то было.
Возможно стратегии перебора можно менять в новых языках. Сейчас появилось много похожих на Prolog языков. Интересно было бы узнать про их возможности.
Возможно стратегии перебора можно менять в новых языках. Сейчас появилось много похожих на Prolog языков. Интересно было бы узнать про их возможности.
Нужно понимать, что «классический» Пролог просто перебирает все варианты подряд поиском в глубину с возвратами. Тех же ферзей на большой доске не расставишь.
Современные системы, основанные на Прологе, гораздо умнее. Главное достижение — constraint logic programming, которое использует интересные алгоритмы для отсечения больших частей дерева поиска. Как пример использования — мое решение Greater Than Sudoku: sdymchenko.com/blog/2015/01/04/greater-than-sudoku-clp/
Еще есть такая интересная вещь, как tabling — вариант эффективной автоматической мемоизации логических программ, использование которого позволяет избегать «зацикливания» и декларативно реализовывать алгоритмы динамического программирования. Пример: sdymchenko.com/blog/2014/12/09/aaaaaa-bprolog/
Современные системы, основанные на Прологе, гораздо умнее. Главное достижение — constraint logic programming, которое использует интересные алгоритмы для отсечения больших частей дерева поиска. Как пример использования — мое решение Greater Than Sudoku: sdymchenko.com/blog/2015/01/04/greater-than-sudoku-clp/
Еще есть такая интересная вещь, как tabling — вариант эффективной автоматической мемоизации логических программ, использование которого позволяет избегать «зацикливания» и декларативно реализовывать алгоритмы динамического программирования. Пример: sdymchenko.com/blog/2014/12/09/aaaaaa-bprolog/
Как пример использования — мое решение Greater Than SudokuСудоку — неинтересный пример. Эта задача слишком легко решается на любом языке. Если головоломки любопытны, то мне было бы гораздо интереснее увидеть декларативное решение некоторых других задач (за приемлемое время). Например, Какуро или Забор. Для них разновидности полного перебора очень плохо работают.
Greater Than Sudoku — это не обычное Sudoku, а совсем другая головоломка.
Да и для решения обычного Sudoku, как учит нас Питер Норвиг norvig.com/sudoku.html, надо реализовать constraint propagation и поиск. Это не очень сложно в случае Sudoku, но в поддерживающих constraint logic programming системах уже реализовано и отлажено.
Для Какуро вот решения от Hakan Kjellerstrand: www.hakank.org/eclipse/kakuro.ecl (ECLiPSe) и www.hakank.org/bprolog/kakuro.pl (B-Prolog).
Для Забора с ходу не найду основанных на Прологе решений, но вроде бы задача идеально подходит для constraint logic programming. Попробую написать решение, как будет время.
Да и для решения обычного Sudoku, как учит нас Питер Норвиг norvig.com/sudoku.html, надо реализовать constraint propagation и поиск. Это не очень сложно в случае Sudoku, но в поддерживающих constraint logic programming системах уже реализовано и отлажено.
Для Какуро вот решения от Hakan Kjellerstrand: www.hakank.org/eclipse/kakuro.ecl (ECLiPSe) и www.hakank.org/bprolog/kakuro.pl (B-Prolog).
Для Забора с ходу не найду основанных на Прологе решений, но вроде бы задача идеально подходит для constraint logic programming. Попробую написать решение, как будет время.
Да и для решения обычного Sudoku, как учит нас Питер Норвиг norvig.com/sudoku.html, надо реализовать constraint propagation и поиск.Пара умных терминов и все выглядит уже по-научному. Не знаю насчет Норвига, но простейшая рекурсия с судоку работает на ура.
Greater Than Sudoku — это не обычное Sudoku, а совсем другая головоломка.
Я знаю :). Просто в способе программирования от обычного судоку она ничем существенным не отличается.
Для Какуро вот решения от Hakan Kjellerstrand
Спасибо. Теперь вот непонятно, у себя что ли пролог развернуть. Хочется посмотреть, как это будет на сетке нормального размера отрабатывать. А то для приведенного примера вручную решить быстрее, чем текст условия набивать :)
А может быть где-то в сети есть возможность побаловаться?
Помню, что в свое время написал на Прологе алгоритм для решения «задачи Эйнштейна»
Пролог — это язык программирования общего назначения, или DSL?
Вот заминусовали человека ни за что. Общего назначения.
А если он общего назначения, то как на нём выглядят не-DSL задачи? Скажем, «принять с командной порт, на котором слушать, принять по tcp список строк с указанного порта, вывести его на stdout».
Примерно так.
Спасибо.
Процитирую тут:
Обычный императивный язык, в котором операторы разделяются запятыми…
Процитирую тут:
server(Port) :-
tcp_socket(Socket),
tcp_bind(Socket, Port),
tcp_listen(Socket, 5),
tcp_open_socket(Socket, In, _Out),
add_stream_to_pool(In, accept(Socket)),
stream_pool_main_loop.
accept(Socket) :-
tcp_accept(Socket, Slave, Peer),
tcp_open_socket(Slave, In, Out),
add_stream_to_pool(In, client(In, Out, Peer)).
client(In, Out, _Peer) :-
read_line_to_codes(In, Command),
close(In),
format(Out, 'Please to meet you: ~s~n', [Command]),
close(Out),
delete_stream_from_pool(In).
Обычный императивный язык, в котором операторы разделяются запятыми…
Ну, это только с первого взгляда так кажется.В Prolog-е нет таких понятий, как присвоение переменных и вызов функций. Всё описывается в виде отношений между сущностями и безусловных фактов о сущностях. Например, A = stdio::read() концептуально означает «существует A, совпадающая с тем что ввёл пользователь в консоль», это не присвоение переменной. Точно также, operation(X1, X2, "+", Result) :- Result = X1 + X2 — это не вызов функции и не присвоение Result суммы X1 + X2. Почитайте статью (я уверен, что вы её не читали), там в первом примере есть описание отношения формулы и операций, с первого взгляда может показаться, что это обычный вызов функции, в котором операторы разделяются запятыми, но по ходу разбора примера становится очевидно, что это не так.
Всё, что можно решить на прологе, можно решить ничуть не труднее на любом другом яву.
Я бы перефразировал, отладить в разы сложнее (особенно когда идут оптимизации и т.п.). Но написать в разы проще, если конечно знаешь что писать. К сожалению образование слишком зациклено именно на алгоритмах: расскажи как ты будешь считать, а потом запиши. Пролог работает абсолютно задачи — формализируй задачу на языке логики, а затем правильно напиши в синтаксисе Пролог.
Стоит отметить, что не все логические задачи решаются пролог, так как он поддерживает не поддерживает логического not().
Стоит отметить, что не все логические задачи решаются пролог, так как он поддерживает не поддерживает логического not().
не поддерживает логического not().
Не могли бы вы пожалуйста указать источник, в котором это сказано?
Гугл считает иначе, выводя первой ссылкой описание оператора отрицания, да и в статье есть пример его использования:
dontAttack(X1, Y1, X2, Y2) :-
any(X1), any(Y1), any(X2), any(Y2), not(attack(X1, Y1, X2, Y2)).
Это не логическое not. По факту оно выражено с предикатом fail и отсечением, что совсем не логическая операция.
Вот здесь проводил ту же дискуссию habrahabr.ru/post/124636/#comment_4103212
Если бы отрицание было действительно логическим то в Прологе бы допускалась запись вида:
A;B;C :- D, E, F.
В принципе появление логического отрицания равносильно появлению логического Или.
А так Пролог ограничен хорновскими дизъюнктами и частичным методом линейной резолюции.
Вот здесь проводил ту же дискуссию habrahabr.ru/post/124636/#comment_4103212
Если бы отрицание было действительно логическим то в Прологе бы допускалась запись вида:
A;B;C :- D, E, F.
В принципе появление логического отрицания равносильно появлению логического Или.
А так Пролог ограничен хорновскими дизъюнктами и частичным методом линейной резолюции.
Это не логическое not.
Приведенный пример означает: dontAttack истина, если не истина attack. Поскольку это единственное правило, описывающее dontAttack с данным набором параметров, то во всех остальных случаях (если attack выполняется), правило dontAttack не выполняется (ложно). Это поведение соответствует оператору отрицания, так как true переходит в false, а false в true.
Почитал дискуссию, судя по всему у вас не получилось описать правило «если А истинно, то Б ложно», поэтому вы утверждаете, что в Прологе отсутствует логическое отрицание. Я правильно вас понял?
Да его нельзя описать. Так же как нельзя доказать следующее правило.
B :- not(A). % A or B, можно записать not(A) :-B. но в методе линейной резолюции обычно пишем (A;B).
B.
:- A (fail, хотя не должен ).
Если бы мы записали это в логическом выражении то это эквивалентно
Пример может быть очень простой. Математическая индукция.
f(X) :- f(1), (f(N) -> f(N+1)).
или что равносильно
или что равносильно
f(N); f(X) :- f(1), f(N+1).
В общем-то, что означает, что никакую теорему методом индукции мы не докажем, даже если сможем поддерживать конструкцию высшего порядка, добавляя это правило ко всем формулам. Хотя метод резолюций применим для данных случаев.
B :- not(A). % A or B, можно записать not(A) :-B. но в методе линейной резолюции обычно пишем (A;B).
B.
:- A (fail, хотя не должен ).
Если бы мы записали это в логическом выражении то это эквивалентно
Пример может быть очень простой. Математическая индукция.
f(X) :- f(1), (f(N) -> f(N+1)).
или что равносильно
или что равносильно
f(N); f(X) :- f(1), f(N+1).
В общем-то, что означает, что никакую теорему методом индукции мы не докажем, даже если сможем поддерживать конструкцию высшего порядка, добавляя это правило ко всем формулам. Хотя метод резолюций применим для данных случаев.
Синтаксис пролога запрещает использовать оператор отрицания следующим образом: not(b(X)) :- <Условие>. Однако ничего не мешает определить новый предикат notB(X) и сказать, что одновременная истинность b(X) и notB(X) приводит к противоречию.
Пример 1
1)Если А ложно, то B ложно
2)А истинно относительно человека с именем «Johnson»
3)B истинно относительно «Smith»
Вывод программы:
A true for Smith
A true for Johnson
Пример 2
1)Если А истинно, то B ложно
2)А истинно относительно «Johnson»
3)А истинно относительно «Smith»
4)B истинно относительно «Smith»
Вывод программы:
Только «A true for Johnson», потому что истинность A для «Smith» приводит к противоречию.
Имхо, если у вас когда-то что-то не получилось, то это не повод заявлять, что это принципиально невозможно и вводить людей в заблуждение.
Пример 1
1)Если А ложно, то B ложно
2)А истинно относительно человека с именем «Johnson»
3)B истинно относительно «Smith»
Исходный код
implement main
open core
class predicates
man:(string) nondeterm anyflow.
aOutput:(string) nondeterm anyflow.
a: (string) nondeterm anyflow.
b:(string) nondeterm(i) nondeterm(o).
notB:(string) nondeterm(i) nondeterm(o).
notBOutput:(string) nondeterm(i) nondeterm(o).
conflict:(string) nondeterm anyflow.
conflictOutput:(string) nondeterm anyflow.
question:() procedure.
clauses
man(«Smith»).
man(«Lucas»).
man(«Johnson»).
a(«Johnson»).
notB(X) :- man(X), not(a(X)).
notBOutput(X) :- man(X), not(aOutput(X)).
conflict(X) :- b(X), notB(X).
aOutput(X) :- man(X), not(a(X)), conflict(X). %A истинно, если ложность A приводит к противоречию
aOutput(X) :- a(X).
/*Дробление A на a и aOutput возникло из-за проблем с зацикливанием, о которых я уже писал.
Далее, если нужно указать почему A истинно, то следует использовать a, во всех остальных случаях — aOutput*/
conflictOutput(X) :- b(X), notBOutput(X).
b(«Smith»).
question() :-
aOutput(X),
not(conflictOutput(X)),
stdio::write(«A true for », X),
stdio::nl,
fail.
question().
run() :- question(), stdio::write(«End»), _ = stdio::readChar().
end implement main
goal
console::runUtf8(main::run).
open core
class predicates
man:(string) nondeterm anyflow.
aOutput:(string) nondeterm anyflow.
a: (string) nondeterm anyflow.
b:(string) nondeterm(i) nondeterm(o).
notB:(string) nondeterm(i) nondeterm(o).
notBOutput:(string) nondeterm(i) nondeterm(o).
conflict:(string) nondeterm anyflow.
conflictOutput:(string) nondeterm anyflow.
question:() procedure.
clauses
man(«Smith»).
man(«Lucas»).
man(«Johnson»).
a(«Johnson»).
notB(X) :- man(X), not(a(X)).
notBOutput(X) :- man(X), not(aOutput(X)).
conflict(X) :- b(X), notB(X).
aOutput(X) :- man(X), not(a(X)), conflict(X). %A истинно, если ложность A приводит к противоречию
aOutput(X) :- a(X).
/*Дробление A на a и aOutput возникло из-за проблем с зацикливанием, о которых я уже писал.
Далее, если нужно указать почему A истинно, то следует использовать a, во всех остальных случаях — aOutput*/
conflictOutput(X) :- b(X), notBOutput(X).
b(«Smith»).
question() :-
aOutput(X),
not(conflictOutput(X)),
stdio::write(«A true for », X),
stdio::nl,
fail.
question().
run() :- question(), stdio::write(«End»), _ = stdio::readChar().
end implement main
goal
console::runUtf8(main::run).
Вывод программы:
A true for Smith
A true for Johnson
Пример 2
1)Если А истинно, то B ложно
2)А истинно относительно «Johnson»
3)А истинно относительно «Smith»
4)B истинно относительно «Smith»
Исходный код
implement main
open core
class predicates
man:(string) nondeterm anyflow.
aOutput:(string) nondeterm anyflow.
a: (string) nondeterm anyflow.
b:(string) nondeterm(i) nondeterm(o).
notB:(string) nondeterm(i) nondeterm(o).
notBOutput:(string) nondeterm(i) nondeterm(o).
conflict:(string) nondeterm anyflow.
conflictOutput:(string) nondeterm anyflow.
question:() procedure.
clauses
man(«Smith»).
man(«Lucas»).
man(«Johnson»).
a(«Johnson»).
a(«Smith»).
notB(X) :- a(X).
notBOutput(X) :- aOutput(X).
conflict(X) :- b(X), notB(X).
aOutput(X) :- man(X), not(a(X)), conflict(X). %A истинно, если ложность A приводит к противоречию
aOutput(X) :- a(X).
/*Дробление A на a и aOutput возникло из-за проблем с зацикливанием, о которых я уже писал.
Далее, если нужно указать почему A истинно, то следует использовать a, во всех остальных случаях — aOutput*/
conflictOutput(X) :- b(X), notBOutput(X).
b(«Smith»).
question() :-
aOutput(X),
not(conflictOutput(X)),
stdio::write(«A true for », X),
stdio::nl,
fail.
question().
run() :- question(), stdio::write(«End»), _ = stdio::readChar().
end implement main
goal
console::runUtf8(main::run).
open core
class predicates
man:(string) nondeterm anyflow.
aOutput:(string) nondeterm anyflow.
a: (string) nondeterm anyflow.
b:(string) nondeterm(i) nondeterm(o).
notB:(string) nondeterm(i) nondeterm(o).
notBOutput:(string) nondeterm(i) nondeterm(o).
conflict:(string) nondeterm anyflow.
conflictOutput:(string) nondeterm anyflow.
question:() procedure.
clauses
man(«Smith»).
man(«Lucas»).
man(«Johnson»).
a(«Johnson»).
a(«Smith»).
notB(X) :- a(X).
notBOutput(X) :- aOutput(X).
conflict(X) :- b(X), notB(X).
aOutput(X) :- man(X), not(a(X)), conflict(X). %A истинно, если ложность A приводит к противоречию
aOutput(X) :- a(X).
/*Дробление A на a и aOutput возникло из-за проблем с зацикливанием, о которых я уже писал.
Далее, если нужно указать почему A истинно, то следует использовать a, во всех остальных случаях — aOutput*/
conflictOutput(X) :- b(X), notBOutput(X).
b(«Smith»).
question() :-
aOutput(X),
not(conflictOutput(X)),
stdio::write(«A true for », X),
stdio::nl,
fail.
question().
run() :- question(), stdio::write(«End»), _ = stdio::readChar().
end implement main
goal
console::runUtf8(main::run).
Вывод программы:
Только «A true for Johnson», потому что истинность A для «Smith» приводит к противоречию.
Имхо, если у вас когда-то что-то не получилось, то это не повод заявлять, что это принципиально невозможно и вводить людей в заблуждение.
Я думаю, «принципиально» слово имеет не негативный, а концептуальный. То, что not иногда выдает «правильные» результаты, абсолютно не делает его логичным.
Я советую вернуться к проблеме доказательства теорем, которая гораздо полнее раскрывает Пролог, и попытаться доказать хоть одну используя принцип индукции. По поводу самого отрицания это не мои выдумки, во-первых подверждения отсутствия отрицания и его введения (Negotation as failure) en.wikipedia.org/wiki/Logic_programming (там же Note that the above example uses true mathematical negation, which cannot be expressed in Prolog.).
Да и подумайте логически, известно что Пролог поддерживает только Хорновские дизъюнкты! Если бы он покрывал все случаи, имело бы смысл вводить разные виды Линейных резолюций для доказательства теорем.
Вот здесь опять же идет такой же вопрос (http://computer-programming-forum.com/55-prolog/494c1f9057062af8.htm)
и приводится ссылка на (See Mark Stickel's papers on his «Prolog Technology Theorem Prover» for one approach.).
Я советую вернуться к проблеме доказательства теорем, которая гораздо полнее раскрывает Пролог, и попытаться доказать хоть одну используя принцип индукции. По поводу самого отрицания это не мои выдумки, во-первых подверждения отсутствия отрицания и его введения (Negotation as failure) en.wikipedia.org/wiki/Logic_programming (там же Note that the above example uses true mathematical negation, which cannot be expressed in Prolog.).
Да и подумайте логически, известно что Пролог поддерживает только Хорновские дизъюнкты! Если бы он покрывал все случаи, имело бы смысл вводить разные виды Линейных резолюций для доказательства теорем.
Вот здесь опять же идет такой же вопрос (http://computer-programming-forum.com/55-prolog/494c1f9057062af8.htm)
и приводится ссылка на (See Mark Stickel's papers on his «Prolog Technology Theorem Prover» for one approach.).
Предполагаю, вот простейший логический пример не работающий в Прологе.
~b -> a.( b \/ a)
b -> c. (~b \/ c)
c -> a. (~c \/ a)
Вопрос верно ли :-a? Ответ нет, но правильный ответ, да a верно.
В синтаксисе Пролога можно записать так
a :- not(b).
c :- b.
a :- c.
?- a.
~b -> a.( b \/ a)
b -> c. (~b \/ c)
c -> a. (~c \/ a)
Вопрос верно ли :-a? Ответ нет, но правильный ответ, да a верно.
В синтаксисе Пролога можно записать так
a :- not(b).
c :- b.
a :- c.
?- a.
not(A(X)) работает следующим образом: если prolog не может доказать верность A(X), то not(A(X)) считается истинным, в противном случае — ложным. Это поведение отличается от классического инвертирования булевой переменной, поэтому not в логическом программировании получил название «negation as failure».
Нашёл по приведённой вами ссылке следующий текст:
что переводится как
То есть тут описывается как работает в Prolog-е not и говорится, что это не тоже самое, что и инвертирование булевой переменной, что вполне логично: в Prolog-е нет присвоения переменных, следовательно нет и инвертирования переменных.
Далее говорится следующее:
что переводится как
Таким образом, в приведенном вами источнике сказано, что not — это логическое отрицание.
По поводу примера, который вы привели: уверен, что Prolog скажет, что A истинно. Prolog не сможет доказать истинность B (т.к. не описано правило по которому оно истинно), следовательно not(B) истинно, из чего следует истинность A согласно правилу 1. Могу написать код, если у вас остались сомнения.
Нашёл по приведённой вами ссылке следующий текст:
In Planner, negation as failure could be implemented as follows:
if (not (goal p)), then (assert ¬p)
which says that if an exhaustive search to prove p fails, then assert ¬p.[1] Note that the above example uses true mathematical negation, which cannot be expressed in Prolog.
что переводится как
Negation as failure (то есть not) может быть написан на Planner-е так: if (not (goal p)), then (assert ¬p), что означает: если не удалось доказать истинность p, тогда говорим что отрицание от p истинно (под отрицанием здесь понимается инвертирование булевой переменной). Обратите внимание, что описанный выше пример использует классическое математическое отрицание (то есть инвертирование булевой переменной), которое невозможно описать на прологе.
То есть тут описывается как работает в Prolog-е not и говорится, что это не тоже самое, что и инвертирование булевой переменной, что вполне логично: в Prolog-е нет присвоения переменных, следовательно нет и инвертирования переменных.
Далее говорится следующее:
The logical status of negation as failure was unresolved until Keith Clark [1978] showed that, under certain natural conditions, it is a correct (and sometimes complete) implementation of classical negation with respect to the completion of the program.
что переводится как
Статус negation as failure (то есть not) был непонятен до тех пор, пока Кейф Кларк в 1978 не доказал, что not это правильная реализация классического отрицания.
Таким образом, в приведенном вами источнике сказано, что not — это логическое отрицание.
По поводу примера, который вы привели: уверен, что Prolog скажет, что A истинно. Prolog не сможет доказать истинность B (т.к. не описано правило по которому оно истинно), следовательно not(B) истинно, из чего следует истинность A согласно правилу 1. Могу написать код, если у вас остались сомнения.
Всё, что можно решить на %programming_language%, можно решить ничуть не труднее на любом другом яву.
Что значит «не труднее» в этом контексте? Затрата времени? Что-то еще?
Описать факты и попросить найти ответ легче, чем описывать логику поиска на, скажем, императивном языке.
Описать факты и попросить найти ответ легче, чем описывать логику поиска на, скажем, императивном языке.
ничуть не труднее
«Не труднее» — это фактически написав мини-эмулятор Prolog'а на Яве lol
Согласно тезису Тьюринга, для любых двух полнотьюринговых языков А и Б: все, что можно решить на А, можно решить и на Б.
Только вот про «трудность» там ничего нет.
Трудность — понятие очень субъективное. Я, например, не могу жить без глобальных переменных и указателей, а кто-то не может жить без лямбд или объектов.
Давно уже выявлено и доказано, что в случае неопределённого результата (например, тупо не хватает входных данных) Prolog выдаёт ложные результаты. Потому он и не имеет практического применения.
Prolog не вводит в заблуждение. Если необходимо доказать гипотезу, то пролог либо выведет её доказательство, либо скажет что не смог его найти (и тогда Prolog-у нужно будет добавить входных фактов). Если нужно опровергнуть гипотезу, то просто немного по-другому задаётся главный вопрос. Ошибиться можно, только если истолковать ответ Prolog-а «я не смог найти доказательство» как «гипотеза не верна», но тут программист сам себе злой чебурашка, и дело совсем не в языке.
Для построения экспертных систем может использоваться не бинарная логика, а логика «истина»/«ложь»/«неизвестность», или её расширенный вариант «истина»/«ложь»/«неизвестность»/«абсурд». Встречается также использование вероятностей вместо «истина»/«ложь».
А что Пролог способен со всеми этими однозначностями реально поделать?
(Хотелось бы увидеть ясный пример того как Пролог подобным оперирует, а не просто минусы за критику вместо реальных аргументов)
А что Пролог способен со всеми этими однозначностями реально поделать?
(Хотелось бы увидеть ясный пример того как Пролог подобным оперирует, а не просто минусы за критику вместо реальных аргументов)
Давно дело было, но читал упоминания Fuzzy Prolog.
Ух ты! Отлично! БОЛЬШУЩЕЕ СПАСИБО!
Именно ограниченность Пролога бинарной логикой — явилось причиной того, что я его в своё время разочаровавшись в нём бросил…
PS Было очень здорово прочитать цикл статей по Fuzzy Prolog.
Именно ограниченность Пролога бинарной логикой — явилось причиной того, что я его в своё время разочаровавшись в нём бросил…
PS Было очень здорово прочитать цикл статей по Fuzzy Prolog.
Надеюсь, у вас хватит энтузиазма разобраться и написать статью. С удовольствием прочту. А многозначную логику можно и на прологе написать. Т.к. он тьюринг-полный на нем всё можно написать. Только местами громоздко будет.
>А многозначную логику можно и на прологе написать
Пример не приведёте? (статью?)
Пример не приведёте? (статью?)
>Надеюсь, у вас хватит энтузиазма разобраться и написать статью.
Погуглил про Fuzzy Prolog. Большая часть результатов — состоит из ссылок на статью «Fuzzy Prolog: A Simple General Implementation Using CLP®». Попытки найти интерпретатор или компилятор ведут на тему www.computer-programming-forum.com/55-prolog/e842ceba994dadd9.htm из единственного сообщения без ответа. Похоже мне чтобы попробовать Fuzzy Prolog нужно будет сначала написать самому эмулятор этого языка (смогу взяться за это только летом).
Погуглил про Fuzzy Prolog. Большая часть результатов — состоит из ссылок на статью «Fuzzy Prolog: A Simple General Implementation Using CLP®». Попытки найти интерпретатор или компилятор ведут на тему www.computer-programming-forum.com/55-prolog/e842ceba994dadd9.htm из единственного сообщения без ответа. Похоже мне чтобы попробовать Fuzzy Prolog нужно будет сначала написать самому эмулятор этого языка (смогу взяться за это только летом).
Было бы полезнее и интереснее почитать статью про новый более перспективный язык, не имеющий недостатков Prolog'а, а не про эту старую «логическую игрушку».
PS Когда-то, будучи студентом, я тоже игрался с Prolog'ом. Но, прочитав об его недостатках, являющихся по причине концепции Prolog'а врождёнными непреодолимыми дефектами — бросил это бесперспективное занятие.
PS Когда-то, будучи студентом, я тоже игрался с Prolog'ом. Но, прочитав об его недостатках, являющихся по причине концепции Prolog'а врождёнными непреодолимыми дефектами — бросил это бесперспективное занятие.
Ну, бороться с зацикливаниями на уровне языка как раз таки можно — при каждом вызове функции (обходе факта или предиката) проверяем нет ли зацикливания -> если есть кидаем исключение -> перехватываем там где зацикливание началось -> перебираем факты дальше не заходя в зацикливающую ветвь. Если бы были под рукой исходники компилятора, быстро бы решил проблему. В остальном претензий к языку нет.
Первый компилятор Prolog'а был написан на Prolog.
Аналогично Алан Кей:
«До меня наконец дошло, что полстраницы кода внизу тринадцатой страницы пособия по LISP 1.5 — это LISP, написанный сам на себе. Для разработки софта это как уравнения Максвелла — для физики»
Аналогично Алан Кей:
«До меня наконец дошло, что полстраницы кода внизу тринадцатой страницы пособия по LISP 1.5 — это LISP, написанный сам на себе. Для разработки софта это как уравнения Максвелла — для физики»
>Первый компилятор Prolog'а был написан на Prolog
Можно подробнее? Точно компилятор, а не интерпретатор?
(Работал с Turbo-Prolog, но там даже и близко нет какой-либо возможности написать компилятор).
Можно подробнее? Точно компилятор, а не интерпретатор?
(Работал с Turbo-Prolog, но там даже и близко нет какой-либо возможности написать компилятор).
Хороший вопрос. Даже не знаю где сейчас уточнить. А сей факт в моей голове уже лет двадцать. Может из книги Братко?
Ведь сама программа на прологе — это структура данных. Ее компилировать не нужно. Максимум — транслировать в бинарные данные.
На прологе легко писать парсеры, которые переведут один набор данных в другой (что-то вроде паттерна Visitor). А выходной набор может быть в виде целых чисел, которые можно вытолкнуть в двоичный поток и получить .com файл.
Ведь сама программа на прологе — это структура данных. Ее компилировать не нужно. Максимум — транслировать в бинарные данные.
На прологе легко писать парсеры, которые переведут один набор данных в другой (что-то вроде паттерна Visitor). А выходной набор может быть в виде целых чисел, которые можно вытолкнуть в двоичный поток и получить .com файл.
Turbo Prolog компилирует.
Я про возможность написания самого компилятора. Как это возможно сделать на декларативном языке? С интерпретатором на декларативном языке — всё понятно. Но, как писать на таком языке компилятор?
Ну а как на Прологе пишут любые программы вида «игра в шашки», которые сложно представить вообще вне императивной парадигмы? Все т. полное, значит, можно реализовать нужные конкструкции. Я в Прологе не спец, но помню работу со списками вида «вставить элемент»/«Удалить»/«найти элемент». Тоже сперва кажется нереальным, потом понимаешь, что к чему.
Шашки с полноценным графическим интерфейсом? Или с буквенно-цифровым типа «e2-e4»?
Какая разница? Мы вопрос принципиальной возможности написания программ, которые обычно на императивных языках реализуются, обсуждаем, или вопрос трудоемкости?
Как какая разница?! Программы имеющие практическое использование пишутся для пользователя. Так что раз тут в этой теме обсуждается в том числе и практическая используемость Пролога, то вопрос написания программы с нормальным пользовательским интерфейсом — важен! Вы же не будете предлагать пользователю для использования программы каждый раз вводить команды Пролога.
Вы акцентируете внимание на несущественном.
На пролог очень компактными (и понятными!) получаются комбинаторные решения. Те же шашки, например.
Речь о том, что «любая серьезная программа содержит в себе LISP интерпретатора и код на LISP». Т.е. если вы будете писать переборный алгоритм, например на Си, вам придется написать свою реализацию Prolog, чаще урезанную, и еще код ограничений для перебора всех вариантов. Так зачем писать этот код, когда можно взять готовый Prolog и написать только ограничения перебора?
На пролог очень компактными (и понятными!) получаются комбинаторные решения. Те же шашки, например.
Речь о том, что «любая серьезная программа содержит в себе LISP интерпретатора и код на LISP». Т.е. если вы будете писать переборный алгоритм, например на Си, вам придется написать свою реализацию Prolog, чаще урезанную, и еще код ограничений для перебора всех вариантов. Так зачем писать этот код, когда можно взять готовый Prolog и написать только ограничения перебора?
С точки зрения практического использования — напротив существенно! Пользователю — абсолютно не важно, как и что внутренне реализовано. Пользователь — желает иметь дружественный интерфейс и удобное представление результатов.
Я не могу на SQL создать нормальный пользовательский интерфейс. Но, я могу из внешней программы с нормальным пользовательским интерфейсом обратиться к SQL-серверу, и отправив туда SQL-запрос, получить нужные результаты, а затем посредством внешней программы представить полученные результаты в нужной пользователю форме.
А я могу через внешнюю программу с интерфейсом точно также обратиться к Prolog-серверу?
Я не могу на SQL создать нормальный пользовательский интерфейс. Но, я могу из внешней программы с нормальным пользовательским интерфейсом обратиться к SQL-серверу, и отправив туда SQL-запрос, получить нужные результаты, а затем посредством внешней программы представить полученные результаты в нужной пользователю форме.
А я могу через внешнюю программу с интерфейсом точно также обратиться к Prolog-серверу?
Да. Например, гляньте Yield Prolog. Есть для C#, Python и JavaScript.
И еще полно библиотек разных реализаций подключаемых через DLL.
И еще полно библиотек разных реализаций подключаемых через DLL.
Было бы хорошо показать это на примерах (а ещё лучше в виде обстоятельной статьи).
Я думаю, человечество ещё не доросло до Пролога. В 90-е годы многие восхваляли ООП и смотрели на Лисп, как на экзотического зверя, который никому не нужен. А теперь языку общего назначения стыдно не иметь лямбд. Доросли, значит. Есть ощущение, что и время Пролога придёт.
Хочу попробовать написать что-то на Прологе. В статье речь идет о Visual Prolog, как я понимаю он исполняется только на Windows.
Если у вас есть опыт, то подскажите современную реализацию пролога что бы запускалась на Linux/Mac, ну и IDE (вот что нагуглил), если есть специализированную.
Если у вас есть опыт, то подскажите современную реализацию пролога что бы запускалась на Linux/Mac, ну и IDE (вот что нагуглил), если есть специализированную.
SWI-Prolog более популярный и имеет больше не связанных с логикой фич типа веб-разработки и т.п. В ECLiPSe лучше constraint programming. В B-Prolog есть tabling. Я постоянно пользуюсь этими тремя реализациями (SWI-Prolog в основном для ответов на StackOverflow).
Редактор — Emacs.
Редактор — Emacs.
А Visual Prolog сильно отличается от поддерживающих ISO-стандарт реализаций. Есть даже мнение, что Visual Prolog это и не Пролог вовсе.
Давно мучает вопрос: А есть ли комерческий/промышленный софт написанный на прологе?
Повторяю: Prolog используется в IBM Watson.
Watson мощный аппаратно-программный комплекс, гибридная экспертная система:
— с первого захода обыграла в «Свою игру» самых крутых игроков в штатах;
— знает онкологию лучше 99% врачей;
— синтезирует рецепты вкусных блюд, которых ранее не существовало;
— доступна по SaaS продвинутым разработчикам;
Watson мощный аппаратно-программный комплекс, гибридная экспертная система:
— с первого захода обыграла в «Свою игру» самых крутых игроков в штатах;
— знает онкологию лучше 99% врачей;
— синтезирует рецепты вкусных блюд, которых ранее не существовало;
— доступна по SaaS продвинутым разработчикам;
В Gerrit правила, по которым коммит считается принятым и попадает в мастер, пишутся на Прологе :)
есть ли комерческий/промышленный софт написанный на прологе?
Цитата из книги Эрика Эванса Предметно-ориентированное проектирование
Еще один перспективный подход в декларативной архитектуре — это логическое программирование (rule-based programming) с механизмом выводов и базой правил. К сожалению, и эта идея может провалиться из-за некоторых тонкостей. Хотя программа, основанная на совокупности логических правил, в принципе декларативна, в большинстве таких систем имеются «управляющие предикаты», добавленные туда для возможности настройки производительности. Этот управляющий код вносит побочные эффекты, и в результате поведение программы уже не полностью определяется декларированными правилами. Добавление, удаление и переупорядочение правил может привести к непредсказуемым и неправильным результатам. Поэтому программист в логической парадигме, как и программист объектно-ориентированный, должен тщательно следить за очевидностью и предсказуемостью поведения кода.
Похоже, Эрик Эванс знал промышленные проекты, в которых использовалась логическая парадигма, так как книга посвящена проектированию программ, работающих со сложной предметной областью.
Говорят, что софт Бурана был написан на Прологе.
Софт Бурана был написан на ДРАКОНе.
PS Про Брюса Ли достоверно известно, что он изучал Вин-Чун, а всё остальные утверждения «я обучал самого Брюса Ли» — это слухи из разряда «говорят, что...».
PS Про Брюса Ли достоверно известно, что он изучал Вин-Чун, а всё остальные утверждения «я обучал самого Брюса Ли» — это слухи из разряда «говорят, что...».
начало цитаты ================================================================
ru.wikipedia.org/wiki/%D0%94%D0%A0%D0%90%D0%9A%D0%9E%D0%9D
Дружелюбный русский алгоритмический язык, который обеспечивает наглядность (сокр. ДРАКОН) — визуальный алгоритмический язык программирования и моделирования[5]. Был разработан в рамках космической программы «Буран». Разработка языка велась с 1986 года при участии Федерального космического агентства (Научно-производственный центр автоматики и приборостроения им. акад. Н. А. Пилюгина, Москва) и Российской академии наук (Институт прикладной математики им. М. В. Келдыша)[5]. Язык построен путём формализации, эргономизации и неклассической структуризации блок-схем алгоритмов, описанных в ГОСТ 19.701-90 и ISO 5807-85, а также для разработки программ реального времени
конец цитаты ================================================================
То есть ПО для Бурана совсем не похоже на Пролог, а представляет императивный язык основанный на теории конечных автоматов.
ru.wikipedia.org/wiki/%D0%94%D0%A0%D0%90%D0%9A%D0%9E%D0%9D
Дружелюбный русский алгоритмический язык, который обеспечивает наглядность (сокр. ДРАКОН) — визуальный алгоритмический язык программирования и моделирования[5]. Был разработан в рамках космической программы «Буран». Разработка языка велась с 1986 года при участии Федерального космического агентства (Научно-производственный центр автоматики и приборостроения им. акад. Н. А. Пилюгина, Москва) и Российской академии наук (Институт прикладной математики им. М. В. Келдыша)[5]. Язык построен путём формализации, эргономизации и неклассической структуризации блок-схем алгоритмов, описанных в ГОСТ 19.701-90 и ISO 5807-85, а также для разработки программ реального времени
конец цитаты ================================================================
То есть ПО для Бурана совсем не похоже на Пролог, а представляет императивный язык основанный на теории конечных автоматов.
Например, мы используем Пролог в промышленной системе (обработка естественного языка).
IMHO, пролог мог бы позиционироваться как замена SQL.
SQL довольно громоздкий и изначально разрабатывался так, чтобы быть похожим на английский язык. Как COBOL :)
Но сейчас пришло современное понимание того, что это не есть хорошо. И пролог в этом контексте выглядит, относительно SQL, языком с более элегантным синтаксисом и одновременно похожей семантикой.
SQL довольно громоздкий и изначально разрабатывался так, чтобы быть похожим на английский язык. Как COBOL :)
Но сейчас пришло современное понимание того, что это не есть хорошо. И пролог в этом контексте выглядит, относительно SQL, языком с более элегантным синтаксисом и одновременно похожей семантикой.
SQL появился чуть позже Prolog. Похоже, авторы не знали пролога. Раз в десять лет заседали и принимали решения о развитии SQL. Если не ошибаюсь, в 80х и 90х годах в решениях этой комиссии одним из 10 пунктов были пункты «двигаться в сторону Prolog». В частности, в стандартах 2000х в SQL была введена рекурсия.
Сегодня SQL уже не торт. Например, LINQ выигрывает у него в автоподстановке имен полей таблицы, т.к. тип таблицы известен до обращения к полям. В SQL сперва записываются поля (по памяти), а уже потом таблица (из которой можно выбрать поля).
Сегодня SQL уже не торт. Например, LINQ выигрывает у него в автоподстановке имен полей таблицы, т.к. тип таблицы известен до обращения к полям. В SQL сперва записываются поля (по памяти), а уже потом таблица (из которой можно выбрать поля).
Есть же en.wikipedia.org/wiki/Datalog.
Есть промежуточный вариант между прологом и SQL — SPARQL.
Создается впечатление, что на Прологе задача описывается так, как будто ты уже знаешь решение.
Вот буквально пару дней назад как сдал экзамен по логическому программированию/программированию в ограничениях, в рамках которого мы изучали язык Oz. Пролог изучал годом раньше. Oz гораздо более интересный и продвинутый мультипарадигменный язык, в котором есть человеческие структуры данных, хорошо реализована функциональная парадигма, можно самому описать стратегию обхода графа, встроенный визуализатор графа решений и много других плюшек. Настоятельно рекомендую ознакомиться всем вдохновившимся прологом.
Ответ на habrahabr.ru/post/254133/#comment_8349545 про Oz
Так может напишите обзорную статью про Oz? Было бы интересно. И есть ли компиляторы (или интерпретаторы) для Oz?
Так может напишите обзорную статью про Oz? Было бы интересно. И есть ли компиляторы (или интерпретаторы) для Oz?
Вас гугль забанил?
Идете en.wikipedia.org/wiki/Oz_(programming_language)
Затем mozart.github.io/
Затем github.com/mozart/mozart2#downloads
PS: Мне тоже было бы интересно прочесть статью по Oz от эксперта в теме.
Идете en.wikipedia.org/wiki/Oz_(programming_language)
Затем mozart.github.io/
Затем github.com/mozart/mozart2#downloads
PS: Мне тоже было бы интересно прочесть статью по Oz от эксперта в теме.
Уже думал об этом. Как окончательно разберусь с сессией – займусь этим. Экспертный обзор не обещаю, но все интересные плюшки постараюсь рассмотреть. Ссылки на компилятор ниже уже выложили.
Все хочется попробовать пролог для решения различных логических задач, но боюсь сломать мозг :(
Prolog можно изучать ступенчато. Т.е. есть вещи очень простые. Вникаешь — уже можешь кодировать. Затем через некоторый момент осознаешь, что не понимаешь, как ЭТО работает. Затем проникаешься, переходишь на еще один уровень и т.д. «до мага 89 уровня» :)
Уровень 1. Принять Унификацию. (в обе стороны!)
Уровень 2. Программа на прологе это База Данных + Запросы
Уровень 3. Унификация работает в обе стороны!!! и в запросах!!!
Уровень 4. В попытке разрешения успеха или неуспеха унификации запросов может уйти в бесконечность (~stack overflow)
Уровень 5. Даже если нет бесконечности, есть проблема комбинаторного взрыва. Перебирать всё нет смысла. Есть удачный порядок перебора, а есть очень затратный.
Уровень 6. Оператор отсечения может быть полезен. И даже очень. Но с его использованием нужно перестроить систему знаний о Prolog.
Уровень 7.… тормоз…
Уровень 8. Оказывается, Prolog очень хорошо масштабируется! Можно по ядрам, а можно и в кластере.
…
Уровень 10. Простой логический решатель.…
Уровень 15. Простой геометрический решатель…
Уровень 25. Системы компьютерной алгебры.…
Уровень 30. Решатель способен поступить в любой университет (сдать ЕГЭ)…
…
Уровень 42. 42!
…
Уровень 69. Гугол не так и много :)
Уровень 1. Принять Унификацию. (в обе стороны!)
Уровень 2. Программа на прологе это База Данных + Запросы
Уровень 3. Унификация работает в обе стороны!!! и в запросах!!!
Уровень 4. В попытке разрешения успеха или неуспеха унификации запросов может уйти в бесконечность (~stack overflow)
Уровень 5. Даже если нет бесконечности, есть проблема комбинаторного взрыва. Перебирать всё нет смысла. Есть удачный порядок перебора, а есть очень затратный.
Уровень 6. Оператор отсечения может быть полезен. И даже очень. Но с его использованием нужно перестроить систему знаний о Prolog.
Уровень 7.… тормоз…
Уровень 8. Оказывается, Prolog очень хорошо масштабируется! Можно по ядрам, а можно и в кластере.
…
Уровень 10. Простой логический решатель.…
Уровень 15. Простой геометрический решатель…
Уровень 25. Системы компьютерной алгебры.…
Уровень 30. Решатель способен поступить в любой университет (сдать ЕГЭ)…
…
Уровень 42. 42!
…
Уровень 69. Гугол не так и много :)
Пояснение по борьбе с исключениями путём модификации компилятора
fact(2).
fact(4).
p(N) :- fact(I), I>N, p(N).
p(N) :- stdio::write(N).
Проще будет понять объяснение, если одновременно читать и трассировать программу. Допустим в goal задали Prolog-у вопрос, истинно ли p(10). В таком случае не будет зацикливания. Prolog заходит в строку 3, в контейнер (например, в красно-черное дерево) кладём объект, состоящий из информации об обходе предиката — p(10), а также хэша этой информации. дальше видим fact(I). кладём в контейнер fact(output). видим факт fact(2). возвращаемся из fact(I) и одновременно достаём из контейнера fact(output). Далее I>N, которое не выполняется (2 > 10 ложно). Далее пролог возвращается в fact(I) и начинает перебирать остальные возможные I. Снова кладем в контейнер fact(output). Видим fact(4). Возвращаемся из fact(I) и одновременно достаём из контейнера fact(output). Видим что I>N — ложно. Далее p(N) :- stdio::write(N), пролог выводит 10. Достаём из контейнера p(10). Программа завершается.
Теперь давайте разберём случай, когда зацикливание происходит. В goal задали вопрос истинно ли p(1). Поначалу выполнение программы похоже. Кладём в контейнер p(1), кладём fact(output), достаём fact(output) и теперь I=2. Теперь снова пытаемся положить в контейнер p(1), но видим что в контейнере есть объект с таким же хэшем, сравниваем сами объекты и видим что они равны. Обнаружили зацикливание. Кидаем исключение. Перехватываем исключение там где происходит ближайший перебор значений, то есть при переборе fact(I). Продолжаем перебор. Теперь I=4, снова зацикливание, снова кидаем исключение и перехватываем на переборе fact(I). Prolog видит что возможные значения I закончились, и продолжает программу, после чего выводит 1 и корректно завершается.
Полное обсуждение тут
fact(2).
fact(4).
p(N) :- fact(I), I>N, p(N).
p(N) :- stdio::write(N).
Проще будет понять объяснение, если одновременно читать и трассировать программу. Допустим в goal задали Prolog-у вопрос, истинно ли p(10). В таком случае не будет зацикливания. Prolog заходит в строку 3, в контейнер (например, в красно-черное дерево) кладём объект, состоящий из информации об обходе предиката — p(10), а также хэша этой информации. дальше видим fact(I). кладём в контейнер fact(output). видим факт fact(2). возвращаемся из fact(I) и одновременно достаём из контейнера fact(output). Далее I>N, которое не выполняется (2 > 10 ложно). Далее пролог возвращается в fact(I) и начинает перебирать остальные возможные I. Снова кладем в контейнер fact(output). Видим fact(4). Возвращаемся из fact(I) и одновременно достаём из контейнера fact(output). Видим что I>N — ложно. Далее p(N) :- stdio::write(N), пролог выводит 10. Достаём из контейнера p(10). Программа завершается.
Теперь давайте разберём случай, когда зацикливание происходит. В goal задали вопрос истинно ли p(1). Поначалу выполнение программы похоже. Кладём в контейнер p(1), кладём fact(output), достаём fact(output) и теперь I=2. Теперь снова пытаемся положить в контейнер p(1), но видим что в контейнере есть объект с таким же хэшем, сравниваем сами объекты и видим что они равны. Обнаружили зацикливание. Кидаем исключение. Перехватываем исключение там где происходит ближайший перебор значений, то есть при переборе fact(I). Продолжаем перебор. Теперь I=4, снова зацикливание, снова кидаем исключение и перехватываем на переборе fact(I). Prolog видит что возможные значения I закончились, и продолжает программу, после чего выводит 1 и корректно завершается.
Полное обсуждение тут
В ходе обсуждения выявился любопытный частный случай, нуждающийся в дополнительной обработке.
В Prolog-е можно дописывать\удалять предикаты во время исполнения программы посредством команд assert и retract. При добавлении нового предиката повторное захождение в некий предикат не всегда говорит о зацикливании, ведь программа может повести себя совсем по-другому. Чтение с консоли, чтение из файла, генерирование случайного числа похоже на то, как если бы мы добавили предикат, описывающий поступившие данные в виде факта, с последующим его удалением.
Давайте представим себе воображаемую ситуацию: программист и Капитан Очевидность собрались вместе, чтобы устранить этот недочёт в алгоритме.
П: Алгоритм считает, что если программа повторно зашла в предикат с теми же самыми параметрами, то программа зациклилась. Когда добавляются новые правила, алгоритм продолжает считать также, но это неверно.
КО: А пусть он так не считает!
П: Хорошо, после того как добавились новые предикаты, алгоритм не будет считать что захождение в тот же самый предикат привело к зацикливанию. Но как добиться того, чтобы алгоритм перестал так считать?
КО: Для того, чтобы ответить на этот вопрос, нужно знать подробности вашего алгоритма.
П: Ну, если вкратце, мы кладём в контейнер запись с пометкой что мы обходили предикат. Потом на основании наличия пометки решаем, произошло ли зацикливание. Есть пометка — считаем что есть зацикливание, нет пометки — нет зацикливания.
КО: Ну так сделайте так, чтобы не было пометки!
П: Хорошо, при добавлении нового предиката удаляем пометки из контейнера. Но какие пометки нужно убрать? Убирать все пометки нецелесообразно. Добавление нового предиката может оказывать влияние не на все другие предикаты, а лишь на некоторые из них.
КО: Ну так вы и убирайте только те, на которые добавление нового предиката могло оказать влияние!
П: Спасибо, Капитан!
(в диалоге описано как устранить недочёт в алгоритме)
В Prolog-е можно дописывать\удалять предикаты во время исполнения программы посредством команд assert и retract. При добавлении нового предиката повторное захождение в некий предикат не всегда говорит о зацикливании, ведь программа может повести себя совсем по-другому. Чтение с консоли, чтение из файла, генерирование случайного числа похоже на то, как если бы мы добавили предикат, описывающий поступившие данные в виде факта, с последующим его удалением.
Давайте представим себе воображаемую ситуацию: программист и Капитан Очевидность собрались вместе, чтобы устранить этот недочёт в алгоритме.
П: Алгоритм считает, что если программа повторно зашла в предикат с теми же самыми параметрами, то программа зациклилась. Когда добавляются новые правила, алгоритм продолжает считать также, но это неверно.
КО: А пусть он так не считает!
П: Хорошо, после того как добавились новые предикаты, алгоритм не будет считать что захождение в тот же самый предикат привело к зацикливанию. Но как добиться того, чтобы алгоритм перестал так считать?
КО: Для того, чтобы ответить на этот вопрос, нужно знать подробности вашего алгоритма.
П: Ну, если вкратце, мы кладём в контейнер запись с пометкой что мы обходили предикат. Потом на основании наличия пометки решаем, произошло ли зацикливание. Есть пометка — считаем что есть зацикливание, нет пометки — нет зацикливания.
КО: Ну так сделайте так, чтобы не было пометки!
П: Хорошо, при добавлении нового предиката удаляем пометки из контейнера. Но какие пометки нужно убрать? Убирать все пометки нецелесообразно. Добавление нового предиката может оказывать влияние не на все другие предикаты, а лишь на некоторые из них.
КО: Ну так вы и убирайте только те, на которые добавление нового предиката могло оказать влияние!
П: Спасибо, Капитан!
(в диалоге описано как устранить недочёт в алгоритме)
Ещё примеры алгоритма борьбы с зацикливаниями.
p() :- consult(«name.txt», имяБД),
retract(fact(N,A,B)),
asserta(fact(random(9),A,B)),
fail;
write(«end»).
Кладём в контейнер пометку об обходе consult(«name.txt», имяБД). consult добавляет в программу новые предикаты; для каждого добавленного предиката извлекаем из контейнера пометки о тех предикатах, поведение которых изменилось после добавления нового предиката. consult не «заходит» ни в один пользовательский предикат. Извлекаем consult из контейнера. Потом обходится предикат retract(fact(N,A,B)), кладём в контейнер пометку об обходе retract(fact(N,A,B)). Извлекаем из контейнера пометки обо всех предикатах, поведение которых изменилось после удаления предиката fact(N,A,B). Эти предикаты можно найти рекурсивно: это непосредственно fact, все предикаты в которых использовался fact (например, если rule():-someRule1(), fact(X,Y,Z), someRule2(), то поведение rule изменилось), все предикаты в которых использовались предикаты в которых использовался fact, и так далее. Достаём из контейнера информацию об обходе retract(fact(N,A,B)). Кладём в контейнер информацию об обходе asserta(fact(random(9),A,B)). Извлекаем из контейнера все предикаты, поведение которых изменилось при добавлении предиката fact. Извлекаем из контейнера информацию об обходе asserta(fact(random(9),A,B)).
p() :- if 42 <> random(10000) then p() end if.
Кладём в контейнер информацию об обходе p(). Кладём в контейнер информацию об обходе random(10000). При вызове random, введении данных извне, добавлении новых предикатов или их удалении, нужно извлечь из контейнера все предикаты, поведение которых может отличаться при следующем их обходе. То, как найти такие предикаты было описано ранее, в данном случае это p(), извлекаем пометку о p() из контейнера. Допустим random выдал 5. Извлекаем из контейнера пометку об обходе random(10000). Теперь мы снова пытаемся обойти p(). В контейнере нет пометки об обходе p(), поэтому мы не детектируем зацикливание и разрешаем это сделать. Помещаем в контейнер пометку об обходе p(). Помещаем в контейнер пометку об обходе random(10000). Допустим random выдал 42. Извлекаем из контейнера пометку об обходе random(10000). Извлекаем из контейнера пометку об обходе p(). Снова пытаемся извлечь пометку об обходе p(), но её нет в контейнере — ничего страшного, нет ну и ладно, продолжаем выполнение программы.
p() :- if -42 <> random(10000) then p() end if.
Выводы алгоритма для примера с 42 и -42 отличаться не будут. Написание предикатов, которые зацикливаются на всех путях их исполнения — ошибка программиста, а не языка, на котором он пишет. Конечно можно облегчить жизнь программиста посредством статического анализатора кода, но это уже совсем другая история.
p() :- consult(«name.txt», имяБД),
retract(fact(N,A,B)),
asserta(fact(random(9),A,B)),
fail;
write(«end»).
Кладём в контейнер пометку об обходе consult(«name.txt», имяБД). consult добавляет в программу новые предикаты; для каждого добавленного предиката извлекаем из контейнера пометки о тех предикатах, поведение которых изменилось после добавления нового предиката. consult не «заходит» ни в один пользовательский предикат. Извлекаем consult из контейнера. Потом обходится предикат retract(fact(N,A,B)), кладём в контейнер пометку об обходе retract(fact(N,A,B)). Извлекаем из контейнера пометки обо всех предикатах, поведение которых изменилось после удаления предиката fact(N,A,B). Эти предикаты можно найти рекурсивно: это непосредственно fact, все предикаты в которых использовался fact (например, если rule():-someRule1(), fact(X,Y,Z), someRule2(), то поведение rule изменилось), все предикаты в которых использовались предикаты в которых использовался fact, и так далее. Достаём из контейнера информацию об обходе retract(fact(N,A,B)). Кладём в контейнер информацию об обходе asserta(fact(random(9),A,B)). Извлекаем из контейнера все предикаты, поведение которых изменилось при добавлении предиката fact. Извлекаем из контейнера информацию об обходе asserta(fact(random(9),A,B)).
p() :- if 42 <> random(10000) then p() end if.
Кладём в контейнер информацию об обходе p(). Кладём в контейнер информацию об обходе random(10000). При вызове random, введении данных извне, добавлении новых предикатов или их удалении, нужно извлечь из контейнера все предикаты, поведение которых может отличаться при следующем их обходе. То, как найти такие предикаты было описано ранее, в данном случае это p(), извлекаем пометку о p() из контейнера. Допустим random выдал 5. Извлекаем из контейнера пометку об обходе random(10000). Теперь мы снова пытаемся обойти p(). В контейнере нет пометки об обходе p(), поэтому мы не детектируем зацикливание и разрешаем это сделать. Помещаем в контейнер пометку об обходе p(). Помещаем в контейнер пометку об обходе random(10000). Допустим random выдал 42. Извлекаем из контейнера пометку об обходе random(10000). Извлекаем из контейнера пометку об обходе p(). Снова пытаемся извлечь пометку об обходе p(), но её нет в контейнере — ничего страшного, нет ну и ладно, продолжаем выполнение программы.
p() :- if -42 <> random(10000) then p() end if.
Выводы алгоритма для примера с 42 и -42 отличаться не будут. Написание предикатов, которые зацикливаются на всех путях их исполнения — ошибка программиста, а не языка, на котором он пишет. Конечно можно облегчить жизнь программиста посредством статического анализатора кода, но это уже совсем другая история.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пролог – декларативный язык, способный решать любые ребусы и доказывать теоремы