Quelques doutes sur la façon dont Prolog convertit automatiquement les grammaires DCG en un ensemble de règles

Question

J'étudie la grammaire DCG dans Prolog en utilisant le livre d'Ivan Bratko: "Programmation pour l'intelligence artificielle" et je trouve un problème pour comprendre comment Prolog convertit automatiquement une grammaire DCG dans un ensemble de règles Prolog.

Par exemple, j'ai la grammaire DCG suivante:

move --> step. 
move --> step, move. 

step --> [up]. 
step --> [down]. 

Où:

moove est une liste de mooves possibile et étape est un mouvement qui pourrait être jusqu'à ou bas

Donc, il dit qu'une liste de coups peut être un seul mouvement (une étape) ou une liste une liste composée de plusieurs mouvements qui peuvent être considérés comme un seul mouvement (un pas) suivi d'une liste de coups (un coup).

Donc, cette grammaire peut générer phrase comme la liste suivante: [haut, bas, bas, haut, bas] ou comme: [up]

Ceci est assez simple

Puis il montrer comment Prolog automatiquement convertit la grammaire DCG précédente en un ensemble de règles standard Prolog (je l'ai renommé comme Move2 et step2 seulement parce que je l'ai mis ce code dans le même fichier de la grammaire DCG précédente):

/* move2 it is TRUE if the difference from the lists List and Rest is an 
    acceptable move. 
*/ 

/* BASE CASE: A moves list can be a single move (a step that can be "up" or "down") 
    It is TRUE that the difference from the lists List and Rest is an acceptable move 
    if it is TRUE that the head of the list is an acceptable move 
*/ 
move2(List, Rest) :- step2(List, Rest). 

/* GENERAL CASE: A moves list can be a single move followed by a list of moves. 
    The difference of List1 and Rest is a valid move if it is TRUE that: 
    the difference between List1 and List 2 is a step 
    the difference between List2 and Rest is a move 
*/ 
move2(List1, Rest) :- step2(List1, List2), 
         move2(List2, Rest). 

/* step predicate extract a single step ("up" or "down") from a list 
*/ 
step2([up|Rest], Rest). 

step2([down|Rest], Rest). 

J'ai essayé d'interpréter la signification de ces règles comme je l'ai écrit dans le commenter mais je ne suis pas si sûr de mon interpretaion ...

Pouvez-vous me donner quelques conseils pour bien le comprendre?

Tnx

Andrea

Answer 1

Je ne pense pas qu'il y ait quelque chose de mal avec le code ou votre interprétation, mais je pense que vous regardez ce « déclarative » sans regarder comme un DCG. Je serais probablement écrire ce code comme ceci:

step --> [up]. 
step --> [down]. 

move --> []. 
move --> step, move. 

Cela devrait fonctionner de façon équivalente, mais il sera beaucoup plus facile à étendre et à maintenir que le vôtre, parce qu'il ne maintient pas explicitement la liste des différences.

Plus vous vous rapprochez de Prolog en exprimant votre intention en langage naturel, mieux c'est. S'il faut beaucoup de mots pour expliquer le fonctionnement de votre code, vous programmez sur le plan procédural. Le Prolog ci-dessus est à peu près aussi proche que nous pouvons sortir de la boîte. Nous pourrions aller plus loin en créant des aides:

one_or_more(_, []) --> []. 
one_or_more(R, [V|Vs]) --> 
    { Rule =.. [R, V] }, 
    Rule, 
    one_or_more(R, Vs). 

step(up) --> [up]. 
step(down) --> [down]. 

moves(Steps) --> one_or_more(step, Steps). 

(Le code ci-dessus est non testé.) Le point est d'illustrer la puissance de la programmation déclarative. Il pourrait être plus de travail pour écrire un prédicat comme one_or_more//2, mais une fois que vous l'avez, le reste de votre programme est élevé à un style plus déclaratif. Certains commentaires pourraient être nécessaires autour de one_or_more//2, car il n'est pas immédiatement évident comment il fonctionne (si il fonctionne même).La lecture déclarative de ce qui précède est, "move (Steps) correspond à une ou plusieurs étapes." C'est la même chose que la lecture déclarative de ma version originale, et la lecture déclarative de la vôtre. La différence est que le code de chacun est plus proche de la lecture déclarative évidente.