programming-languages - 反向推理引擎(找到一个随机的 X，其中 foo(X) 为真)

Question

我知道像 Prolog 这样的语言允许您编写如下内容:

凡人(X) :- 人(X)。 % 所有的人都会死
人(苏格拉底)。 % 苏格拉底是人

?- 凡人(苏格拉底)。 % 苏格拉底会死吗？
是的

我想要的是这样的东西，但倒退。假设我有这个:

凡人(X) :- 人(X)。
人(苏格拉底)。
人(柏拉图)。
人(亚里士多德)。

然后我要求它给我一个随机的 X，其中 mortal(X) 是真的(因此它应该根据一些随机种子给我一个“苏格拉底”、“柏拉图”或“亚里士多德”)。

我的问题是:

这种反向推理有名字吗？

有没有支持它的语言或库？

编辑

正如下面有人指出的那样，您可以简单地询问 mortal(X) ，它会返回所有 X，您可以简单地从列表中随机选择一个。但是，如果该列表非常大，可能达到数十亿，该怎么办？显然，在这种情况下，在选择一个之前生成所有可能的结果是行不通的。

要了解这将如何成为一个实际问题，请想象一个简单的语法，它生成了一个形式为“adjective1 noun1 adverb transitionive_verb adjective2 noun2”的随机句子。如果形容词、名词、动词等的列表非常大，你可以看到组合爆炸是多么的一个问题。如果每个列表有 1000 个单词，那么您将有 1000^6 个可能的句子。

Answer 1

可以轻松实现随机化的深度优先搜索策略，而不是 Prolog 的深度优先搜索。所需要做的就是在选择点随机化程序流，以便每次到达析取点时都会选择搜索树(= prolog 程序)上的一个随机极点，而不是第一个。

但是，请注意，这种方法并不能保证所有解决方案的可能性都相同。为了保证这一点，需要提前知道每个极点将生成多少个解来相应地对随机化进行加权。