Fonctions en assembleur

Le minuscule ordinateur peut être programmé en langage d’assemblage grâce aux multiples instructions qu’il supporte. En théorie, ce langage d’assemblage est suffisant pour écrire n’importe quel programme. Cependant, il est fastidieux et dangereux d’écrire un programme sans le découper en fonctions et procédures qui peuvent être testées indépendamment et qui sont ensuite combinées.

Vous avez utilisé des fonctions et procédures dans le langage python sans analyser en détails comment ce langage supportait ces différentes constructions. Nous allons maintenant les analyser en nous appuyant sur le langage d’assemblage du minuscule CPU.

Commençons par réfléchir aux différentes opérations qu’un langage de programmation tel que python doit réaliser pour supporter différents types de fonctions. Tout d’abord, analysons comment implémenter une procédure, c’est-à-dire une fonction qui ne prend pas d’argument et ne retourne pas de résultat. Notre premier exemple simple est une procédure qui affiche de l’information à l’écran. Une telle procédure pourrait être utilisée dans un programme pour afficher le contenu d’un menu à l’écran.

def p():
    print("Bonjour")

Il est intéressant d’analyser comment un langage tel que python fait appel à une telle procédure dans un programme. Regardons plus en détails le code ci-dessous. La première ligne initialise la variable a à la valeur 1. La deuxième ligne transfère l’exécution du programme à la procédure p(). Le code de cette procédure est composé d’un ensemble d’instructions qui se trouvent en mémoire et vont afficher Bonjour à l’écran. Après l’exécution de cette procédure, le programme python retourne à l’exécution de la troisième ligne et place la valeur 2 dans la variable a. La quatrième ligne relance l’exécution de la procédure p(). Celle-ci va à nouveau exécuter les instructions qui permettent d’afficher Bonjour à l’écran, mais après son exécution le programme python exécutera la ligne 5. On remarque une différence importante entre les deux invocations de la procédure p(). Après la première invocation, on exécute la ligne 3 du programme python. Après la deuxième invocation, on exécute la ligne 5 du programme python.

a=1            # ligne 1
p()            # ligne 2
a=2            # ligne 3
p()            # ligne 4
a=3            # ligne 5

En python, il est facile d’imprimer de l’information à l’écran. En minuscule assembleur, cette opération nécessite nettement plus d’efforts. Analysons un autre exemple en python qui utilise les variables globales. En python, une fonction utilise normalement les arguments qu’elle a reçus ou définit ses propres variables locales. Il est aussi possible de définir des variables globales, c’est-à-dire des variables qui sont stockées dans la mémoire du programme et sont accessibles à toutes les fonctions de ce programme. Cette utilisation d’une variable globale est illustrée dans le programme python ci-dessous.

compteur=0

def compte():
    global compteur
    compteur = compteur+1

a=1          # ligne 1
compte()     # ligne 2
a=2          # ligne 3
compte()     # ligne 4
a=3          # ligne 5

La variable compteur est une variable globale (python impose l’utilisation du mot clé global dans sa définition dans la procédure compte) qui est initialisée dans le programme principal et modifiée dans la procédure compte. Analysons l’exécution de ce programme pas à pas. Ce programme manipule deux variables en mémoire : a et compteur. La première ligne initialise la variable a à la valeur 1. La deuxième ligne incrémente la variable compteur qui passe à 1. La troisième ligne fait passer la valeur de la variable a à 2. La quatrième ligne incrémente la variable compteur qui passe également à 2. Enfin, la dernière ligne place la valeur 3 dans la variable a.

Pour bien comprendre comment une telle procédure peut être utilisée à plusieurs endroits dans un même programme, il est intéressant d’essayer de la convertir en minuscule assembleur.

Commençons par assigner une zone mémoire pour la variable a, par exemple l’adresse 16. Nous pouvons ensuite écrire en assembleur les lignes impaires qui correspondent aux différentes assignations de cette variable.

// ligne 1
@1
D=A
@a
M=D
// à compléter
// ligne 3
@2
D=A
@a
M=D
// à compléter
// ligne 5
@3
D=A
@a
M=D

Nous devons également assigner une zone mémoire pour stocker la variable compteur. Supposons que celle-ci soit stockée à l’adresse 17. La Fig. 13 présente le contenu initial de notre mémoire.

Contenu de la mémoire

Il nous faut maintenant pouvoir faire appel à la procédure compte() après l’exécution des lignes 1 et 3. Le corps de cette procédure peut s’écrire en deux instructions en minuscule assembleur.

@compteur
M=M+1

Une première approche pour inclure notre procédure dans le programme en minuscule assembleur est d’intégrer directement ces instructions en ligne (inline en anglais). Cette technique est parfois utilisée dans certains langages de programmation pour de très petites fonctions qui doivent s’exécuter rapidement.

   // ligne 1
   @1
   D=A
   @a  
   M=D
   // ligne 2
   @compteur    // procédure compte
   M=M+1        // procédure compte
   // ligne 3
   @2
   D=A
   @a  
   M=D
   // ligne 4
   @compteur    // procédure compte
   M=M+1        // procédure compte
   // ligne 5
   @3
   D=A
   @a  
   M=D

Ce programme est téléchargeable depuis asm/procedure-ex1.asm.

Cette approche fonctionne dans notre exemple simple, mais elle a deux inconvénients majeurs. Le premier est que le code de la procédure doit être recopié à chaque invocation de la procédure dans un programme. Cela consomme inutilement de l’espace mémoire surtout si le programme appelle la procédure à de nombreux endroits. Le deuxième inconvénient est que si la procédure modifie le contenu des registres A ou D, elle pourrait avoir un impact non-voulu sur les instructions du programme principal.

Il serait préférable de pouvoir isoler les instructions de la procédure dans une partie de la mémoire et d’y faire appel en exécutant un saut inconditionnel. Une première approche pourrait être la suivante. La code de la procédure compte est placé après l’étiquette COMPTE et on fait appel à la procédure en utilisant un saut inconditionnel vers cette adresse.

(LIGNE1)
   @1  // ligne 1
   D=A
   @a  
   M=D
   @COMPTE // ligne 2
   0;JMP
(LIGNE3)
   @2  // ligne 3
   D=A
   @a  
   M=D
   // ligne 4
   @COMPTE
   0;JMP
(LIGNE5)
   @3    // ligne 5
   D=A
   @a  
   M=D
(COMPTE) 
   @compteur  
   M=M+1
   @retour	
   0;JMP

Malheureusement, ce n’est pas suffisant. Après la première exécution de la procédure compte, l’exécution doit reprendre à l’adresse LIGNE3 tandis qu’après la seconde exécution de la même procédure, il faut poursuivre l’exécution du programme principal à partir de l’adresse LIGNE5. Pour résoudre ce problème, nous devons rendre le code de la procédure plus générique. Notre procédure doit pouvoir retourner, via une instruction JMP à l’adresse de l’instruction qui suit celle à partir de laquelle elle a été appelée. Malheureusement, il n’est pas possible d’extraire cette information des registres du minuscule CPU durant l’exécution de notre procédure. Le programme appelant devra donc calculer cette adresse, souvent appelée adresse de retour et la sauvegarder à un endroit où la procédure peut la récupérer. Sur le minuscule ordinateur, le seul endroit où nous pouvons stocker de l’information est dans la mémoire. Une première solution est de réserver une adresse en mémoire pour sauver cette adresse de retour. Dans ce cas, l’appel à un procédure se déroule comme suit :

1. Sauvegarde de l’adresse de retour en mémoire

2. Appel de la procédure (via l’instruction JMP)

3. Exécution du corps de la procédure

4. Récupération de l’adresse de retour

5. Saut à l’adresse de retour pour poursuivre l’exécution du programme appelant

Il nous reste à traduire cela en minuscule assembleur. Supposons que l’étiquette retour corresponde à l’adresse réservée en mémoire pour stocker l’adresse de retour. L’appel à une procédure peut se réaliser en utilisant les instructions suivantes :

// juste avant l'appel à la procédure
  @SUIVANT  // sauvegarde de l'adresse qui suit l'appel à la procédure
  D=A       // ...
  @retour   // ...
  M=D       // dans la zone mémoire "retour"
  @COMPTE   // appel de la procédure compte
  0;JMP     // ...
(SUIVANT)   // adresse de l'instruction qui suit l'appel à la procédure

La fin de la procédure doit également être adaptée. Il faut d’abord charger l’adresse de retour depuis la mémoire avant d’exécuter le JMP. Cela se fait en utilisant la séquence d’instructions suivante :

(COMPTE)
  @compteur
  M=M+1
  @retour   // adresse où est stockée l'adresse de retour
  A=M       // chargement de l'adresse se trouvant en mémoire
  0;JMP     // saut vers l'adresse de retour

Le programme complet intègre ces deux modifications. Il est téléchargeable depuis asm/procedure-ex3.asm.

   @compteur
   M=0
(LIGNE1)
   @1  // ligne 1
   D=A
   @a  
   M=D
   @LIGNE3  // sauvegarde de l'adresse de retour
   D=A
   @retour
   M=D	
   @COMPTE  // appel de la procédure
   0;JMP                  // adresse 11 
(LIGNE3)                  // adresse 12
   @2  // ligne 3
   D=A
   @a  
   M=D
   @LIGNE5  // sauvegarde de l'adresse de retour
   D=A
   @retour
   M=D	
   @COMPTE  // appel de la procédure
   0;JMP	          // adresse 21
(LIGNE5)                  // adresse 22
   @3    // ligne 5
   D=A
   @a  
   M=D                    // adresse 25
   @FIN
   0;JMP
(COMPTE) 
   @compteur  
   M=M+1
   @retour
   A=M	
   0;JMP
(FIN)

Il est intéressant d’observer l’évolution de la mémoire durant l’exécution de ce programme. La fig-mem-addr11 présente l’état de la mémoire lors de l’exécution de l’instruction 0;JMP se trouvant à l’adresse 11. A ce moment, l’adresse 16 contient le compteur initialisé à zéro, l’adresse 17 contient la variable a initialisée à 1. L’adresse de retour est l’adresse de l’instruction qui suit l’instruction 0;JMP, c’est-à-dire la valeur 12. Elle est stockée en mémoire à l’adresse 18.

Contenu de la mémoire durant l’exécution de l’instruction (0;JMP) se trouvant à l’adresse 11

Après l’exécution de cette instruction, le programme va exécuter le code de la procédure. Celui-ci va incrémenter la valeur de la variable compteur et ensuite revenir au programme principal à l’instruction se trouvant à l’adresse 12. La fig-mem-addr12 présente l’état de la mémoire à ce moment.

Contenu de la mémoire durant l’exécution de l’instruction se trouvant à l’adresse 12

L’exécution du programme se poursuit. Lors de l’exécution de la seconde instruction 0;JMP du programme principal, le contenu de la mémoire est tel que représenté en fig-mem-addr21.

Contenu de la mémoire durant l’exécution de l’instruction se trouvant à l’adresse 21

En pratique, une telle procédure n’est pas isolée et il est courant qu’une procédure fasse appel à une autre procédure. Analysons ce cas de figure en utilisant l’exemple ci-dessous en python.

compteur=0

def oppose():
    global compteur
    compteur = -compteur


def compte():
    global compteur
    compteur = compteur+1
    oppose()

    
a=1          # ligne 1
compte()     # ligne 2
a=2          # ligne 3
compte()     # ligne 4
a=3          # ligne 5

Dans ce programme, la procédure compte() incrémente le compteur et la procédure oppose() inverse le signe de ce compteur. Après exécution de la ligne 3, la variable compteur contient la valeur -1. A la fin du programme, cette variable contient la valeur 0. Nous pouvons maintenant essayer de convertir ce petit programme en minuscule assembleur.

   @compteur
   M=0
(LIGNE1)
   @1  // ligne 1
   D=A
   @a  
   M=D
   @LIGNE3  // sauvegarde de l'adresse de retour
   D=A
   @retour
   M=D	
   @COMPTE  // appel de la procédure
   0;JMP                  // adresse 11 
(LIGNE3)                  // adresse 12
   @2  // ligne 3
   D=A
   @a  
   M=D
   @LIGNE5  // sauvegarde de l'adresse de retour
   D=A
   @retour
   M=D	
   @COMPTE  // appel de la procédure
   0;JMP	          // adresse 21
(LIGNE5)                  // adresse 22
   @3    // ligne 5
   D=A
   @a  
   M=D                    // adresse 25
   @FIN
   0;JMP
(COMPTE) 
   @compteur  
   M=M+1
   @SUIVANT  // sauvegarde de l'adresse de retour
   D=A
   @retour
   M=D	
   @OPPOSE   // appel de la procédure
   0;JMP                      
(SUIVANT)                                   
   @retour                 // adresse 36
   A=M	
   0;JMP
(OPPOSE)
   @compteur               // adresse 39
   M=-M
   @retour
   A=M
   0;JMP
(FIN)
	

Ce programme (téléchargeable via asm/procedure-ex4.asm) utilise les mêmes variables en mémoire que le programme précédent. Son exécution démarre de la même façon. Il est intéressant d’observer le premier appel à la procédure compte. Au début de son exécution la mémoire contient les valeurs représentées en fig-mem-ex4-a.

Contenu de la mémoire durant la première instruction de la procédure compte

La procédure incrémente la valeur de la variable compteur. Ensuite elle fait appel à la procédure oppose(). Pour cela, elle sauvegarde l’adresse qui suit celle de l’instruction 0;JMP, dans ce cas l’adresse 36. Elle exécute ensuite l’instruction 0;JMP. A ce stade, la mémoire contient les valeurs représentées dans la fig-mem-ex4-b.

Contenu de la mémoire durant la première instruction de la procédure compte

La procédure oppose() s’exécute et place la valeur -1 dans la variable compteur. Il ne lui reste plus qu’à retourner au programme appelant, c’est à dire dans le corps de la procédure compte(). L’adresse 36 est donc chargée de la mémoire et l’instruction 0;JMP est exécutée. Les trois instructions qu’il reste à exécuter dans la procédure compte() sont les suivantes :

(SUIVANT)
    @retour                 // adresse 36
    A=M
    0;JMP

Ces instructions vont recharger la valeur stockée à l’adresse de retour, c’est-à-dire 36 et ensuite l’instruction 0;JMP va redémarrer l’exécution des instructions à cette adresse. Nous avons malheureusement construit une boucle infinie…

Le problème que nous observons est dû au fait qu’en sauvegardant l’adresse de retour dans la procédure compte() pour supporter l’appel à la procédure oppose(), on écrase l’adresse qui devait permettre à la procédure compte() de retourner au bon endroit du programme appelant. Pour supporter une procédure qui appelle une autre procédure, nous avons besoin de stocker deux adresses de retour. Mais il est aussi possible qu’une procédure appelle une procédure qui elle-même appelle une autre procédure, … En toute généralité la succession des appels de procédure n’est pas nécessairement bornée. De plus, une procédure p1() peut appeler une procédure p2(), mais cette procédure p2() peut aussi être appelée par la procédure p4() qui elle-même est une procédure appelée par p5() qui est appelée par la procédure p1(). Il suffit pour s’en convaincre de regarder le nombre d’appels à des fonctions de type print qu’un programme peut contenir.

Avant d’appeler une procédure, nous devons trouver une moyen pour sauvegarder l’adresse de retour de cette procédure. Lors de son exécution, notre procédure peut aussi sauvegarder des adresses de retour, mais à la fin de son exécution nous devons pouvoir récupérer l’adresse de retour que nous avions sauvegardée. Cela correspond au fonctionnement d’une pile (stack en anglais). Une pile est une structure de données permettant de stocker un nombre quelconque de données. Elle supporte deux opérations: l’ajout d’une donnée au sommet de la pile (push en anglais) et le retrait de la donnée se trouvant au sommet de la pile (pop en anglais).

La pile la plus connue dans la vie de tous les jours est la pile d’assiettes. Lorsque l’on a besoin d’un assiette, on prend celle qui se trouve au sommet de la pile. Après avoir fait la vaisselle, on remet les assiettes propres au sommet de la pile également. Pour bien comprendre le fonctionnement d’une structure de données en pile en informatique, il suffit de se rappeler comment on manipule une pile d’assiettes…

Note

Comment stocker une pile de mots en mémoire ?

La solution la plus simple pour stocker et manipuler une pile de mots en minuscule assembleur est d’utiliser une zone de mémoire contiguë. Une première approche est d’utiliser l’adresse p pour stocker l’élément se trouvant en bas de la pile et d’ajouter les éléments suivants aux adresses p+1, p+2, … Pour illustrer cette approche, la Fig. 18 présente l’évolution d’une pile initialement vide lors de l’exécution de la séquence push(3) ; pop ; push(2) ; push(5) d’opérations. Avec cette approche, le sommet de la pile est toujours l’élément dont l’adresse est numériquement la plus élevée.

Evolution de la pile vers les adresses numériquement croissantes

Outre les données, une telle structure doit également stocker l’adresse de l’élément se trouvant au sommet de la pile. Après l’opération push(3) le sommet de la pile est à l’adresse p. Il est à la même adresse après l’opération push(2) et atteint l’adresse p+1 après l’opération push(5).

Une seconde approche est d’utiliser l’adresse p pour stocker le premier élément de la pile et d’ajouter les éléments suivants aux adresses p-1, p-2, … La Fig. 18 illustre l’évolution d’un telle pile lors de l’exécution des opérations suivantes: push(3) ; pop ; push(2) ; push(5). Avec cette approche, l’élément se trouvant au sommet de la pile est celui dont l’adresse est numériquement la plus basse.

Evolution de la pile vers les adresses numériquement décroissantes

Outre les données, cette structure doit également stocker l’adresse de l’élément se trouvant au sommet de la pile. Après l’opération push(3) le sommet de la pile est à l’adresse p. Il est à la même adresse après l’opération push(2) et atteint l’adresse p-1 après l’opération push(5).

Même si la première solution peut paraître la plus naturelle par analogie aux piles d’assiettes, c’est généralement la deuxième solution qui est préférée car elle facilite la gestion de la mémoire et maximise l’espace qui est disponible pour la pile sans inutilement contraindre la mémoire utilisée par un programme.

Avant de modifier notre programme pour y intégrer une pile, il est intéressant de réfléchir à la façon dont on peut implémenter une pile d’entiers en utilisant le minuscule assembleur. Les deux opérations que nous devons supporter sont :

• push(x) place au sommet de la pile la valeur x. Après l’exécution de push, la pile contient un élément de plus.

• y=pop() récupère la valeur se trouvant au sommet de la pile et la retire. Cette opération ne peut être réalisée que sur une pile qui contient au moins un élément. Après l’exécution de pop, la pile contient un élément de moins.

Pour implémenter ces deux opérations, nous adoptons la représentation de la pile qui démarre aux adresses hautes et réservons 10 mots en mémoire pour stocker notre pile en supposant qu’elle ne contiendra jamais plus d’éléments. Nous supposons également que cette zone mémoire commence à l’adresse 1000. De plus, la variable pile contient à tout moment l’adresse de l’élément se trouvant au sommet de la pile.

Pile pouvant stocker 10 éléments

Avant d’écrire les opérations push et pop en minuscule assembleur, nous devons encore déterminer où doit se trouver la valeur que push sauve sur le stack et où l’opération pop va sauver le mot qui se trouvait au sommet de la pile. Dans ces deux cas, nous choisissons le registre D. Celui-ci devra contenir l’entier à écrire sur la pile avant d’exécuter le code correspondant à l’opération push. De façon similaire, l’opération pop se terminera en laissant la valeur se trouvant au sommet de la pile dans le registre D. A tout moment, la variable pile contiendra l’adresse de l’élément se trouvant au sommet de la pile.

Nous pouvons maintenant écrire les instructions pour implémenter l’opération push. Il faut tout d’abord décrémenter la variable qui contient le sommet de la pile pour « faire de la place » pour ce nouvel élément. Comme notre pile grandit en mémoire vers les adresses basses, il suffit pour cela de décrémenter l’adresse contenue dans la variable pile. Nous devons ensuite sauvegarder la valeur se trouvant dans le registre D à cette adresse.

// opération push
         // D contient l'entier à placer au sommet de la pile
@pile
M=M-1    // libération d'une place au sommet de la pile
@pile
A=M      // l'adresse contenue dans la variable pile est placée dans A
M=D      // sauvegarde de la valeur contenue dans le registre D

L’opération pop est assez proche. Nous devons d’abord récupérer la valeur se trouvant à l’adresse contenue dans le registre pile et la placer dans le registre D. Ensuite, il faut indiquer que l’élément qui était au sommet de la pile ne s’y trouve plus. Pour cela, il suffit d’incrémenter l’adresse contenue dans la variable pile puisque notre pile grandit vers les adresses basses.

// opération pop

@pile
A=M        // chargement de l'adresse contenue dans la variable pile
D=M        // sauvegarde de la donnée se trouvant au sommet de la pile
@pile
M=M+1      // libération de la place correspondant au sommet de la pile
           // la donnée lue au sommet de la pile est dans le registre D

Le programme ci-dessous (téléchargeable depuis asm/pile-exemple.asm) illustre le fonctionnement d’une telle pile.

    // exemple d'utilisation de la pile
    // celle-ci démarre à l'adresse 1000
    @1000
    D=A	
    @pile
    M=D
    // push (2)
    @2
    D=A	
    @pile
    M=M-1    
    @pile
    A=M 
    M=D
    // push (7)
    @7
    D=A	
    @pile
    M=M-1    
    @pile
    A=M 
    M=D
    // pop
    @pile
    A=M
    D=M		
    @pile
    M=M+1
    // push (9)
    @9
    D=A	
    @pile
    M=M-1    
    @pile
    A=M
    M=D
    // pop
    @pile
    A=M
    D=M		
    @pile
    M=M+1
    // pop
    @pile
    A=M
    D=M		
    @pile
    M=M+1	

Durant son exécution, la mémoire d’un de nos programmes en minuscule assembleur comprendra trois parties. Tout d’abord, le bas de la mémoire (adresses de 0 à 15) est réservé pour stocker des valeurs particulières. Le livre en définit plusieurs dans les derniers chapitres. Nous en discuterons prochainement. La deuxième partie de la mémoire contient les variables, tableaux et chaînes de caractères utilisés par le programme. Dans le minuscule assembleur, cette zone démarre à l’adresse 16 et peut grandir vers le haut si le programme a besoin de plus de mémoire (nous ne discuterons pas de ce cas de figure dans ce cours introductif, mais vous en entendrez parler l’an prochain en langage C notamment). La dernière partie de la mémoire est réservée à la pile. Celle-ci démarre à une adresse haute et grandit vers le bas au fur et à mesure que l’on y stocke des adresses et des données. Nous verrons que cette pile a de nombreuses utilisations en assembleur et par extension dans les langages de programmation.

Organisation de la mémoire de données d’un programme

Pour pouvoir utiliser cette pile, nous devons d’abord convenir de l’adresse qui correspond au sommet de la pile. Nous prenons la convention de débuter la pile à l’adresse la plus haute en mémoire RAM, 16383.

Nous pouvons maintenant réécrire notre programme en assembleur en utilisant cette pile. Le livre réserve l’adresse 0 en mémoire de données pour stocker l’adresse du sommet de la pile. Grâce à cette pile, nous pouvons réécrire les fonctions compte et oppose.

La fonction oppose est la plus simple. Elle calcule d’abord l’opposé de la variable compteur. Ensuite, elle récupère sur le pile l’adresse de retour et incrémente l’adresse du sommet de pile. Elle se termine par un saut à cette adresse de retour.

La fonction compte est un peu plus compliquée puisqu’elle contient un appel à la fonction oppose et qu’elle doit retourner au programme appelant. Elle incrémente d’abord la valeur de la variable compteur. Ensuite, elle sauve l’adresse de retour sur la pile avant d’appeler la procédure oppose. Au retour de celle-ci, elle récupère l’adresse de retour qui est au sommet de la pile pour retourner au programme appelant.

Le programme complet est repris ci-dessous. Il est téléchargeable depuis asm/procedure-pile.asm.

   @16383 // sommet choisi pour notre pile
   D=A
   @SP    // 0 par convention dans le livre
   M=D	
   @compteur
   M=0
(LIGNE1)
   @1  // ligne 1
   D=A
   @a  
   M=D
   @SP
   M=M-1    // libération d'une place au sommet de la pile 	
   @LIGNE3  // sauvegarde de l'adresse de retour
   D=A
   @SP
   A=M 	
   M=D
   @COMPTE  // appel de la procédure
   0;JMP                  // adresse 18 
(LIGNE3)                  // adresse 19
   @2  // ligne 3
   D=A
   @a  
   M=D
   @SP
   M=M-1    // libération d'une place au sommet de la pile 	
   @LIGNE5  // sauvegarde de l'adresse de retour
   D=A
   @SP
   A=M 	
   M=D	
   @COMPTE  // appel de la procédure
   0;JMP	          // adresse 31
(LIGNE5)                  // adresse 32
   @3    // ligne 5
   D=A
   @a  
   M=D                    // adresse 35
   @FIN
   0;JMP
(COMPTE) 
   @compteur  
   M=M+1
   @SP
   M=M-1    // libération d'une place au sommet de la pile 	
   @SUIVANT  // sauvegarde de l'adresse de retour
   D=A
   @SP
   A=M 	
   M=D		
   @OPPOSE   // appel de la procédure
   0;JMP                      
(SUIVANT)                                   
   @SP                 // adresse 48
   A=M
   D=M	
   @SP
   M=M+1
   A=D	
   0;JMP
(OPPOSE)
   @compteur           // adresse 56
   M=-M
   @SP                 // adresse 58
   A=M
   D=M	
   @SP
   M=M+1
   A=D	
   0;JMP	
(FIN)
	

Grâce à cette pile, il est possible d’écrire des programmes qui contiennent un nombre quelconque de procédures qui s’appellent l’une l’autre et dans un ordre quelconque. La pile grandira au fur et à mesure des appels successifs à des procédures et rétrécira chaque fois qu’une procédure se termine. Il est important de noter que pour que ce système fonctionne correctement il est nécessaire que chaque procédure manipule correctement la pile. Si le sommet de la pile se situe à l’adresse A au début de l’exécution d’une procédure, à la fin de celle-ci la pile doit contenir exactement les mêmes informations. Si une procédure laissait la pile avec un élément en plus ou un élément en moins lorsqu’elle retourne à l’adresse de retour dans le programme appelant, alors le programme complet ne fonctionnerait plus correctement. Pour s’en rendre compte, il suffit de prendre le programme ci-dessous et de l’exécuter après avoir par exemple remplacé une des instructions qui modifie la pile dans les fonctions compte ou oppose. Il faut être très rigoureux lorsque l’on écrit des programmes en langage assembleur qui manipulent la pile.

Note

Stack overflow

Les langages de programmation tels que python utilisent aussi une pile pour supporter les appels de procédures et de fonctions. C’est à l’interpréteur ou au compilateur de gérer correctement la pile. En général, le langage de programmation réserve une zone mémoire pour stocker la pile du programme. Certains langages de programmation comme python ou Java vérifient que la pile ne déborde pas lors de l’exécution d’un programme. Le cas échéant, ils lancent une exception qui indique un dépassement de pile (stack overflow en anglais) et le programme est arrêté. Pour cela, ils doivent vérifier l’état de la pile avant chaque opération push ou pop. D’autres langages de programmation comme le C ne vérifient pas la taille de la pile à chaque opération. Avec ces langages, il est possible que la pile croisse tellement qu’elle rencontre la zone contenant les données du programme. Dans ce cas, le programme aura un comportement totalement incohérent. Certaines attaques sur des programmes écrits en C exploitent ce genre de limitations du langage.

Nous avons utilisé la pile pour stocker les adresses de retour des procédures. En assembleur, et par extension dans la plupart des langages de programmation, la pile joue un rôle fondamental. C’est grâce à la pile que nous allons pouvoir également supporter les fonctions auxquelles il faut passer des arguments du programme appelant vers la fonction, mais aussi récupérer des valeurs de retour. Il faut aussi permettre à une fonction d’utiliser de la mémoire pour stocker des données temporaires pendant son exécution et de libérer correctement cette mémoire après.

Revenons à un exemple simple en python pour bien comprendre ce qu’il se passe avec des fonctions. Notre première fonction, f1, prend un entier en argument et retourne un entier également. Durant son exécution, elle utilise une variable locale, y. La deuxième fonction, f2 prend également un entier en argument et retourne un résultat entier. Le corps de la fonction f2 fait deux appels à la fonction f1 et utilise deux variables locales. Enfin, la fonction min prend deux arguments entiers et retourne un résultat entier. Elle utilise une variable locale.

# incrémente son argument de 1
def f1(x):
    y=x+1
    return(y)

# incrémente son argument de 2
def f2(x):
    y=f1(x)
    z=f1(y)
    return(z)

# retourne le minimum
def min(x,y):
    if (x<y):
        r=x
    else:
        r=y
    return(r)

print(f1(3)) # affiche 4
print(f2(5)) # affiche 7
print(min(3,5)) # affiche 3

Pour supporter ces différents types de fonctions, nous devons répondre à trois questions :

1. Comment un programme appelant peut-il passer les arguments à une fonction ?

2. Comment un programme appelant peut-il récupérer le résultat d’une fonction ?

3. Comment une fonction peut-elle utiliser de la mémoire pour stocker ses variables locales ?

Commençons par la première question. Avant d’appeler une fonction, il est nécessaire d’avoir d’abord calculé les valeurs des arguments que l’on doit passer à cette fonction. Une fonction peut avoir un, deux, ou un nombre quelconque d’arguments. Ceux-ci devront être placés en mémoire dans une zone qui est accessible à la fonction lors de son exécution. Notre fonction doit déjà récupérer l’adresse de retour sur la pile. Les arguments de la fonction seront également placés sur la pile, dans l’ordre dans lequel ils sont passés à la fonction. Durant son exécution, la fonction pourra facilement récupérer ses arguments depuis la pile.

Pour le résultat de la fonction, deux approches sont possibles. La première est d’utiliser la pile pour retourner ce résultat. La seconde est de placer le résultat de la fonction dans un registre du processeur. La première solution a l’avantage de permettre à une fonction de retourner plusieurs résultats, comme en python par exemple. La seconde est utilisée par de très nombreux langages de programmation. C’est celle que nous adoptons dans ce chapitre. Par convention, une fonction écrite en minuscule assembleur retournera un seul mot de 16 bits et celui-ci sera placé dans le registre D qui est le seul registre vraiment utilisable sur le minuscule processeur.

Commençons par la fonction f1 pour illustrer le passage des arguments et de la valeur de retour d’une fonction simple. Pour le passage des arguments, nous devons convenir de l’ordre dans lequel ceux-ci et l’adresse de retour doivent être placés sur la pile. Le livre de référence choisit de placer d’abord les arguments et ensuite l’adresse de retour. Lors d’un appel à la fonction f1(7), la pile ressemblera à la fig-pile-avant-f1 où sp est l’adresse du sommet de la pile.

Contenu de la pile lors de l’appel à la fonction ``f1``

Pour récupérer son argument, la fonction f1 doit donc lire l’information se trouvant à l’adresse sp+1 tandis que l’adresse de retour se trouve au sommet de la pile. Le programme complet est téléchargeable via asm/f1.asm.

     @16383    // initialisation pile
     D=A
     @SP
     M=D
     @SP       // libération de la place pour l'argument     
     M=M-1
     @7        // argument
     D=A
     @SP
     A=M
     M=D
     @SP       // libération de la place pour l'adresse de retour     
     M=M-1
     @RETOUR   // adresse de retour
     D=A
     @SP
     A=M
     M=D
     @F1      // appel à la fonction   
     0;JMP
(RETOUR)
     // D contient le résultat de f1(7)
     @FIN
     0;JMP
(DEBUT)
// Implémentation simple en minuscule assembleur de la fonction f1
// def f1(x):
//     y=x+1
//    return(y)
(F1)
     @SP
     A=M+1   // adresse de l'argument x
     D=M+1   // calcul de y=x+1 et sauvegarde dans D
     @SP     // récupération de l'adresse de retour
     M=M+1   // et suppression de l'adresse de retour de la pile
     M=M+1   // et de l'argument
     A=M     // adresse du sommet de la pile après f1
     A=A-1   // adresse de l'argument de f1 sur la pile
     A=A-1   // adresse de l'adresse de retour sur la pile
     A=M     // chargement de l'adresse de retour dans A
     0;JMP   // retour au programme appelant
(FIN)     

Il est intéressant d’examiner un peu plus en détails l’implémentation de la fonction f1. Tout d’abord, notre fonction doit récupérer son argument. Celui-ci étant le deuxième élément sur la pile, il suffit de mettre son adresse dans le registre A. C’est ce que font les deux premières instructions de notre fonction. Après l’exécution de ces deux instructions, le registre A contient l’adresse de la zone mémoire contenant l’argument de la fonction f1. Pour incrémenter cet argument, il nous suffit de calculer M+1. Comme le résultat de ce calcul est aussi la valeur de retour de la fonction f1, il suffit de le stocker dans le registre D. En trois lignes nous avons donc implémenté le corps de la fonction. Il nous reste ensuite à récupérer l’adresse de retour de la fonction f1 sur la pile et de retirer cette adresse ainsi que l’argument pour que la fonction appelante retrouve la pile dans l’état dans lequel celle-ci se trouvait avant l’appel à f1. Toutes ces opérations doivent se faire sans utiliser le registre D puisque celui-ci contient déjà la valeur retournée par notre fonction. Les trois instructions suivantes (@SP, M=M+1 et M=M+1) modifient l’adresse du sommet de pile et « suppriment » donc l’adresse et l’argument qui s’y trouvent. Il est utile de noter qu’il suffit d’incrémenter l’adresse contenue dans SP pour retirer un élément sur la pile. Il n’est pas nécessaire de remplacer la valeur qui s’y trouve par zéro. Mettre cette valeur à zéro serait une perte de temps et donc de performance. Après l’exécution de ces trois instructions, SP contient la bonne valeur. Il nous reste à récupérer l’adresse de retour. Si X est l’adresse actuelle du sommet de la pile, alors l’adresse de retour doit se trouver à l’adresse X-2. Les quatre instructions qui suivent permettent de récupérer cette adresse et de la stocker dans le registre A pour pouvoir exécuter un saut vers cette adresse sans utiliser le registre D.

Nous pouvons maintenant analyser une fonction qui prend deux arguments comme celle qui calcule le minimum.

     @x        // force l'assembleur à réserver l'adresse 16 pour x
     @y        // force l'assembleur à réserver l'adresse 17 pour y
     @z        // force l'assembleur à réserver l'adresse 18 pour z
     @16383    // initialisation pile
     D=A
     @SP
     M=D
     @SP       // libération de la place pour le second argument     
     M=M-1
     @y        // argument
     D=M
     @SP
     A=M
     M=D
     @SP       // libération de la place pour le premier argument     
     M=M-1
     @x        // argument
     D=M
     @SP
     A=M
     M=D	
     @SP       // libération de la place pour l'adresse de retour     
     M=M-1
     @RETOUR   // adresse de retour
     D=A
     @SP
     A=M
     M=D
     @MIN      // appel à la fonction   
     0;JMP
(RETOUR)
     // D contient le résultat de min(x,y)
     @z
     M=D
     @FIN
     0;JMP
(DEBUT)
// Implémentation simple en minuscule assembleur de la fonction min
// def min(x,y):
//    if(x<y):
//        return(x)
//    return(y)	
(MIN)
     @SP
     A=M+1   // adresse de l'argument y
     D=M     // sauvegarde dans D
     @SP
     A=M+1
     A=A+1   // adresse de l'argument x
     D=D-M   // y-x
     @RETY
     D;JGT    
     @SP     // saut conditionnel a échoué, D doit contenir y
     A=M+1   // adresse de l'argument y
     D=M     // valeur de retour 
     @RET
     0;JMP
(RETY)
     @SP     // saut conditionnel a réussi, D doit contenir x
     A=M+1   // adresse de l'argument y
     A=A+1   // adresse de l'argument x
     D=M     // valeur de retour 
     @RET
     0;JMP
(RET)
     @SP     // récupération de l'adresse de retour
     M=M+1   // et suppression de l'adresse de retour de la pile
     M=M+1   // et suppression du second argument
     M=M+1   // et suppression du premier argument
     A=M     // adresse du sommet de la pile après min
     A=A-1   // adresse du premier argument sur la pile
     A=A-1   // adresse du deuxième argument sur la pile		
     A=A-1   // adresse de l'adresse de retour sur la pile
     A=M     // chargement de l'adresse de retour dans A
     0;JMP   // retour au programme appelant
(FIN)     

L’implémentation de cette fonction en minuscule assembleur est téléchargeable via asm/min.asm. Le script de test est téléchargeable via asm/min.tst. Par rapport à la fonction f1 que nous avons présentée précédemment, il faut regarder comment chaque argument est récupéré de la pile. A la fin de l’exécution de la fonction min, il faut retirer les trois éléments qui avaient étés placés sur la pile par le programme appelant. De cette façon, le programme qui a appelé la fonction min retrouve la pile dans l’état dans lequel elle se trouvait avant l’appel à la fonction.

Note

Utilisation de la pile par une fonction

Une fonction telle que f1 ou min qui utilise la pile doit respecter plusieurs principes pour garantir le bon fonctionnement du programme qui l’a appelée :

1. La fonction ne peut accéder aux éléments qui ont été placés sur la pile avant ses arguments et son adresse de retour. Les informations qui se trouvent dans le bas de la pile sont nécessaires à l’exécution d’autres fonctions et ne peuvent en aucun cas être modifiées par la fonction.

2. La fonction peut rajouter des éléments sur la pile, soit directement soit en appelant d’autres fonctions. Cela implique que l’adresse du sommet de pile peut changer durant l’exécution de la fonction. Quelles que soient les modifications qu’elle fait à la pile, la fonction doit garantir qu’après n’importe laquelle de ses exécutions la pile retrouvera l’état qu’elle avait avant l’appel à la fonction.

Si un de ces principes n’est pas respecté par une fonction, le programme qui utilise cette fonction risque d’avoir un comportement erratique voire totalement incorrect. C’est le développeur d’une fonction en assembleur qui doit garantir la correction de sa fonction pour toutes ses exécutions possibles. Comme dans des langages de programmation de plus haut niveau, les tests les plus exhaustifs possibles sont une excellente façon de vérifier le bon fonctionnement d’un fonction. Notez qu’il existe également des techniques qui permettent de prouver la correction d’une fonction, mais celles-ci sortent largement du cadre de ce document.

Dans notre implémentation des fonctions f1 et min, nous avons utilisé la technique du passage par valeur, c’est-à-dire que lorsqu’elle est appelée, une fonction reçoit du programme appelant les valeurs de ses arguments. Ces valeurs sont copiées sur la pile par le programme appelant et utilisées par la fonction. Cette technique est utilisée par de nombreux langages de programmation comme python lorsque l’on passe des valeurs d’un type primitif comme des réels ou des entiers à une fonction.

Il existe une seconde technique pour passer les arguments à une fonction. C’est le passage par référence. Dans ce cas, le programme appelant fournit à la fonction qu’il appelle une référence vers son argument. Cette référence est l’adresse en mémoire à laquelle la variable contenant l’argument est stockée. La différence fondamentale entre le passage par référence et le passage par valeur est que comme la fonction connaît l’adresse de la variable contenant son argument, elle peut modifier son contenu alors que c’est impossible avec le passage par valeur. En python, le passage par référence est utilisé lorsque l’argument passé à une fonction est une référence à un objet ou une liste. Il est possible de mixer le passage par référence et le passage par valeur dans une même fonction avec un argument entier passé par valeur et une liste passée par référence.

A titre d’illustration, la fonction inc ci-dessous permet d’incrémenter la variable dont l’adresse est passée par le programme appelant comme argument. Le corps de la fonction inc accède à l’adresse de la variable utilisée par le programme appelant et modifie sa valeur avant de terminer son exécution.

     @x       // variable
     @r       // résultat
     @16383    // initialisation pile
     D=A
     @SP
     M=D
     @SP       // libération de la place pour l'argument     
     M=M-1
     @x        // adresse de la variable passée en argument
     D=A
     @SP
     A=M
     M=D
     @SP       // libération de la place pour l'adresse de retour     
     M=M-1
     @RETOUR   // adresse de retour
     D=A
     @SP
     A=M
     M=D
     @INC      // appel à la fonction   
     0;JMP
(RETOUR)
     // D contient le résultat de inc(x)
     @r
     M=D
     @FIN
     0;JMP
// Implémentation simple en minuscule assembleur de la fonction inc qui
// incrémente la valeur stockée à l'adresse passée en argument
// exemple de passage par référence - bien spécifier quand c'est le cas
(INC)
     @SP
     A=M+1   // élément de la pile contenant l'argument
     D=M     // 
     A=D
     M=M+1   // incrémentation de la variable
     @SP
     A=M+1   // adresse contenant l'argument
     M=D     // mise à jour de la valeur de la variable passée en argument
     @SP     // récupération de l'adresse de retour
     M=M+1   // et suppression de l'adresse de retour de la pile
     M=M+1   // et de l'argument
     A=M     // adresse du sommet de la pile après inc
     A=A-1   // adresse de l'argument de inc sur la pile
     A=A-1   // adresse de l'adresse de retour sur la pile
     A=M     // chargement de l'adresse de retour dans A
     0;JMP   // retour au programme appelant
(FIN)     

Le programme complet (asm/inc.asm) et son script de test (asm/inc.tst) sont téléchargeables.

Nous devons maintenant trouver une réponse à la troisième question. Lors de son exécution, une fonction doit souvent utiliser de la mémoire, pour stocker des résultats intermédiaires de calculs ou des variables locales. C’est le cas de la fonction fct dans l’exemple en python ci-dessous. Celle-ci a besoin de mémoire pour réaliser les calculs qui se trouvent dans son corps. Il en va de même par exemple pour une fonction qui contiendrait une simple boucle.

# retourne x+2*y si x<y et y-5*x sinon
def fct(x,y):
    if (x<y):
        r=x+2*y
    else:
        r=y-5*x
    return(r)

Chacune des variables locales d’une fonction doit être stockée à une adresse mémoire. Une première approche naïve pour résoudre ce problème serait de réserver une zone de mémoire fixe pour les variables locales utilisées par chaque fonction. Dans une implémentation en assembleur de l’exemple ci-dessus, on pourrait réserver une adresse en mémoire RAM pour la variable r de la fonction fct. Malheureusement, cette approche a deux inconvénients. Premièrement, toute la mémoire qu’une fonction peut utiliser durant son exécution doit être réservée en RAM avant de pouvoir exécuter cette fonction. Si une fonction doit utiliser un grand tableau lorsqu’elle est appelée avec une valeur spécifique d’un argument, alors la zone nécessaire pour ce tableau doit toujours être réservée, même si la fonction n’est jamais exécutée par le programme. Le deuxième inconvénient est qu’il est impossible avec cette approche de supporter une fonction f qui appelle une fonction g qui elle-même appelle une fonction f car le premier appel à la fonction f aura initialisé les « variables locales de la fonction f » puis fera appel à la fonction g. Lorsque g fait appel de son côté à la fonction f, cette seconde invocation de la fonction f va modifier les données stockées aux adresses en mémoire qui correspondent à ses variables locales et donc modifier les variables utilisées par la première invocation de la fonction f. Si ce second inconvénient peut paraître un peu théorique et hypothétique à ce stade, il est malheureusement bien réel en pratique.

On peut éviter ces deux inconvénients en utilisant la pile comme mémoire pour stocker les variables locales d’une fonction. La pile n’utilise la RAM que durant l’exécution de la fonction, il n’y a donc pas de gaspillage de mémoire comme avec la solution précédente. Dans le cas où une invocation de la fonction f appelle la fonction g qui appelle elle-même la fonction f, le bas de la pile contiendra les arguments, adresse de retour et variables de la première invocation de la fonction f. Au-dessus de ces informations, on trouvera les arguments, adresses de retour et variables locales de la fonction g. Enfin, les arguments, adresse de retour et variables locales de la seconde invocation de la fonction f sont au sommet de la pile. A la fin de son exécution, cette invocation de la fonction f libère la mémoire qu’elle utilise sur la pile.

La meilleure illustration de l’utilisation de la pile par les fonctions en assembleur est le support des fonctions récursives. En informatique, on parle de récursion lorsqu’une fonction s’appelle elle-même. C’est le cas par exemple de la fonction sumn qui permet de calculer la somme des n premiers naturels.

# Somme des n premiers naturels
def sumn(n):
    if(n==0):
        return(0)
    return(n+sumn(n-1))

print(sumn(1)) # affiche 1
print(sumn(3)) # affiche 6

Cette fonction peut être traduite en minuscule assembleur. Il y a trois parties distinctes dans cette fonction récursive. La première, généralement baptisée le cas de base, est la partie du code qui calcule la valeur de retour lorsque l’argument de la fonction est nul. Les premières instructions récupèrent l’argument de la pile et le placent dans le registre D. Si celui-ci est nul, il contient déjà la valeur de retour (0). Il suffit ensuite d’exécuter les instructions qui permettent de retirer l’argument et l’adresse de retour de la pile et ensuite de retourner au programme appelant.

La deuxième partie de la fonction sumn est l’appel récursif (à partir de l’étiquette RECURSION). Dans ce cas, nous commençons par décrémenter l’argument qui avait préalablement été placé dans le registre D. La valeur calculée est celle qui est passée à l’appel sumn(n-1). Elle est placée sur la pile ainsi que l’adresse de retour (RETSUMN).

La troisième partie de la fonction sumn est le retour de l’appel récursif (après RETSUMN). Nous recevons dans le registre D le résultat du calcul de sumn(n-1). Il nous reste à y additionner la valeur de l’argument qui se trouve sur la pile. Cette addition est réalisée par les trois premières instructions de cette partie. Ensuite, il suffit de retirer l’argument et l’adresse de retour de la pile pour retourner au programme appelant.

     @x       // variable
     @r       // résultat
     @16383    // initialisation pile
     D=A
     @SP
     M=D
     @SP       // libération de la place pour l'argument     
     M=M-1
     @x        // adresse de la variable passée en argument
     D=M
     @SP
     A=M
     M=D
     @SP       // libération de la place pour l'adresse de retour     
     M=M-1
     @RETOUR   // adresse de retour
     D=A
     @SP
     A=M
     M=D
     @SUMN      // appel à la fonction   
     0;JMP
(RETOUR)
     // D contient le résultat de SUMN(x)
     @r
     M=D
     @FIN
     0;JMP
// Implémentation simple en minuscule assembleur de la fonction récursive
// sumn qui retourne la somme des n premiers naturels
(SUMN)
     @SP
     A=M+1   // élément de la pile contenant l'argument
     D=M     //
     @RECURSION
     D;JNE
             // argument == 0, D contient déjà 0
     @FINSUMN
     0;JMP
(RECURSION)
             // D contient l'argument, calculer n-1 puis appeler sumn
     D=D-1
     @SP       // libération de la place pour l'argument     
     M=M-1
     @SP
     A=M
     M=D
     @SP       // libération de la place pour l'adresse de retour     
     M=M-1
     @RETSUMN   // adresse de retour
     D=A
     @SP
     A=M
     M=D
     @SUMN      // appel à la fonction
     0;JMP
(RETSUMN)     
                // retour de sumn(n-1), reste à récupérer n et n+D
     @SP
     A=M+1      // élément de la pile contenant l'argument
     D=D+M      // calcul de la valeur de retour
(FINSUMN)
             // libération de la pile et retour
     @SP     // récupération de l'adresse de retour
     M=M+1   // et suppression de l'adresse de retour de la pile
     M=M+1   // et de l'argument
     A=M     // adresse du sommet de la pile après SUMN 
     A=A-1   // adresse de l'argument de SUMN sur la pile
     A=A-1   // adresse de l'adresse de retour sur la pile
     A=M     // chargement de l'adresse de retour dans A
     0;JMP   // retour au programme appelant	     			  	
(FIN)     

Ce programme (asm/sumn.asm) et son script de test (asm/sumn.tst) sont téléchargeables.

Pour bien comprendre le fonctionnement d’un tel programme récursif et son utilisation de la pile, il est intéressant d’observer son exécution pas à pas en parallèle avec l’évolution de la pile. La Fig. 28 présente l’état de la pile lors de l’appel à la fonction sumn avec 3 comme argument. Par convention, le sommet de la pile se trouve en bas de la figure et utilise une police de caractères grasse.

Contenu de la pile lors de l’appel à la fonction sumn(3)

Durant son exécution, cette fonction fait appel à sumn(2). La Fig. 29 présente l’état de l’appel au moment de cet appel.

Contenu de la pile lors de l’appel à sumn(2)

Lors de son exécution, l’invocation de la fonction sumn avec 2 comme argument va d’abord faire appel à sumn(1). La Fig. 30 présente l’état de l’appel au moment de cet appel.

Contenu de la pile lors de l’appel à sumn(1)

Lors de son exécution, l’invocation de la fonction sumn avec 1 comme argument va d’abord faire appel à sumn(0). La Fig. 31 présente l’état de l’appel au moment de cet appel.

Contenu de la pile lors de l’appel à sumn(0)

Nous sommes maintenant dans l’exécution de la fonction sumn(0). Celle-ci retourne la valeur 0 dans le registre D et retire les deux mots se trouvant au sommet de la pile. Elle retourne à l’adresse RETSUMN avec la pile dans l’état représenté à la Fig. 30. Grâce à cette pile, la fonction sumn récupère son argument (1) et retourne la valeur 1 qui est la somme entre la valeur du registre D et son argument. A la fin de son exécution, cette invocation de la fonction sumn retire les deux mots qui se trouvaient au sommet de la pile.

L’état de la pile est maintenant celui de la Fig. 29 et le registre D contient la valeur 1. Nous sommes dans la dernière partie de l’invocation de la fonction sumn(2). Celle-ci calcule son résultat (3) et retire les deux mots se trouvant au sommet de la pile avant de faire un saut à l’adresse RETSUMN.

Nous sommes maintenant dans l’invocation de la fonction sumn(3). L’état de la pile est celui de la Fig. 28. La fonction récupère son argument (3) et l’ajoute au résultat de la fonction appelée qu’elle a reçu dans le registre D (3). Le registre D contient maintenant le résultat final (6) de l’appel sumn(3). Il ne reste plus qu’à retirer les deux mots se trouvant au sommet de la pile et retourner à l’adresse RETOUR dans le programme appelant.

Note

Pour aller au delà

L’explication des fonctions récursives marque la fin de notre exploration des principes de fonctionnement des ordinateurs. Même si nous avons couvert différents aspects du fonctionnement des ordinateurs modernes, nous sommes loin d’en avoir fait le tour. Vous aurez d’autres occasions de compléter votre formation dans ce domaine passionnant dans la suite de vos études.

En deuxième année du bachelier, vous apprendrez à exploiter les processeurs multi-coeurs en utilisant notamment le langage Java dans le cours Informatique 2. Vous apprendrez aussi à programmer en langage C dans le cours Projet 3. De nos jours, le langage C est le langage de programmation qui remplace l’assembleur dans la plupart des cas où il est nécessaire de contrôler finement le matériel. Le cours de Calculabilité, logique et complexité vous permettra d’apprendre les bases théoriques de l’informatique et notamment un modèle théorique du fonctionnement des ordinateurs qui est la machine de Turing. Le cours de Paradigmes de programmation et concurrence vous permettra de mieux comprendre comment fonctionnent les langages de programmation.

En troisième année du bachelier, le cours de Systèmes informatiques vous permettra de comprendre comment fonctionne un système d’exploitation. Vous aurez à nouveau l’occasion d’écrire des programmes en langage C et en assembleur mais sur des processeurs réels cette fois. Le cours de Réseaux informatiques vous permettra de comprendre comment les ordinateurs connectés à Internet peuvent s’échanger de l’information.

En Master, le cours Architecture and performance of computer systems vous permettra de comprendre plus en profondeur les interactions entre le matériel et le logiciel et les facteurs qui influencent les performances d’un ordinateur. D’autres cours à option sont accessibles dans ce domaine comme Design and Architecture of digital electronic systems ou Design of Embedded and real-time systems.

En attendant, si vous cherchez des informations complémentaires, il existe de nombreux livres de références très complets :

• la seconde partie du livre The Elements of Computing Systems écrit par Noam Nisan et Shimon Schocken et publié au MIT Press poursuit son exploration des ordinateurs en développant les différentes couches logicielles dont un assembleur et une machine virtuelle qui supporte un langage un peu plus facile à utiliser que le minuscule assembleur. Cette machine virtuelle est ensuite utilisée pour implémenter un langage de programmation orienté objet simple et un petit système d’exploitation.

• la série de livres Computer Organization and Design - The Hardware/Software Interface écrits par David Patterson et John Hennessy. Ces livres présentent le fonctionnement des ordinateurs en détaillant un microprocesseur particulier. Il en existe trois versions. La première, Computer Organization and Design MIPS Edition se concentre sur les processeurs MIPS que l’on trouve dans différents types d’ordinateurs embarqués. La deuxième, Computer Organization and Design RISC-V Edition s’appuie sur les nouveaux processeurs RISC-V dont toutes les spécifications sont disponibles en open-source. La troisième, Computer Organization and Design ARM Edition présente les processeurs ARM que l’on retrouve sur la plupart des smartphones de nos jours. Une ancienne édition de ce livre a été traduite en français mais n’est malheureusement plus disponible. David Patterson et John Hennessy ont également écrit le livre Computer Architecture : A quantitative approach qui fait référence dans le domaine, mais s’adresse plutôt à des étudiants de master ou des professionnels.