Avertissement : les exécutions de certains des programmes de cet article peuvent être différentes de celles annoncées car elles dépendent des mises à jour de la version en ligne de scratch2. Et c’est justement le propos de cet article de leur substituer des programmes robustes dans le sens où leur exécution ne dépend pas des mises à jour ou même du langage.
Une des nouveautés dans le nouveau programme du collège de mathématiques de 2016 est le thème E : Algorithmique et programmation et dans ce thème, les connaissances et compétences associées
- Écrire un programme dans lequel des actions sont déclenchées par des événements extérieurs.
- Programmer des scripts se déroulant en parallèle :
- Déclenchement d’une action par un événement
C’est avec ces actions que les repères de progressivité suggèrent de commencer : « en 5ème, les élèves s’initient à la programmation événementielle ». Or la programmation événementielle n’est pas une notion simple.
Prenons comme exemple Charly et Bob qui viennent tous deux de passer le brevet des collèges en Amérique du Nord du 7 juin 2017. Afin de vérifier leurs réponses dans l’exercice 5, ils écrivent tous deux le programme proposé.
Charly est dépité, il a répondu à la question 5 que lorsque le chat atteint la balle, il dit « je t’ai attrapé » pendant 2 secondes et retourne à sa place initiale. Or quand il teste son programme, il ne se passe rien quand le chat atteint la balle.
Charly appelle Bob qui lui dit qu’il ne comprend pas car avec son programme quand le chat atteint la balle, il dit « je t’ai attrapé » pendant 2 secondes et retourne à sa place initiale. Ils comparent leur programmes et ne voient aucune différence (et visuellement il n’y en a effectivement aucune). Charly remarque cependant que s’il appuie sur une touche une fois le chat sur la balle, il dit « je t’ai attrapé » pendant 2 secondes et retourne à sa place initiale. Il pense alors que son ordinateur lui en veut ou qu’avec lui ça ne marche jamais.
L’initiation à la programmation ne semble pas avoir pour effet de démystifier l’ordinateur et l’informatique pour Charly et pourtant cela me semble un des buts principaux d’un tel enseignement.
Dans cet article, je vais présenter les explications dont a besoin Charly pour comprendre pourquoi son programme ne se comporte pas comme celui de Bob ainsi que des solutions à lui proposer pour qu’une telle situation ne lui arrive plus. J’aborderai les notions de concurrence, d’interdépendance, de synchronisation, de section critique et distinguerai la programmation parallèle et la programmation séquentielle.
Instructions concurrentes, instructions interdépendantes
Dans les programmes de Bob et Charly, à chaque fois qu’on appuie sur une flèche, deux événements sont en concurrence. Par exemple, si j’appuie sur la flèche du haut, les deux événements suivants sont en concurrence :
Même si ces instructions sont écrites en parallèle, elles ne sont jamais exécutées en même temps (scratch n’utilise qu’un processeur/coeur) mais l’une puis l’autre
- dans la cas de Bob d’abord le déplacement puis le test
- dans le cas de Charly d’abord le test puis le déplacement.
Le problème est que ces deux instructions sont interdépendantes car la valeur du test dépend de la position du chat qui dépend du déplacement.
Dans le programme de Bob, le test a lieu après le déplacement donc le chat parle après avoir atteint la balle.
Dans le programme de Charly, le test a lieu sur la position qui va être quittée lors du déplacement, il est donc normal que le chat ne dise rien quand il arrive sur la balle. Il parlera lors du déplacement suivant.
Lorsque deux instructions sont concurrentes dans un programme scratch, elles ne s’exécutent pas en même temps mais l’une puis l’autre (tellement rapidement que pour l’utilisateur elles semblent s’exécuter en même temps) car il n’y a qu’un processeur/coeur pour l’exécuter. On pourrait espérer qu’un peu de hasard ait été introduit et que d’une exécution à l’autre le parallélisme apparaisse par un ordre d’instructions différent mais il n’en est rien. Voilà pourquoi le programme de Charly se comporte toujours de la même façon tout comme celui de Bob.
Si un peu de hasard avait été introduit, la relation d’interdépendance apparaîtrait plus nettement lors de l’exécution des programmes.
Dans la version de scratch 2 en ligne, l’instruction exécutée en dernier est celle qui a été modifiée ou déplacée en dernier. Donc si on veut que le test soit effectué après le déplacement, il suffit de modifier ou déplacer l’événement avec la conditionnelle juste avant de lancer l’exécution. Il n’y a aucun intérêt à retenir cette information, car elle sera peut être obsolète dès la prochaine mise à jour.
Ce qu’il faut retenir par contre est que
- deux instructions en concurrence sont exécutées l’une puis l’autre, tellement rapidement que cela semble simultané
- il est difficile de savoir laquelle des deux va être exécutée en premier
C’est pourquoi il faut éviter les instructions concurrentes interdépendantes et préférer une autre solution algorithmique. Si on utilise des instructions concurrentes interdépendantes, il faut s’assurer que toutes leurs exécutions possibles correspondent à ce qui est attendu.
Même si l’expérimentation est fondamentale en informatique, il me semble indispensable de prendre un peu de temps pour faire des synthèses de ce qui a été vu par les uns et les autres. Dans le cas de Bob et Charly, je montre le problème qu’ils ont rencontré, la cause (les instructions concurrentes interdépendantes), une solution efficace et je définis une règle il faut éviter les instructions concurrentes interdépendantes. Pour certains élèves, la synthèse permet de consolider une analyse qu’ils ont faite et éventuellement de leur donner le vocabulaire adapté, pour d’autres le problème aura aiguisé leur curiosité et ils retiendront au moins une partie de la synthèse, d’autres l’oublieront.
Alors cette solution ?
Dans cet exemple, on n’a pas vraiment besoin que le déplacement ait lieu en même temps que l’annonce du chat. Il suffit que le chat parle juste après avoir attrapé la balle. On n’a donc pas besoin d’instructions en parallèle mais d’instructions séquentielles, on remplace donc le programme du chat par :
Plus de concurrence, plus de problème. (On peut créer un nouveau bloc si on souhaite éviter la répétition du code).
Une première question à poser à l’élève que l’on aide est donc : est ce que les instructions peuvent se succéder ? Auquel cas, on les écrit à la suite les unes des autres, c’est de la programmation séquentielle beaucoup plus facile à appréhender. Ou est ce qu’elles doivent avoir lieu en même temps ?
Synchronisation
Que faire quand on veut synchroniser deux instructions ? Prenons deux autres exemples :
- d’une part deux chiens identiques à la couleur près qui se dirigent l’un vers l’autre à la même vitesse, dont on souhaite qu’ils disparaissent quand ils se touchent
- d’autre part une balle qui se dirige vers une barre. On souhaite que la balle rebondisse sur la barre et que la barre disparaisse dès qu’elle est touchée (comme dans un casse-brique)
Les chiens
On considère le programme chien1 où les scripts des deux chiens sont similaires (à gauche le script du chien vert, à droite celui du chien bleu) :
A chaque exécution du programme, quel que soit le bloc modifié en dernier, le chien vert disparaît, seul reste le chien bleu.
Si on remplace pour chaque chien l’instruction avancer de 20 par avancer de 10, alors à chaque exécution du programme, quel que soit le bloc modifié en dernier, le chien bleu disparaît, seul reste le chien vert.
Si on inverse l’ordre des lutins comme dans le programme chien2, cette fois-ci le chien bleu disparaît pour une avancée de 20 et le vert pour une avancée de 10.
La conditionnelle si dog3 touché est en concurrence avec la conditionnelle si dog2 touché. Les blocs d’instructions si dog3 touché, caché et si dog2 touché, caché sont interdépendants car si le lutin dog3 se cache alors le lutin dog2 ne peut plus le toucher et vice versa. L’exécution du programme semble imprévisible tant qu’on ne l’a pas testé.
Une solution pour la rendre prévisible et obtenir le résultat souhaité (la disparition des deux chiens) est de supprimer cette interdépendance, de n’avoir qu’un test de collision. Se pose alors le problème de prévenir les deux lutins de cette collision. On utilise alors un message qui permet de partager avec tous les lutins une information.
Lorsqu’un chien entre en collision avec l’autre chien, il envoie alors un message à tous les lutins. A sa réception, chaque lutin disparaît.
Remarque : si comme dans l’exemple présenté les objets en mouvement sont nettement plus longs qu’un pas, un seul test suffit.
Rebond
Bob et Charly tentent tous deux de résoudre le problème posé : écrire un programme où une balle qui se dirige vers une barre, rebondit sur la barre et la barre disparaît dès qu’elle est touchée.
Ils proposent le même script pour la barre :
Bob propose le script suivant pour la balle :
Il constate que lorsque la balle arrive à la hauteur de la barre, la barre disparaît mais la balle continue tout droit. Ce qui n’est pas le résultat attendu.
Charly est content ; son script répond au problème posé :
Ils attendent du professeur qu’il leur explique pourquoi le programme de Bob ne produit pas le résultat attendu alors que celui de Charly y parvient. Je fais remarquer à Bob et Charly que dans leur programme il y a deux blocs d’instructions concurrentes interdépendantes si Paddle est touché,orienté à -90 dans le script de la balle et si ballon est touché,caché dans le script de la barre. En effet si le lutin Paddle est caché, le lutin ballon ne peut plus le toucher.
Comme eux, je suis bien en peine de savoir lequel est exécuté en premier, étant donné qu’ils sont tous deux dans une boucle répéter indéfiniment et donc sont exécutés indéfiniment. Quand on exécute le programme de Bob, la barre disparaît avant que la balle ait pu tester sa présence. Mais pourquoi ? Mystère !
Je rappelle alors que lorsque des instructions s’exécutent en parallèle il est bien difficile de prédire dans quel ordre elles vont s’exécuter. C’est pourquoi il faut éviter les instructions concurrentes interdépendantes.
En faisant un seul test et en envoyant un message à tous les lutins pour prévenir que ce test a comme valeur vraie, il n’y a plus de concurrence. La disparition de la barre n’a plus d’influence sur l’orientation de la balle.
Section critique, exclusion mutuelle
Nous venons de voir qu’il faut éviter les instructions concurrentes interdépendantes. Des groupes d’instructions peuvent être concurrentes pour une ressource, on désigne alors ces groupes par le terme section critique. Lors de l’exécution, à chaque instant, au plus une de ces sections critiques peut être en train d’être exécutée.
Plus généralement quand l’exécution d’un groupe d’instructions empêche l’exécution d’un autre groupe d’instructions et vice versa, on parle d’exclusion mutuelle.
Nous allons voir ces situations à travers deux exemples .
On veut dessiner un cercle à une position aléatoire à chaque fois que l’on clique sur le bouton
Bob vient me voir car son programme ne marche pas
Effectivement il ne produit pas le résultat attendu.
Le dessin d’un cercle peut être interrompu par une nouvelle demande dessin. Comment faire pour que l’exécution d’un dessin exclue tout autre demande ?
Voici le résultat attendu pour un autre programme :
Dans ce cas le mouvement passe d’une balle à l’autre. Le mouvement de l’une exclut le mouvement de l’autre. Le programme ne doit pas les exécuter en même temps. Comment réaliser cette exclusion mutuelle ?
Dessin aléatoire
Voici les scripts de Bob pour le bouton
et pour le lutin qui dessine
Bob a utilisé un message pour que le bouton indique au lutin qui dessine qu’il doit tracer un cercle. Il est confronté à un problème : on ne peut pas demander au lutin qui dessine de commencer un nouveau cercle alors qu’il est déjà en train d’en dessiner un.
On est face à une section critique : deux scripts veulent tous deux utiliser la même ressource stylo. Il s’agit de l’exécution en cours du dessin du cercle et du message cercle qui appelle une nouvelle exécution de cette même suite d’instructions.
Alice propose une solution intéressante au problème, elle fait disparaître le bouton tant qu’un cercle est en train d’être dessiné :
Pour cela, elle utilise un nouveau message qui indique au bouton quand le lutin qui dessine est à nouveau disponible :
scripts du bouton
scripts du lutin qui dessine
C’est une solution très satisfaisante, Alice a évité la concurrence entre le dessin et un nouvel ordre de dessiner.
Une autre solution pour empêcher le dessin d’être interrompu est d’utiliser une variable et de n’avoir qu’un seul script pour le lutin qui dessine :
pour le bouton
pour le lutin qui dessine
Si on enrichit le programme pour proposer 3 formes à dessiner, un cercle, un carré ou une étoile, les programmes précédents s’adaptent sans mal : la proposition d’Alice, la seconde solution.
Remarque : il est également possible d’utiliser des clones pour obtenir le résultat attendu. Cette solution permet de dessiner plusieurs cercles en même temps. Il faut cependant trouver une astuce (un costume différent par exemple), pour que les clones ne créent pas de clone d’eux-même à la réception du message cercle. Pour la version 3 formes, j’ai utilisé un lutin de dessin par forme.
Transmission du mouvement
Une solution pour obtenir l’exécution attendue est d’utiliser des envois de messages entre les balles. La balle noire commence et indique qu’elle a fini en envoyant un message à la balle rouge qui prend le relai et envoie un message quand elle a fini et ainsi de suite.
On remarque que seule la balle active teste s’il y a collision afin d’éviter tout problème de concurrence.
Une autre solution est d’utiliser une variable qui indique quelle balle est active.
Dans ce cas, seule la balle noire teste s’il y a collision afin d’éviter tout problème de concurrence, c’est elle également qui gère quelle balle est active en modifiant la valeur de la variable.
On peut poursuivre cet idée en ayant plusieurs balles qui peuvent bouger chacune à leur tour : d’abord la balle noire, puis la balle rouge, puis la bleue, puis la verte et ainsi de suite.
Chaque balle à son tour se déplace, teste la collision avec la balle suivante et transmet le mouvement à travers la variable lutin en mouvement.
On peut reprendre l’usage de la variable de cet exemple pour partager une ressource entre plusieurs lutins de façon à ce qu’il n’y ait pas de famine, c’est-à-dire que chacun dispose de la ressource à un moment donné.
Conclusion
Comme nous l’avons vu, il n’y a pas de vrai parallélisme avec scratch car on ne dispose que d’un processeur/coeur. L’ordre d’exécution des instructions est toujours le même si les actions de l’utilisateur du programme sont les mêmes. Et ceci augmente la difficulté d’écriture des programmes. En effet si d’une exécution à l’autre, une instruction était parfois exécutée et parfois une autre, on pourrait penser qu’elles sont interdépendantes ou, tout du moins, qu’il y a un souci avec cette partie du programme, mais scratch n’a pas ce fonctionnement.
De plus, le simple déplacement d’un bloc d’instructions et l’ordre de création des lutins peuvent avoir une influence sur l’exécution d’un programme scratch. C’est pourquoi il est vraiment important d’éviter les instructions concurrentes interdépendantes en utilisant une autre solution algorithmique. Si on en utilise, il faut vérifier que toutes leurs exécutions possibles correspondent à ce qui est attendu.
Comme il n’y a pas de vrai parallélisme avec scratch et comme la lecture d’un programme avec des scripts en parallèle est généralement plus difficile que celle d’un programme séquentiel, autant privilégier l’écriture séquentielle quand les deux sont possibles et lisibles.