Fonctionnement d’AlgoTouch

Dans cette page, nous proposons d’expliquer les principes de fonctionnement du logiciel AlgoTouch. Comment les actions de l’utilisateur sont-elles transformées en programme? Comment le programme ainsi produit peut-il s’exécuter?

Ordinateur

Pour comprendre le fonctionnement d’AlgoTouch, il faut rappeler les principes de base du fonctionnement d’un ordinateur. Un ordinateur de base comprend essentiellement 4 entités :

  • une unité appelée mémoire centrale
  • une unité centrale
  • un clavier
  • un écran

Les ordinateurs modernes possèdent également d’autres éléments : de la mémoire sur disque, des connecteurs (USB, prise réseau, prise HDMI, prise casque), microphone, caméra, etc.

Mémoire

La mémoire est un dispositif électronique capable de stocker de grandes quantités de données codées sous forme de 8 chiffres binaires appelés octets. Chaque octet est stocké à un endroit précis de la mémoire appelé adresse. L’unité de mémoire ne possède que 2 commandes :

  1. stocker un octet à une adresse donnée
  2. récupérer la valeur d’un octet à une adresse donnée

Le rôle de la mémoire est double. Elle permet d’une part de stocker des données en quantité importante : des milliards d’octets (giga). D’autre part, elle contient des programmes codés sous forme d’octets.

Unité centrale

L’unité centrale est un composant électronique appelé aussi processeur. Son rôle est d’exécuter les instructions d’un programme. Le processeur contient une unité de calculs et quelques emplacements mémoire (appelés registres) pour stocker des résultats intermédiaires. Puisque le programme se trouve en mémoire, l’unité centrale répète la séquence suivante :

  1. récupérer la prochaine instruction en mémoire
  2. effectuer les opérations nécessaire à l’exécution de cette instruction

Globalement les instructions sont de 5 types :

  1. Chargement (Load) : charger une donnée dans le processeur depuis la mémoire
  2. Rangement (Store) : stocker une valeur du processeur en mémoire
  3. Entrées/sorties (E/S): charger une donnée saisie au clavier ou afficher une donnée à l’écran
  4. Opération (Op): effectuer une opération sur des données internes au processeur (additions, soustractions, multiplications, divisions, comparaisons sur des nombres entiers ou réels)
  5. Branchement (Branch) : déterminer l’adresse mémoire de la prochaine instruction à exécuter

Écran

L’écran sert à envoyer des informations compréhensibles par l’utilisateur. En effet, les informations codées en mémoire ne sont pas directement accessibles. Les programmes transforment les données, par exemple les nombres, sous une forme lisible. Un nombre étant codé sous forme binaire, il faut le transformer en une suite de caractères (des chiffres).

Par exemple, l’instruction qui affiche le contenu de la variable Nbre de valeur 4839 doit d’abord coder cette valeur dans une chaîne de caractères ASCII, ici le tableau Ch.  

 

Cette transformation peut donner lieu à un exercice!

Codage d'un entier en chaîne de caractères

Clavier

Le clavier sert à communiquer avec la machine. En effet, lorsqu’un programme s’exécute, il demande parfois des informations à l’utilisateur. Chaque frappe sur le clavier transmet un code qui est analysé par le programme.

Par exemple, le programme demande un nombre qu’il va ranger dans une variable (age). L’utilisateur frappe les caractères 1 puis 9 et valide par la touche Entrée. Les codes ASCII de ces deux caractères, respectivement 49 et 57, sont récupérés par le programme qui construit le nombre 19 (00010011 en binaire) qu’il range dans la variable age.

 

Cette transformation peut donner lieu à un exercice!

Lecture d'un nombre en tant que caractères

Modélisation avec AlgoTouch

AlgoTouch étant basé sur la manipulation directe des données d’un programme, la partie principale de l’interface graphique représente d’une certaine manière la mémoire d’une machine. Mais au lieu de représenter des milliards d’octets, l’interface visualise uniquement certaines données sous une forme plus facilement interprétable. Ce sont les variables, les tableaux, les macros (unités de programme). 

Transformation des actions en programme

L’utilisateur interagit avec le logiciel principalement avec la souris sur un ordinateur ou avec son doigt lorsqu’il utilise un tableau interactif. Il peut, d’une part, de façon classique, activer des menus et d’autre part, agir directement sur la partie graphique.  Le logiciel réagit aux différentes actions effectuées avec la souris.  Ce sont principalement :

  • l’appui sur un bouton (gauche ou droit)
  • le déplacement de la souris bouton enfoncé
  • le relâchement d’un bouton
  • le clic sur un bouton (gauche ou droit). C’est en fait un appui suivi du relâchement dans un court délai.

L’utilisateur utilise aussi, de temps en temps, le clavier pour saisir des informations comme par exemples, les nom et rôle d’une variable ou d’une macro, des valeurs, le nom d’un fichier, etc.

Illustrons sur un exemple simple, comment Agt analyse les gestes de l’utilisateur pour construire les instructions de programme associées. Considérons le cas où l’utilisateur veut affecter la valeur de la variable val dans la variable cpt.

Exécution d’un programme

Pour exécuter un programme AlgoTouch, Agt simule le fonctionnement d’un ordinateur très simple. Comme cet ordinateur n’existe pas, on parle de machine virtuelle notée MV par la suite. 

Machine virtuelle AlgoTouch

Sa mémoire contient les variables, constantes, index, tableaux ainsi que les programmes codés de chaque macro. Son unité centrale est composée d’une unité de calcul ainsi que d’une petite mémoire locale particulière appelée pile d’exécution. Contrairement à la mémoire centrale, les données de cette pile ne sont pas repérées par une adresse. Mais la pile fonctionne sur le modèle d’une “pile d’assiettes”. Lorsqu’on ajoute une donnée, opération d’écriture, elle est placée au sommet de la pile. A l’inverse la lecture d’une donnée consiste à prendre la valeur en sommet de pile.

La machine virtuelle AlgoTouch possède un jeu d’instruction spécifique très limité. Il est constitué de quelques instructions seulement. Un programme doit donc être traduit en une suite de ces instructions.

Jeu d’instructions de la MV

Les instructions, classées par catégories évoquées plus haut, sont les suivantes :

Chargement d'une donnée

  • PushValue valeur : empile la valeur
  • PushVariable variable : empile le contenu de la variable
  • PushIndexedVar tableau : empile le contenu d’une variable indexée
  • PushRead “prompt” : empile la valeur saisie par l’utilisateur

Rangement en mémoire

  • Assign variable : range le sommet de pile dans la variable
  • IndexedAssignment tableau :  le tableau  indexé par la valeur en sommet de pile reçoit le nouveau sommet de pile.

Entrées/sorties

  • PushRead “message” : empile la valeur saisie par l’utilisateur après affichage du message
  • PopWrite “message” : affiche le message puis le sommet de pile

Branchement

  • Branch condition adresse : définit la prochaine adresse à exécuter en fonction de la condition (always, false, true)
  • CallMacro macro : la prochaine instruction sera la première instruction de la macro
  • EndBloc  Terminate : retourne à l’adresse suivant de dernier appel de macro

Opérations

  • TwoOp opération : effectue une opération sur les deux valeurs en sommet de pile et range le résultat au sommet de pile.

     

    Les opérations sont soit des opérations arithmétiques (+, -, x, /, %), soit des comparaisons (==, !=, >, >=, <, <=). Dans ce dernier cas, le résultat vaut 0 si la comparaison rend faux ou 1 si vrai. 

Diverses commandes

Par ailleurs, pour faciliter la mise au point des programmes, diverses instructions ont été créées :
  • Continue : instruction sans effet débutant un bloc
  • EndBloc : instruction terminant chaque bloc. Permet d’arrêter le programme dans divers cas.
  • Todo “Message” : instruction produite lors d’une conditionnelle pour arrêter le programme afin de compléter le code manquant.

Exemples de code

Voici quelques exemples de code illustrant le rôle des différentes instructions.

Macro simple sans conditionnelle

Cet exemple illustre comment sont traduites les instructions d’affectations, d’opérations et d’entrées/sorties. La macro Affectations est une macro simple opérant sur un tableau a indexé par i. Elle demande à l’utilisateur de saisir une valeur x. On calcule la somme de x et a[i] dans r. Affichage de r, rangement de r dans a[i] et enfin incrémentation de i.

Détaillons le programme produit.

Détaillons le code produit.

Traduction du programme en instructions

Macro simple avec une conditionnelle

Considérons l’exemple très simple d’une macro qui compare deux entiers x et y puis affiche le minimum.

Traduction du programme en instructions

Macro boucle

Considérons l’exemple très simple d’une macro qui affiche les entiers de 0 à 9.

Traduction du programme en instructions

Macro boucle avec appel de macro

Reprenons le programme qui vérifie s’il existe des valeurs en double dans un tableau. Dans ce programme, il y a un appel à la macro Exist dans le corps de la boucle.

Une partie du code associé à ce programme est illustré ci-dessous. En particulier, le code correspondant à la partie Loop est surligné.

L’appel de la macro Exist est traduit par l’instruction à l’adresse 17 :
Call macro Exist

Le déroulement de l’appel de la macro Exist dans le programme Double est le suivant. Lorsque la machine virtuelle charge l’instruction à l’adresse 17, elle décode une instruction de type appel de macro. Comme après l’exécution de la macro Exist, le programme Double doit reprendre en séquence, la machine virtuelle conserve l’adresse 18 et le nom de la macro Double en sommet de pile. Ensuite, la machine virtuelle définit l’adresse de la prochaine instruction à exécuter comme étant l’adresse 0 du code Exist.

Extraits du code de la macro Double, autour de l’appel de macro Exist :
16: Continue
17: Call macro Exist
18: PushVariable i

Les instructions de la macro Exist s’exécutent normalement jusqu’à la dernière à l’adresse 37 :

EndBloc End algorithm

Cette instruction vient chercher au sommet de pile consécutivement le nom de la macro en attente puis l’adresse de redémarrage. Dans le cas présent la macro Double et l’adresse 18. C’est à cet endroit que la machine virtuelle va exécuter la prochaine instruction.

Extraits du code de la macro Exist, le début et la fin :

0 : Continue 
1 : PushVariable i
2 : PushVariable 1
3 : TwoOp ADD
4 : Assign j
...
33 : Continue 
34 : EndBloc End core loop
35 : Branch always : 8
36 : Continue 
37 : EndBloc End algorithm