2

我正在努力编写更具可读性的声明性程序。所以我决定实现一个我们目前使用的简单算法。程序实现如下：

  1. 有命令和资源
  2. 每个命令可以提供和需要多个资源
  3. 该算法将遍历所有命令并安排提供所有要求的命令。
  4. 该命令提供的所有资源现在都提供给
  5. 如果所有命令都安排好了，我们就完成了
  6. 如果还有命令，我们就不能满足依赖关系，我们不能为算法的迭代安排新命令

所以我想出的数据记录变体看起来不错，但有两个问题：

  1. 这是错误的
  2. 我需要一个循环来读取结果

您可以在此处找到完整的源代码。

这取决于假设，您可以使用 pytest 轻松运行它。

下面的测试失败：如果我们需要以前的“等级”或顺序提供的资源。它找不到它。我试图使跟随递归，但即使在简单的例子中它也失败了。

def test_graph_multirequire():
    """Test if the resolver can handle a graph with multiple requires"""
    tree = [
        [('A'), ('B'), ('C'), ('D'), ('E'), ('F'), ('G'), ()],
        [(), ('A'), ('B'), ('C', 'A'), ('D'), ('E'), ('F'), ('G')]
    ]
    run_graph(tree)


def run_graph(tree):
    """Run an example"""
    try:
        tree_len = len(tree[0])
        index = list(range(tree_len))
        random.shuffle(index)
        for i in index:
            + is_command(i)
            for provide in tree[0][i]:
                + provides(i, provide)
            for require in tree[1][i]:
                + requires(i, require)
        ##############################
        is_root(X) <= is_command(X) & ~requires(X, Y)
        follows(X, Z) <= (
            provides(X, Y) & requires(Z, Y) & (X != Z)
        )
        order(0, X) <= is_root(X)
        order(N, X) <= (N > 0) & order(N - 1, Y) & follows(Y, X)
        ##############################
        ordered = []
        try:
            for x in range(tree_len):
                nodes = order(x, N)
                if not nodes:
                    break
                ordered.extend([x[0] for x in nodes])
        except AttributeError:
            ordered = index
        assert len(ordered) >= tree_len
        print(ordered)
        provided = set()
        for command in ordered:
            assert set(tree[1][command]).issubset(provided)
            provided.update(tree[0][command])
    finally:
        pd.clear()

我的问题：

  1. 我是否使用了错误的工具？
  2. 有人知道全面的数据记录方法吗？
  3. 您如何实际解决上述问题？

编辑：

  1. 我缺少像 all() 和 exists() 这样的量词，如何在 pyDatalog 中表达？
4

1 回答 1

1

pyDatalog（和 prolog）非常适合此类问题。挑战在于摆脱传统的过程式编程思维方式。您可能想在网上搜索有关 prolog 的课程：许多原则也适用于 pyDatalog。

用声明性语言编写循环涉及 3 个步骤：

1）定义一个谓词，其中包含在循环时发生变化的所有变量。

在这种情况下，您想要跟踪部分计划、已经产生的内容以及还有待计划的内容：

partial_plan(Planned, Produced, Todo)

例如，partial_plan([0,], ['A',], [1,2,3,4,5,6,7]) 为真。要查找计划，您将查询：

partial_plan([C0,C1,C2,C3,C4,C5,C6,C7], L, [])

2）描述基本（=最简单）的情况。在这里，起点是仍然必须计划所有命令的时候。

+ partial_plan([], [], [0,1,2,3,4,5,6,7])

3) 描述迭代规则。在这里，您要选择一个要完成的命令，并且它的要求已经产生，并将其添加到 Planned ：

partial_plan(Planned1, Produced1, Todo1) <= (
    # find a smaller plan first
    (Planned0 == Planned1[:-1]) &
    partial_plan(Planned0, Produced0, Todo0) &
    # pick a command to be done, reducing the list of todos, 
    pick(Command, Todo0, Todo1) &
    # verify that it can be done with what has been produced already
    subset(requirement[Command], Produced0) &
    # add it to the plan 
    (Planned1 == Planned0 + [Command, ]) &
    (Produced1 == Produced0 + result[Command])
    )

我们现在必须定义在第三步中引入的谓词。

# pick
pick(Command, Todo0, Todo1) <= (
    (X._in(enumerate(Todo0))) & # X has the form [index, value]
    (Command == X[1]) &
    (Todo1 == Todo0[:X[0]] + Todo0[X[0]+1:]) # remove the command from Todo0
    )

# result and requirement are defined as logic functions, 
# so that they can be used in expressions
for i in range(len(tree[0])):
    result[i] = tree[0][i]
    requirement[i] = tree[1][i]

子集检查L1 的所有元素是否在 L2 中（注意 all 量词）。它也被定义为一个循环：

subset([], List2) <= (List2 == List2) # base case
subset(L1, L2) <= (
    (0 < len(L1)) &
    (L1[0]._in(L2)) & # first element in L2
    subset(L1[1:], L2) # remainder is a subset of L2
    )

然后，您必须声明上面的所有 pyDatalog 变量和谓词，以及“枚举”、“结果”和“要求”函数。

注意：这还没有经过测试；可能需要进行一些小的更改。

于 2016-03-05T16:41:28.280 回答