Graphique de dépendance Résolution avec pyDatalog

Question

Je m'efforce d'écrire des programmes déclaratifs plus lisibles. J'ai donc décidé d'implémenter un algorithme simple que nous utilisons actuellement. La mise en œuvre de la procédure est la suivante:

1. Il y a des commandes et des ressources
2. Chaque commande peut fournir et exiger des ressources multiples
3. L'algorithme boucle sur toutes les commandes et planifier les commandes que toutes leurs exigences sont prévues .
4. Toutes les ressources de la commande fournit sont désormais prévus
5. Nous avons terminé si toutes les commandes sont programmées
6. Nous ne pouvons pas satisfaire les dépendances s'il y a des commandes gauche et nous ne pouvons pas planifier de nouvelles commandes pour une itération de l'algorithme

Ainsi, la variante datalog je suis venu avec l'air bien, mais a deux problèmes:

1. Il est faux
2. J'ai besoin d'une boucle pour lire le résultat

Vous pouvez trouver la source complète here.

Cela dépend de l'hypothèse et vous pouvez facilement l'exécuter avec pytest. Ci-dessous le test qui échoue: Si nous avons besoin de ressources fournies par un "rank" ou une commande précédente. Il ne peut pas le trouver. J'ai essayé de faire récursif suit, mais alors il échoue même dans les exemples simples.

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

Mes questions:

1. Suis-je utiliser le bon outil?
2. Est-ce que quelqu'un est au courant des procédures détaillées du journal des données?
3. Comment résolvez-vous réellement le problème ci-dessus?

Edit:

4. Je suis absent quantificateurs comme tous() et exists(), comment puis-je exprimer en pyDatalog?

Answer 1

pyDatalog (et prolog) est bien adapté pour un tel problème. Le défi consiste à s'écarter de l'approche traditionnelle de la programmation procédurale. Vous pouvez rechercher sur le Web un cours sur prologue: de nombreux principes s'appliqueront également à pyDatalog.

Ecrire une boucle dans un langage déclaratif implique 3 étapes:

1) définir un prédicat avec toutes les variables qui changent tandis que le bouclage.

Dans ce cas, vous voulez garder une trace d'un plan partiel, ce qui a été produit déjà, et ce qui reste à prévoir:

partial_plan(Planned, Produced, Todo) 

Par exemple, partial_plan ([0,], [ 'A',], [1,2,3,4,5,6,7]) est vrai. Pour trouver un plan, vous devez interroger:

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

2) décrire le cas de base (= le plus simple). Ici, le point de départ est quand toutes les commandes doivent encore être planifiées.

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

3) décrire la règle d'itération. Ici, vous voulez choisir une commande à faire, et dont les exigences ont déjà été produites, et l'ajouter à prévu:

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

Nous avons maintenant de définir les prédicats introduites dans la 3ème étape.

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

sous-ensemble qui vérifie tous les éléments de L1 sont dans L2 (notez le tout quantificateur). Il est également défini comme une boucle:

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 
    ) 

Vous devrez alors déclarer toutes les variables pyDatalog et prédicats ci-dessus, et les fonctions « Énumérer », « résultat » et « exigence ».

Note: cela n'a pas été testé; quelques changements mineurs peuvent être nécessaires.