将非基础变量引入自定义 DSL 查询语言的 Prolog 查询中

Question

我已经使用 SWI-Prolog 编写了一个外部 DSL，它通过使用 DCG 解析文本来工作，将解析的表达式转换为事实，然后 asserted 进入 Prolog 进程，然后向用户公开查询语言使用相同的 DCG 语法查询事实。

我一直在试图弄清楚如何将基于 DCG 的解析器产生的基本术语转换为具有变量的非基本术语，这些变量可以传递到像 findall/3 到 [=79 这样的函子中=] 用户的查询结果列表。

这是一个可以查询的数据集示例：

congruent(const(aa), const(bb)).
congruent(const(bb), const(cc)).
congruent(const(cc), const(dd)).

这里是来自解析器的规范化查询词的示例：

congruent(const(aa), wildcard).

所以我大概需要一些方法将 wildcard 从一个原子转换为一个自由变量，我可以将其传递给 findall/3（或类似变量）。例如：

findall(X, congruent(const(aa), X), Result).

我的问题出现在尝试用自由变量替换 wildcard 时。 AFAIK，仿函数不能 return 一个完全未绑定的自由变量，所以我无法创建任何方法来以编程方式下降复杂查询项以在找到 wildcard 原子的任何地方插入自由变量，然后通过变成像 findall/3.

这样的函子

这是一个更完整的（尽管是人为的）示例，它说明了我尝试将变量引入查询的方式：

main :-
    query(congruent(const(aa), wildcard), Result),
    format("Result: ~p~n", [Result]).

query(QueryTerm, Result) :-
    % This is what I cannot figure out how to implement...
    xform_wildcards_to_free_vars(QueryTerm, QueryWithVars),

    term_variables(QueryWithVars, FreeVars),
    findall(FreeVars, QueryWithVars, Result).

% This is a contrived fact that transforms only one specific
% type of query, but even this wouldn't work because Wildcard
% would be considered a singleton.
xform_wildcards_to_free_vars(
        congruent(const(X), wildcard),
        congruent(const(X), Wildcard)
).

我仔细研究了 SWI-Prolog 文档，试图找到一些可以让我将基本术语转换为非基本术语的仿函数，但我一直在旋转我的轮子无法找到任何东西。我错过了什么？当然，这是 Prolog 的一个足够常见的用例，它支持这个。

编辑：示例测试用例

下面的Guy Coder让我提供一个测试用例，所以就在这里。评论太长了。

:- table congruent/2.

congruent(A, C) :- congruent(A, B),
                   congruent(B, C).

congruent(const(aa), const(bb)).
congruent(const(bb), const(cc)).
congruent(const(cc), const(dd)).
congruent(const(cc), const(ee)).
congruent(const(ee), const(ff)).
congruent(const(yy), const(zz)).

assert_congruences :-
    assertion(congruent(const(aa), const(bb))),
    assertion(congruent(const(bb), const(dd))),
    assertion(congruent(const(bb), const(ee))),
    assertion(congruent(const(bb), const(ff))),
    assertion(not(congruent(const(bb), const(yy)))),
    assertion(not(congruent(const(bb), const(zz)))).

assert_query :-
    query(congruent(const(aa), wildcard), Results),
    assertion(member(const(ff), Results)).

上面的最后一行显示了假设的 query/2 函子如何 return 一个术语列表，如果像上面那样使用 findall/3在找到 wildcard 的地方引入了自由变量。

我确实需要这个来处理复杂的术语，这些术语可以在一个术语中嵌套一个或多个通配符。我上面的示例仅显示了一个传递性 congruent/2 谓词，但我还有其他逻辑上更复杂的谓词也可用于查询。

编辑 2：实施有效！谢谢 slago 和 Isabelle！

好的，我终于成功了！这是我想出的：

:- module(repl, []).

:- table congruent/2.

congruent(A, C) :- congruent(A, B),
                   congruent(B, C).

congruent(A, B) :-
    congruences(List),
    nth0(IndexA, List, A),
    nth0(IndexB, List, B),
    IndexA < IndexB.

congruences([const(aa), const(bb), const(cc), const(dd)]).
congruences([const(cc), const(ee), const(ff)]).
congruences([const(yy), const(zz)]).

related(const(aa), eins).
related(const(cc), zwei).
related(const(ff), drei).
related(const(zz), vier).

main :-
    FooQuery = ( congruent(const(aa), wildcard(foo)) ),
    BarQuery = ( related(wildcard(foo), wildcard(bar)) ),

    query_and_log(FooQuery),
    query_and_log(BarQuery),
    query_and_log((FooQuery,BarQuery)).

query_and_log(QueryTerm) :-
    query(QueryTerm, Result),
    format("~nQUERY: ~p~nRESULT:~p~n~n-----~n", [QueryTerm, Result]).

query(QueryTerm, Result) :-
    prepare_query(QueryTerm, NamedVars, QueryWithVars),
    findall(NamedVars, QueryWithVars, Result), !.

prepare_query(Term, NamedVars, TermWithVars) :-
    dict_create(EmptyDict, vars, []),
    xform_wildcards_to_free_vars(Term, EmptyDict-[], VarsDict-[TermWithVars]),
    format("~nPREPARED QUERY VARS: ~p~nPREPARED QUERY TERMS: ~p~n",
           [VarsDict, TermWithVars]),
    dict_pairs(VarsDict, vars, NamedVars).

% Compound terms must be recursively searched for new wildcards while
% reusing any previously created wildcard fresh variables.
xform_wildcards_to_free_vars(Term, PrevVars-PrevTerms, NewVars-NewTerms) :-
    compound(Term),
    Term =.. [TermName|SubTerms],
    TermName \= wildcard,
    foldl(
        xform_wildcards_to_free_vars,
        SubTerms,
        PrevVars-[],
        NewVars-SubTermsWithVars
    ),
    TermWithVars =.. [TermName|SubTermsWithVars],
    append(PrevTerms, [TermWithVars], NewTerms).

% Atomic terms are emitted as-is into NewTerms leaving Vars unchanged
xform_wildcards_to_free_vars(Term, Vars-PrevTerms, Vars-NewTerms) :-
    atomic(Term),
    not(Term =.. [wildcard|_]),
    append(PrevTerms, [Term], NewTerms).

% When Name is already found in Vars, re-use the same variable
xform_wildcards_to_free_vars(wildcard(Name), Vars-PrevTerms, Vars-NewTerms) :-
    get_dict(Name, Vars, ReusedVar),
    append(PrevTerms, [ReusedVar], NewTerms).

% When Name isn't in PrevVars, create a new fresh var in NewVars for it
xform_wildcards_to_free_vars(wildcard(Name), PrevVars-PrevTerms, NewVars-NewTerms) :-
    not(get_dict(Name, PrevVars, _)),
    put_dict(Name, PrevVars, FreshVar, NewVars),
    append(PrevTerms, [FreshVar], NewTerms).

% Re-write wildcard with no args as wildcard('?')
xform_wildcards_to_free_vars(wildcard, V1-T1, V2-T2) :-
    xform_wildcards_to_free_vars(wildcard('?'), V1-T1, V2-T2).

与我之前共享的代码示例相比，这里有一些值得一提的更改：

现在有一个 related/2 谓词，其中包含一些用于连接的简单虚拟数据
通配符现在有原子名称来区分它们
同余在语义上的作用相同，但现在有一个 congruences/1 谓词。这是一个表面上的变化。
xform_wildcards_to_free_vars/3 现在用字典折叠术语的子术语（“args”）以跟踪先前创建的新变量。如果没有这个，wildcard(foo) 的每次出现都会有自己的 unique 新变量，而不是重复使用以前的变量。

这是 main/0 的输出：

?- repl:main.

PREPARED QUERY VARS: vars{foo:_8244}
PREPARED QUERY TERMS: congruent(const(aa),_8244)

QUERY: congruent(const(aa),wildcard(foo))
RESULT:[[foo-const(ff)],[foo-const(dd)],[foo-const(ee)],[foo-const(bb)],[foo-const(cc)]]

-----

PREPARED QUERY VARS: vars{bar:_8616,foo:_8578}
PREPARED QUERY TERMS: related(_8578,_8616)

QUERY: related(wildcard(foo),wildcard(bar))
RESULT:[[bar-eins,foo-const(aa)],[bar-zwei,foo-const(cc)],[bar-drei,foo-const(ff)],[bar-vier,foo-const(zz)]]

-----

PREPARED QUERY VARS: vars{bar:_9236,foo:_9120}
PREPARED QUERY TERMS: congruent(const(aa),_9120),related(_9120,_9236)

QUERY: congruent(const(aa),wildcard(foo)),related(wildcard(foo),wildcard(bar))
RESULT:[[bar-drei,foo-const(ff)],[bar-zwei,foo-const(cc)]]

-----
true.

这是一个棘手的问题，但我很欣慰它运行得这么好！ Slago 和 Isabelle 对我找到这种方法很有帮助！

Answer 1

单例变量是一种方法。您的解决方案实际上很好，如果您用下划线标记单例变量，则不会发出警告：

xform_wildcards_to_free_vars(
        congruent(const(X), wildcard),
        congruent(const(X), _Wildcard)
).

这确实是“return [包含一个]完全未绑定的自由变量的术语”。它将给出您似乎期望的结果（与您原来的 main/0）：

?- main.
Result: [[const(dd)],[const(ee)],[const(bb)],[const(cc)],[const(ff)]]
true.

单例变量在纯 Prolog 中相当无用，因为它们无法共享，因此即使单例变量绑定到某物，您以后也无法检查该绑定。但是您使用不纯的 term_variables/2 确实引入了对以前未共享变量的共享，因此您的程序按预期工作。 reader 标记为单例的变量稍后会共享，这只是有点误导。

如果只有一个变量，另一种方法是将变量公开为额外参数：

xform_wildcards_to_free_vars(
        congruent(const(X), wildcard),
        congruent(const(X), Wildcard),
        Wildcard
).

query(QueryTerm, Result) :-
    xform_wildcards_to_free_vars(QueryTerm, QueryWithVars, Var),
    findall(Var, QueryWithVars, Result).

这与您的版本相同，但更纯粹，可以说更清晰，因为 Wildcard 变量的共享显示得很清楚。但是，如果您可以拥有多个应对应于不同变量的不同通配符，那么您的查询转换谓词将涉及更多记账工作。

Answer 2

我认为更通用的解决方案是更改语法，使其在句子解析期间插入和收集必要的变量。

只是为了说明这一点（无需过多关注下面呈现的语法和代码的质量），您可以尝试这样的操作：

binrel(Vars-Term) -->                   % a simple binary relation
    entity(X),
    relation(R),
    entity(Y),
    { include(var, [X,Y], Vars),        % include only variables in Vars list
      Term =.. [R, X, Y] }.

entity(_)   --> [wildcard], !.          % use a fresh variable for each wildcard!
entity(C)   --> [C], { C \= wildcard }.
relation(R) --> [R], { R \= wildcard }.

db_tell(Text) :-
    tokenize_atom(Text, Tokens),
    phrase(binrel(_-Term), Tokens),
    functor(Term, Name, Arity),
    dynamic(Name/Arity),
    assertz(Term).

db_ask(Text, Results) :-
    tokenize_atom(Text, Tokens),
    phrase(binrel(Vars-Term), Tokens),
    findall(Vars, Term, Results).

db_create :-
    db_tell('ann likes apple'),
    db_tell('ann likes orange'),
    db_tell('bob likes banana'),
    db_tell('coy likes banana').

示例：

?- db_create.
true.

?- db_ask('ann likes wildcard', Results).
Results = [[apple], [orange]].

?- db_ask('bob likes wildcard', Results).
Results = [[banana]].

?- db_ask('wildcard likes orange', Results).
Results = [[ann]].

?- db_ask('wildcard likes wildcard', Results).
Results = [[ann, apple], [ann, orange], [bob, banana], [coy, banana]].

Answer 3

另一种可能性是递归地将术语转换为新的等效术语，用新变量替换通配符。

% wildcards_to_variables(++Term, --NewTerm, --Variables)

  wildcards_to_variables(wildcard, Variable, [Variable]) :- !.
  wildcards_to_variables(Term, Term, []) :- atomic(Term), !.
  wildcards_to_variables(Term, NewTerm, Variables) :-
      compound(Term),
      compound_name_arguments(Term, Name, Args),
      maplist(wildcards_to_variables, Args, NewArgs, Vars),
      compound_name_arguments(NewTerm, Name, NewArgs),
      append(Vars, Variables).

示例：

?- wildcards_to_variables(congruent(const(aa), wildcard), NewTerm, Variables).
NewTerm = congruent(const(aa), _A),
Variables = [_A].

?- wildcards_to_variables(congruent(const(wildcard), wildcard), NewTerm, Variables).
NewTerm = congruent(const(_A), _B),
Variables = [_A, _B].

?- wildcards_to_variables(and(congruent(const(aa),wildcard), congruent(wildcard,const(wildcard))), NewTerm, Variables).
NewTerm = and(congruent(const(aa), _A), congruent(_B, const(_C))),
Variables = [_A, _B, _C].

因此，查询谓词query/2可以定义为：

query(Term, Results) :-
    wildcards_to_variables(Term, NewTerm, Vars),
    findall(Vars, NewTerm, Results).

将非基础变量引入自定义 DSL 查询语言的 Prolog 查询中

Introducing non-ground vars into a Prolog query for a custom DSL query language

prolog

编辑：示例测试用例

编辑 2：实施有效！谢谢 slago 和 Isabelle！