Процедурна семантика на swi-Prolog: неразбиране на полученото заместване

Не успявам да разбера поведението на swi-prolog, когато базата данни

на(a,b).

се запитва с

:- върху (A, B), върху (C, D).

Доколкото разбирам, това, което трябва да се случи, е следното: първо, най-лявата цел в заявката се съпоставя с базата данни. Това успява незабавно, което води до премахването на споменатия гол от заявката, както и до замяната

[A=a,B=b]

След това това заместване се прилага към оставащия гол, което не прави нищо, тъй като нито А, нито Б се появяват във втория гол. Сега оставащата цел се съпоставя с базата данни, което отново успява. Сега сме готови и трябва да останем със смяната

[A=a,B=b,C=a,D=b]

И това трябва да е единственото заместване, което интерпретаторът може да измисли, при условие че разбирането ми за процедурната семантика на пролозите е правилно. За съжаление, swi-prolog мисли друго. Вместо това идва със замяната

[A=C,B=D,C=a,D=b]

Ако сте много щедри, бихте могли да кажете, че „и двата отговора означават едно и също“, но аз никога не съм щедър, когато става въпрос за разбиране какво прави една програма, и се натъкнах на това в контекст, в който това наистина има значение. Така че ще бъда много благодарен, ако някой може да ми помогне да разбера какво се случва.


substitution semantics prolog
person Nestor    schedule 10.04.2020    source източник
comment
Вторият изход трябва да бъде [A=C,B=D,C=a,D=b] вместо [A=C,B=D,C=a,D=a]   -  person David Tonhofer    schedule 11.04.2020
comment
Благодаря, коригирано! :)   -  person Nestor    schedule 12.04.2020

Отговори (3)


arrow_upward
2
arrow_downward

Нещо близко до изхода, който искате, но използвайки обичайното представяне на двойки на Prolog:

bindings(Query, Bindings) :-
    term_variables(Query, Variables),
    copy_term(Query, Copy),
    term_variables(Copy, VariablesCopy),
    call(Copy),
    pairs_keys_values(Bindings, Variables, VariablesCopy).

Примерно обаждане:

?- bindings((on(A,B),on(C,D)), Bindings).
Bindings = [A-a, B-b, C-a, D-b].

Единственият нестандартен предикат е pairs_keys_values/3, но той е наличен в няколко библиотеки. По-горе използвах library(pairs) от SWI-Prolog. Logtalk (който можете да стартирате с повечето системи Prolog) предоставя pairs библиотечен обект с keys_values/3 предикат със същата семантика и ред на аргументите.

person Paulo Moura    schedule 10.04.2020
comment
Благодаря ви, това определено работи. Така че практическата страна на въпроса ми е решена. Все още обаче не успявам да разбера какво точно прави swi-prolog, за да изведе A=C, B=D. Очевидно моята идея за процедурната семантика на prologs не улавя точно какво прави abstract машината на warren (двигателят под капака на swi-prolog). - person Nestor; 11.04.2020

arrow_upward
1
arrow_downward

Но двете замествания са еднакви.

Можем да познаем нещо само чрез неговите взаимодействия; за която и да е валидна реализация на substitute( Term, Substitution, Substituted_term ) не може да се наблюдава разлика с нито един от двата формуляра, които показвате.

Следователно това е чисто въпрос на представителство. Всяко представяне може да бъде избрано, стига наблюдаваните резултати да останат същите.

person Will Ness    schedule 10.04.2020
comment
Няма съмнение, че сте прави, що се отнася до смисъла на резултата. Как обаче интерпретаторът на пролог знае, че A=C и B=D. При условие, че пътят на изчислението е както е описано в началния ми въпрос, не би трябвало. - person Nestor; 11.04.2020
comment
в такъв случай вашият е по-скоро въпрос за имплементация на езика. може би трябва да бъде маркиран като такъв, така че това е ясно. - person Will Ness; 11.04.2020
comment
Може би SWI прави някаква стъпка на уплътняване всеки път, когато добавя ново свързване към текущото заместване; или дори само когато го докладвате на най-високо ниво... - person Will Ness; 11.04.2020
comment
@Nestor Никога няма да разберем. Горното ниво може да има позицията, че просто отпечатва всеки термин веднъж (той вече агресивно съкращава списъците при разпечатване, grrr) и когато срещне друга променлива, препращаща към този термин, вместо това просто ще отпечата израз за равенство на променлива. - person David Tonhofer; 11.04.2020

arrow_upward
0
arrow_downward

Имайте предвид, че резултатът е валиден дори за:

on(a,b).
on2(a,b).

?- on(A,B),on2(C,D).
A = C, C = a,
B = D, D = b.

Във всеки случай би било по-хубаво от Prolog да пише

A = C = a,
B = D = b.

Ето диаграма от по-рано, която адаптирах. Нямам представа дали нещата се изпълняват така, може би NULL указатели се използват, когато променливата е "прясна"? Не е важно.

Променливи и техните обвързвания

person David Tonhofer    schedule 11.04.2020
comment
Понякога мисля за logvars като за именувани указатели. set-once (т.е. едно присвояване), разбира се (без обратно проследяване). когато вътрешният свободен logvar на термин е зададен по-надолу по пътя, горното свързване за този термин остава както е. (това е процедурно). за A=p(X), X=z или {A-->p(X)} се превръща в {A-->p(X); X-->z}, или {A--> place1:value=p( place2:value=X ) ; X--> NIL} се превръща в {A--> place1:value=p( place2:value=z ) ; X--> place2} (т.е. без споделяне или с него). нещо такова може би. Всъщност никога не съм прилагал собствен Prolog. - person Will Ness; 11.04.2020
comment
@WillNes Понякога се чудя как изобщо е възможно да се програмира в Prolog, защото човек никога не обмисля всички последици от това, което се случва там, и все още може да излъчва код независимо от това. Със сигурност има докторска степен по когнитивни науки. - person David Tonhofer; 11.04.2020
comment
импликациите са същите, семантично; единствената възможна разлика е оперативна (т.е. същата стойност, различно време/пространство, за да стигнете до там). това е много по-изразено в Haskell btw. и второ между другото, мечтата ми е никога да не се занимавам с оперативни съображения -- за това се предполага, че са там компилаторите. :) Може би някой ден. :) - person Will Ness; 11.04.2020