Introduction à la programmation : Les bases du langage Racket (1)

J’ai toujours rêvé que mon ordinateur soit aussi simple à utiliser que mon téléphone. Ce rêve est devenu réalité : je ne comprends plus comment utiliser mon téléphone — Bjarne Stroustrup, Créateur du langage C++.

L’informaticien, c’est le gars qui fait faire par un ordinateur les tâches qu’il ne sait pas faire lui-même.
Le développeur, c’est le gars qui explique à l’ordinateur ce que l’informaticien ne sait pas faire…
Mais alors, l’ordinateur, c’est un moyen de communication entre un informaticien et un développeur…
— Anonyme.

 

Nous faisons un détour pour faire un peu de programmation. Le but de ce détour est de vous permettre de digérer ce que nous avons vu dans la première partie de l’Arithmétique et d’apprendre les bases du langage Racket. Programmer, c’est en quelque sorte calculer suivant un ordre déterminé et précis. On dit aussi computer et un synonyme de programmation est computation. Nous avons déjà appris ce qu’est un langage de programmation et son rôle. Je ne vais donc pas revenir sur ce sujet, je vais juste répondre à une question que nombre d’entre vous se posent certainement, savoir pourquoi j’ai choisi le langage Racket parmi tant de langages existants.

Sur l’origine du langage Racket

En effet, j’aurais pu choisir le langage Python, qui est l’un des langages les plus utilisés — sinon le langage le plus utilisé — aujourd’hui, car il est facile à prendre en main par les débutants, il a une grande communauté et c’est un langage qui sert vraiment à tout faire. Et surtout, c’est le langage que j’utilise quotidiennement dans mes travaux de recherche. Mais, je ne l’ai pas choisi pour cette épopée car sa syntaxe un peu sophistiquée — quoique plus simple que celle de certains langages très utilisés — pourrait rebuter certains débutants. Je profite de l’occasion pour dire que la syntaxe d’un langage de programmation est la manière dont les idées sont représentées dans ce langage. Cette définition est évidemment très simplifiée mais elle nous convient parfaitement.

D’un autre côté, j’aurais pu également choisir le langage C, qui est aussi l’un des langages les plus utilisés. Selon le classement 2017 de l’IEEE (Institute of Electrical and Electronics Engineers, la plus grande association mondiale de professionnels techniques), le langage C vient en seconde position après Python (voir image ci-après). Mais, je ne choisis pas ce langage car, étant un langage compilé, son cycle de développement est relativement long et donc non adapté aux débutants. Sans entrer dans des détails trop techniques, voyez un langage compilé comme un langage dans lequel les programmes écrits ne peuvent pas être exécutés immédiatement pour observer les résultats : une étape de compilation — qui est d’autant plus longue que le programme l’est — est nécessaire avant de voir les résultats. Le problème c’est qu’à chaque petite modification du code, il faut compiler de nouveau le programme. Les langages interprétés (comme Python, JavaScript, etc.), en revanche, ne requièrent pas d’étape de compilation. Le programme est immédiatement exécuté et affiché.

Classement des 10 meilleurs langages de programmation de l’année 2017 (colonne de gauche) en comparaison au classement de 2016 (colonne de droite)
Classement des 10 meilleurs langages de programmation de l’année 2017 (colonne de gauche) en comparaison au classement de 2016 (colonne de droite) (Source : Developpez.com)

Il ne faut toutefois pas voir la compilation comme une limitation. Les langages compilés sont généralement plus rapides que les langages interprétés. Mais, puisque notre but est d’apprendre la programmation sans être distrait pas des artifices du langage, le langage C n’est pas un bon choix.

Alors, pourquoi j’ai choisi Racket ? Racket est un langage de la famille des langages LISP (LISt Processor). LISP a été développé dans les années 50 par un informaticien et mathématicien du MIT (Massachusetts Institute of Technology, l’une des meilleures écoles des États-Unis), John McCarthy (l’un des pères de la branche de l’informatique appelée Intelligence Artificielle). Il s’est basé sur la thèse de doctorat du logicien Alonzo Church, portant sur le lambda-calcul (c’est de là que vient le symbole grec lambda (\(\mathbf{\lambda}\)) du logo de blogdescodeurs et de celui de Racket). LISP est de la même génération que des langages comme FORTRAN et ALGOL60, mais LISP trouve ses fondements même dans les maths car conçu par un mathématicien. Il permet donc de représenter plus naturellement les idées mathématiques que n’importe quel autre langage. Et comme le pense la plupart des utilisateurs de LISP, c’est certainement le meilleur langage de programmation. Du moins, pour celui qui est soucieux de représenter directement et aisément ses idées mathématiques en code exécutable par l’ordinateur. Eric Raymond, un célèbre hacker (dans le sens de programmeur de génie) dit ceci de LISP : “Lisp vaut la peine d’être appris pour une raison différente — l’expérience profonde de l’illumination que vous aurez quand vous l’aurez compris. Cette expérience fera de vous un meilleur programmeur pour le reste de vos jours, même si vous n’utilisez jamais vraiment Lisp lui-même.

Je dis que Racket fait partie de la famille des langages LISP car après le premier LISP créé par McCarthy, plusieurs arômes (flavors, en anglais) de LISP ont été créés. On peut citer entre autres MacLisp, EuLisp, ZetaLisp, Scheme, etc. Chacun de ces langages a ses spécificités, mais ils sont tous des LISP. Afin de ramener tous ces arômes à un seul, un langage commun a vu le jour : Common LISP. Ce langage est considéré comme le standard des langages LISP. Toutefois, d’un autre côté, le développement de Scheme a continué. La particularité de ce dernier est qu’il est vraiment un langage plus petit, donc adapté à l”enseignement. De ce fait, Scheme est le langage généralement utilisé pour enseigner l’informatique dans les meilleures écoles des États-Unis. Racket est né de Scheme : c’est un arôme de Scheme. Ses créateurs l’ont développé en ayant en tête les collégiens. Ils voulaient un langage qui leur permettraient d’enseigner plus facilement l’Algèbre à leurs élèves. C’est exactement à ce même dessein que j’ai choisi Racket.

Une des particularités des langages LISP est qu’ils sont dépourvus de syntaxe. Par là je veux dire que toutes les idées sont représentées d’une seule manière. Du coup, les utilisateurs du langage se concentrent sur les idées plutôt que sur les règles syntaxiques.
Cependant, il ne faut pas croire que les langages LISP ne sont pas compilés. Au départ oui, LISP était un langage interprété, mais à la longue, les hackers ont développés de puissants compilateurs pour LISP. Donc, aujourd’hui, les logiciels qui permettent de programmer en LISP (tel que DrRacket), embarque un interpréteur et un compilateur. Mais, la compilation se fait de manière transparente pour l’utilisateur, de sorte qu’il a l’impression que son code est seulement interprété. Voilà toute la magie de LISP ! 🙂

Des concepts de base de la programmation

Avant d’étudier Racket, voyons ici les concepts de base de la programmation. Ces concepts sont fondamentaux, ils ne dépendent donc pas d’un langage spécifique quoiqu’ils peuvent avoir des significations un peu différentes d’un langage à l’autre. Commençons par le concept de variable.

Le concept de variable

En programmation, une variable désigne une information qui est susceptible de changer au fil du temps. Elle est représentée par un identificateur qui est généralement une suite de caractères. Par exemple, l’identificateur poids peut être utilisé pour désigner ma pesanteur 59 (kilogrammes), qui est une variable. Cette variable peut devenir 60 (kilogrammes) si je pèse, plus tard, une unité de plus. Les caractères que peuvent contenir un identificateur dépendent vraiment du langage.

Une variable a donc deux caractéristiques :

  • Son identificateur : Tout comme chacun de vous a un prénom spécifique qui lui permet de se différencier des autres membres de sa famille ou tout comme lorsque vous vous inscrivez sur ce blog, on vous demande un nom d’utilisateur qui doit être unique — différent de celui des autres membres –, chaque variable a un identificateur unique qui permet de la distinguer des autres variables.
  • Sa valeur : La valeur de la variable prénom qui m’identifie est Le Messie, comme vous devez bien le savoir maintenant. Une variable a donc une valeur : on dit aussi qu’elle est associée ou liée à une valeur.
    Certains langages, comme le C, le C++ ou le Java, exigent qu’on associe une valeur à une variable dès sa création. D’autres langages comme ceux de la famille LISP permettent de créer une variable en spécifiant son identificateur seulement. Mais, avant que d’utiliser cette variable dans une quelconque opération, elle doit être liée à une valeur.

Il se peut qu’une variable ne change jamais : on appelle ce genre de variables des variables constantes ou tout simplement des constantes. Les constantes sont généralement définies par convention. Par exemple, le nombre pi, que nous verrons en maths, vaut 3.14 à un centième d’unité près. Ce nombre est déjà défini dans la plupart des langages, il ne peut donc pas être modifié. Il existe un grand nombre de constantes en sciences physiques, mais celles-ci ne sont pas déjà définies dans les langages.

Le concept de type et de structure de données

Au concept de variable, on associe celui de type. Le type d’une variable est la nature (ou le genre) de cette variable. J’aurais pu considérer le type comme une caractéristique de la variable donc l’ajouter dans la section précédente. Mais je ne l’ai pas fait pour deux raisons. La première est que selon le langage, le sens concret du concept de type varie. Certains langages semblent l’associer à l’identificateur de la variable, d’autres (comme les langages LISP) l’associent à la valeur de la variable. Aussi, dans la suite, quand je parlerai de type d’une variable, entendez que je parle du type de la valeur de cette variable. La seconde est que le concept de type est très important donc il doit être traité séparément.

On distingue deux catégories de type de donnée :

  • Les types concrets : J’appelle types concrets les types qui sont évidents par la nature même des données. Par exemple le nombre 12 est un entier, le nombre \(\frac{2}{3}\) est une fraction, le nombre 8.235 est une fraction décimale, ‘C’ est une lettre de l’alphabet ou caractère, ‘Le Messie’ est un assemblage de caractères ou chaîne de caractères
    En programmation, selon les langages, on a les types suivants : entier (integer, en anglais), le type rationnel (rational, en anglais. Il s’agit des nombres fractionnaires), les types flottant et double (float et double, en anglais. Il s’agit des nombres irrationnels en simple et double approximation), le type caractère (character ou char, en anglais), le type chaîne de caractères (string, en anglais).
    Les types que je viens de citer sont les plus primitifs, mais chaque langage en spécifie plein d’autres similaires. Par exemple, on peut avoir plusieurs types d’entier et de flottant.
  • Les types abstraits : Ces types ne sont pas évidents en soi : ils ne sont pas primitifs. Ils sont conçus à partir d’une spécification (ensemble d’exigences ou caractéristiques à respecter lors d’une conception) mathématique d’un ensemble de données et des opérations qu’on peut effectuer sur elles. Chaque langage implémente (traduit en langage de programmation) ces types à sa manière, en suivant la spécification. Pour ce faire, les programmeurs, qui implémentent le type abstrait, disposent les données de manière que les opérations qu’on effectuera sur elles soient rapides. Cette implémentation concrète du type abstrait est appelée structure de données.
    Les types abstraits les plus courants sont : les listes (type primitif pour LISP), les arbres binaires, les ensembles, les dictionnaires ou tableaux associatifs (hash table, en anglais), les files et les piles.

Même si les types concrets sont primitifs à tous les langages, ils sont également implémentés à partir d’une spécification. Après tout, on implémente tout en programmation. La seule différence c’est que l’implémentation des types concrets est généralement réalisée par les concepteurs du langage de programmation, alors que l’implémentation des types abstraits est le plus souvent réalisée par les utilisateurs du langage. On voit ici la distinction entre concepteurs d’un langage et utilisateurs de ce langage. Vous et moi sommes des utilisateurs du langage Racket. Nous pouvons donc implémenter un type abstrait qu’on utilisera spécialement dans notre épopée. Mais les types entiers, flottants, etc., nous sont déjà donnés par les concepteurs de Racket.

Il faut noter que le type rationnel n’est primitif que dans certains langages haut niveau, comme Python et les LISP. Il n’est pas primitif en C. Celui donc qui veut l’utiliser en C devra l’implémenter. Quoique ce type soit déjà implémenté en Racket, nous nous amuserons à écrire notre propre implémentation, dans un but pédagogique.

Bien que ce soit hors-sujet, il convient que je donne ici la classification des langages de programmation selon leur niveau d’abstraction.  On distingue :

  • Les langages très bas niveau : Ce sont des langages dont la syntaxe et les opérations se rapprochent de la machine. Par exemple, puisque l’une des opérations de base de l’ordinateur est l’addition, pour faire l’opération \(5 + 5 + 5 + 5 + 5 + 5 + 5\), ces langages se contenteraient d’utiliser l’addition plutôt que d’implémenter l’opération de multiplication. Alors que nous sommes bien d’accord que la multiplication réduirait l’opération à \(5 \times 7\).
    Ces langages dépendent du type de processeur utilisé par l’ordinateur. Du coup, un programme qui fonctionne bien sur une machine devra être réécrit pour fonctionner sur une autre machine. On dit que le programme n’est pas portable sur différentes machines. L’Assembleur est un langage très bas niveau.
  • Les langages bas niveau : Ces langages sont une octave plus abstraite que les langages très bas niveau. Leur syntaxe est plus proche de celle des langues humaines. Ces langages implémenteraient l’opération de multiplication dont on a précédemment parlé. Mais, ce sont des langages relativement proches de la machine car ils donnent la possibilité aux utilisateurs de manipuler directement la mémoire.
    C est un langage bas niveau.
  • Les langages haut niveau : Ces langages sont vraiment très proches des langues humaines. Elles implémentent — et permettent d’implémenter — des opérations quelques octaves supérieures aux opérations des langages bas niveau.
    Python, C++, JavaScript, Java, R sont des langages haut niveau.
  • Les langages très haut niveau : Je ne crois pas que cette catégorie soit commune, je l’ajoute en connaissance de cause. Ces langages permettent d’implémenter des idées plusieurs octaves plus abstraites que ces des langages haut niveau. Ils permettent aux utilisateurs d’implémenter des opérations du même niveau que les opérations abstraites développées par les concepteurs. En un mot, ils permettent d’exprimer les idées presque dans toutes les octaves que l’utilisateur peut imaginer. L’imagination est donc la limite.
    Les langages LISP sont des langages très haut niveau.

Notez que plus les langages sont abstraits et moins ils sont efficients (rapides). C’est le prix à payer pour l’abstraction. Mais ce prix est nécessaire à payer lorsque nous privilégions l’expressivité à la rapidité. Pour qu’un langage très haut niveau soit aussi rapide qu’un langage bas niveau, il lui faut un puissant compilateur. C’est le cas pour LISP dont les codes peuvent s’exécuter aussi rapidement que les codes en C.

Continuons notre classification des langages, cette fois selon l’usage du concept de type. On a :

  • Les langages statiquement (ou fortement) typés : On voit clairement apparaître le type de chaque variable dans la syntaxe de ces langages. Et une fois que le type est assigné, la variable ne peut plus changer de type. C, C++ et Java sont des langages de ce type.
  • Les langages dynamiquement (ou faiblement) typés : Dans ces langages, on ne déclare pas explicitement le type de la variable. On laisse le soin à l’interpréteur ou au compilateur de le deviner.

Syntaxe et sémantique d’un langage

Je ne compte pas faire un cours de grammaire. Il s’agit de juste vous montrer la différence principale qui existe entre ces deux concepts.

La syntaxe d’un langage définit les règles de représentation des idées dans ce langage. Par exemple, en français une proposition est une expression composée (à quelques variations près) d’un sujet suivi d’un verbe suivi d’un attribut (ou complément) :

Proposition = Sujet + Verbe + Attribut

Ceci est la syntaxe d’une proposition. Ainsi, en français, les propositions suivantes sont syntaxiquement correctes :

Je vais à l’école : “Je” est le sujet, “vais” est le verbe, “à l’école” est le complément.
La voiture est de couleur rouge : “La voiture” est le sujet, “est” est le verbe et “de couleur rouge” est le complément.

En revanche, les expressions suivantes ne sont pas des propositions :

Manges ! : Il n’y a ni sujet ni complément.
La voiture : Il n’y a ni verbe ni complément.

La sémantique est concernée par le sens d’une expression et non par sa syntaxe. En effet, une proposition peut être syntaxiquement correcte mais être sémantiquement incorrecte, c’est-à-dire n’avoir aucun sens dans le langage. Considérons la proposition suivante :

Le pain mange la souris: “Le pain” est le sujet, “mange” est le verbe et “la souris” est le complément.

Même si la proposition ci-dessus est syntaxiquement correcte, elle n’a vraiment aucun sens. Un pain ne peut manger une souris. C’est plutôt le contraire qui est possible. On dit donc que la proposition est sémantiquement incorrecte.

Les langages de programmation ont également ces notions de syntaxe et de sémantique. Certains langages ont vraiment de nombreuses règles de syntaxe : chaque grande idée a une syntaxe spécifique. Ce qui fait que ces langages sont difficiles à maîtriser. Du moins, quand il s’agit de syntaxe. LISP se distingue par la simplicité de sa syntaxe, au point même qu’on dit qu’il n’a pas de syntaxe. Pour ce qui est de la sémantique, elle relève du bon sens comme dans nos langues humaines. Tout comme nous ne pouvons pas dire que le pain mange la souris, nous ne pouvons pas faire :

“Jean” + “Jean” + “Jean”

Où le symbole \(+\) représente l’opération arithmétique. Cette opération est sémantiquement incorrecte car l’addition arithmétique ne s’applique qu’aux nombres.

Il y a une foule d’autres concepts mais ceux-là sont les plus importants pour nous à ce stade. Au fil de notre évolution, nous introduirons de nouveaux concepts.

Des bases de la programmation Racket

Prise en main de DrRacket

L’interface de DrRacket

Je suppose que vous avez déjà installé DrRacket sur votre PC ou un équivalent sur votre smartphone. Ceux qui ne l’ont pas encore fait peuvent voir le cours ici.

Nous allons voir les différentes parties de l’interface de DrRacket qui se présente à vous quand vous l’ouvrez. Considérons l’image ci-dessous où j’ai numéroté ces parties.

Les principales parties de l'interface de DrRacket
Les principales parties de l’interface de DrRacket
  1. La zone de définition. C’est dans cette zone qu’on écrit les programmes dans le but de pouvoir l’enregistrer, plus tard, dans un fichier.
  2. La zone d’interaction : Dans cette zone, on peut directement exécuter soit du code qu’on y entre, soit du code se trouvant dans la zone de définition. C’est une sorte d’interpréteur qui nous renvoie une résultat à chaque requête. C’est la zone dans laquelle vous passerez plus de temps pour tester vos programmes avant de les certifier corrects et les enregistrer.
  3. Le menu de sélection du langage : Ce menu permet de sélectionner un type de langage. DrRacket intègre trois grandes catégories de langage :
    1. Le langage Racket : C’est Racket dans toute sa totalité.
    2. Les langages d’enseignement : C’est Racket scindé en plusieurs niveaux (étudiant débutant, étudiant intermédiaire, étudiant avancé, …). Ces langages sont adaptés à l’enseignement. Le niveau débutant ne contient que les opérations nécessaires au débutants, il est donc plus léger que le langage intermédiaire ou avancé.
    3. Les autres langages : Il s’agit d’autres langages que DrRacket supporte, tels que Algol 60, FrTime, etc.
  4. Les boutons Exécuter (Run) et Arrêter (Stop) : Ces boutons permettent de contrôler l’exécution d’un programme. Si vous avez écrit du code que vous voulez exécuter, vous n’avez qu’à cliquer sur le bouton Exécuter. Si le programme est en cours d’exécution et que vous souhaitez l’arrêter, vous cliquez sur le bouton Arrêter.
  5. Le nom du fichier actuel : Lorsqu’on a écrit du code dans la zone de définition, que nous en sommes contents et que nous voulons l’enregistrer pour pouvoir le réutiliser plus tard, on l’enregistre dans un fichier. Un fichier est juste un ensemble d’informations qu’on stocke quelque part sur la mémoire de masse de l’ordinateur (le disque dur en général). Un fichier a un nom et une taille. Après avoir enregistré le fichier, son nom s’affiche dans les deux zones représentées par le numéro 5. Actuellement, il est indiqué “Untitled”, ce qui signifie “Sans titre”. C’est ce que vous voyez lorsque vous lancer DrRacket sans avoir ouvrir un fichier. On voit sur la figure ci-dessous que le fichier ouvert s’appelle “arithmetique.rkt”. Notez que le suffixe “rkt” s’appelle extension du fichier. C’est un concept de Microsoft Windows qui lui permet de distinguer les fichiers et de décider le logiciel par défaut qui permet d’ouvrir ce fichier. Aussi, par défaut les fichiers d’extension rkt seront ouverts par Racket.
  6. La liste des définitions : Cette liste contient toutes les définitions de la zone de définitions. Si le fichier contient un grand nombre de définitions n’apparaîtront pas dans la partie visible de la zone de définition. Il faudra donc utiliser la barre de défilement pour voir les autres définitions. La liste des définitions vous permet d’accéder directement à la définition que vous voulez voir, quelque soit sa position et sans avoir à défiler (Voir figure ci-dessous).
  7. La barre des menus : Presque tous les logiciels ont une barre des menus, DrRacket n’est pas une exception. Ce sont des menus déroulants qui contiennent des options. Cette barre contient les menus suivants :
    1. File (Fichier) : Ce menu contient les options générales d’ouverture de fichier, de création d’un nouveau fichier, d’enregistrement de fichier, de réglages de la page et surtout une option pour quitter DrRacket. Les options que vous utiliserez le plus sont certainement New (Nouveau) qui permet de créer un nouveau fichier, Save Definitions (Enregistrer les Définitions) pour enregistrer les définitions dans un fichier, et Open (Ouvrir) qui permet d’ouvrir un fichier existant sur une mémoire de masse.
      Remarquez qu’il y a Ctrl + N à côté du menu New : c’est un raccourci qui vous permet d’effectuer la même opération en appuyant et en maintenant la touche Ctrl (du clavier) et en appuyant la touche N. On peut donc utiliser les raccourcis en lieu et place du déplacement dans la barre de menu.
    2. Edition (Édition) : On trouve dans ce menu, les opérations générales de traitement de texte, telles que l’annulation d’une saisie, la copie d’un texte, le collage d’un texte, la sélection de tout le texte, etc. Il y aussi une option pour définir les préférences du logiciel.
    3. View (Affichage) : On règle ici les paramètres d’affichage du texte et aussi de certains parties de l’interface. Par exemple, l’option Hide Definitions (Cacher les Définitions) permet de cacher la zone de définition.
    4. Language (Langage) : Pareil que le menu 3.
    5. Racket : On trouve dans ce menu, quelques options pour contrôler l’exécution des programmes. On y retrouve par exemple les boutons Exécuter et Arrêter, vus précédemment.
    6. Insert (Insérer) : Ce menu comprend des options pour insérer certains types de données dans le code, telles que les images, les zones de texte, les fractions, etc.
    7. Tabs (Onglets) : Ce menu permet de gérer les onglets ouverts. Les onglets sont de nouvelles fenêtres qu’on ouvre dans une même fenêtre, ils sont tous contenus dans cette fenêtres. Si vous avez déjà une fenêtre ouverte, le fait d’ouvrir une nouvelle fenêtre fera que vous vous retrouverez avec deux fenêtres distinctes. On pourra fermer une de ces fenêtres sans, toutefois, fermer à l’autre. Mais le fait de créer un nouvel onglet, crée une nouvelle fenêtre mais celle-ci n’est pas indépendante de la première. Si on ferme la première, la seconde se voit fermer (Voir figure ci-dessous).
    8. Help (Aide) : Via ce menu, vous pourrez consulter la documentation (doc) de Racket (Pas besoin d’internet), chercher des mises à jour de Racket, changer la langue de l’interface (ma version est en anglais mais vous pourrez transformer votre interface en français), etc. Vous vous référerez très souvent à la doc donc jetez-y un œil !
Interface détaillée de DrRacket
Interface détaillée de DrRacket

Il y a quelques éléments de l’interface de DrRacket que je n’ai pas mentionnés. Nous en parlerons au moment opportun.

Pour pouvoir maîtriser l’interface de DrRacket, il ne suffit pas juste de lire et de bosser par cœur ma description, vous devez interagir avec lui afin d’en faire votre ami. Nous passerons tellement de temps avec lui qu’il est vraiment important que vous le preniez en main. Si possible, rêvez en DrRacket 😆

Interaction avec DrRacket

Pour tout ce qui suit, nous utiliserons le langage Racket dans DrRacket (et non un des langages d’enseignement). Veillez donc à le sélectionner (c’est la première option des options de sélection du langage). C’est impératif si vous voulez obtenir les mêmes résultats que moi et surtout si vous voulez pouvoir exécuter tous les codes de ce chapitre. Après avoir sélectionné le langage, cliquez sur Run (ou Exécuter) pour que DrRacket. Vous saurez que le langage Racket a été sélectionné si dans la zone de définition, il apparaît la déclaration suivante :

#lang racket

Cette déclaration indique à DrRacket que le langage que le REPL (ou le compilateur) doit considérer est Racket en entier. Lorsque vous voudrez ajouter du code dans la zone de définition, placez-le juste en bas de cette déclaration.

Nous allons voir ici ce que c’est qu’interagir avec DrRacket. Dans la zone d’interaction de DrRacket, après le message de bienvenue et d’autres textes, vous avez le symbole chevron droit (>). Lorsque vous cliquez à droite de ce chevron, le curseur se met à clignoter. C’est DrRacket vous disant qu’il attend que vous lui demander de faire quelque travail. Saisissez par exemple l’opération suivante et appuyez sur la touche Entrée :

>  (+ 1 2 3 4 5 6 7)
\(=>\)  28
>

Vous venez de demander à DrRacket de vous calculer la somme des sept premiers entiers naturels. Lorsque vous appuyer sur Entrée, DrRacket, n’attendant que ça, lis les instructions (l’addition dans cet exemple), les évalue (ou les traite), affiche le résultat et vous demande encore du travail. Vous devez obtenir 28 comme résultat. Le symbole \(=>\) est là juste pour indiquer le résultat, il n’apparaîtra pas dans DrRacket. Autant de fois que vous donnerez des opérations valides à DrRacket, il fera la même chose et vous en demandera encore. Quel infatigable ce DrRacket ! 😆

Ce cycle (ou boucle) de lecture, évaluation et affichage que réalise DrRacket est ce que les anciens Lispers (même les nouveaux) appellent Read-Eval-Print-Loop (ou REPL). Ça donne textuellement en français : Lire-Évaluer-Afficher-Boucle. C’est un interpréteur de Racket. Cette facilité d’interaction est l’un des avantages des langages qui ont la capacité d’être interprétés.

Continuez d’interagir avec DrRacket en lui donnant les opérations suivantes :

>  (+ 1 2 (* 3 4))
\(=>\)  15
>  (sqr 5)
\(=>\)  25
>  (sqrt 9)
\(=>\)  3
>

Dans la première opération, vous demandez au REPL de DrRacket de d’abord faire le produit de 3 par 4 et ensuite d’ajouter 1 et 2. Dans la seconde, vous lui demandez de calculer le carré de 5 (sqr vient de square, qui signifie carré en anglais). Et dans la dernière, vous lui demandez de calculer la racine carrée de 9 (sqrt vient de square root, qui signifie racine carrée en anglais). Dans la suite, je vais supprimer le dernier chevron du REPL mais retenez qu’il sera toujours là tant que vous ne lui faites rien de mal.

Si le chevron du REPL tarde à s’afficher de nouveau, dans la zone d’interaction, après lui avoir demandé d’effectuer une opération, il y a deux cas : soit l’opération est vraiment longue donc ça demande du temps au REPL, soit l’opération contient ce qu’on appelle une boucle infinie. Dans le premier cas, soyez patients jusqu’à ce que le REPL finisse le travail. Dans le second cas, il ne finira jamais, vous devrez donc l’arrêter en appuyant le bouton Arrêter. Souvent, il est difficile de savoir dans quel cas on se trouve, on a donc pas d’autre choix que d’arrêter l’exécution du programme.

Considérons maintenant que nous sommes satisfaits de notre interaction avec le REPL et que nous voulons sauvegarder (enregistrer) les opérations que nous venons de faire, pour pouvoir les réutiliser plus tard. Il suffit de copier chaque opération depuis la zone d’interaction (sans les chevrons et les résultats, évidemment) et de la coller dans la zone de définition.

Quelques opérations dans la zone de définitions de DrRacket.
Quelques opérations dans la zone de définitions de DrRacket.

Actuellement, la fenêtre est intitulé “Untitled 4”, ce qui signifie que je n’ai jamais enregistré le fichier. Toujours dans ce titre, notez aussi le symbole astérisque (*) qui se trouve à droite du mot DrRacket. Ce symbole apparaîtra chaque fois que le fichier a été modifié après sa dernière sauvegarde. Sauvegardons maintenant notre programme. Allez dans la barre des menus et faites File, ensuite Save Definitions (File > Save Definitions) ou utilisez tout simplement le raccourci Ctrl + S. La boîte de dialogue suivante s’affiche :

Enregistrer un fichier sous DrRacket
Enregistrer un fichier sous DrRacket

Dans la zone Nom du fichier, mettez un nom que vous voulez (de préférence sans espace ni caractère spécial comme les accents). Je lui donne le nom operations. Dans la zone Type, Racket Sources est sélectionné par défaut. Choisissez aussi le dossier où vous voulez le fichier. Il est préférable de créer un dossier pour vos codes Racket : dans mon cas, c’est le dossier racket-prj situé dans le dossier Mes Documents. Une fois cela fait, cliquez sur le bouton Enregistrer pour sauvegarder le fichier et un fichier operations.rkt sera créé. Sur la figure précédente, vous pouvez voir que j’ai déjà quelques fichiers créés. L’apparence de ces fichiers est appelée leur icône. Sous Windows, le logo de Racket apparaîtra sur l’icône (Voir figure ci-dessous) pour indiquer que c’est un fichier Racket et donc si vous double-cliquez sur ce fichier depuis le dossier où vous l’avez enregistré, il sera ouvert avec DrRacket. Cela est possible à cause de l’extension rkt associé au nom du fichier. Sous Linux, le logo n’apparaîtra pas parce que l’extension n’a aucun sens pour ce système d’exploitation. Les utilisateurs avancés de Linux sauront comment exécuter un fichier Racket via le terminal.

Icône d'un fichier Racket sous Windows
Icône d’un fichier Racket sous Windows

Après avoir enregistré le fichier, voici ce qu’on obtient :

Titre de la fenêtre DrRacket après enregistrement d'un fichier
Titre de la fenêtre DrRacket après enregistrement d’un fichier

Remarquez bien que la fenêtre est maintenant intitulée “operations.rkt” et que l’astérisque a disparu. Dès que vous modifierez le fichier dans la zone de définition, astérisque réapparaîtra pour vous indiquer que le fichier n’a pas encore été enregistré par sa dernière modification. Dès que vous avez enregistré le fichier une fois, toutes les autres fois où vous ferez Ctrl + S, le fichier sera automatiquement enregistré sans qu’une boîte de dialogue s’ouvre. On dit que l’enregistrement se fait silencieusement. C’est normal car vous n’avez plus à saisir un nom. Toutefois, il peu quelques fois être utile d’enregistrer le même fichier sous un autre nom. Dans ce cas, faites File > Save Definitions As (ou Fichier > Enregistrer Définitions Sous, en français), ou utilisez tout simplement le raccourci Ctrl + Shift + S.

La syntaxe de Racket

Nous avons vu que LISP est l’abréviation de LISt Processing. En français, ça signifie “traitement de listes“. En effet, les concepteurs de LISP ont voulu un langage qui serait uniforme quelque soit le type de construction qu’on peut vouloir faire avec. Ils ont donc choisi la structure de donnée, liste, pour à la fois représenter la donnée (qui se trouve en forme de liste) et tous les programmes LISP. Ainsi, un programme LISP n’est rien d’autre qu’une liste.

Voici à quoi ressemble une liste en LISP :

Une liste en LISP
Une liste en LISP

Une liste est une collection de données de tout type délimitée par des parenthèses. Les éléments de la liste sont normalement séparés par un espace. En LISP, une liste a deux modes : soit elle désigne une liste d’éléments quelconques qui constitue une donnée, soit elle désigne un programme LISP. Lorsqu’elle est dans le premier mode, ces éléments n’ont pas vraiment de sens. Et pour l’exécuter dans le REPL, il faut le précéder d’une apostrophe () (appelé communément quote). Par exemple :

>  ‘(1 2 4 5)
\(=>\) ‘(1 2 4 5)
>  ‘(“le chat” 2)
\(=>\) ‘(“le chat” 2)

Le REPL nous retourne la même liste que nous lui avons envoyé.

Lorsque la liste est dans le second mode, son premier élément est considéré comme une opération qui a un sens particulier pour LISP : ce peut être une fonction, une macro, une forme spéciale, une forme lambda (Nous les verrons plus tard). Par exemple :

>  (+ 1 2 (* 3 4))
\(=>\)  15
>  (sqr 5)
\(=>\)  25

À la différence du premier mode, le REPL considère chaque premier élément de la liste comme une opération spécifique et il se sert du code de cette opération pou retourner le résultat.

Notez que le REPL ignorera tous les espaces (lorsque vous appuyez plusieurs fois la touche Espace du clavier) et les retours à la ligne (lorsque vous appuyez plusieurs fois la touche Entrée du clavier) de trop que vous mettez entre les éléments de la liste. Par exemple :

>  '(1 2                 3                              4)
 
\(=>\)  '(1 2 3 4)

 

>  '(1 2
         

         3

                              



                                4)


 \(=>\)  '(1 2 3 4)

Convenez avec moi qu’il n’y a aucune raison de faire de la sorte en pratique. Il est toutefois souvent utile, lorsqu’on a une liste à plusieurs expressions importantes, de faire un retour à la ligne à la fin de chaque expression et d’ajouter quelques espaces au début de l’expression suivante. Voici un exemple :

>  (+ (* 1 2)
      (/ 2 3)
      (- 5 2))

Cette disposition particulière que nous donnons au code est appelée indentation du code. C’est très important pour améliorer la lisibilité du code. Sur ce petit exemple, vous ne voyez certainement pas l’avantage de l’indentation, mais ça devient manifeste quand le code est long. Aussi, je vous demande de veiller à ce que votre code soit bien indenté. DrRacket facilite votre en ajoutant automatiquement les espaces de gauche à chaque fois que vous appuyez sur la touche Entrée. Et croyez-moi, il le fait intelligemment bien. Tout ce que vous avez donc à faire, c’est d’aller à la ligne et DrRacket fera le reste.

Si vous essayez de donner au REPL une liste dont le premier élément n’est pas une opération qu’il connaît et que vous ne quotez pas la liste, le REPL ne sera pas content et vous retournera une erreur :

>  (1 2 3 4)
\(=>\)  function call: expected a function after the open parenthesis, but received 1

Ce message signifie que le REPL s’attendait à une fonction comme premier élément après la parenthèse ouvrante, mais il constate que c’est le symbole 1. Puisqu’aucune opération n’est enregistré sous ce nom, il ne peut rien faire donc il retourne une erreur (en couleur rouge).

Il est en effet possible de représenter tous les types de données sous forme de liste mais, pour être en conformité avec l’usage général, les types concrets sont représentés tels qu’ils le sont dans le langage d’où ils proviennent.

  • Les nombres : sont représentés par une suite de chiffres contenant éventuellement la virgule décimale. 1, 2, 25, 654447, 752.15 sont des nombres valides sous Racket.
  • Les fractions : sont représentés comme en maths, en séparant le numérateur et le dénominateur par le symbole slash (/). La ligne horizontale n’existe pas sur le clavier. Les fractions 1/2, 523/4545 et 111/25 sont valides sous Racket.
  • Les caractères : sont précédés par #\. Les caractères a, B, Z, e, “, # sont représentés en Racket par #\a, #\B, #\Z, #\e, #\” et #\# respectivement.
  • Les chaînes de caractères : sont délimités par le symbole double apostrophe (). Voici quelques chaînes de caractères : “Lisp est un langage puissant.”, “Ok ! mais Python est également bien”, “Ah bon ?”.

En plus de ces types concrets, voici deux autres types importants en Racket :

– Les booléens : sont utilisés pour représenter la valeur de vérité de certaines expressions. Ces expressions sont appelées propositions. Une proposition est soit vraie — représentée par #t ou #true — soit fausse — représentée par #f pu #false. Voici quelques exemples dans le REPL :

>  (odd? 2)
\(=>\)  #f
>  (even? 18)
\(=>\)  #t
>  (number? “Cool”)
\(=>\)  #f
>  #true
\(=>\)  #t
>  #f
\(=>\)  #f

odd?, even? et number? sont des fonctions qui testent si un nombre est impair, si un nombre est pair et si une donnée est un nombre, respectivement.

– Les symboles : un symbole est une chaîne de caractères non pas délimité par une double-quote mais précédé par une seule quote. Un symbole peut contenir presque tous les caractères sauf les espaces, les parenthèses et éventuellement d’autres caractères réservés par le langage Racket. Les symboles ‘blogdescodeurs, ‘deux-cents, ‘racine-carree?, ‘+, ‘/, ‘kilobit=>bit, sont valides en Racket.
Notez que les symboles sont sensibles à la casse (majuscule ou minuscule), c’est-à-dire que les symboles ‘blogdescodeurs, ‘BLOGDESCODEURS et ‘BlogDesCodeurs sont différents. Le REPL nous le prouve :

>  (symbol=? ‘blogdescodeurs ‘BLOGDESCODEURS)
\(=>\)  #f
>  (symbol=? ‘blogdescodeurs ‘BlogDesCodeurs )
\(=>\)  #f
>  (symbol=? ‘BlogDesCodeurs ‘BLOGDESCODEURS)
\(=>\)  #f

Si vous omettez le symbole quote, le REPL ne sera pas content, à moins que le symbole représente déjà quelque chose que vous avez préalablement défini dans le REPL ou défini dans Racket. Par exemple, le symbole pi représente la constante 3.14 (à un centième de l’unité). Puisque ce symbole et la valeur qu’il représente sont prédéfinis dans Racket, on peut évaluer pi dans le REPL sans qu’il ne se plaigne :

>  pi
\(=>\)  3.141592653589793

Le REPL nous retourne une approximation de pi à 15 chiffres après la virgule.

Une autre remarque importante est de ne pas confondre la chaîne de caractères “blogdescodeurs” et le symbole ‘blogdescodeurs. D’abord parce qu’ils sont de types différents donc représentés différemment. Enfin, parce qu’on les comprend différemment. La chaîne de caractères est une suite de caractères de type caractère, on peut extraire chaque caractère en utilisant des opérations définies pour les chaînes de caractères : on peut donc dire que le caractère #\g se trouve dans la chaîne “blogdescodeurs”. Cependant, même si visiblement, le symbole est également une suite de caractères, on considère que cette suite est indivisible (on dit que c’est un atome). Aucune opération nous ne nous permet d’en extraire les caractères : on ne peut donc pas dire que le caractère #\g se trouve dans ‘blogdescodeurs. Le symbole doit être vu comme un tout indivisible.
La principale utilisation des symboles en LISP est comme identificateur. Les symboles servent à nommer les quantités de tout type.

Puisque nous avons dit que LISP utilise la structure de liste pour représente la plupart de ses constructions, vous vous doutez qu’un programme peut comporter un grand nombre de listes imbriquées les unes dans les autres. En effet, ceux qui n’aiment pas LISP définissent son sigle par Lot of Infuriatingly Silly Parentheses, ce qui signifie en français : Lot de parenthèses ridiculement idiotes. Ils ont certainement raison sur ce point mais c’est ce qui rend LISP supérieur aux autres langages. Une remarque sur les parenthèses est que toute parenthèse ouverte doit être fermée et que les parenthèses ouvertes doivent être fermées dans le bon ordre. La première ouverte doit être la première fermée, ainsi de suite. Si cela n’est pas respecté, le REPL ne sera pas content. Dans le cas de DrRacket, le REPL attendra que vous fermiez toutes les parenthèses avant de lire l’expression. Vous n’avez donc pas à vous souciez de si oui ou non vous avez fermé une parenthèse : vous le saurez lorsque vous appuierez sur Entrée. Par exemple, si vous entrez ‘(1 (2 3 (4))), le REPL vous retournera bien cette liste car les trois parenthèses ouvrantes ont été bien fermées. Mais si vous entrez ‘(1 (2 3 (4) ou ‘(1 (2 3 (4) (, le REPL attendra que vous fermiez toutes les parenthèses avant de lire et évaluer votre expression.

Toutes les expressions qu’on peut légitimement donner à bouffer au REPL, sans qu’il ne plaigne, sont appelées formes : Les listes sous leurs deux modes sont des formes, les symboles définis sont des formes, les données de type concrets sont également des formes.

Les listes en Racket

Nous avons déjà globalement parlé des listes en LISP mais ce que nous avons vu n’est que la représentation visuelle des listes, c’est-à-dire ce que vous entrez dans le REPL ou qu’il vous affiche. Nous verrons ici un peu plus en détail la structure de liste : comment Racket l’implémente en mémoire.

Les opérateurs CAR et CDR

En effet, en Racket (comme dans la quasi-totalité des LISP), une liste est une structure de données composée de deux éléments : un pointeur sur le premier élément de la liste et un pointeur sur le reste des éléments. Un pointeur est une donnée qui stocke l’adresse mémoire d’une autre donnée. Rappelez-vous que nous avons dit dans notre cours sur le système informatique que toute donnée qui est stockée en mémoire a une adresse spécifique, et que cette adresse permet au processeur de manipuler la donnée. Une donnée à laquelle on associe la valeur de l’adresse d’une autre donnée est ce que nous appelons pointeur. Les pointeurs sont beaucoup utilisés en langage C pour manipuler la mémoire, c’est pourquoi on dit que c’est un langage bas niveau. En LISP, à part pour expliquer certains concepts, vous n’aurez jamais à manipuler les pointeurs, tout ceci a été abstrait par les concepteurs du langage afin que vous ne fassiez pas n’importe quoi à votre mémoire : oui ! c’est pas sans risque de manipuler directement sa mémoire.

Le pointeur sur le premier élément est historiquement appelé CAR et le pointeur sur le reste des éléments est appelé CDR. L’image ci-dessous montre comment l’on peut se représenter cela.

La structure de liste en Racket
La structure de liste en Racket

Notez qu’en mémoire, les adresses des éléments de la liste ne doivent pas nécessairement se suivre, c’est-à-dire que si le premier élément est à l’adresse 00000001, le second élément peut être à l’adresse 00110111 plutôt qu’à l’adresse 00000010. Ce sont les pointeurs CAR et CDR qui sont chargés de maintenir cet ordre apparent. Cette disposition des éléments en mémoire est appelé contiguïté. Dans le cas des listes, les éléments ne pas contigus en mémoire. Nous verrons plus tard des structures de données pour lesquels les éléments sont contigus en mémoire.

CAR et CDR sont des opérations qui nous permettent de récupérer le premier élément et le reste des éléments d’une liste, respectivement. CDR retourne nécessairement une liste. Voici quelques exemples :

>  (car ‘(5 “maths” 7 1/2))
\(=>\)  5
>  (cdr ‘(5 “maths” 7 1/2))
\(=>\)  ‘(“maths” 7 \(\frac{1}{2}\))

Et si on veut récupérer le second élément de la liste ? Eh bien ! il suffit de prendre le premier élément du reste des éléments de la liste obtenue par CDR. En d’autres termes, on doit faire un CAR du précédent CDR comme sur l’exemple ci-dessous :

>  (car (cdr ‘(5 “maths” 7 1/2)))
\(=>\)  “maths”

Comme vous pouvez le voir, on a juste chaîné les opérations : la première étant l’argument de la seconde. Le REPL évalue la première opération, c’est-à-dire (cdr ‘(5 “maths” 7 1/2)), et retourne (“maths” 7 0.5). Ce résultat est ensuite envoyé comme argument à la seconde opération, soit (car ‘(“maths” 7 0.5)), et retourne donc “maths”. Voici comment récupérer les autres éléments :

>  (car (cdr (cdr ‘(5 “maths” 7 1/2))))
\(=>\)  7
>  (car (cdr (cdr (cdr ‘(5 “maths” 7 1/2)))))
\(=>\) \(\frac{1}{2}\)

Ces opérations étant tellement courantes qu’il y a des raccourcis. Lorsqu’on a plus de deux opérations CAR et CDR chaînées, il y a une opération dont le nom commence par la lettre “c”, suivi d’autant de “a” ou “d” qu’il y a de CAR ou CDR (en allant de gauche à droite), et se termine par la lettre “r”. Par exemple, les deux opérations précédentes peuvent d’effectuer autrement comme suit :

>  (caddr ‘(5 “maths” 7 1/2))
\(=>\)  7
>  (cadddr ‘(5 “maths” 7 1/2))
\(=>\) \(\frac{1}{2}\)

Mais, à partir d’un chaînage de quatre CAR/CDR, il n’y a pas de raccourcis, et il est mieux d’utiliser d’autres opérations que nous verrons dans un prochain cours.

Que se passe-t-il si on demande au REPL de nous retourner le résultat de (cdr ‘(1/2)) ? Puisque la liste ‘(1/2) ne contient qu’un seul élément, le reste des éléments de cette liste est une liste qui ne contient aucun élément : c’est la liste vide ou liste nulle, notée ‘(). le REPL retournera donc ‘().

>  (cdr ‘(1/2))
\(=>\)  ‘()

Notez que les opérations CAR/CDR ne s’appliquent qu’aux listes ayant au moins un élément. Tenter de les appliquer à d’autres types de donnée ou à une liste vide retourne une erreur.

>  (car ‘())
\(=>\)  car: contract violation
expected: pair?
given: ‘()

>  (cdr 5)
\(=>\) cdr: contract violation
expected: pair?
given :5

Dans les deux cas, le REPL dit que CAR et CDR attendent une paire d’éléments comme argument mais ces opérations reçoivent autre chose. En effet, la paire dont il s’agit n’est rien d’autre que les deux pointeurs dont on a parlé plus haut.

Nous avons vu comment on récupère les éléments d’une liste, mais comment construit-on une liste à partir d’éléments donnés ? Bonne question ! Voyons comment on y arrive.

L’opérateur CONS

Nous avons donc au départ une liste vide ‘() et nous avons les éléments suivants : “banane”, ‘code, 125.2, #\F, #t. Nous voulons construire la liste ‘(“banane”, ‘code, 125.2, #\F, #t). Pour ce faire, Racket nous fournit l’opération CONS (construire) qui permet d’ajouter un élément comme premier élément d’une liste. Ainsi, (cons #t ‘()) donne ‘(#t), ensuite (cons #\F ‘(#t)) donne ‘(#\F #t), et ainsi de suite jusqu’à construire la liste entière. Il en ressort donc qu’il faut chaîner autant de CONS qu’il y a d’éléments à ajouter en tête de liste.

>  (cons “banane” (cons ‘code (cons 125.2 (cons #\F (cons #t ‘())))))
\(=>\) ‘ (“banane” ‘code 125.2 #\F #t)

Il existe plein d’autres opérations pour construire les listes mais CONS est le plus primitif. Nous verrons les autres dans la suite de notre apprentissage du langage.

Il convient que je fasse une remarque importante. Puisqu’une liste peut contenir des données de tout type, elle peut donc contenir d’autres listes et ces dernières en contenir d’autres, et ainsi de suite. Par exemple : ‘(1 (2 3) (4 (6))) et ‘((1 2) 3) sont des listes.

La représentation graphique des listes

Nous allons voir deux représentations graphiques de la structure de liste : la représentation sous forme de cases et la représentation sous forme d’arbre binaire.

– On peut représenter graphiquement une liste par un ensemble de cases rectangulaires, chaque case étant divisée en deux sous-rectangles (ou carrés) et toutes les cases sont reliés par des flèches dans un ordre spécifique. Le premier sous-rectangle contient le pointeur CAR et le second contient le pointeur CDR. Ces sous-rectangles sont historiquement appelés cons cells (cellules cons, en français). Comme nous l’avons précédemment, une liste n’est qu’une chaîne de cellules cons.

La figure suivante montre la représentation des listes ‘(“banane”, ‘code, 125.2, #\F, #t) et ‘(1 (2 3) (4 (6))) sous forme de cellules cons.

La représentation des listes sous forme de cellules CONS
La représentation des listes sous forme de cellules CONS

La représentation de la liste ‘(1 (2 3) (4 (6))) est beaucoup plus compliquée car cette liste contient de nombreuses sous-listes. Mais, ça reste facile quand on se rappelle bien que toute liste est une cellule cons. On remarque aussi que les données qui ne sont pas des listes ne sont pas représentées sous forme de cases et qu’à chaque fois qu’on rencontre ce genre de données, on s’arrête dans notre progression. On s’arrête aussi à la liste vide ‘(), car elle n’est pas non plus une cellule cons, au sens de Racket.

– Les listes peuvent également être représentées sous forme d’arbre binaire. Avant de donner la définition d’un arbre binaire, faisons une petite analogie avec les arbres que nous connaissons dans la nature. Un arbre est composé d’une racine, d’un tronc, de branches et de feuilles. Les branches sont comme des petits troncs et sont également composées de branches et de feuilles. La progression de l’arbre s’arrête aux feuilles.

Un arbre binaire est une structure de données qui est soit une donnée atomique (tout ce qui est indivisible) soit une paire dont chaque élément est lui-même un arbre binaire. Les feuilles de l’arbre binaire (ses atomes) sont appelés points terminaux, car c’est à ces points que se termine sa progression. Les points auxquels les branches se forment sont appelés nœuds.

Ici, ce n’est pas tant l’arbre binaire dans son sens de structure de données qui nous intéresse, mais c’est plutôt sa représentation graphique.  Voici comment on pourrait représenter nos deux listes précédentes, sous forme d’arbre :

Représentation d'une liste comme un arbre binaire
Représentation de la liste ‘(“banane” ‘code 125.2 #\F #t) comme un arbre binaire
Représentation d'une liste comme un arbre binaire
Représentation de la liste ‘(1 (2 3) (4 (6))) comme un arbre binaire

Comme vous pouvez le voir, cette représentation est nettement plus simple que la précédente. Elle est en effet plus abstraite, c’est pourquoi les listes vides intermédiaires n’apparaissent pas. Mais, c’est une représentation alternative valide des listes en Racket.

 

Nous voilà donc au terme de la première partie de ce chapitre sur les bases du langage Racket. Relisez ce cours plusieurs fois jusqu’à ce que vous maîtrisiez les différents concepts. Dans le prochain chapitre, nous continuerons notre exploration de Racket. D’ici-là, allons prendre un bon café !

 

 

  •  
    26
    Shares
  • 26
  •  
  •  
  •  
  •  

2
Poster un Commentaire

avatar
1 Fils de commentaires
1 Réponses de fil
0 Abonnés
 
Commentaire avec le plus de réactions
Le plus populaire des commentaires
2 Auteurs du commentaire
Arnold NGORANEvariste Dossou Auteurs de commentaires récents
  S’abonner  
plus récent plus ancien Le plus populaire
Notifier de
Evariste Dossou
Invité
Dossou

bonjour le messie je vous remercie pour ce que vous faites pour nous grâce a vos efforts je parviens a intégrer peu a peu le monde de la programmation .J’ai réussi a installer Dr Racket mais j’ai échoué a chaque fois que je voulait valide après avoir saisi (+1234567) .Le logiciel m’affiche un message d’erreur .Veuillez éclairer ma lanterne Svp. Sur ce merci et bonne continuation a vous