Les programmes du manuel ISN traduits en Scheme (à ma façon)

L’association EPI (Enseignement public et informatique), par son groupe ITIC (Informatique et technologies de l’information et de la communication) qui réfléchit à la question depuis 1971, a réalisé un manuel destiné aux élèves qui prennent la spécialité ISN (informatique) en terminale (première version, avec les programmes en Java, suivie d’une seconde version avec les programmes en Python. Ces deux manuels sont disponibles en librairie ou en ligne librement consultables. Il y a aussi un livre du maître.

À l’instigation de Gilles Dowek, auteur principal de ce manuel, j’ai entrepris la traduction en Scheme des programmes d’exemples de ce livre. Ces programmes sont destinés à être publiés sur le site du manuel, mais comme il m’est apparu que le style fonctionnel inhérent à Scheme entrait assez mal dans le cadre Java-Python du livre, j’en donne ici une version adaptée assez librement, cependant que la version publiée sur le site de Gilles Dowek sera sans doute, après discussion, plus proche des modèles OCaml que j’ai traduits.

Les textes des programmes en Java, Python et les autres langages sont ici.

 Chapitre 1 - Bataille navale, taxes, fractions

Bataille navale :

Taxes :

Taux quelconque :

Fraction :

Second degré :

Poste :

 Chapitre 2 - Température, calendrier, recherche de mot

Température, d’abord l’algorithme en pseudo-code :

Algo : Moyenne Donnée : Observations tableau Soit : nbJours <- longueur(Observations) somme <- 0 pour i allant de 0 à nbJours - 1 faire somme <- somme + Observations[i] fait retourner somme / nbJours fin

puis le programme en Scheme :

Calendrier :

Algo : Bissextile Donnée : année si année mod 400 = 0 alors retourner vrai sinon si année mod 4 = 0 et année mod 100 != 0 alors retourner vrai sinon retourner faux finsi finsi fin Algo : nbJoursMois Données : année mois si mois = 2 alors si Bissextile(année) alors retourner 29 sinon retourner 28 finsi sinon retourner 30 + (mois + (mois / 8)) mod 2 finsi fin

Logarithme :

Oui ?

Second degré :

 Chapitre 3 - Newton, factorielle, répertoire, polynôme

Mesure principale :

Racine de 2 par la méthode de Newton :

Factorielle :

Répertoire :

Calcul formel :

Initiales :

 Chapitre 4 - Horaire, comptage, division, aléa, pseudonyme, répertoire

Horaire :

Horaire encore :

Nombre de a :

Division décimale :

Réinitialisation :

Globale :

Générateur de nombres pseudo-aléatoires :

Un pseudonyme convenable :

Algo : appartient Données : lettre mot Soit : L <- longueur(mot) pour i allant de 0 à L-1 faire si lettre = mot[i] alors retourner vrai finsi fin pour retourner faux fin Algo : BonPseudo Donnée : pseudo Soient : autorises <- "abcdefghijklmnopqrstuvwxyz" L <- longueur(pseudo) pour i allant de 0 à L-1 faire si appartient(pseudo[i], autorises) = faux alors retourner faux finsi fin pour retourner vrai fin

et en Scheme :

Portée :

Répertoire avec des procédures :

Échange (là les méthodes normales de Scheme avec des procédures butent sur le passage des arguments par valeur ; il faut soit, comme ici, définir une forme spéciale avec define-syntax, soit comme nous le verrons plus loin « envelopper » les valeurs à échanger dans un vecteur) :

Par valeur :

Échange en enveloppant les valeurs dans un vecteur d’une case :

 Chapitre 5 - Horaire, puissance, quotient

Encore les horaires :

Élever à la puissance :

Le quotient :

 Chapitre 11 - Répertoire

Nous nous proposons d’informatiser la consultation de notre répertoire téléphonique, enregistré comme suit dans un fichier :

Alice 0606060606 Bob 0606060607 Charles 0606060608 Djamel 0606060609 Emmanuel 0606060610 Frédérique 0606060611 Guillaume 0606060612 Hector 0606060613 Isabelle 0606060614 Jérôme 0606060615

Voici la procédure principale. Elle commence par compter les lignes du fichier pour en déduire la taille du répertoire : en effet, les vecteurs qui vont nous servir à enregistrer les noms et les numéros de téléphone sont de type rigide, comme exposé ci-dessus, il nous faut donc connaître leur taille à l’avance pour les créer, il ne sera plus possible de les agrandir ensuite. Puis elle invoque la procédure de construction de l’annuaire proprement dit dans deux vecteurs noms et tels, et enfin appelle la procédure qui demande à l’utilisateur d’entrer le nom recherché, soumis à la procédure de recherche dans l’annuaire :

Voici la procédure pour compter les lignes du fichier qui contient le répertoire (ici nous avons deux lignes par entrée dans le répertoire) :

Il nous faut d’abord charger le fichier en mémoire sous une forme propre à faciliter sa consultation ultérieure :

La procédure de recherche d’un nom dans le répertoire :

Pour faire de ces programmes un module compilable il faut ajouter le fichier suivant :

On compilera et on exécutera ce programme par les commandes suivantes :

$ bigloo repertoire-main.scm -o repertoire $ ./repertoire repertoire.txt

 Chapitre 12 - Des lettres au hasard

Des lettres au hasard :

 Chapitre 18 - Additioneur binaire

Additioneur binaire :

 Chapitre 20 - Recherche dans un répertoire

 Recherche dichotomique dans un répertoire

Nous nous proposons d’informatiser la consultation de notre répertoire téléphonique, enregistré comme ci-dessus (pour le chapitre 11) dans un fichier.

Le répertoire, avec recherche dichotomique :

Voici la procédure pour compter les lignes du fichier qui contient le répertoire (ici nous avons deux lignes par entrée dans le répertoire) :

Il nous faut d’abord charger le fichier en mémoire sous une forme propre à faciliter sa consultation ultérieure :

Voici un programme de recherche dichotomique, plus efficace que celui du chapitre 11 :

Pour faire de ces programmes un module compilable il faut ajouter le fichier suivant :

On compilera et on exécutera ce programme par les commandes suivantes :

$ bigloo repertoire-dichot-main.scm -o repertoire-dichot $ ./repertoire repertoire.txt

 Recherche dans un répertoire, avec adressage associatif

Le programme de répertoire, compilé, avec adressage associatif (hash table). Voici le fichier principal repertoire-hash-main.scm :

Voici la procédure pour compter les lignes du fichier qui contient le répertoire (ici nous avons deux lignes par entrée dans le répertoire) :

La fonction d’association :

 Zéro d’une fonction

 Chapitre 21 - Tri par sélection et par fusion

 Tri par sélection

Le principe du tri par sélection est le suivant : on met en bonne position l’élément numéro 1, c’est-à-dire le plus petit. Puis en met en bonne position l’élément suivant. Et ainsi de suite jusqu’au dernier. Par exemple, si l’on part d’un tableau dans l’état suivant :

On commence par rechercher, parmi les 12 valeurs, quel est le plus petit élément, et où il se trouve. On l’identifie en quatrième position (c’est le nombre 3), et on l’échange alors avec le premier élément (le nombre 45). Le tableau devient ainsi :

On recommence à chercher le plus petit élément, mais cette fois, seulement à partir du deuxième (puisque le premier est maintenant correct, on n’y touche plus). On le trouve en troisième position (c’est le nombre 12). On échange donc le deuxième avec le troisième :

On recommence à chercher le plus petit élément à partir du troisième (puisque les deux premiers sont maintenant bien placés), et on le place correctement, en l’échangeant, ce qui donnera in fine :

Nous aurons besoin d’un algorithme pour déterminer l’indice du plus petit élément d’un vecteur, à partir d’un certain indice i :

Algo : MinR Données : V un tableau indicé de 0 à L-1 i un indice compris entre 0 et L-1 Résultat : l'indice de la plus petite valeur de V entre i et L-1 imin <- i pour j allant de i+1 à L-1 faire si V[imin] > V[j] alors imin <- j finsi fait retourner(imin)

Voici l’algorithme de tri par sélection :

Algo : tri-select Donnée : vecteur V Résultat : V trié Soient i <- 0 L <- longueur(V) posmini <- 0 tant que i < longueur(V) ;; on calcule avec MinR l'indice posmini du plus ;; petit élément de V entre V[i] et V [L-1] posmini <- MinR(V, i) ;; Il ne reste plus qu'à effectuer la permutation. permute(V, i, posmini) ;; On a placé correctement l'élément numéro i, ;; on passe à présent au suivant. i <- i+1 fait retourner V fin

Soit en Scheme :

 Tri par fusion

Tri par fusion, récursif :