Пролог: отсутствует функция?

Question

Любой программист, имеющий некоторый опыт в Прологе, знает преимущества использования унарной записи чисел. Например, если мы представляем число в виде списка 1" ("4"- это список"[1,1,1,1]"и т. Д.), Мы можем определить:

unary_succ(X,[1|X]).

следующие запросы делают то, что ожидается:

?- X=[1,1],unary_succ(X,Y).
X = [1, 1],
Y = [1, 1, 1].

?- unary_succ(X,Y),X=[1,1].
X = [1, 1],
Y = [1, 1, 1].

?- unary_succ(X,Y),Y=[1,1].
X = [1],
Y = [1, 1].

Таким образом, оператор unary_succ(X,Y) "связывает" X и Y таким образом, что, если после того, как факт установлен, одна из этих переменных связана со значением, другая - с другой.

Однако такое поведение невозможно, если мы используем внутреннее представление чисел:

?- X=2,succ(X,Y).
X = 2,
Y = 3.

?- succ(X,Y),X=2.
ERROR: succ/2: Arguments are not sufficiently instantiated

?- succ(X,Y),Y=2.
ERROR: succ/2: Arguments are not sufficiently instantiated

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

Мои вопросы:

а) какой-то простой способ сделать это в прологе.

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

Любые комментарии приветствуются.

Спасибо всем.

* Приложение I *

Другой пример:

user_id(john,1234).
user_id(tom,5678).

и запросы:

X=john,user_id(X,Y).
user_id(X,Y),X=john

что в настоящее время решается путем возврата.

Answer 1

Эта тема известна как сопрограммирование, и для ее решения достаточно общим способом - afaik - требуется расширение базовой модели вычислений Prolog. К счастью, большинство прологов имеют такое расширение... Итак, давайте попробуем в SWISH создать собственное "реактивное" расширение:

my_succ(X, Y) :- when((nonvar(X);nonvar(Y)), succ(X, Y)).

отредактируйте не совсем точно, но Ян разместил в списке рассылки SWI-Prolog простой пример приложения сопроводителя:

?- freeze(X, writeln(X)), findall(X, between(1,3,X), Xs).
1
2
3
Xs = [1, 2, 3],
freeze(X, writeln(X)).

Answer 2

Проблема, которую вы описываете, существует до тех пор, пока ответы системы Prolog ограничены (синтаксическими) подстановками ответов. В вашем примере цель succ(X, Y) потребовалось бы бесконечно много ответов, чтобы описать весь набор решений. По этой причине instantiation_error выдается вместо.

Для решения этой проблемы нам нужно расширить ответы. Таким образом, ответы включают не только замены ответов, но и более сложный способ описания некоторых наборов.

library(clpfd) предлагая ограничения по Z (и наиболее заметные конечные области).

?- use_module(library(clpfd)).
?- Y #= X+1.
X+1#=Y.

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

?- Y #= X+1, X #= Y+1.
Y+1#=X,
X+1#=Y.

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

when/2 также известен как сопрограмма и во многих случаях слабее, чем вы получаете с clpfd, Но в некоторых случаях это сильнее для некоторых реализаций clpfd, Рассматривать dif/2 который может быть выражен как when(?=(X,Y), X \== Y) а также

| ?- dif(X, Y), X = Y.
no

... тогда как (в SICStus)

| ?- X #\= Y, X #= Y.
Y #= X,
Y #\= X,
Y in inf..sup,
X in inf..sup ? ;
no

library(clpq) предлагает решатель, который сильнее во многих ситуациях, но не имеет целочисленных конкретных ограничений, таких как mod/2, Во многих ситуациях это все еще интересно использовать, как здесь, в SICStus:

| ?- use_module(library(clpq)).
yes
| ?- {Y=X+1}.
{X = -1+Y} ?
yes
| ?- {Y=X+1}, {X=Y+1}.
no