Запоминать (и кэшировать) решения, найденные в запросе 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))
    ).

Теперь нет точки выбора.

Это все еще не чистая реализация, если у вас есть выбор нескольких решений. Любые решения после первого будут обрезаны ->,

Это совет о том, как в целом делать то, что делает таблинг. Я сам не следовал этому совету целую вечность, поэтому здесь могут быть неточности. Надеюсь, что остальные члены банды появятся и поправят меня, если я буду вне базы.

  1. У вас есть предикат foo/4 это неэффективно.
  2. Добавьте это в свой файл:

    :- dynamic(cached_foo/4).
    
  3. переименовывать foo/4 в compute_foo/4 или что-то.
  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))
      ).
    
Другие вопросы по тегам