Запоминать (и кэшировать) решения, найденные в запросе Prolog?
В этом вопросе о StackExchange я спросил (и он был решен) о программе Prolog, которую я пытался создать. Но хотя он работает в принципе, он не соответствует моим потребностям в реальном мире.
Прежде чем я начну изучать еще один язык (Datalog), я хотел бы попробовать свою уже проделанную работу и узнать, как я могу реализовать в Prolog способ запоминания результатов предыдущих запросов, чтобы один и тот же запрос выполнялся только один раз. Итак, я ищу способ добавить результат успешного запроса в список, и если тот же запрос запрашивается снова, он не повторяет вычисление, а использует запомненный результат.
Моя главная проблема заключается в том, что я не могу найти способ сохранить результат успешного запроса в списке, который передается "по цепочке".
В
% get this out of the way, quickly
isARelation( Source, Relation, Target, _) :-
isADirectRelation( Source, Relation, Target).
% Structural Chains
isARelation( Source, Relation, Target, Visited) :-
\+ member( [Source,Relation,Target], Visited),
structuralOrDependencyRelation( RelationOne),
structuralOrDependencyRelation( RelationTwo),
weakest( Relation, RelationOne, RelationTwo),
isADirectRelation( Source, RelationOne, Intermediate),
isARelation( Intermediate, RelationTwo, Target, [[Source,RelationOne,Intermediate]|Visited]).
isARelation( Source, Relation, Target, Visited) :-
\+ member( [Source,Relation,Target], Visited),
structuralOrDependencyRelation( RelationOne),
structuralOrDependencyRelation( RelationTwo),
weakest( Relation, RelationOne, RelationTwo),
isADirectRelation( Source, RelationTwo, Intermediate),
isARelation( Intermediate, RelationOne, Target, [[Source,RelationTwo,Intermediate]|Visited]).
Как мне реализовать, что первый звонок
isARelation(A, B, C, []).
делает подсчет результатов и второй звонок
isARelation(A, B, C, []).
использует найденный ранее результат, который хранится "глобально"?
2 ответа
Это не совсем ответ на ваш вопрос:(
Другой ответ имеет правильную идею, но реализация имеет проблему. Допустим, мы хотим сделать запоминанную версию возведения в квадрат числа:
:- dynamic mem_square/2.
square(N, S) :-
( mem_square(N, S)
; S is N*N,
assertz(mem_square(N, S))
).
Кстати, скобки в другом ответе совершенно не нужны. Они также не нужны, но именно так вы обычно оборачиваете дизъюнкцию, на тот случай, если она является частью соединения. Другими словами, это: a ; (b, c)
такой же как a ; b, c
, но (a ; b), c
не такой же.
Теперь, если я загружу эту программу с верхнего уровня и сделаю запрос:
?- square(3, S).
S = 9. % first time it's fine
?- square(3, S).
S = 9 ;
S = 9. % now there's two
?- square(3, S).
S = 9 ;
S = 9 ;
S = 9. % now three
Если вы продолжаете запрашивать запомненный факт и возвращаетесь к нему, вы будете продолжать вычислять снова и снова и добавлять все новые и новые идентичные копии. Вместо этого вы можете попробовать, например, это:
:- dynamic mem_square/2.
square(N, S) :-
( mem_square(N, S)
-> true
; S is N*N,
assertz(mem_square(N, S))
).
Теперь нет точки выбора.
Это все еще не чистая реализация, если у вас есть выбор нескольких решений. Любые решения после первого будут обрезаны ->
,
Это совет о том, как в целом делать то, что делает таблинг. Я сам не следовал этому совету целую вечность, поэтому здесь могут быть неточности. Надеюсь, что остальные члены банды появятся и поправят меня, если я буду вне базы.
- У вас есть предикат
foo/4
это неэффективно. Добавьте это в свой файл:
:- dynamic(cached_foo/4).
- переименовывать
foo/4
вcompute_foo/4
или что-то. Создать новый предикат
foo/4
это выглядит так:foo(X, Y, Z, Q) :- cached_foo(X, Y, Z, Q) ; ( compute_foo(X, Y, Z, Q), assertz(cached_foo(X, Y, Z, Q)) ).