Сделайте предикат обратимым

Question

Я новичок в прологе; Я исхожу из опыта структурированного программирования, что станет очевидным:)

Я строю запрос пролога, который включает в себя изменение числа; например. reverse_num(123,X) результаты в X = 321, Я придумал следующее определение, но оно работает только тогда, когда я указываю число в качестве первого параметра.

reverse_num(Num, Revnum) :-
  number_chars(Num, Atoms),
  reverse(Revatoms, Atoms),
  number_chars(Reversed, Revatoms),
  Reversed = Revnum.

number_chars/2 предикат не любит необоснованную переменную, если я делаю: reverse_num(X,123) (где я ожидаю X быть 321).

Я слишком стараюсь, чтобы reverse_num делал то, что не должен (следует понимать, что он работает только с числом в качестве первого параметра и переменной в качестве второго)?

Или есть простой / прямой способ обработки переменной в качестве первого параметра?

Answer 1

Реляционное именование

Прежде чем перейти к кодированию, давайте сделаем шаг назад. В конце концов, идея в Прологе - определить отношения. Ваше имя reverse_num/2 скорее предлагает некоторые действия, num_reversed/2 может быть лучшим именем

Определить отношение

Ваше определение не так уж плохо, позвольте мне переписать его ¹:

num_reversed(Num, Reversed) :-
   number_chars(Num, Chars),
   reverse(Chars, Revchars),
   number_chars(Reversed, Revchars).

?- num_reversed(123,X).
X = 321.

?- num_reversed(1230,X).
X = 321.

?- num_reversed(12300,X).
X = 321.

Вы видите образец? Все числа N*10^I иметь тот же результат!

Теперь давайте спросим еще:

?- num_reversed(Num, 321).
ERROR: number_chars/2: Arguments are not sufficiently instantiated

Хм, что мы ожидали? На самом деле, мы хотели все 123*10^I быть напечатанным. Это бесконечно много решений. Таким образом, приведенный выше запрос, если правильно ответить, потребует печати бесконечного множества решений. Если мы напечатаем их напрямую, это займет всю жизнь нашей вселенной и даже больше!

Именно по этой причине Пролог вместо этого создает ошибку инстанцирования. Этим Пролог по существу заявляет:

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

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

Coroutining

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

Но ради всего этого мы могли бы сделать наше определение более универсальным, сделав его следующим

 ?- when(nonvar(Num), num_reversed(Num, Reversed)).
 when(nonvar(Num), num_reversed(Num, Reversed)).

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

?- when(nonvar(Num), num_reversed(Num, -1)).
when(nonvar(Num), num_reversed(Num, -1)).

Другие предложили также подождать nonvar(Reversed) это было бы правильно, если бы мы давали бесконечно много ответов - но, как мы видели, это просто занимает слишком много времени.

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

Тем не менее, более перспективным потомком этого развития являются ограничения. Там механизмы гораздо чётче определены. В практических целях программисты будут использовать только существующие библиотеки, такие как CLPFD, CLPQ или CHR. Реализация собственной библиотеки - это совершенно нетривиальный проект сам по себе. На самом деле это может быть даже возможно обеспечить реализацию num_reversed/2 с помощью library(clpfd) то есть ограничение отношения к целочисленному регистру.

Зависящие от режима условия

Традиционно многие такие проблемы решаются путем явного тестирования экземпляров. Это хороший стиль, чтобы выполнять это исключительно с nonvar/1 а также ground/1 как условие в when/2 - тестовые предикаты другого типа легко приводят к ошибкам, о чем свидетельствует другой ответ.

num_reversed(Num, Reversed) :-
   (  nonvar(Num)
   -> original_num_reversed(Num, Reversed)
   ;  original_num_reversed(Reversed, Base),
      (  Base =:= 0
      -> Num is 0
      ;  length(_, I),
         Num is Base*10^I
      )
   ).

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

Что касается определения number_chars/2, ISO/IEC 13211-1:1995 имеет следующий подпункт шаблона и режима:

8.16.7.2 Шаблон и режимы

number_chars(+number, ?character_list)
number_chars(-number, +character_list)

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

Обратите внимание, однако, что из-за очень похожих проблем, number_chars/2 это не отношение. Как пример, Chs = ['0','0'], number_chars(0, Chs) успешно, тогда как number_chars(0, Chs), Chs = ['0','0'] выходит из строя.

_{Очень мелкий шрифт}

1 Это переписывание необходимо, потому что во многих прологах reverse/2 завершается только если известен первый аргумент. И в SWI это переписывание необходимо из-за некоторых специфических недостатков.

Answer 2

number_chars/2 Предикат имеет подпись:

number_chars(?Number, ?CharList) 

Но хотя и не полностью указано в подписи, по крайней мере Number или же CharList должны быть созданы. Вот откуда возникает ошибка.

Если вы позвоните:

reverse_num(Num,123)

Ты позвонишь number_chars/2 с обоими неустановленными в то время, так что предикат будет ошибкой.

Не очень хорошее решение проблемы - спросить Num или же RevNum являются number/2s. Вы можете сделать это, написав две версии. Кроме того, он будет фильтровать другие звонки, такие как reverse_num(f(a),b), так далее.:

reverse_num(Num,Revnum) :-
    \+ number(Num),
    \+ number(Revnum),
    throw(error(instantiation_error, _)).

reverse_num(Num, Revnum) :-
    ground(Num),
    number(Num),
    !,
    number_chars(Num, Atoms),
    reverse(Revatoms, Atoms),
    number_chars(Revnum, Revatoms).

reverse_num(Num, Revnum) :-
    ground(Revnum),
    number(Revnum),
    reverse_num(Revnum,Num).

Или вы можете в случае, если вы используете два nonground (например, reverse_num(X,Y).) ошибка инстанцирования вместо false как говорит @false:

reverse_num(Num,Revnum) :-
    \+ number(Num),
    \+ number(Revnum),
    !,
    throw(error(instantiation_error, _)).

reverse_num(Num, Revnum) :-
    number(Num),
    !,
    number_chars(Num, Atoms),
    reverse(Revatoms, Atoms),
    number_chars(Revnum, Revatoms).

reverse_num(Num, Revnum) :-
    reverse_num(Revnum,Num).

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

Если predicate/2 является коммутативным, решение, которое может быть обобщено, имеет следующий характер:

predicate(X,Y) :-
    predicate1(X,A),
    predicate2(A,B),
    % ...
    predicaten(C,Y).
predicate(X,Y) :-
    predicate(Y,X).

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

Answer 3

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

Если используется система Prolog, которая поддерживает сопрограммирование и when/2 встроенный предикат (например, SICStus Prolog, SWI-Prolog или YAP), попробуйте как:

reverse_num(Num, Reversed) :-
  when( ( ground(Num); ground(Atoms) ), number_chars(Num, Atoms) ),
  when( ( ground(Reversed); ground(Revatoms) ), number_chars(Reversed, Revatoms) ),
  reverse(Atoms , Revatoms).

это дает:

?- reverse_num( 123, X ).
X = 321.

?- reverse_num( X, 123 ).
X = 321 .

(спасибо людям, которые предоставили ответы на эти вопросы: Пролог: отсутствует функция?)

Answer 4

Этот сеанс SWISH показывает мое усилие ответить.

Затем я вернулся сюда, где обнаружил, что у меня настроение @PasabaPorAqui (+1), но я не понял его правильно.

Но такая интересная тема: обратите внимание, насколько регулярным является шаблон соединения.

reverse_num(X, Y) :-
    when((nonvar(Xs);nonvar(Ys)), reverse(Xs, Ys)),
    when((nonvar(X) ;nonvar(Xs)), atomic_chars(X, Xs)),
    when((nonvar(Y) ;nonvar(Ys)), atomic_chars(Y, Ys)).

Итак, мы можем обобщить простым способом (после учета поправки PasabaPorAqui, Ground/1 это ключ):

% generalized... thanks Pasaba Por Aqui
:- meta_predicate when_2(0).
when_2(P) :-
    strip_module(P,_,Q),
    Q =.. [_,A0,A1],
    when((ground(A0);ground(A1)), P).

reverse_num(X, Y) :-
    maplist(when_2, [reverse(Xs, Ys), atomic_chars(X, Xs), atomic_chars(Y, Ys)]).

Я думаю, что понимаю, почему nonvar/1 был проблематичным: список, обращенный к реверсу, "запускается" слишком рано, когда только голова становится связанной… слишком быстро!

maplist / 2 на самом деле не нужен: от руки мы можем написать

reverse_num(X, Y) :-
    when_2(reverse(Xs, Ys)),
    when_2(atomic_chars(X, Xs)),
    when_2(atomic_chars(Y, Ys)).

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

reverse_num(X, Y) -:-
    reverse(Xs, Ys),
    atomic_chars(X, Xs),
    atomic_chars(Y, Ys).

edit SWISH, возможно, не подходит для term_rewrite... так что вот подход более низкого уровня:

:- op(900, xfy, ++).
A ++ B ++ C :- when_2(A), B ++ C.
A ++ B :- when_2(A), when_2(B).

reverse_num(X, Y) :- 
    reverse(Xs, Ys) ++ atomic_chars(X, Xs) ++ atomic_chars(Y, Ys).

Answer 5

Если оставить в стороне проблему конечных нулей, превращающихся в ведущие нули, не похоже, что это должно быть намного сложнее, чем что-то вроде этого (сделанное несколько более сложным, имея дело с отрицательными числами):

reverse_number(X,Y) :- number(X) , ! , rev(X,Y) .
reverse_number(X,Y) :- number(Y) , ! , rev(Y,X) .

rev(N,R) :-
  N < 0 ,
  ! ,
  A is abs(N) ,
  rev(A,T) ,
  R is - T
  .
rev(N,R) :-
  number_chars(N,Ns) ,
  reverse(Ns,Rs) ,
  number_chars(R,Rs)
  .

Обратите внимание, что для этого требуется хотя бы один из аргументов reverse_number/2 быть воплощенным в жизнь.