Нелогичное поведение min_member/2

min_member(-Мин., +Список )

Истинно, когда Min является наименьшим элементом в стандартном порядке членов. Сбой, если список пуст.

?- min_member(3, [1,2,X]).
X = 3.

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

Как это можно оправдать? Как я должен интерпретировать это решение?

РЕДАКТИРОВАТЬ:

Один из способов предотвратить успех min_member/2 с помощью этого решения — изменить стандартную библиотеку (SWI-Prolog) реализация следующим образом:

xmin_member(Min, [H|T]) :-
    xmin_member_(T, H, Min).

xmin_member_([], Min0, Min) :-
    (   var(Min0), nonvar(Min)
    ->  fail
    ;   Min = Min0
    ).
xmin_member_([H|T], Min0, Min) :-
    (   H @>= Min0 
    ->  xmin_member_(T, Min0, Min)
    ;   xmin_member_(T, H, Min)
    ).

Причина неудачи вместо того, чтобы выдавать ошибку создания экземпляра (что @mat предлагает в своем ответе, если я правильно понял), заключается в том, что это четкий вопрос:

«Является ли 3 минимальным членом [1,2,X], когда X — свободная переменная?»

и ответ на это (по крайней мере, для меня) ясное «Нет», а не «Я не могу сказать».

Это тот же класс поведения, что и sort/2:

?- sort([A,B,C], [3,1,2]).
A = 3,
B = 1,
C = 2.

И применяются те же приемы:

?- min_member(3, [1,2,A,B]).
A = 3.

?- var(B), min_member(3, [1,2,A,B]).
B = 3.

min prolog clpfd
person Community    schedule 09.12.2014    source источник
comment
ваша говядина в основном заключается в том, следует ли рассматривать такие предикаты как инструменты более высокого или более низкого уровня. И они явно являются низкоуровневыми инструментами: Верно, когда Min является наименьшим членом в стандартном порядке терминов - довольно ясно (хотя, возможно, его можно было бы улучшить, сказав, что Min объединяется с ...).   -  person Will Ness    schedule 09.12.2014
comment
@WillNess Да, это хороший способ выразить это двумя предложениями. Унифицирует более описательно, чем есть.   -  person    schedule 09.12.2014

Ответы (6)


arrow_upward
4
arrow_downward

Это общее свойство многих (всех?) предикатов, которые зависят от стандартного порядка термов, тогда как порядок между двумя термовами может измениться после объединения. Базовая линия - это соединение ниже, которое также нельзя отменить:

?- X @< 2, X = 3.
X = 3.

Большинство предикатов, использующих аннотацию -Value для аргумента, говорят, что pred(Value) совпадает с pred(Var), Value = Var. Вот еще один пример:

?- sort([2,X], [3,2]).
X = 3.

Эти предикаты представляют чистые отношения только в том случае, если входные данные земля. Однако слишком сложно требовать, чтобы входные данные были заземлены, потому что они могут осмысленно использоваться с переменными, если пользователь знает, что он / она не должен в дальнейшем создавать экземпляры любого из упорядоченных терминов. В этом смысле я не согласен с @mat. Я согласен с тем, что ограничения, безусловно, могут сделать некоторые из этих отношений обоснованными.

person Jan Wielemaker    schedule 09.12.2014
comment
да. Что касается sort/2, в документации говорится: True if Sorted может быть объединен со списком, содержащим элементы List, отсортированные в соответствии со стандартным порядком терминов, и поведение, которое вы показываете, следует. С min_member/2 все немного загадочнее. - person ; 09.12.2014

arrow_upward
7
arrow_downward

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

Как это можно оправдать? Как я должен интерпретировать это решение?

Во-первых, посмотрите на объявление режима или индикатор режима:

min_member(-Min, +List)

В документации SWI это описывает, как программист должен использовать этот предикат. Таким образом, первый аргумент не должен быть конкретизирован (и, вероятно, также не должен иметь псевдонима в рамках цели), второй аргумент должен быть конкретизирован в виде какого-либо списка. Для всех других целей вы предоставлены сами себе. Система предполагает, что вы можете проверить это самостоятельно. Вы действительно в состоянии сделать это? У меня, со своей стороны, с этим довольно большие трудности. ISO имеет другую систему, которая также происходит из 10 декабря.

Кроме того, реализация пытается быть разумной для неуказанных случаев. В частности, он старается быть непоколебимым в первом аргументе. Таким образом, минимум сначала вычисляется независимо от значения Min. Затем полученное значение объединяется с Min. За эту устойчивость к неправомерному использованию часто приходится платить. В этом случае min_member/2 всегда должен посещать весь список. Независимо от того, полезно это или нет. Учитывать

?- length(L, 1000000), maplist(=(1),L), min_member(2, L).

Ясно, что 2 не является минимумом L. Это можно обнаружить, рассматривая только первый элемент списка. Из-за общности определения необходимо просмотреть весь список.

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

8.5.4 копия_терм/2

8.5.4.1 Описание

copy_term(Term_1, Term_2) истинно, если и только если Term_2 объединяет
с термином T, который является переименованной копией (7.1.6.2)
Term_1.

or

8.4.3 сортировка/2

8.4.3.1 Описание

sort(List, Sorted) истинно, если и только если Sorted объединяется с
отсортированным списком List (7.1.6.5).

Вот те аргументы (в скобках) встроенных функций, которые можно понимать только как выходные аргументы. Обратите внимание, что есть еще много других аргументов, которые фактически являются выходными аргументами, но не требуют процесса унификации после какой-либо операции. Вспомните 8.5.2 arg/3 (3) или 8.2.1 (=)/2 (2) или (1).

8.5.4 1 copy_term/2 (2), 8.4.2 compare/3 (1 ), 8.4.3 sort/2 (2), 8.4.4 keysort/2 (2), 8.10.1 findall/3 (3), 8.10.2 bagof/3 (3), 8.10.3 setof/3 (3).

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

Срочный заказ

Исторически сложилось так, что стандартный порядок терминов1 был определен, чтобы разрешить определение setof/3 и sort/2 примерно в 1982 году. (До этого, как и в 1978 году, он не упоминался в руководстве по DEC10 руководство пользователя.)

Начиная с 1982 года порядок терминов часто (эмм, аб-) использовался для реализации других порядков, в частности, потому, что DEC10 не предлагал напрямую предикаты более высокого порядка. call/N должен был быть изобретен двумя годами позже (1984); но потребовалось еще несколько десятилетий, чтобы стать общепринятым. Именно по этой причине программисты на Прологе несколько небрежно относятся к сортировке. Часто они намереваются сортировать термины определенного типа, но предпочитают использовать для этой цели sort/2 — без дополнительной проверки ошибок. Еще одной причиной этого была отличная производительность sort/2, превосходящая различные эффективные библиотеки в других языках программирования спустя десятилетия (я полагаю, что в STL тоже была ошибка в этом отношении). Кроме того, полная магия в коде — я помню, что одна переменная называлась Omniumgatherum — не позволяла копировать и изменять код.

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

Оба SICStus и SWI имеют min_member/2, но только SICStus имеет min_member/3 с дополнительным аргументом для указания используемого порядка. Итак, цель

?- min_member(=<, M, Ms).

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

Сноски:

1 Я цитирую стандарт в стандартном порядке терминов, поскольку это понятие существовало примерно с 1982 года, тогда как стандарт был опубликован в 1995 году.

person false    schedule 09.12.2014

arrow_upward
5
arrow_downward

Очевидно, что min_member/2 не является истинным отношением:

?- min_member(X, [X,0]), X = 1.
X = 1.

тем не менее, после простой замены двух целей с помощью (весьма желательной) коммутативности конъюнкции, мы получаем:

?- X = 1, min_member(X, [X,0]).
false.

Это явно совсем плохо, как вы правильно заметили.

Ограничения — это декларативное решение таких проблем. В случае целых чисел ограничения конечной области являются полностью декларативным решением таких проблем.

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

person mat    schedule 09.12.2014
comment
Я пытался найти поведение, которое лучше всего соответствует вопросу, заданному в запросе, и ответу, который мы получаем, глядя на решение. Таким образом, спрашивая, Является ли 3 минимальным членом [1,2,X], я ожидал бы ответа Нет, а не ошибки инстанцирования. - person ; 09.12.2014
comment
Да, в данном случае известно достаточно ясно, чтобы дать определенный ответ, поэтому он не попадает в категорию, в которой мы слишком мало знаем, чтобы дать обоснованный ответ. В вашем примере кода также подумайте о случаях, когда длина списка еще не известна! ?- min_member(X, Xs). и т. д. - person mat; 09.12.2014

arrow_upward
2
arrow_downward

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

?- min_member(X, [A, B]), A = 3, B = 2.
X = A, A = 3,
B = 2.

можно избежать, если некоторые условия можно отложить на момент, когда A и B будут реализованы.

promise_relation(Rel_2, X, Y):-
    call(Rel_2, X, Y),
    when(ground(X), call(Rel_2, X, Y)),
    when(ground(Y), call(Rel_2, X, Y)).

min_member_1(Min, Lst):-
    member(Min, Lst),
    maplist(promise_relation(@=<, Min), Lst).

Что я хочу от min_member_1(?Min, ?Lst), так это выразить отношение, которое говорит, что Min всегда будет ниже (в стандартном порядке терминов), чем любой из элементов в Lst.

?- min_member_1(X, L), L = [_,2,3,4], X = 1.
X = 1,
L = [1, 2, 3, 4] .

Если переменные создаются позже, порядок, в котором они связываются, становится важным, так как может быть выполнено сравнение между свободной переменной и созданной.

?- min_member_1(X, [A,B,C]), B is 3, C is 4, A is 1.
X = A, A = 1,
B = 3,
C = 4 ;
false.
?- min_member_1(X, [A,B,C]), A is 1, B is 3, C is 4.
false.

Но этого можно избежать, объединив их все в одной цели:

?- min_member_1(X, [A,B,C]), [A, B, C] = [1, 3, 4].
X = A, A = 1,
B = 3,
C = 4 ;
false.

Версии

Если сравнения предназначены только для экземпляров переменных, promise_relation/3 можно изменить для проверки отношения только тогда, когда обе переменные будут созданы:

promise_relation(Rel_2, X, Y):-
    when((ground(X), ground(Y)), call(Rel_2, X, Y)).

Простой тест:

?- L = [_, _, _, _], min_member_1(X, L), L = [3,4,1,2].
L = [3, 4, 1, 2],
X = 1 ;
false.

! Были внесены изменения, чтобы улучшить первоначальный пост благодаря комментариям и предложениям пользователя false.

person Tudor Berariu    schedule 09.12.2014
comment
Спасибо! Ты прав. Я изменил Goal =.. [Rel, X, Y], Goal на call(Rel, X, Y). Плохие старые привычки. - person Tudor Berariu; 09.12.2014
comment
Еще раз спасибо. Вы правы, я отредактировал ответ. - person Tudor Berariu; 09.12.2014
comment
Одна небольшая проблема: используйте вместо Rel, а Rel_2 таким образом, очевидно, что термин ожидает два дополнительных аргумента. Никто ни для чего не использует переменные _2, так что это понятно. - person false; 09.12.2014
comment
То, что вы считаете, - это сделать предикат безопасным, отложив его выполнение. В 1980-х годах с этим широко экспериментировали, особенно с MU и NU-Prolog, но без особого успеха. Кажется, что у вас часто оказывается слишком много колеблющихся целей, с которыми вы не можете справиться. И тогда это начинает становиться действительно тяжелым. Если вы хотите больше: просто задайте вопрос. - person false; 09.12.2014

arrow_upward
1
arrow_downward

Вот как реализован min_member/2:

min_member(Min, [H|T]) :-
    min_member_(T, H, Min).

min_member_([], Min, Min).
min_member_([H|T], Min0, Min) :-
    (   H @>= Min0
    ->  min_member_(T, Min0, Min)
    ;   min_member_(T, H, Min)
    ).

Таким образом, кажется, что min_member/2 на самом деле пытается объединить Min (первый аргумент) с наименьшим элементом в List в стандартном порядке терминов.

person Tudor Berariu    schedule 09.12.2014

arrow_upward
0
arrow_downward

У меня есть замечание относительно вашей реализации xmin_member. Это терпит неудачу на этом запросе:

?- xmin_member(1, [X, 2, 3]).
false.

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

ymin_member(Min, Lst):-
    member(Min, Lst),
    maplist(@=<(Min), Lst).

Конечно хуже с точки зрения эффективности, но на тот случай работает:

?- ymin_member(1, [X, 2, 3]).
X = 1 ;
false.

?- ymin_member(X, [X, 2, 3]).
true ;
X = 2 ;
false.
person Tudor Berariu    schedule 09.12.2014
comment
Да, я имел в виду, что это провал. Согласно стандартному порядку членов, свободная переменная меньше любой непеременной, и, очевидно, X не равно 1 (однако ее можно объединить с 1...). Я был бы рад, если бы документация была немного более ясной по этому поводу. См. Также ответ @Jan. - person ; 09.12.2014
comment
Я знаю, что для SWI-Prolog это была просто проблема с документацией для этого предиката. Но я думал, что задача состоит в том, чтобы реализовать как можно более общую версию min_member/2. - person Tudor Berariu; 09.12.2014
comment
Я предполагаю, что мой основной вопрос был скорее о том, как мне реагировать, когда я вижу такое поведение, и позже, когда я должен ожидать этого от библиотечных предикатов. Тем не менее, это полезный ответ. - person ; 09.12.2014