Понимание побочных эффектов Пролога, например, write / 1

Question

В настоящее время я изучаю Пролог, и мне трудно понять побочные эффекты.

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

n_times(N) :- 1 =< N.
n_times(N) :- N > 1, N1 is N - 1, n_times(N1).
test_x(N) :- n_times(N), write('x'), fail.
test_x(_).

Может кто-нибудь объяснить, почему это работает?Почему write('x') выполняется N раз?Насколько я понимаю, Пролог должен попытаться найти решение для n_times(N), а затем выполнить write('x') один раз.Я предполагаю, что это как-то связано с побочными эффектами, но я не смог найти практического объяснения этому.

Мое собственное решение выглядит следующим образом:

test_x(N) :- write('x'), N1 is N - 1, N1 >= 1, test_x(N1).

Здесь я могу видетьwrite вызывается при каждом рекурсивном вызове.

Answer 1

Это так называемый отказоустойчивый цикл .

Более простая ситуация, с которой нужно разобраться:

repeat :- true.
repeat :- repeat.

forever_x :- repeat, write('x'), fail.

, которая навсегда печатает x в приглашении.

Почему?Потому что соединения Пролога (,, "и") целей похожи на вложенные циклы :

find(G):- this(X1), that(X2).

точно так же (в псевдокод )

def find(G):
         foreach solution X1 to { this(X1) }:
             foreach solution X2 to { that(X2) }:
                 yield G using the found values X1, X2.

Возврат происходит естественным образом в циклах. Если для некоторых X1 не существует X2, который удовлетворяет that(X2), то G не получается,и внешний цикл просто пропускает к следующему значению X1, которое удовлетворяет this(X1).

. А расчеты Пролога (;, "или") целей - это просто сопоставление циклов (просто помещая один цикл за другим).

Таким образом, определение repeat действует так, как если бы оно было определено как

def repeat:
     yield        % yield an empty value that isn't used anywhere
     repeat       % call self, yielding again; and again; repeating endlessly

def forever_x:
     foreach solution to { repeat }:           % endless stream of empty solutions
         foreach solution to { write('x') }:   % there will be only one, empty solution
            foreach solution to { fail }:      % there will be no solutions, ever, so
                yield                          % this will never happen

, а ваш n_times/1, как если бы

% n_times(N) :- N =< 1.
% n_times(N) :- N > 1, N1 is N - 1, n_times(N1).

def n_times(n):
    foreach solution to { n =< 1 }:            % succeeds at most once
         yield n
    foreach solution to { n > 1 }:             % at most once, mutually exclusively
         foreach solution to { n1 = n - 1 }:   % there will be only one solution
             n_times(n1)

, поэтому, естественно, это удастся, то есть «доходность», n раз.