Пролог: проверь транзитивность на простые факты

Question

Я намеревался реализовать простой пример (только для себя) транзитивности в Прологе.

Это мои факты:

trust_direct(p1, p2).
trust_direct(p1, p3).
trust_direct(p2, p4).
trust_direct(p2, p5).
trust_direct(p5, p6).
trust_direct(p6, p7).
trust_direct(p7, p8).
trust_direct(p100, p200).

Я написал этот предикат, чтобы проверить, A трасты C, что верно, когда есть B что доверяет C а также A доверяет этому B:

trusts(A, B) :-
    trust_direct(A, B).

trusts(A, C) :-
    trusts(A, B),
    trusts(B, C).

Предикат возвращается true за trusts(p1, p2) или же trusts(p1, p5) например, но trusts(p5, p6) уже возвращается ERROR: Out of local stack,

Пролог быстро заполняет стек?

Или это моя идея / реализация trusts плохо / тратить системную память?

Answer 1

Да, Пролог быстро заполняет локальный стек.

Чтобы увидеть это, достаточно рассмотреть только следующий фрагмент программы:

трасты (A, C):-
        трасты (A, B),
        ложь,
        трасты (B, C).

Это называется срез-срез: я вставил false/0 так, чтобы все после false/0 можно игнорировать Я указываю части, которые могут быть проигнорированы зачеркнутым текстом.

Это означает, что фрагмент фактически эквивалентен:

трасты (A, C):-
        трасты (A, B),
        ложный.

Теперь, используя любой из приведенных выше фрагментов, мы сразу получаем:

? - трасты (p5, p6).
ОШИБКА: вне локального стека

Чтобы избавиться от этой проблемы, вы должны изменить оставшийся фрагмент. По этой причине такой фрагмент служит объяснением проблемы.

Например, рассмотрим следующую версию:

трасты (A, B):-
        доверительный_каталог (A, B).
трасты (A, C):-
        доверительный_каталог (A, B),
        трасты (B, C).

Пример запроса:

? - трасты (p5, p6).
правда;
ложный.

Теперь это работает, как и ожидалось. Это декларативно эквивалентно версии, которую вы опубликовали, и имеет гораздо лучшие свойства завершения:

? - доверяет (X, Y), ложно.
ложный.

Это показывает, что программа теперь завершается повсеместно.

Альтернативные решения:

• использовать функции таблинга вашей системы Prolog
• использовать определение транзитивного замыкания
• и т.п.