EPITA

Introdution à Prolog, cours n° 4

Jean-François Perrot

Génération de code pour expressions arithmétiques

1. Préambule
   1. L'idée
   2. L'assembleur LMU
   3. Exemples
   4. Auxiliaires d'usage général
      1. Syntaxe de LMU
      2. Confection d'une liste d'instructions LMU, avec une liste différentielle
      3. Impression d'une liste d'instructions au format LMU.


2. Le générateur de code simpliste "tout dans la pile"


3. Le générateur raisonnable avec pile dans les registres et gestion du débordement


4. Le générateur optimal avec calcul préliminaire du nombre de registres nécessaires
   1. Calcul du nombre minimum de registres
   2. Le prédicat maître
   3. Premier prédicat auxiliaire
   4. Second prédicat auxiliaire

Préambule

• L'idée

  L'écriture d'un générateur de code à partir d'un arbre syntaxique est très facile en Prolog.
  Nous traitons ici le cas bien connu des expressions arithmétiques,
  en prenant comme arbres syntaxiques les termes Prolog en syntaxe standard.
  Le résultat sera une liste d'instructions LMU, que nous afficherons à l'écran.
  
  Nous donnerons trois versions successives, voir les exemples ci-dessous.
  

• L'assembleur LMU

  LMU (comme Langage Machine Universel, appellation reprise au regretté Louis Nolin) est un assembleur ultra-simple,
  qui permet d'observer des phénomènes intéressants, que tout informaticien doit connaître et que les langages de plus haut niveau cachent.
  
  Nous n'utiliserons ici que la partie relative
  
  • au chargement des registres, désignés par R0, R1, etc...
    
    • "load immédiat" : LDI Ri cte
    • "load registre" : LDR Ri etiq, où etiq désigne une adresse en mémoire, ici ce sera simplement un nom
      
  • aux opérations arithmétiques
    
    • format "à trois registres" du type ADD Ri Rj Rk <==> Ri := Rj+Rk
    • quatre opérations ADD, MUL, SUB, DIV.

  • et à la pile : PSH Ri & POP Rj.
    

• Exemples

  ?- try0(1-(b*b-4*(a*c))/2).         LDI  R0  1          PSH  R0          LDR  R0  b          PSH  R0          LDR  R0  b          POP  R1          MUL  R0  R1  R0          PSH  R0          LDI  R0  4          PSH  R0          LDR  R0  a          PSH  R0          LDR  R0  c          POP  R1          MUL  R0  R1  R0          POP  R1          MUL  R0  R1  R0          POP  R1          SUB  R0  R1  R0          PSH  R0          LDI  R0  2          POP  R1          DIV  R0  R1  R0          POP  R1          SUB  R0  R1  R0  true ; false.

  ?- try1(1-(b*b-4*(a*c))/2).         LDI  R0  1          LDR  R1  b          LDR  R2  b          MUL  R1  R1  R2          LDI  R2  4          PSH  R2          LDR  R2  a          LDR  R3  c          MUL  R3  R2  R3          POP  R2          MUL  R2  R2  R3          SUB  R1  R1  R2          LDI  R2  2          DIV  R1  R1  R2          SUB  R0  R0  R1  true ; false.

  ?- try2(1-(b*b-4*(a*c))/2).         LDR  R0  c          LDR  R1  a          MUL  R0  R1  R0          LDI  R1  4          MUL  R0  R1  R0          LDR  R1  b          LDR  R2  b          MUL  R1  R2  R1          SUB  R0  R1  R0          LDI  R1  2          DIV  R0  R0  R1          LDI  R1  1          SUB  R0  R1  R0  true ; false.

  
  



• Auxiliaires d'usage général

  • Syntaxe de LMU
    

    Les mnémoniques :
    • mnem(+, 'ADD'). 
    • mnem(-, 'SUB'). 
    • mnem(*, 'MUL'). 
    • mnem(/, 'DIV').
      
      
    Confection des symboles noms de registres à partir de leurs numéros: 
    par exemple     registre(3, R3)     - on rappelle que  82 = ascii('R').
    
    registre(Num, Nom) :- name(Num, Chn), name(Nom, [82 | Chn]).
    

  • Confection d'une liste d'instructions LMU, avec une liste différentielle

    L'instruction à ajouter est représentée par la liste d'atomes Lcode,
    les deux arguments suivants sont les deux listes différentielles nécessaires au fonctionnement de la notation DCG.
    
    clmu(Lcode, T-[Inst|Q], T-Q) :- Inst =.. Lcode.

?- clmu(['MUL', 'R0', 'R1', 'R0'], X-X, Y).
X = ['MUL'('R0', 'R1', 'R0')|_G322],
Y = ['MUL'('R0', 'R1', 'R0')|_G322]-_G322.
    
    Le recours à une liste différentielle pour engendrer la liste d'instructions va nous permettre
    d'utiliser la notation des grammaires Prolog pour alléger l'écriture du générateur de code.
    Les arguments supplémentaires désignant la liste différentielle des instructions engendrées
    seront ajoutés automatiquement par le compilateur Prolog.
    

  • Impression d'une liste d'instructions au format LMU.

    Comme la liste est incomplète (puisqu'elle est issue d'une liste différentielle),
    la précaution "nonvar(X)" dans la défnition du prédicat plmu
    est utile pour éviter des erreurs au retour-arrière.
    
    vlmu(Linst-Q) :- maplist(plmu, Linst).
plmu(X) :- nonvar(X), tab(8), X =.. Lcode, slmu(Lcode).
slmu([]) :- nl.
slmu([T | Q]) :- write(T), tab(2), slmu(Q).

Le générateur de code simpliste "tout dans la pile"

genexp0(Exp) --> {number(Exp), !}, clmu(['LDI', 'R0', Exp]).
genexp0(Exp) --> {atomic(Exp), !}, clmu(['LDR', 'R0', Exp]).
genexp0(Exp) --> {functor(Exp, Op, 2),
                arg(1, Exp, Ag), arg(2, Exp, Ad)},
                genexp0(Ag), clmu(['PSH', 'R0']),
                genexp0(Ad), clmu(['POP', 'R1']),
                {mnem(Op, Codop)},
                clmu([Codop, 'R0', 'R1', 'R0']).


Le générateur raisonnable avec pile dans les registres et gestion du débordement

maxreg(3).         % seule manière de déclarer une constante en Prolog !

genexp1(Exp, PRL) --> {number(Exp), !, registre(PRL, RPRL)}, % PRL = Premier Registre Libre
                            clmu(['LDI', RPRL, Exp]).
genexp1(Exp, PRL) --> {atomic(Exp), !, registre(PRL, RPRL)},
                            clmu(['LDR', RPRL, Exp]).
genexp1(Exp, PRL) --> {functor(Exp, Op, 2), arg(1, Exp, Ag), arg(2, Exp, Ad),
                       mnem(Op, Codop), registre(PRL, RPRL)},
                     genaux1(Codop, Ag, Ad, PRL, RPRL).

genaux1(Codop, Ag, Ad, PRL, RPRL) --> {maxreg(MR), PRL < MR, !, % on ne déborde pas
                       PRL1 is PRL+1, registre(PRL1, RPRL1)},
                    genexp1(Ag, PRL), genexp1(Ad, PRL1),
                    clmu([Codop, RPRL, RPRL, RPRL1]).

genaux1(Codop, Ag, Ad, PRL, RPRL) --> {PRL1 is PRL-1, registre(PRL1, RPRL1)},
                clmu(['PSH', RPRL1]), % on déborde
                genexp1(Ag, PRL1), genexp1(Ad, PRL),
                clmu([Codop, RPRL, RPRL1, RPRL]),
                clmu(['POP', RPRL1]).


Le générateur optimal avec calcul préliminaire du nombre de registres nécessaires

1. Calcul du nombre minimum de registres

   Les listes de Prolog vont nous permettre de construire "au vol" une structure arborescente parallèle à l'arbre d'expression
   et portant en chacun de ses sommets le nombre minimum de registres nécessaires à la séquence de code
   qui correspond au sommet homologue de l'arbre d'expression.
   Le prédicat nmrn(Exp, Liste) contrôlant cette construction est défini ci-après.
   Sa définition récursive traduit directement la spécification :
          nmrn(E) = 1 si E est une constante ou une variable
          nmrn(Eg op Ed) =
                  soit ng = nmrn (Eg), nd = nmrn(Ed)
                     max (ng, nd) si ng =/= nd
                     nd+1 si ng = nd.
   
   On l'utilisera ainsi :
   genopt(Exp, PRL) :- {nmrn(Exp, A)}, genexp2(Exp, A, PRL).

nmrn(Exp, [1]) :- number(Exp), !.
nmrn(Exp, [1]) :- atomic(Exp), !.
nmrn(Exp, [R | [G | D]]) :- functor(Exp, Op, 2),
                arg(1, Exp, Ag), arg(2, Exp, Ad),
                nmrn(Ag, G), nmrn(Ad, D), resrn(G, D, R).

resrn([NG |_], [ND |_], R) :- NG=ND, !, R is NG+1.
resrn([NG |_], [ND |_], NG ) :- NG>ND, !.
resrn([NG |_], [ND |_], ND) .

   Exemple :
   ?- nmrn(x*3-(y+3-(x*(y-1))), A).
A = [3, [2, [1], 1], 3, [2, [1], 1], 2, [1], 2, [1], 1].



2. Le prédicat maître

   à l'arité près, identique à genexp1.
Comme ci-devant, un auxiliaire genaux2 va gérer le débordement dans la pile.
   
   genexp2(Exp, ARN, PRL) --> {number(Exp), !, registre(PRL, RPRL)},
                    clmu(['LDI', RPRL, Exp]).
genexp2(Exp, ARN, PRL) --> {atomic(Exp), !, registre(PRL, RPRL)},
                    clmu(['LDR', RPRL, Exp]).
genexp2(Exp, [_ | [ARG | ARD]], PRL) -->   
        {functor(Exp, Op, 2), arg(1, Exp, Ag), arg(2, Exp, Ad),
        mnem(Op, Codop), registre(PRL, RPRL)},
        genaux2(Codop, Ag, Ad, ARG, ARD, PRL, RPRL).

   
   

3. Premier prédicat auxiliaire

   L'appel récursif à genexp2 va demander un intermédiaire de plus genaux21,
   pour déterminer l'ordre d'évaluation des sous-arbres
   celui qui est le plus gournamd en registres devant être traité en premier.

genaux2(Codop, Ag, Ad, ARG, ARD, PRL, RPRL) -->
                {maxreg(MR), PRL < MR, !, % on ne déborde pas
                PRL1 is PRL+1, registre(PRL1, RPRL1),
                ARG = [NRG | _], ARD = [NRD | _]},
                genaux21(Codop, Ag, Ad, ARG, ARD, NRG, NRD,
                                   PRL, RPRL, PRL1, RPRL1).

genaux2(Codop, Ag, Ad, ARG, ARD, PRL, RPRL) -->
                {PRL1 is PRL-1, registre(PRL1, RPRL1)},
                clmu(['PSH', RPRL1]), % on déborde
                genexp2(Ag, ARG, PRL1), genexp2(Ad, ARD, PRL),
                clmu([Codop, RPRL, RPRL1, RPRL]),
                clmu(['POP', RPRL1]).
   
   

4. Second prédicat auxiliaire

   genaux21(Codop, Ag, Ad, ARG, ARD, NRG, NRD,
                            PRL, RPRL, PRL1, RPRL1) -->
                {NRG > NRD, !},  % le sous-arbre gauche d'abord
                genexp2(Ag, ARG, PRL), genexp2(Ad, ARD, PRL1),
                clmu([Codop, RPRL, RPRL, RPRL1]).

genaux21(Codop, Ag, Ad, ARG, ARD, NRG, NRD,
                            PRL, RPRL, PRL1, RPRL1) -->  % le sous-arbre droit d'abord
                genexp2(Ad, ARD, PRL), genexp2(Ag, ARG, PRL1),
                clmu([Codop, RPRL, RPRL1, RPRL]).