Заморозка / блокировка 2 целей по переменным, которые стали недоступны

Question

Я сделал следующую небольшую программу, чтобы определить, используется ли память для таких целей, как freeze(X,Goal) восстанавливается, когда X становится недоступным:

%:- use_module(library(freeze)). % Ciao Prolog needs this

freeze_many([],[]).
freeze_many([_|Xs],[V|Vs]) :-
   freeze(V,throw(error(uninstantiation_error(V),big_freeze_test/3))),
   freeze_many(Xs,Vs).

big_freeze_test(N0,N,Zs0) :-
   (  N0 > N
   -> true
   ;  freeze_many(Zs0,Zs1),
      N1 is N0+1,
      big_freeze_test(N1,N,Zs1)
   ).

Давайте запустим следующий запрос...

?- statistics, length(Zs,1000), big_freeze_test(1,500,Zs), statistics.

... с различными процессорами Prolog и посмотрите на потребление памяти. Какая разница!

(AMD64) SICStus Prolog 4.3.2: используется глобальный стек = 108 МБ
(AMD64) B-Prolog       8.1: стек + куча в использовании = 145 МБ
(i386)  Ciao Prolog    1.14.2: используется глобальный стек =  36 МБ (~72 МБ с AMD64)
(AMD64) SWI-Prolog     7.3.1: глобальный стек используется = 0,5 МБ
(AMD64) YAProlog       6.2.2: используется глобальный стек =  16 МБ

Когда выполняется больше итераций с ?- length(Zs,1000), big_freeze_test(1,10000,Zs). Я сделал следующие замечания:

• Чао Пролог сообщает {ERROR: Memory allocation failed [in Realloc()]} перед прерыванием.

• /questions/tagged/sicstus-prolog и b-prolog выделяют все больше и больше, пока машина не замерзнет.

• swi-prolog выполняет все итерации за 3,554 секунды.
• yap также выполняет все итерации, но занимает 36,910 секунд.

Есть идеи, почему он работает с SWI-Prolog и YAProlog, но не с другими?

Учитывая время выполнения, почему SWI-Prolog обошел YAProlog более чем на порядок?

Моя интуиция склоняется к взаимодействию "приписанных переменных" с "сборкой мусора". SWI-Prolog и YAProlog имеют (разделяют?) API и реализацию атрибутивных переменных, отличные от других процессоров Prolog... и, опять же, это может быть что-то совершенно другое. Спасибо!

Answer 1

TL;DR: ошибки в SWI больше нет!

Вы создаете 500000 замороженных целей, которые впоследствии будут недоступны. Что означают эти цели? Системы Prolog не анализируют цель в отношении ее семантической значимости (до ее фактического выполнения). Поэтому мы должны предположить, что цели могут быть семантически значимыми. Поскольку цели уже отсоединены, единственный смысловой эффект, который они могут иметь, заключается в том, чтобы быть ложным и, таким образом, сделать следующий ответ ложным.

Так что достаточно рассмотреть freeze(_,false) вместо.

Семантически предикаты p/0 а также q/0 эквивалентны:

p :-
   false.

q :-
   freeze(_,false).

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

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

В SICStus это показано следующим образом:

| ?- q.
prolog:freeze(_A,user:false) ? ;
no

В SWI и YAP эти цели не отображаются по умолчанию, и, следовательно, есть вероятность, что ошибки, как эта, не были обнаружены.

---

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

Сначала я посмотрел на числа SICStus: 216 байт за стоп-кадр! Это 27 слов с 13 только для термина, представляющего цель. Так что просто 14 слов для замораживания. Не так плохо.

PPS: замороженная цель была throw/2 должно было быть throw/1

---

^{Мелкий шрифт 1: некоторые примеры: замена ответа} X = 1 ^{содержит ровно одно решение, и} X = [_A] ^{содержит бесконечно много решений, таких как} X = [a] ^{и многое, многое другое. Все это становится намного сложнее в контексте ограничений.}

Answer 2

Восстановление заблокированных целей недопустимо в определенных условиях. Например, в CC это не будет разрешено, так как программа имеет как минимум 3 результата:

Есть статья Эвана Тика, объясняющая CC:

Программа успешно завершается, когда, начиная с начального пользовательского запроса (соединения атомов), после некоторого количества шагов сокращения не остается ни целей, ни выполняемых, ни приостановленных. Кроме того, программа блокируется, если остаются только приостановленные цели. Третий результат - сбой программы, который определяется более формально ниже.

РАЗОБРЕТЕНИЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ СОВМЕСТНОЙ ЛОГИКИ
Эван Тик - 1995
https://core.ac.uk/download/pdf/82787481.pdf

Вот пример, который иллюстрирует проблему. freeze/2 более примитивен, чем CLP(FD). Поэтому CLP (FD) может иногда делать следующее:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.21)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- [user].
test(A,B) :- A #< X, X #< B.

?- test(1,2).
false

?- test(1,3).
true

Но теперь, если я делаю то же самое с замораживанием, я теряю всю информацию, поскольку SWI-Prolog восстанавливает замороженные цели:

?- [user].
test2(A,B) :- freeze(X,(integer(X),A<X)), freeze(X,(integer(X),X<B)).

?- test2(1,2).
true.

?- test2(1,3).
true.

Возможно, необходим более точный контроль за поведением сборки мусора.

Редактировать 1: Для более точного управления в SWI-Prolog предлагается заключить в call_residue_vars/2. Я не знаю, является ли это самым умным решением, но, по крайней мере, это решение:

?- call_residue_vars(test2(1,2),L).
L = [_5538],
freeze(_5538,  (integer(_5538), 1<_5538)),
freeze(_5538,  (integer(_5538), _5538<2)).

?- call_residue_vars(test2(1,3),L).
L = [_5544],
freeze(_5544,  (integer(_5544), 1<_5544)),
freeze(_5544,  (integer(_5544), _5544<3)).

Answer 3

Объяснение @false относительно ответов против решений немного сбивает с толку.

теория

Вот мое правило большого пальца для того, когда мы должны freeze/2 а когда нет. Предположим, у нас есть предикат pred/n мы хотим заморозить первый аргумент. Так что мы будем делать что-то вместе в контексте:

.. freeze(V, pred(V, T1, .., Tn)) ..

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

exists V : pred(V, T1, .., Tn).

Если вы можете доказать или опровергнуть это, вы также можете построить предикат pred'(T1, .., Tn) со следующим определением:

pred'(T1, .., Tn) <=> exists V : pred(V, T1, .., Tn).

Ирония заключается в том, что этот предикат будет читать в Прологе следующим образом, но мы не хотим использовать pred, нам нужен pred 'каким-то другим способом, так что это только для иллюстрации:

/* for illustration means only */
pred'(T1, .., Tn) :- pred(_, T1, .., Tn).

Итак, совет сейчас, пожалуйста, сделайте следующее в своем коде при использовании freeze/2, и вы будете в безопасности:

.. pred'(T1, .., Tn), freeze(V, pred(V, T1, .., Tn)) ..

Примеры

Звучит сложно? Может быть. Давайте сделаем несколько примеров. Сначала pred(V) = false пример из @false. Конечно у нас есть:

pred(V) <=> false
pred' <=> false

Так что в основном это говорит не использовать freeze/2 на false, Еще один пример предположим, что мы имеем pred(V) = V > 0, Конечно у нас есть:

pred(V) <=> V > 0
pred' <=> true

Так что в основном это говорит о том, что использовать freeze/2 на V > 0пока проблем нет.

отказ

Будьте осторожны, методика работает не всегда, вышеупомянутое требуемое доказательство исключения квантификатора может быть не так легко получить на бумаге или с помощью некоторого помощника по доказательству, предиката. pred' может также оказаться немного дороже и т.д..

С другой стороны, я не совсем задумывался о том, что происходит при взаимодействии замороженных целей, но с другой стороны. pred' может быть дешевле, если принять во внимание некоторые контекстные инварианты, которые также можно рассматривать как взаимодействие с другими заблокированными целями.

до свидания