Каковы плюсы и минусы использования ручной итерации списка против рекурсии через сбой

Question

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

Что я пытаюсь решить, следует ли использовать метод 1 или 2, и каковы плюсы и минусы каждого из них, особенно большое количество фактов.

methodone Кажется расточительным, поскольку факты доступны, зачем беспокоиться о создании списка из них (особенно большого списка). Это также должно иметь последствия для памяти, если список достаточно велик? И он не использует преимущества функции Prolog's backtracking.

methodtwo использует возможность возврата, чтобы сделать рекурсию для меня, и я бы предположил, что она будет гораздо более эффективной с точки зрения памяти, но насколько хороша практика программирования? Это, возможно, уродливее, чтобы следовать, и могут ли быть какие-либо другие побочные эффекты?

Одна проблема, которую я вижу, заключается в том, что каждый раз, когда вызывается fail, мы теряем способность передавать что-либо обратно вызывающему предикату, например. если это было methodtwo(SeasonResults), так как мы постоянно прерываем предикат. Таким образом, methodtwo нужно будет утверждать факты для хранения состояния.

Предположительно (?) Метод 2 будет быстрее, так как он не обрабатывает (большой) список?

Я мог представить, что если бы у меня был список, то methodone был бы способ пойти .. или это всегда так? Может ли смысл в любых условиях утверждать список фактов, используя methodone, затем обрабатывать их с использованием метода два? Полное безумие?

Но с другой стороны, я читал, что утверждение фактов - очень «дорогой» бизнес, поэтому обработка списка может быть способом, даже для больших списков?

Любые мысли? Или иногда лучше использовать один, а не другой, в зависимости от (какой) ситуации? например. для оптимизации памяти используйте метод 2, включая утверждение фактов и, для метода использования скорости 1?

season(spring). 
season(summer). 
season(autumn). 
season(winter). 

% Season handling 
showseason(Season) :- 
    atom_length(Season, LenSeason), 
    write('Season Length is '), write(LenSeason), nl. 

% ------------------------------------------------------------- 
% Method 1 - Findall facts/iterate through the list and process each 
%-------------------------------------------------------------- 
% Iterate manually through a season list 
lenseason([]). 
lenseason([Season|MoreSeasons]) :- 
    showseason(Season), 
    lenseason(MoreSeasons). 


% Findall to build a list then iterate until all done 
methodone :- 
    findall(Season, season(Season), AllSeasons), 
    lenseason(AllSeasons), 
    write('Done'). 

% ------------------------------------------------------------- 
% Method 2 - Use fail to force recursion 
%-------------------------------------------------------------- 
methodtwo :- 
    % Get one season and show it 
    season(Season), 
    showseason(Season), 

    % Force prolog to backtrack to find another season 
    fail. 

% No more seasons, we have finished 
methodtwo :- 
    write('Done'). 

Answer 1

метод один кажется расточительным, так как факты доступны, зачем строить список из них (особенно большого списка). Это также должно иметь последствия для памяти, если список достаточно велик?

Да, метод 1 принимает Θ (n) память. Главное преимущество заключается в том, что оно декларативно, т. Е. Имеет простой логический смысл.

Способ 2: «неудачный цикл», как программисты Пролога называют его, занимает постоянную память, является процедурным и может быть предпочтительным, когда вы все равно выполняете процедурные (вне-логические) вещи; то есть в коде ввода/вывода это нормально использовать.

Обратите внимание, что SWI-Prolog имеет третий способ написания этого цикла:

forall(season(S), showseason(S)). 

Это работает только если showseason успешным для каждого связывания season(S).

Answer 2

При использовании findall, почему бы не maplist, а также:

findall(S, season(S), L), maplist(showseason, L). 

И не в чистом логическом ядре Пролога. И да, вы выделяете целый список для всех решений.

Ваш второй метод называется «отказоустойчивым циклом», и в нем нет ничего плохого, кроме как невозможно вернуться к предыдущим решениям после отказа от отказа. Вот почему findall является экстра логичным. Внутренне это может быть imd'd как управляемый ошибкой цикл, который сохраняет свои промежуточные результаты посредством утверждения. Таким образом, второй концептуально чист, а также не выделяет лишнюю память. Он обычно используется в предикатах верхнего уровня «драйвер» (т. Е. UI).

Answer 3

Давайте посмотрим на ваш пример. Это очень просто, поэтому мы подумаем, что это сложнее. Однако, кажется, вы считаете само собой разумеющимся, что побочные эффекты необходимы. Позвольте мне задать несколько вопросов:

В вашем примере вы сделали очень интересное открытие: имена всех сезонов имеют одинаковую длину. Какая потрясающая проницательность! Но подождите, правда ли это? Самый прямой способ проверить это, является:

?- season(S), atom_length(S,L). 
S = spring, 
L = 6 ; 
S = summer, 
L = 6 ; 
S = autumn, 
L = 6 ; 
S = winter, 
L = 6. 

Нет необходимости в findall/3, нет необходимости в write/1.

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

?- season(S), atom_length(S,L), dif(L,6). 
false. 

Итак, теперь мы точно знаем, что нет сезона разной длины.

Это мой самый первый ответ на ваш вопрос:

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

Есть несколько причин, почему придерживаться интерпретатора оболочки является хорошей идеей:

• Если ваши программы могут быть легко опрошены на верхнем уровне, это будет тривиально добавить тестовые случаи для них.

• Оболочка Toplevel используется многими другими пользователями и поэтому очень хорошо протестирована. Ваше собственное письмо часто ошибочно и не проверено. Подумайте о ограничениях. Подумайте о том, как писать поплавки. Будете ли вы использовать write/1 для поплавков? Каков правильный способ писать поплавки, чтобы их можно было точно прочитать? Там есть способ сделать это в iso-prolog. Вот ответ:

В ISO, writeq/1,2, write_canonical/1,2, write_term/2,3 с возможностью quoted(true) гарантии, что поплавки могут быть считаны точно. То есть, они такие же w.r.t.(==)/2

• Интерактивная система оболочки показывает правильный текст Пролог. Фактически, сам ответ - это вопрос! Его можно вставить обратно в верхний слой - только для того, чтобы получить тот же ответ. Таким образом вы узнаете более экзотические, но неизбежные детали Prolog, такие как цитирование, экранирование и брекетинг. В противном случае невозможно понять синтаксис, поскольку анализаторы Prolog часто чрезвычайно разрешимы.

• Ваша программа, скорее всего, будет более доступна для декларативных рассуждений.

Весьма вероятно, ваши две процедуры methodone и methodtwo неверны: Вы забыли перевод строки после написания Done. Итак, methodone, methodone содержит искаженную строку. Как легко это проверить?

Но давайте посмотрим немного дальше в вашу программу. То, что так типично для циклов, вызванных ошибками, заключается в том, что они начинают невинно, как что-то, что делает «только» побочные эффекты, но рано или поздно они склонны привлекать больше семантических частей. В вашем случае atom_length/2 спрятан в отказоустойчивом цикле, полностью недоступном для тестирования или рассуждений.

соображения эффективности

Пролог системы часто реализовать отказ от deallocating стека. Поэтому для отказоустойчивых контуров не требуется сборщик мусора. Вот почему люди считают, что сбойные петли эффективны. Однако это не обязательно так. Для цели, такой как findall(A, season(A), As), каждый ответ для A копируется в некоторое пространство. Это тривиальная операция для чего-то вроде атомов, но представьте себе больший термин. Скажи:

 
blam([]). 
blam([L|L]) :- blam(L). 

bigterm(L) :- length(L,64), blam(L). 

Во многих системах findall/3 или assertz/1 для этого большого срока будет заморозить систему.

Кроме того, системы, такие как SWI, YAP, SICStus, имеют довольно сложные сборщики мусора. И использование меньшего числа циклов, управляемых сбоями, поможет еще больше улучшить эти системы, поскольку это создает спрос на more sophisticated techniques.