Овеществление земли в Прологе с атрибутивными переменными

Question

Я работаю над собственной реализацией.

Внутри,when/2должен уметь — за неимением лучшего слова — «овеществлять»ground/1. Выполнение этого с использованием переменных с атрибутами (в стиле SICStus-Prolog) - вот о чем этот вопрос.

Моя реализация должна работать как следующая "эталонная" реализация:

Ground_t (Термин, T):-
   когда (земля (термин), T = истина).

В порыве любопытства я написал следующий маленький решатель:

:- модуль(ground_t,[ground_t/2]).

:- use_module(библиотека(atts)).
:- атрибут Ground_t/1.

Ground_t (Термин, T):-
    (земля(срок)
    -> Т = правда
    ; term_variables(Термин,Vs),
       create_mutable(Vs,MVs),
       attach_to_new_vars(Vs,MVs,T)
    ).

прикрепить_к_новым_варам([],_,_).
attach_to_new_vars([V|Vs],MVs,T) :-
    ( get_atts(V,+ground_t(Cs0))
    -> Cs = Cs0
    ; С = []
    ),
    put_atts(V,+ground_t([MVs-T|Cs])),
    attach_to_new_vars(Vs,MVs,T).

% простой случай: унифицировать с основным термином
cliques_var_goals__ground([],_,[]).
cliques_var_goals__ground([MVs-T|Cs],Var,Goals) :-
    get_mutable(Vs0,MVs),
    list_eq_removed_atmost_once(Vs0,Var,Vs1),
    update_mutable(Vs1,MVs),
    (Vs1 = []
    -> Цели = [T=true|Цели0]
    ; Голы = Голы0
    ),
    cliques_var_goals__ground(Cs,Var,Goals0).

list_eq_removed_atmost_once([],_,[]).
list_eq_removed_atmost_once([X|Xs],E,Ys) :-
    ( Х == Е
    -> Ys = Xs % удалить элемент. сделать это не более одного раза и остановиться
    ; Ys = [X|Ys0],
       list_eq_removed_atmost_once(Xs,E,Ys0)
    ).

% общий случай: унифицировать с неосновным термином
cliques_var_other__nonvar([],_,_).
cliques_var_other__nonvar([MVs-T|Cs],Var,Other) :-
    get_mutable(Vs0,MVs),
    term_variables(Vs0+Другое,Vs1),
    term_variables(Другое,Новый0),
    list_eq_removed_atmost_once (Новый0, Переменная, Новый),
    list_eq_removed_atmost_once(Vs1,Var,Vs2),
    attach_to_new_vars (Новые, MV, T),
    update_mutable(Vs2,MVs),
    cliques_var_other__nonvar(Cs,Var,Other).

sort_all([]).
sort_all([MVs-_T|Xs]):-
    get_mutable(Vs0,MVs),
    термин_переменные (Vs0,Vs),
    update_mutable(Vs,MVs),
    sort_all (Xs).

merge_cliques_post_unify(Cs0,Cs1, Другое):-
    добавить (Cs0,Cs1,Cs01),
    sort_all (Cs01),
    put_atts(Другое,+ground_t(Cs01)).

verify_attributes (переменная, другое, цели): —
    ( get_atts(Var,+ground_t(Cs0))
    -> (земля(Другое)
       -> cliques_var_goals__ground(Cs0,Var,Цели)
       ; невар(Другое)
       -> cliques_var_other__nonvar(Cs0,Var,Другое),
          Цели = []
       ; get_atts(Другое,+ground_t(Cs1))
       -> Цели = [merge_cliques_post_unify(Cs0,Cs1,Другое)]
       ; put_atts(Другое,+ground_t(Cs0)),
          Цели = []
       )
    ; Цели = []
    ).

клики_к_цели([]) --> [].
cliques_to_goal([MVs-T|Cs]) -->
    {get_mutable(Vs,MVs)},
    ( { Против = [] } -> []
    ; {Vs = [V]} -> [ground_t(V,T)]
    ; [ground_t(Vs,T)]
    ),
    клики_к_цели(Cs).

list_to_commalist([],истина).
list_to_commalist([X],Y):-
    !,
    Х = Y.
list_to_commalist([X|Xs],(X,Y)) :-
    list_to_commalist(Xs,Y).

attribute_goals(Var) -->
    {get_atts(Var,+ground_t(Cs))},
    клики_к_цели(Cs).

attribute_goal(Var,Цель):-
    фраза (attribute_goals(Var), цели),
    list_to_commalist(Цели,Цель).

Это была легкая часть; теперь самое сложное...

Как мне проверить, эквивалентно ли поведение двух решателей, при выполнении нескольких шагов псевдонимов переменных и создания экземпляров в лесу общих терминов?

---

Вот несколько простых ручных тестов, которые я провел:

| ?- Ground_t(X+Y,T1).
| ?-ground_t(X+Y,T1),X=f(U).
| ?-ground_t(X+Y,T1),X=f(U),U=Y.
| ?-ground_t(X+Y,T1),X=f(U),U=Y,Y=y.

| ?-ground_t(X+Y,T1),ground_t(X+Z,T2).
| ?-ground_t(X+Y,T1),ground_t(X+Z,T2),X = -U,Z = +V.
| ?-ground_t(X+Y,T1),ground_t(X+Z,T2),X = -U,Z = +U.
| ?-ground_t(X+Y,T1),ground_t(X+Z,T2),X = -U,Z = +U,U=u.
| ?-ground_t(X+Y,T1),ground_t(X+Z,T2),X = -U,Z = +U,U=u,Y=U.

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

Answer 1

Действительно сложная часть - это, прежде всего, понять, чтоground_t/2на самом деле о. Оно ничего не материализует, ибо нетfalse.

Кажется, это какой-то внутренний вспомогательный предикат, который вам нужно реализовать. Если это внутренний предикат, он не должен соответствовать всем ожиданиям, которые у нас есть в отношении реального ограничения. В частности, ваша реализация (а также ваша эталонная реализация с использованием встроенногоwhen/2) не ограничивает все задействованные переменные:

      SICStus 4.8.0beta3 (x86_64-linux-glibc2.17): Mon Oct 17 20:11:03 UTC 2022
...
| ?- when(ground(A-B),T=true),copy_term(A,Ac,Ac_0),copy_term(B,Bc,Bc_0).
Ac_0 = prolog:trig_ground(Ac,[_A],[Ac,_A],_B,_B),
Bc_0 = true,
prolog:trig_ground(A,[B],[A,B],_C,_C),
prolog:when(_C,ground(A-B),user:(T=true)) ? ;
no
| ?- ground_t(A-B,T),copy_term(A,Ac,Ac_0),copy_term(B,Bc,Bc_0).
Ac_0 = ground_t:(ground_t([Ac,_A],_B),true),
Bc_0 = ground_t:true ? ;
no
| ?- ground_t(A-B,T).
ground_t([A,B],T) ? ;
no
| ?- 

Так что оба не очень стесняютB, Хотяground_t:trueкак бы подсказывает. Кроме того, кажется, что цельground_t([A,B],T)отображается только тогда, когда нетcopy_term/3был использован.

Учитывая такие слабые требования,freeze/2это все, что тебе нужно. Совершенно не нужно вникать в квадроциклы.

      myground_t(Term, T) :-
    term_variables(Term, Vs),
    myvars_t(Vs, T).

myvars_t([], true).
myvars_t([V|Vs], T) :-
    freeze(V, myground_t([V|Vs], T)).

| ?- myground_t(A-B,T),copy_term(A,Ac,Ac_0),copy_term(B,Bc,Bc_0).
Ac_0 = prolog:freeze(Ac,user:myground_t([Ac,_A],_B)),
Bc_0 = true,
prolog:freeze(A,user:myground_t([A,B],T)) ? ;
no

(Хорошая реализацияterm_variables/2можно было бы избежать повторного создания идентичных суффиксов списка. Нет, в настоящее время я ничего не знаю.) Чего не хватает в этой реализации?

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