什么使 DCG 谓词变得昂贵？
What makes a DCG predicate expensive?
我正在构建一个定义从句语法来解析 20,000 条半自然文本。随着我的谓词数据库规模的增长（现在多达 1,200 条规则），解析一个字符串可能需要相当长的时间——特别是对于 DCG 目前无法解释的字符串，因为我还没有编码语法。对于包含 30 个单词的字符串，当前的最坏情况是 3 分钟。我正在想办法优化它，或者我是否应该开始研究云计算。
我正在使用 SWI-Prolog，它提供了一个 "profile" 目标，它提供了一些统计数据。我惊讶地发现我数据库中最简单的规则占用了大部分执行时间。我的语料库包含表示数字的字符串，我想在 scalar/3 谓词中捕获这些字符串。这些占用了总执行时间的 ~50-60%。
一开始，我的 scalars.pl 中有 70 行，代表我语料库中数字的数字和自然语言表示。像这样：
scalar(scalar(3)) --> ["three"].
scalar(scalar(3)) --> ["3"].
scalar(scalar(4)) --> ["four"].
scalar(scalar(4)) --> ["4"].
...等等。
考虑到文件的长度是问题所在，我加入了一个新规则，可以自动解析任何数字表示：
scalar(scalar(X)) --> [Y], { atom_number(Y, X) }.
多亏了它，我的规则从 70 条减少到 31 条，并有所帮助 -- 但这并不是一个巨大的节省。还有什么可以做的吗？我的感觉可能不是，因为有什么比列表中的单个原子更简单的呢？
这些标量在整个语法中的很多地方都被调用，我认为这就是问题的根源。尽管它们是简单的规则，但它们无处不在，而且不可避免。高度通用的语法对我的应用程序不起作用，如果我最终有 3,000 条或更多规则我也不会感到惊讶。
我从来没有构建过这么大的 DCG，所以我不确定在性能方面我能期待多少。很高兴就此提出任何建议：是否有其他编码这些规则的方法？我是否应该接受某些解析需要很长时间的事实，并弄清楚如何 运行 并行解析？
提前致谢！
编辑：我被要求提供一个可重现的例子，但要做到这一点，我必须 link 对整个项目如此，因为这是一个规模问题。为了完整起见，这是我正在做的玩具版本。试想一下，有大量文件描述了数百个名词、数百个动词和数百个句法结构。
sent(sent(VP, NP)) --> vp(VP), np(NP).
vp(vp(V)) --> v(V).
np(np(Qty, Noun)) --> qty(Qty), n(Noun).
scalar(scalar(3)) --> ["three"].
scalar(scalar(X)) --> [Y], { atom_number(Y, X) }.
qty(qty(Scalar)) --> scalar(Scalar).
v(v(eat)) --> ["eat"].
n(n(pie)) --> ["pie"].
以下是我作为新手 Prologer 解决性能和优化问题的方法。
1.) 为您的应用程序引入超时。我通过 Python 3.6 中的子进程模块调用 Prolog，它允许您设置超时。随着我更多地使用我的代码库，我对成功解析可能需要多长时间有了很好的了解，并且可以假设任何花费更长的时间都不会起作用。
2.) 使用打包在 swi-prolog IDE 中的图形分析器。这提供了更多的洞察力，因为您可以在调用树周围跳来跳去。我发现根据子项的执行时间对谓词进行排序特别有用。之前我把它想成河流中的污染。 "Man, there's a lot of junk floating in here,"我想，没有考虑到上游一些工厂贡献了很多垃圾。
至于如何在不损害语法的语义和表达能力的情况下优化 DCG，我认为这将是另一个 Stack Overflow 的问题。至于我最初的问题，这仍然是一个悬而未决的问题——（对我来说）看似简单的谓词需要相当长的时间。
您可能要调查的程序的一个方面是确保各个谓词快速成功并快速失败。这对于检查具有很多子句的谓词特别有用。
例如，当 scalar(X) 在不是标量的标记上求值时，程序将必须尝试 31 次（按您的最后计数）次才能确定标量//1 失败。如果您的程序结构是针对每个标记检查标量 (X)，那么这可能会非常昂贵。
此外，如果标量 (X) 确实碰巧发现一个标记匹配但后续目标失败，那么您的程序似乎将重试标量 (X)，直到所有标量//1 子句都已尝试.
明智地使用 cut (!) 或 if-then-else (C1->G1;C2->G2;G3) 可以显着提高性能。
或者您可以构造谓词，使它们依赖于索引到 select 适当的子句。例如：
scalar(scalar(N)) --> [Token], {scalar1(Token, scalar(N))}.
scalar1("3", scalar(3)) :- !.
scalar1(Y, scalar(X)) :- atom_number(Y, X).
这将剪切和子句索引（如果编译器提供）与 scalar1/1 谓词一起使用。
编辑：您应该阅读 R. A. O'Keefe 的 The Craft of Prolog。它是 Prolog 实用方面的优秀指南。
我正在构建一个定义从句语法来解析 20,000 条半自然文本。随着我的谓词数据库规模的增长（现在多达 1,200 条规则），解析一个字符串可能需要相当长的时间——特别是对于 DCG 目前无法解释的字符串，因为我还没有编码语法。对于包含 30 个单词的字符串，当前的最坏情况是 3 分钟。我正在想办法优化它，或者我是否应该开始研究云计算。
我正在使用 SWI-Prolog，它提供了一个 "profile" 目标，它提供了一些统计数据。我惊讶地发现我数据库中最简单的规则占用了大部分执行时间。我的语料库包含表示数字的字符串，我想在 scalar/3 谓词中捕获这些字符串。这些占用了总执行时间的 ~50-60%。
一开始，我的 scalars.pl 中有 70 行，代表我语料库中数字的数字和自然语言表示。像这样：
scalar(scalar(3)) --> ["three"].
scalar(scalar(3)) --> ["3"].
scalar(scalar(4)) --> ["four"].
scalar(scalar(4)) --> ["4"].
...等等。
考虑到文件的长度是问题所在，我加入了一个新规则，可以自动解析任何数字表示：
scalar(scalar(X)) --> [Y], { atom_number(Y, X) }.
多亏了它，我的规则从 70 条减少到 31 条，并有所帮助 -- 但这并不是一个巨大的节省。还有什么可以做的吗？我的感觉可能不是，因为有什么比列表中的单个原子更简单的呢？
这些标量在整个语法中的很多地方都被调用，我认为这就是问题的根源。尽管它们是简单的规则，但它们无处不在，而且不可避免。高度通用的语法对我的应用程序不起作用，如果我最终有 3,000 条或更多规则我也不会感到惊讶。
我从来没有构建过这么大的 DCG，所以我不确定在性能方面我能期待多少。很高兴就此提出任何建议：是否有其他编码这些规则的方法？我是否应该接受某些解析需要很长时间的事实，并弄清楚如何 运行 并行解析？
提前致谢！
编辑：我被要求提供一个可重现的例子，但要做到这一点，我必须 link 对整个项目如此，因为这是一个规模问题。为了完整起见，这是我正在做的玩具版本。试想一下，有大量文件描述了数百个名词、数百个动词和数百个句法结构。
sent(sent(VP, NP)) --> vp(VP), np(NP).
vp(vp(V)) --> v(V).
np(np(Qty, Noun)) --> qty(Qty), n(Noun).
scalar(scalar(3)) --> ["three"].
scalar(scalar(X)) --> [Y], { atom_number(Y, X) }.
qty(qty(Scalar)) --> scalar(Scalar).
v(v(eat)) --> ["eat"].
n(n(pie)) --> ["pie"].
以下是我作为新手 Prologer 解决性能和优化问题的方法。
1.) 为您的应用程序引入超时。我通过 Python 3.6 中的子进程模块调用 Prolog，它允许您设置超时。随着我更多地使用我的代码库，我对成功解析可能需要多长时间有了很好的了解，并且可以假设任何花费更长的时间都不会起作用。
2.) 使用打包在 swi-prolog IDE 中的图形分析器。这提供了更多的洞察力，因为您可以在调用树周围跳来跳去。我发现根据子项的执行时间对谓词进行排序特别有用。之前我把它想成河流中的污染。 "Man, there's a lot of junk floating in here,"我想，没有考虑到上游一些工厂贡献了很多垃圾。
至于如何在不损害语法的语义和表达能力的情况下优化 DCG，我认为这将是另一个 Stack Overflow 的问题。至于我最初的问题，这仍然是一个悬而未决的问题——（对我来说）看似简单的谓词需要相当长的时间。
您可能要调查的程序的一个方面是确保各个谓词快速成功并快速失败。这对于检查具有很多子句的谓词特别有用。
例如，当 scalar(X) 在不是标量的标记上求值时，程序将必须尝试 31 次（按您的最后计数）次才能确定标量//1 失败。如果您的程序结构是针对每个标记检查标量 (X)，那么这可能会非常昂贵。
此外，如果标量 (X) 确实碰巧发现一个标记匹配但后续目标失败，那么您的程序似乎将重试标量 (X)，直到所有标量//1 子句都已尝试.
明智地使用 cut (!) 或 if-then-else (C1->G1;C2->G2;G3) 可以显着提高性能。 或者您可以构造谓词，使它们依赖于索引到 select 适当的子句。例如：
scalar(scalar(N)) --> [Token], {scalar1(Token, scalar(N))}.
scalar1("3", scalar(3)) :- !.
scalar1(Y, scalar(X)) :- atom_number(Y, X).
这将剪切和子句索引（如果编译器提供）与 scalar1/1 谓词一起使用。
编辑：您应该阅读 R. A. O'Keefe 的 The Craft of Prolog。它是 Prolog 实用方面的优秀指南。