依赖关系图用pyDatalog解析

Question

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

1. 有命令和资源
2. 每个命令都可以提供，需要多种资源
3. 该算法将遍历所有命令和安排所规定的所有他们的要求的命令。现在提供了
4. 如果全部命令被安排
5. 我们不能满足的依赖关系，如果有离开的命令，我们不能对一个迭代调度新命令我们完成
6. 命令提供的所有资源该算法

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

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

您可以找到完整的源码here。

这取决于假设，你可以很容易地用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. 您是如何真正解决上述问题的？

编辑：

我的思念像所有的量词（）和存在（），我该如何表达这种在pyDatalog？

Answer 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）描述迭代规则。在这里，你想选择做一个命令，其要求已产生，并将其添加到计划：

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]) 
    ) 

现在，我们必须定义在第3步介绍了谓词。

# 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（注意所有量词）。它也被定义为一个循环：

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变量及以上谓词，和“枚举”，“结果”和“需求”的功能。

注意：这尚未经过测试;可能需要一些小的更改。