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

[toc heading_levels=”1,2″] Nous continuons notre descente sur l’arène de Racket. Dans ce chapitre, nous explorerons les derniers éléments de base à partir desquels nous pourrions écrire des programmes décents en Racket. D’abord, nous terminerons notre étude des expressions conditionnelles. Ensuite, nous introduirons une nouvelle structure de donnée appelée structure. Ensuite, nous exposerons les notions de boucle et de récursivité qui sont très importantes en programmation. Et nous finirons par des applications de tout ce que nous avons appris jusqu’ici. Commençons sans plus tarder !

Les expressions conditionnelles AND et OR

Il arrive qu’on prenne une décision basée sur la vérité de plusieurs propositions, et non sur la vérité d’une seule proposition. Par exemple, vous décidez d’acheter un téléphone si l’appareil photo (AP) arrière a une résolution d’au moins 16 MP (mégapixels), s’il y a un appareil photo avant pour prendre des selfies, si l’écran fait au moins 5.5″ (pouces) et la mémoire ROM fait au moins 16 GB. Si une de ces conditions n’est pas respectée, vous n’achetez pas le phone. Voici une représentation algorithmique de la situation :

Si le phone a un AP arrière >= 16 MP et un AP avant et un écran >= 5.5" et une ROM >= 16 GB
    On l'achète
Sinon
    On ne l'achète pas

En Racket, l’opérateur and permet de vérifier que chaque condition, parmi une suite de conditions, est vraie. Sa syntaxe est la suivante :

(and cond1 cond2condN)

L’autre scénario est que vous décidiez d’acheter le téléphone si au moins une des conditions est satisfaite. Par exemple, si le phone a seulement une ROM de 32 GB et que les autres conditions ne sont pas satisfaites, vous l’achetez. Mais si aucune condition n’est remplie, vous n’achetez pas le phone. On pourrait représenter algorithmiquement comme suit :

Si le phone a un AP arrière >= 16 MP ou un AP avant ou un écran >= 5.5" ou une ROM >= 16 GB
    On l'achète
Sinon
    On ne l'achète pas

C’est l’opérateur or qui permet de réaliser cela en Racket, et sa syntaxe est la suivante :

(or cond1 cond2condN)

On peut utiliser and et or dans deux principales situations. Soit en tant que prédicat, donc utilisables avec toutes les autres expressions conditionnelles. Par exemple :

> (define x 14)

> (if (and (number? x) (even? x))
        "x est un nombre pair"
        "x n'est soit pas un nombre soit pas pair"

\(=>\) “x est un nombre pair” ; x est à la fois un nombre et un nombre pair

> (define y (+ 1 14))

> (if (or (number? y) (even? y)
        "y est soit un nombre soit un nombre pair"
        "y n'est ni un nombre ni un nombre pair"

\(=>\) “y est soit un nombre soit un nombre pair” ; y est un nombre mais il n’est pas pair

> (define z (+ y 1.5))

> (if (and (number? z) (integer? z))
        "x est un nombre pair"
        "x n'est soit pas un nombre soit pas pair"

\(=>\) “x n’est soit pas un nombre soit pas pair” ; z est un nombre mais pas un entier

L’autre situation où l’on peut faire usage de and et de or est directement en tant qu’expressions conditionnelles. Par exemple :

> (and (number? x) (integer? x) “x est un nombre entier”)
\(=>\) “x est un nombre entier”

Remarquez bien qu’on utilise la propriété du REPL de Racket qui est de retourner la valeur de la dernière forme si aucune erreur ne s’est produite avant son évaluation. Puisque x est un nombre et qu’il est entier, alors la dernière forme, qui est le string “x est un nombre entier”, est évalué et le REPL affiche le même string “x est un nombre entier” comme résultat. Si l’une des conditions n’était pas remplie, le REPL ne retournerait #f sans même évaluer les autres conditions : cette caractéristique des opérateurs and et or est appelée court-circuit.

> (and (integer? z) (number? z) “z est un nombre entier”)
\(=>\) #f

Dans cet exemple, lorsque le REPL évalue la condition (integer? z) et qu’il se rend compte qu’elle est fausse (puisque z n’est pas un nombre entier), il n’a plus besoin d’évaluer les formes restantes et il retourne #f. Ce qu’il fait est logique puisque pour que le and soit vrai, il faut que toutes ses conditions, sans exclusive, soient vraies.

Toutefois, dans le cas de or, il suffit que toutes les conditions soient fausses pour que la dernière forme soit évaluée. Si une condition est vraie, le REPL retourne immédiatement #t sans évaluer les formes suivantes.

> (or (integer? z) (number? z) “z est soit un nombre soit entier”)
\(=>\) #t

Dans cet exemple, le REPL retourne #t car même si la première condition est fausse, la seconde étant vraie, il retourne #t sans avoir besoin d’évaluer la dernière forme. C’est logique car pour que le or soit vrai, il faut juste qu’une seule de ses conditions soit vraie.

> (define nom “Le Messie”)
> (or (number? nom) (integer? nom) “nom n’est ni un nombre ni un entier”)
\(=>\) “nom n’est ni un nombre ni un entier”

Cette fois, le REPL retourne la valeur de la dernière forme car les deux premières conditions sont toutes fausses.

Notez que même si la deuxième utilisation de and et or soit légitime, elle peut prêter à confusion comme vous avez dû le constater dans les exemples précédents. Il est donc préférable de n’en faire usage que dans la première situation, c’est-à-dire en tant que prédicat.

Le prédicat NOT

Je profite de cette discussion sur les prédicats and et or pour introduire le prédicat not. Comme son nom l’indique, ce prédicat permet de retourner le contraire de la valeur de vérité d’une proposition. Ainsi, la proposition est vraie, ce prédicat retournera faux, si elle est fausse, il retournera vrai.

> (not #t)
\(=>\) #f
> (not #f)
\(=>\) #t
> (not (odd? 3))
\(=>\) #f
> (not (odd? 4))
\(=>\) #t

Ces exemples sont assez basiques pour qu’ils ne nécessitent pas d’explications.

Les structures

Nature des structures

Les structures sont un type de données (plus précisément une structure de données) qui à une variable associe plusieurs autres. Imaginez que vous vouliez développer un programme qui serait comme un répertoire téléphonique mais pour PC. Un répertoire sert à stocker des informations sur des personnes ou des choses éventuellement. Mais nous allons nous limiter aux personnes. Les informations qui pourraient nous intéresser sont : le nom, le prénom, le numéro de téléphone, l’adresse e-mail et l’intitulé du poste. Le tableau ci-dessous présente les trois premières personnes de notre répertoire.

La colonne Id (pour identifiant) indique l’ordre dans lequel nous avons enregistré ces contacts dans notre répertoire. Par exemple, on pourrait dire que le nom du contact numéro 2 est DUPONT.

Comme vous pouvez le voir, pour représenter chaque personne dans le répertoire, il faudra utiliser une structure de données qui, comme les listes, soit capable de stocker plusieurs données de type divers. On aurait donc pu directement utiliser la structure de liste et représenter, par exemple le contact 1 de manière suivante :

> (define contact-1 ‘(1 JOHNSON Mike 0121-544 “john@x.com” “Doctorant”))

Et questionner le REPL sur le nom et l’e-mail du contact 1 comme suit :

> (second contact-1)
\(=>\) ‘JOHNSON
> (fourth contact-1)
\(=>\) “john@x.com”

Ceci est vraiment bien mais ça manque d’expressivité, de précision. On serait plus content d’avoir des opérateurs dont les noms comportent les noms des informations qu’on recherche. Par exemple, plutôt que les opérateurs second et fourth, il serait intéressant d’avoir des opérateurs contact-nom et contact-email. De cette façon, on serait plus précis, car second et fourth sont trop généraux. Racket nous offre la structure de données adéquate, et elle s’appelle (peut-être par coïncidence) : structure. Les structures sont classiques dans la plupart des langages haut niveau.

Notez que hormis la précision apportée par le type structure, il est plus efficace que le type liste. Pour récupérer les éléments d’une liste, on chaîne les opérateurs CAR et CDR, alors si la liste est très longue, cette opération devient très inefficace. Cela est dû à la manière dont la structure de liste rangent les éléments en mémoire. En revanche, le type structure associe à chaque donnée une étiquette (un symbole) et celle-ci contient l’adresse mémoire de la donnée (elle pointe donc vers la donnée). Cette opération est très rapide.

Détails du type structure

Passons maintenant aux détails du type structure. Voici sa syntaxe :

(struct nom-struct ([slot-1 options-1] [slot-2 options-2] … [slot-N options-N]) struct-options)

slot-1 à slot-N représentent les attributs ou caractéristiques de la structure dont le nom est nom-struct. Ils sont tous des symboles Racket. À chaque slot, on peut associer une ou plusieurs options (par exemple l’option #:mutable) et on peut associer des options à la structure elle-même. Nous verrons quelques options au fil de notre apprentissage, mais vous pouvez consulter la doc sur les structures pour en savoir plus.

Nous pouvons maintenant créer notre structure qu’on appelle contact.

> (struct contact (id nom prenom tel email poste) #:mutable)

Remarquez que nous avons ajouté l’option #:mutable pour indiquer que cette structure pourra être modifiée. On peut maintenant interroger le REPL sur la valeur de contact :

> contact
\(=>\) #<procedure:contact>

Le REPL est très peu bavard à ce sujet, mais il nous informe quand même que contact existe et que c’est une procédure (ou programme). Définissons maintenant les trois contacts du tableau précédent :

> (define contact-1 (contact 1 ‘JOHNSON ‘Mike ‘0121-544 “john@x.com” “Doctorant”))
> (define contact-2 (contact 2 ‘DUPONT ‘Charles ‘2541-401 “charles@fg.com” “Ingénieur”))
> (define contact-3 (contact 3 ‘KABLAN ‘Thierry ‘5410-512 “thierry@bz.com” “Comptable”))

Remarquez bien les types de données que j’ai choisis pour chaque attribut de la structure. En effet, le choix entre le type symbole (pour le nom, le prénom et le numéro de téléphone) et le type string (pour l’e-mail et le poste) est quelque peu arbitraire. Notez toutefois que s’il y a des espaces dans les valeurs, par exemple Mike Robert comme prénoms, il faut nécessairement utiliser le type string. Notez également que vous n’êtes pas obligés d’avoir un seul type pour un attribut donné : vous pouvez créer un contact dont le prénom est de type symbole et un autre contact dont le prénom est de type string. Mais, il est préférable — et même recommandé — de garder le même type pour chaque attribut, pour des raisons de cohérence et parce que certains opérateurs ne s’appliquent pas indifféremment à tout type de donnée.

Essayons maintenant d’interroger le REPL sur le contact 1 :

> contact-1
\(=>\) #<contact>

Oh ! il est toujours peu bavard, mais encore il nous informe que contact-1 est de type contact. C’est une information importante.

Revenons à un peu de théorie sur le type structure en Racket. Lorsqu’on crée une structure, Racket crée automatiquement plusieurs opérateurs, dont les principaux sont les suivants :

  • des accesseurs : qui permettent d’accéder aux différents slots. On a les accesseurs nomstruct-slot-1, nom-struct-slot-2, …, nom-struct-slot-N. On voit bien que le nom de la fonction est constitué du nom de la structure et du nom du slot séparés par un trait d’union (le tiret de la touche 6 du clavier AZERTY). On leur passe en argument la variable à accéder.
  • des modificateurs : qui permettent de modifier la valeur associée à un slot. On a les modificateurs set-nomstruct-slot-1!, set-nomstruct-slot-2!, …, set-nomstruct-slot-N!. On leur passe en arguments, la variable à modifier et la nouvelle valeur du slot.
    Notez que le modificateur n’est créé pour un slot que si ce slot a été déclaré modifiable (ou si la structure est déclaré modifiable) lors de la création de la structure.
  • un prédicat : qui permet de vérifier si la donnée qu’on lui passe en argument est du type de la structure. Ce prédicat a pour identificateur nomstruct?. Cette dénomination ne doit plus vous étonner.

On peut maintenant accéder aux attributs des contacts enregistrés :

> (contact-id contact-1)
\(=>\) 1
> (contact-nom contact-1)
\(=>\) ‘JOHNSON
> (contact-prenom contact-1)
\(=>\) ‘Mike
> (contact-tel contact-1)
\(=>\) ‘0121-544
> (contact-email contact-1)
\(=>\) “john@x.com”
> (contact-poste contact-1)
\(=>\) “Doctorant”
> (contact-age contact-1)
\(=>\) contact-age: undefined;
cannot reference an identifier before its definition ; Erreur

Comme vous pouvez le voir, on a pu accéder à toutes les caractéristiques du contact 1. Le dernier exemple retourne une erreur car l’opérateur n’est pas défini, puisque nous n’avons pas défini de slot nommé age dans la structure contact. Voici maintenant comment on utilise le prédicat associé à la structure :

> (contact? contact-1)
\(=>\) #t
> (contact? contact-2)
\(=>\) #t
> (define nom “Le Messie”)
> (contact? nom)
\(=>\) #f

Imbrication de structures

Imaginez maintenant que plutôt que de juste mettre l’intitulé du poste, on désire en plus associer le nom de l’entreprise. On peut pour ce faire, créer une structure poste dont les attributs seraient titre pour l’intitulé du poste et entreprise pour le nom de l’entreprise.

> (struct poste (titre entreprise))

On peut créer de nouveaux postes de la manière suivante :

> (define poste-1 (poste “Doctorant” “CMA”))
> (define poste-2 (poste “Ingénieur” “SIR”))
> (define poste-3 (poste “Comptable” “KPMG”))

Et modifier la valeur du slot poste de nos contacts.

> (set-contact-poste! contact-1 poste-1)
> (set-contact-poste! contact-2 poste-2)
> (set-contact-poste! contact-3 poste-3)

Notez que nous n’étions pas obligés de créer les variables poste-1, poste-2 et poste-3 puisque nous n’allons certainement plus les réutiliser. On aurait pu faire comme suit :

> (set-contact-poste! contact-1 (poste “Doctorant” “CMA”))

Ce que nous venons de faire en ajoutant un slot de type structure est appelé imbrication de structures. On peut imbriquer les structures autant que nous le souhaitons. Voici comment on pourrait interroger le REPL sur l’entreprise du contact 1 :

> (poste-entreprise (contact-poste contact-1))
\(=>\) “CMA”

J’espère que cette syntaxe ne vous surprend pas 🙂

Transparence des structures

On avait précédemment noté que le REPL n’était pas très bavard sur le contenu d’une variable de type structure. C’est parce que par défaut, quand on crée une structure, elle est opaque (non transparente). Pour la rendre transparente, il faut ajouter l’option #:transparent.

> (struct contact (id nom prenom tel email poste) #:mutable #:transparent)

Ce faisant, notre structure devient transparente. Alors, le REPL sera plus bavard maintenant si on lui demande les détails d’un contact :

> contact-1
\(=>\) (contact 1 ‘JOHNSON ‘Mike ‘0121-544 “john@x.com” #<poste>)

Cette fois, nous avons tous les détails du contact 1. Le REPL nous retourne une liste dont le premier élément est le type de la variable. Oups ! le REPL n’a rien dit sur le poste. Pourquoi ? parce qu’on n’a pas déclaré la structure poste comme transparente, lors de sa création. On va donc y remédier.

> (struct poste (titre entreprise) #:transparent)

Interrogeons de nouveau le REPL sur les détails du contact 1.

> contact-1
\(=>\) (contact 1 ‘JOHNSON ‘Mike ‘0121-544 “john@x.com” (poste “Doctorant” “CMA”))

Il est important de remarquer que la décision sur les options doit se prendre avant la création d’une structure, car sinon vous êtes obligés de redéfinir toutes les variables qui ont pour type cette structure, à chaque ajout ou suppression d’une option. Dans les exemples précédents, j’ai fait comme si on pouvait ajouter une option et que Racket mettrait à jour automatiquement toutes les instances de la structure, mais ce n’est pas le cas. Je devais normalement redéfinir contact-1, contact-2 et contact-3, lorsque j’ai ajouté l’option #:mutable et lorsque j’ai ajouté l’option #:transparent. Vous comprenez donc pourquoi il est nécessaire d’ajouter toutes les options désirées à la création de la structure.

Nous avons parcouru tout ce qu’il y a de basique à savoir sur les structures. Passons maintenant aux boucles.

Les boucles en Racket

Lorsque j’étais à l’école primaire, il arrivait que je sois puni par l’instituteur parce que j’étais très bavard (un peu comme le REPL 😆 ). La punition consistait à écrire sur un papier la phrase “Je ne bavarderai plus en classe.” cent fois. Avez-vous également subi un sort similaire ? Ah ha ! je vous assure que c’était horrible. Lorsque j’ai appris la programmation et son concept de boucle, je me suis dit que ça aurait pu m’être en primaire 😉 . Afin que vous compreniez le pourquoi de cette affirmation, parlons un peu théorie.

Un boucle est une structure de contrôle qui permet d’exécuter un même code un certain nombre de fois, suivant la vérité de certaines conditions. Certainement tous les langages de programmation implémentent la notion de boucle. Quand je dis boucle, entendez une forme Racket dont l’opérateur permet de répéter un code plusieurs fois. Voyons ce qu’il en est en Racket.

Les boucles FOR

Comme nous allons le voir dans la suite, Racket possède un grand nombre de boucles : une boucle for qui est très générale et des boucles for/… spécifiques à certaines structures de données ou autres opérations. Nous ne verrons que la boucle for et la boucle for/list. Nous allons apprendre à les utiliser par des exemples.

Soit à répéter la phrase “Je ne bavarderai plus en classe.” quatre fois. On pourrait le faire de la manière suivante :

> (for ([i '(1 2 3 4)])
      (display "Je ne bavarderai plus en classe.\n"))

\(=>\) Je ne bavarderai plus en classe.
Je ne bavarderai plus en classe.
Je ne bavarderai plus en classe.
Je ne bavarderai plus en classe.

Notez que la valeur de chaque élément de la liste ‘(1 2 3 4) n’a aucune importance, c’est le nombre d’éléments qui importe. J’aurai donc pu faire :

> (for ([i '(1 1 1 1)])
      (display "Je ne bavarderai plus en classe.\n"))

Et cela m’aurait donné le même résultat.
Notez aussi j’ai utilisé l’opérateur display pour afficher la phrase sans les double-quotes et parce qu’il sait interpréter le symbole \n. (séquence d’échappement qui équivaut à un retour à la ligne). En effet, s’il n’avait pas le symbole \n, le REPL afficherait les quatre phrases “Je ne bavarderai plus en classe.” collées et sur la même ligne.

Dans la syntaxe de la boucle for, [i ‘(1 1 1 1)] est appelée clause de la boucle où i est la variable liée, dans l’ordre, à la chaque valeur de la séquence ‘(1 1 1 1). Une clause for a donc la forme [id-var sequence]. Une séquence est un terme générique pour désigner toute collection ordonnées de données. Par exemple les listes et les chaînes de caractères sont des séquences. La forme (display …) fait partie de ce qu’on appelle le corps de la boucle. Le corps peut contenir plusieurs formes. La boucle for de l’exemple peut s’interpréter comme suit : Pour chaque valeur de la variable i dans la séquence ‘(1 1 1 1), affiches-moi la phrase “Je ne bavarderai plus en classe.”.

Voici une manière plus utile d’employer la boucle for et qui nous permettra de mieux appréhender son fonctionnement :

> (for ([i '(1 2 3 4)])
      (display (+ i 1)))

On pourrait interpréter ce code par : Pour chaque valeur de la variable i dans la séquence ‘(1 2 3 4), affiches-moi le nombre qui a une unité de plus que i. Puisque la séquence ‘(1 2 3 4) comporte quatre éléments, le corps de la boucle sera exécuté quatre fois et à chaque exécution — qu’on appelle aussi itération — la variable sera associée à une valeur de la séquence dans l’ordre. Décrivons les itérations pas à pas :

Itération 1 : i \(\leftarrow\) 1 (i est associée à 1). Le REPL évalue l’expression (+ 1 1) et affiche 2.
Itération 2 : i \(\leftarrow\) 2 (i est associée à 2). Le REPL évalue l’expression (+ 2 1) et affiche 3.
Itération 3 : i \(\leftarrow\) 3 (i est associée à 3). Le REPL évalue l’expression (+ 3 1) et affiche 4.
Itération 4 : i \(\leftarrow\) 4 (i est associée à 4). Le REPL évalue l’expression (+ 4 1) et affiche 5.

À la fin de ces, le REPL nous retourne ceci :

\(=>\) 2345

On obtient donc le résultat espéré. Cette fois les résultats ne pas séparés par un retour à la ligne, c’est pourquoi on a l’impression que le REPL nous a retourné le nombre 2345.

Quoique’au sens strict du terme, un nombre entier ne soit pas une séquence, on peut tout de l’imaginer comme étant la séquence composée de tous les nombres entiers qui le précède, en commençant. Par exemple, 4 peut être vu comme la séquence ‘(0 1 2 3). Notez que le nombre en question n’apparaît pas dans la séquence et que le nombre d’éléments de la séquence reste toutefois égal à ce nombre parce qu’on a commencé par 0.

> (for ([i 4])       
    (display "Je ne bavarderai plus en classe.\n"))

\(=>\) Je ne bavarderai plus en classe.
Je ne bavarderai plus en classe.
Je ne bavarderai plus en classe.
Je ne bavarderai plus en classe.

> (for ([i 4])       
    (display i))

\(=>\) 0123

À ce stade, comprenez-vous maintenant pourquoi les boucles m’auraient aidé en primaire ? Eh bien ! j’aurais écrit la boucle suivante sur la feuille de papier et je l’aurais rendu à mon instituteur :

> (for ([i 100])       
    (display "Je ne bavarderai plus en classe.\n"))

Bien-sûr ! il est peu probable qu’il eusse compris ce langage et donc il eusse été encore plus nerveux 😆 . Oh le code !

Puisque les chaînes de caractères sont des séquences, l’exemple suivant est légitime.

> (for ([car "blogdescodeurs"])       
    (printf "~a..." car))

\(=>\) b…l…o…g…d…e…s…c…o…d…e…u…r…s…

L’opérateur printf est l’opérateur d’affichage de données par excellence de Racket. Il permet de faire des choses vraiment complexes. Comme vous pouvez le voir dans cet exemple, printf nous permet d’afficher trois points de suspension après chaque caractère auquel la variable car est liée. Le symbole ~a est une séquence de formatage comprise par printf qui lui indique commet afficher la variable car dans le résultat. ~a lui dit d’afficher la variable telle quelle. L’opérateur printf prend donc comme arguments un texte à afficher (qui est une chaîne de caractères dite formatée) et zéro ou plusieurs variables. En général, le nombre de variables correspond au nombre de séquences de formatage contenues dans le texte. Notez que formater une donnée, c’est lui donner une certaine apparence. Voici un autre exemple d’utilisation de printf :

> (for ([car "blogdescodeurs"]
        [i (string-length "blogdescodeurs")])      
    (printf "~a...~a..." car (+ i 1)))

\(=>\) b…1…l…2…o…3…g…4…d…5…e…6…s…7…c…8…o…9…d…10…e…11…u…12…r…13…s…14…

Dans cet exemple, la boucle for a deux clauses. Dans la seconde, l’expression associée à la variable i, (string-length “blogdescodeurs”), retourne la longueur de la chaîne de caractères “blogdescodeurs”, c’est-à-dire le nombre de caractères qu’elle comporte. Cette expression retourne 14, donc i sera associée à la séquence ‘(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14). Dans la forme printf, nous avons deux séquences de formatage ~a. La première sert à formater la variable car et la seconde sert à formater le résultat de l’expression (+ i 1). Donc le but de l’exemple, c’est d’afficher les différents caractères de la chaîne “blogdescodeurs” suivi de leurs positions dans la chaîne et séparés par des points de suspension.

Je vous invite à consulter la doc de Racket pour plus d’exemples sur l’utilisation de printf.

La boucle for/list permet d’accumuler (ou regrouper) le résultat de chaque itération sous forme de liste. Par exemple :

> (for/list ([i 4])       
    (sqr i))

\(=>\) ‘(0 1 4 9)

Pour rappel, la fonction sqr retourne le carré du nombre qu’on lui passe en argument.

> (for/list ([car "blogdescodeurs"])       
    car)

\(=>\) ‘(#\b #\l #\o #\g #\d #\e #\s #\c #\o #\d #\e #\u #\r #\s)

La récursivité

Un concept important en programmation est la récursivité. On dit qu’un programme est récursif s’il fait appel à lui-même dans son corps. Ici, nous allons nous intéresser aux fonctions récursives. Une fonction est donc dite récursive si elle fait référence à elle-même dans son corps.

La fonction length

Prenons un exemple. Proposons-nous d’écrire notre version de la fonction length de Racket et appelons-la rec-length. Cette fonction prend une liste en argument et le nombre d’éléments de la liste. Voici une définition récursive d’une liste : une liste est soit la liste vide soit une liste à deux éléments dont le premier élément est un atome et le second élément est une liste.

Un caractère important de cette définition, c’est qu’elle a deux parties :

  1. les clauses d’arrêt : Chacune de ces clauses contient une condition qui, lorsqu’elle est vraie, permet d’arrêter l’exécution de la fonction et de retourner le résultat.
    Dans le cas de la définition précédente, cette clause est une liste est soit la liste vide. En effet, si la liste est vide, il n’y a plus lieu d’inspecter le contenu de la liste.
  2. les clauses récursives : ces clauses permettent de réduire le problème initial en un sous-problème de même nature mais plus simple (rappelez-vous de la technique diviser pour mieux régner).
    Dans le cas de la définition de la liste, cette clause est une liste est soit un liste à deux éléments dont le premier élément est un atome et le second élément est une liste. En effet, si la liste n’est pas vide, elle contient donc des éléments et pour inspecter ces éléments, il suffit de prendre le premier élément et de remarquer que le reste des éléments forment encore une liste. Puisque le fait d’enlever le premier élément ne détruit pas la nature de la liste. Ce faisant, nous avons réduit la liste initiale en une liste qui a un élément de moins. Mais, puisque nous avons encore une liste et que celle-ci peut être vide, on continue son inspection en retournant à l’étape 1. On procède ainsi de suite jusqu’à épuiser tous les éléments de la liste.

Remarquez que cette manière d’examiner une liste nous permet d’obtenir son nombre d’éléments. En effet, si nous ne pouvons pas retirer d’élément, alors la liste est vide et nous concluons que sa longueur est 0. Sinon, nous retirons le premier élément de la liste, et nous notons que la longueur temporaire est 1. Ensuite, nous continuons l’inspection de la liste, si nous arrivons pas à retirer un nouvel élément, alors nous nous arrêtons là et nous concluons que la longueur totale de la liste est 1. Sinon, nous retirons encore un élément et nous notons que la longueur temporaire de la liste est \(1 + 1 = 2\). Nous continuons de cette manière jusqu’à trouver la longueur totale de la liste. Cette procédure est la récursion et nous avons eu l’habitude d’écrire nos algorithmes de l’Arithmétique de cette manière.

Voici donc le code de la fonction rec-length :

> (define (rec-length lst)
     (if (null? lst)
         0
         (+ 1 (rec-length (cdr lst)))))

On retrouve bien les deux parties de toute fonction récursive :

  1. Une clause d’arrêt : c’est la condition (null? lst) qui vérifie si la liste est vide. Si cette condition est vraie, alors on retourne 0.
  2. Une clause récursive : La forme (+ 1 (rec-length (cdr lst))) contient un appel à la fonction rec-length. Elle est donc récursive par définition. Remarquez cependant que cet appel prend en argument le reste de la liste, (cdr lst), cela montre bien que nous avons réduit le problème. Et de cette façon, nous sommes sûr que le programme se terminera. En effet, si on passait la liste originale à la l’appel récursif, notre fonction ne s’arrêterait jamais.
    La forme (+ 1 (rec-length (cdr lst))) prend également soin d’ajouter 1 à chaque fois que nous atteignons la clause récursive. Cela est logique puisqu’on n’atteint cette clause que si la liste n’est pas vide. Si nous n’ajoutons pas les 1, on aurait 0 comme résultat final.

Utilisons maintenant notre fonction pour déterminer la taille de quelques listes. Nous détaillerons pas à pas le premier exemple.

> (rec-length ‘(5 1 2 0))
\(=>\) 4
  • Au départ la variable, lorsqu’on fait l’appel (rec-length ‘(5 1 2 0)), lst est liée à la liste ‘(5 1 2 0) (\(lst \leftarrow ‘(5 1 2 0)\)). On rentre dans le corps de fonction. L’expression conditionnelle if est alors évaluée. La clause (null? lst) (qui est la clause d’arrêt) retourne #f puisque la liste n’est pas vide. Puisque cette clause est fausse, la seconde décision de if est évaluée (la clause récursive). C’est l’expression (+ 1 (rec-length (cdr lst))). On voit bien que cette expression ajoute 1 au résultat de l’appel de la fonction rec-length avec l’argument (cdr lst) qui est le reste de la liste initial donc ‘(1 2 0). Le problème initial est donc réduit à (+ 1 (rec-length ‘(1 2 0))).
  • Lorsqu’on fait l’appel (rec-length ‘(1 2 0)), lst est maintenant liée à la liste ‘(1 2 0) (\(lst \leftarrow ‘(1 2 0)\)). On rentre dans le corps de fonction. La clause (null? lst) retourne #f puisque la liste n’est pas vide. La seconde décision, (+ 1 (rec-length (cdr lst))), est évaluée. Cette expression ajoute 1 au résultat de l’appel de la fonction rec-length avec l’argument (cdr lst) qui est le reste de la liste précédente donc ‘(2 0). Le second problème est donc réduit à (+ 1 (rec-length ‘(2 0))). Et n’oublions pas l’unité qu’on avait initialement ajouté. On a donc (+ 1 (+ 1 (rec-length ‘(2 0)))).
  • Lorsqu’on fait l’appel (rec-length ‘(2 0)), lst est maintenant liée à la liste ‘(2 0) (\(lst \leftarrow ‘(2 0)\)). On rentre dans le corps de fonction. La clause (null? lst) retourne #f puisque la liste n’est pas vide. La seconde décision, (+ 1 (rec-length (cdr lst))), est évaluée. Cette expression ajoute 1 au résultat de l’appel de la fonction rec-length avec l’argument (cdr lst) qui est le reste de la liste précédente donc ‘(0). Le troisième problème est donc réduit à (+ 1 (rec-length ‘(0))). Et n’oublions pas l’unité qu’on avait initialement ajouté. On a donc (+ 1 (+ 1 (+ 1 (rec-length ‘(0))))).
  • Lorsqu’on fait l’appel (rec-length ‘(0)), lst est maintenant liée à la liste ‘(0) (\(lst \leftarrow ‘(0)\)). On rentre dans le corps de fonction. La clause (null? lst) retourne #f puisque la liste n’est pas vide. La seconde décision, (+ 1 (rec-length (cdr lst))), est évaluée. Cette expression ajoute 1 au résultat de l’appel de la fonction rec-length avec l’argument (cdr lst) qui est le reste de la liste précédente donc ‘(), la liste vide. Le quatrième problème est donc réduit à (+ 1 (rec-length ‘())). Et n’oublions pas l’unité qu’on avait initialement ajouté. On a donc (+ 1 (+ 1 (+ 1 (+ 1 (rec-length ‘()))))).
  • Lorsqu’on fait l’appel (rec-length ‘()), lst est maintenant liée à la liste ‘() (\(lst \leftarrow ‘()\)). On rentre dans le corps de fonction. Cette fois, puisque la liste est vide, la clause (null? lst) retourne #t et la première décision, qui consiste à retourner le chiffre 0, est évaluée. Et on s’arrête là puisqu’il n’y a plus d’appel à la fonction rec-length. On a donc finalement (+ 1 (+ 1 (+ 1 (+ 1 0)))).
  • L’expression (+ 1 (+ 1 (+ 1 (+ 1 0)))) s’évalue comme suit :
    (+ 1 (+ 1 (+ 1 (+ 1 0)))) \(=>\) (+ 1 (+ 1 (+ 1 1))) \(=>\) (+ 1 (+ 1 2)) \(=>\) (+ 1 3) \(=>\) 4
  • La liste ‘(5 1 2 0) est donc de taille 4.

Voici d’autres exemples d’application de la fonction rec-length :

> (rec-length ‘())
\(=>\) 0
> (rec-length ‘(chat poule souris riz maïs avoine))
\(=>\) 6
> (rec-length ‘(#\a #\b ‘c))
\(=>\) 3

La fonction factorielle

Un autre exemple classique de récursion est la fonction mathématique appelée factorielle. Cette fonction est définie pour tout nombre entier naturel. La factorielle de 5 est notée 5!, celle de 8 est notée 8!. Et voici comment on calcule ces factorielles :

\begin{split}
5! & = 5 \times 4 \times 3 \times 2 \times 1 = 120 \\
8! & = 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 40320
\end{split}

La factorielle d’un entier naturel est donc le produit de ce nombre et de tous les nombres entiers naturels (différents de 0) plus petits que lui. Essayons de trouver une définition récursive de la factorielle. Analysons les factorielles suivantes :

\begin{split}
5! & = 5 \times \mathbf{4 \times 3 \times 2 \times 1}\\
4! & = \mathbf{4 \times 3 \times 2 \times 1}
\end{split}

On remarque que l’expression de la factorielle 4 se retrouve exactement dans celle de 5. La factorielle de 5 est donc le produit de 5 et de la factorielle de 4!. On peut l’exprimer comme suit :

$$5! = 5 \times \mathbf{4!}$$

Continuons l’analyse avec la factorielle de 3.

$$3! = 3 \times 2 \times 1 = 6$$

On voit donc que \(4! = 4 \times 3!\) et donc que :

$$5! = 5 \times 4 \times \mathbf{3!}$$

Poursuivons avec la factorielle de 2.

$$2! = 2 \times 1 = 2$$

On voit donc que \(2! = 2 \times 1!\) et donc que :

$$5! = 5 \times 4 \times 3 \times \mathbf{2!}$$

Et terminons avec la factorielle de 1.

$$1! = 1$$

On a finalement :

$$5! = 5 \times 4 \times 3 \times \times 2 \times 1$$

C’est exactement la définition de la factorielle. Mais, il ressort de cette analyse que la factorielle d’un nombre entier naturel se réduit au produit de ce nombre et de la factorielle de l’entier qui est plus petit d’une unité. Cette définition est récursive puisqu’elle fait référence la fonction factorielle. Par convention, la factorielle de 0 est 1 (0! = 1). Ce qui rend la factorielle définie pour les nombres entiers.

Munie de la définition récursive de la factorielle, nous pouvons coder la fonction comme suit :

> (define (! n)
    (if (zero? n)
        1
        (* n (! (- n 1)))))

J’ai appelé la fonction par son symbole !. Cet identificateur est valide en Racket. Notez qu’on retrouve bien les deux parties de toute fonction récursive. Voici comment on peut lire cette fonction : On définit la fonction ! pour tout nombre n (entendez que ce nombre est entier). Si n est égal à 0, alors retournes 1, sinon retourne le produit de n et du nombre qui est plus petit que lui d’une unité, c’est-à-dire (- n 1).

Voici des exemples d’utilisation de la fonction ! :

> (! 5)
\(=>\) 120
> (! 8)
\(=>\) 40320
> (! 0)
\(=>\) 1

Procédez pas à pas comme nous l’avons dans la première application de la fonction rec-length.

Applications

Nous allons dans cette section écrire les programmes Racket de quelques algorithmes que nous avons vus dans la première partie de notre cours sur l’Arithmétique.

La multiplication et la division des nombres entiers

Supposons que le langage Racket nous offre le premier mode élémentaire de génération des nombres et son inverse, c’est-à-dire l’addition et la soustraction, et essayons de coder le second mode et son inverse, c’est-à-dire la multiplication et la division. Nous avons déjà vu leurs algorithmes dans le cours sur l’Arithmétique, nous ne les rappellerons donc pas ici. Retrouvez-les ici. Nous allons juste les défnir récursivement.

La multiplication

Multiplier un nombre entier par un autre, c’est ajouter le premier au produit du premier et du nombre entier est plus petit que le second facteur d’une unité. Cette définition est récursive. Éclaircissons-la par un exemple.

Proposons de multiplier 5 par 3. On procède comme suit :

  • 5 fois 3 se réduit à 5 plus le produit de 5 et 2, avec 2 étant égal à 3 moins 1. Symboliquement, on écrit : \(5 \times 3 = 5 + (5 \times (3 – 1)) = 5 + (\mathbf{5 \times 2})\). On a donc réduit le problème à 5 fois 2 puisqu’on a supposé que Racket nous offre l’addition et la soustraction.
  • 5 fois 2 se réduit à 5 plus le produit de 5 et 1, avec 1 étant égal à 2 moins 1. Symboliquement, on écrit : \(5 \times 2 = 5 + (5 \times (2 – 1)) = 5 + (\mathbf{5 \times 1})\). On a donc réduit le problème à 5 fois 1. Mais n’oublions pas les premières 5 unités ajoutées au début. On a donc en tout : \(5 \times 3 = 5 + 5 + (5 \times 1)\).
  • 5 fois 1 se réduit à 5 plus le produit de 5 et 0, avec 0 étant égal à 1 moins 1. Symboliquement, on écrit : \(5 \times 2 = 5 + (5 \times (1 – 1)) = 5 + (\mathbf{5 \times 0})\). On a donc réduit le problème à 5 fois 0. Et comme le produit de tout nombre par 0 est égal à 0, alors on s’arrête là. On a donc en tout : \(5 \times 3 = 5 + 5 + 5 + (5 \times 0) = 5 + 5 + 5\).
  • Finalement, on calcule \(5 + 5 + 5\) et on obtient 15, qui est le produit de 5 par 3.

Voici donc le code de notre fonction :

> (define (mult a b)
     (if (zero? b)
         0
         (+ a (mult a (- b 1)))))

Ce code ressemble à celui de la fonction factorielle à part que la fonction a deux paramètres. On retrouve ici exactement la définition que nous avons donnée. Je vous laisse donc son interprétation comme exercice.

Voici des exemples d’utilisation de la fonction mult :

> (mult 5 3)
\(=>\) 15
> (mult 0 0)
\(=>\) 0
> (mult 4 6)
\(=>\) 24

La division

Le quotient de la division d’un nombre entier (dividende précédent) par un autre (diviseur) est la somme de l’unité et du quotient de la division du nouveau dividende — qui est est le reste de la différence du dividende précédent et du diviseur — par le diviseur. Cette définition est récursive. Prenons un exemple pour la clarifier.

On se propose de diviser 18 par 3. On procède comme suit :

  • 18 divisés par 3 se réduit à 1 plus le quotient de 15 par 3, avec 15 étant égal à 18 moins 3. Symboliquement, on écrit : \(18 \div 3 = 1 + ((18 – 3) \div 3) = 1 + (\mathbf{15 \div 3})\). On a donc réduit le problème à 15 divisés par 3 puisqu’on a supposé que Racket nous offre l’addition et la soustraction.
  • 15 divisés par 3 se réduit à 1 plus le quotient de 12 par 3, avec 12 étant égal à 15 moins 3. Symboliquement, on écrit : \(15 \div 3 = 1 + ((15 – 3) \div 3) = 1 + (\mathbf{12 \div 3})\). On a donc réduit le problème à 12 divisés par 3. Mais n’oublions pas la première unité ajoutée au début. On a donc en tout : \(18 \times 3 = 1 + 1 + (12 \div 3)\).
  • 12 divisés par 3 se réduit à 1 plus le quotient de 9 par 3, avec 9 étant égal à 12 moins 3. Symboliquement, on écrit : \(12 \div 3 = 1 + ((12 – 3) \div 3) = 1 + (\mathbf{9 \div 3})\). On a donc réduit le problème à 9 divisés par 3. Donc en tout : \(18 \times 3 = 1 + 1 + 1 + (9 \div 3)\).
  • 9 divisés par 3 se réduit à 1 plus le quotient de 6 par 3, avec 6 étant égal à 9 moins 3. Symboliquement, on écrit : \(9 \div 3 = 1 + ((9 – 3) \div 3) = 1 + (\mathbf{6 \div 3})\). On a donc réduit le problème à 6 divisés par 3. Donc en tout : \(18 \times 3 = 1 + 1 + 1 + 1 + (6 \div 3)\).
  • 6 divisés par 3 se réduit à 1 plus le quotient de 3 par 3, avec 3 étant égal à 6 moins 3. Symboliquement, on écrit : \(6 \div 3 = 1 + ((6 – 3) \div 3) = 1 + (\mathbf{3 \div 3})\). On a donc réduit le problème à 3 divisés par 3. Donc en tout : \(18 \times 3 = 1 + 1 + 1 + 1 + 1 + (3 \div 3)\).
  • 3 divisés par 3 se réduit à 1 plus le quotient de 0 par 3, avec 0 étant égal à 3 moins 3. Symboliquement, on écrit : \(3 \div 3 = 1 + ((3 – 3) \div 3) = 1 + (\mathbf{0 \div 3})\). On a donc réduit le problème à 0 divisés par 3. Or le quotient de 0 divisé par tout nombre est égal à 0. Donc o s’arrête là. On a donc en tout : \(18 \times 3 = 1 + 1 + 1 + 1 + 1 + 1 + (0 \div 3) = 1 + 1 + 1 + 1 + 1 + 1\).
  • Finalement, on calcule \(1 + 1 + 1 + 1 + 1 + 1\) et on obtient 6, qui est le quotient de 18 par 3.

Voici donc le code de notre fonction :

> (define (div a b)
     (if (zero? a)
         0
         (+ 1 (div (- a b) b))))

Remarquez que ce code est semblable à celui de la fonction mult à la différence que la condition (zero? a) est appliquée à la variable a qui est le dividende, puisque c’est cette variable qui évolue à chaque nouvel appel de la fonction div, comme le montre l’expression (div (- a b) b). que la fonction a deux paramètres. On retrouve encore exactement la définition récursive de la division. Je vous laisse donc son interprétation comme exercice.

Voici des exemples d’utilisation de la fonction div :

> (div 18 3)
\(=>\) 6
> (div 0 15)
\(=>\) 0
> (div 225 15)
\(=>\) 15

Tous ces exemples fonctionnent correctement parce que le quotient est exact. Si le quotient n’est pas exact, comme dans (div 27 4), notre l’exécution ne s’arrêtera jamais. Enfin, DrRacket va se plaindre de manque de mémoire. Par défaut, la mémoire volatile qui lui est allouée est de 128 MB. Il vous demandera donc si vous désirez l’augmenter à 256 MB. Même si vous acceptez cette proposition et que vous relancez (div 27 4), DrRacket demandera à augmenter sa mémoire. Et ainsi de suite jusqu’à ce que vous ayez alloué toute votre mémoire RAM à DrRacket, et même là, ça ne suffirait pas. Ce n’est donc pas la solution.

En programmation, quand un programme plante pour certaines valeurs d’arguments, on dit qu’il contient un bogue (bug, en anglais). L’action de supprimer un bogue est appelée débogage. En général, un programme peut contenir un grand nombre de bugs. Le programmeur supprime les bugs les plus évidents mais d’autres bugs peuvent apparaître lors de l’utilisation du programme. Le débogage est donc une sorte d’activité récursive. 😆

Dans le cas de la fonction div, nous savons exactement ce qui pose problème. En effet, à force de réduire le dividende, s’il advient qu’au lieu d’être égal au diviseur, de sorte que le nouveau dividende soit nul, il est plus petit que le diviseur, au prochain appel de la fonction div, on essayera de soustraire un grand nombre d’un petit nombre. Au stade de notre évolution en Arithmétique, nous avons que cela n’est pas légitime. Mais, Racket est plus fort que nous, il arrive à calculer cette différence. Mais, le problème est qu’aucune clause ne lui dit à quel moment s’arrêter, donc il continuera la récursion jusqu’à ce qu’il ‘y ait plus de mémoire. Vous voyez bien que pour résoudre le problème, il nous faut une condition d’arrêt supplémentaire qui dit : si le dividende b est plus petit que diviseur a, retournes 0. En effet, on retourne 0 parce qu’on estime qu’on ne peut pas retrancher un grand nombre dans un petit nombre, et que 0 n’a aucune influence sur l’addition.

Voici donc la nouvelle version de la fonction div :

> (define (div a b)
     (cond [(zero? a) 0]
           [(< a b) 0]
           [else (+ 1 (div (- a b) b))])

Remarquez qu’au lieu de l’expression condition if, j’utilise cette fois cond car il y a plus de deux clauses. Toutefois, puisque les deux premières clauses retournent la même valeur, on peut les combiner en une seule clause avec le prédicat or. Et du coup, on pourrait de nouveau utiliser if.

> (define (div a b)
     (if (or (zero? a) (< a b))
         0
         (+ 1 (div (- a b) b))))

Cette nouvelle version de div peut maintenant évaluer (div 27 4) :

> (div 27 4)
\(=>\) 6

Nous sommes donc satisfaits d’avoir résolu ce bug. Mais, il y a un autre bug évident : c’est la division par 0. On ne peut pas diviser un nombre par 0. Mais l’évaluation de (div 4 0) s’exécutera indéfiniment car (- a b) s’évaluera toujours à 4. Le problème se réduira donc jamais. Ce qui n’est pa conforme à la logique de la récursivité. Nous allons donc résoudre ce bug en retournant une erreur si le second argument est égal à 0. Voici la nouvelle version de div :

> (define (div a b)
     (cond [(zero? b) (error "Division par zéro illégitime.")]
           [(or (zero? a) (< a b)) 0]
           [else (+ 1 (div (- a b) b))]))

Cette fois, nous avons corrigé tous les bugs mineurs. Mais, il serait intéressant de pouvoir également retourner la valeur du reste de la division. Une simple modification de la version précédente nous permet d’y arriver en remarquant que le reste est la dernière valeur du dividende. Voici la nouvelle version de div :

> (define (div a b)
    (define (div-rec a b acc)
       (cond [(zero? b) (error "Division par zéro illégitime.")]
             [(zero? a) (values acc 0)]
             [(< a b) (values acc a)]
             [else (div-rec (- a b) b (+ 1 acc))]))
    (div-rec a b 0))

Cette version est plus difficile que les précédentes mais elle renferme des notions importantes. D’abord, on voit bien que j’ai défini une fonction dans une autre. En Racket, cela est légitime et on parle de définition locale. Alors, pourquoi ai-je eu beoin de faire cette définition ? Je dirai que c’est par pure nécessité.

En effet, jusqu’ici nos fonctions ne retournaient qu’une seule valeur. Pour pouvoir retourner plusieurs valeurs, soit on les accumule dans une liste et o retourne cette liste, mais ce serait encore une valeur, soit utilise l’opérateur values qui permet de retourner plusieurs valeurs. Alors, grâce à cet opérateur, nous sommes capables de retourner le quotient et le reste de la division. C’est bien beau mais cela soulève une autre difficulté : c’est que nous ne pouvons passer values dans la clause récursive, car si nous le faisons, nous nous retrouverons avec une chaîne d’appel de values et ça serait une erreur. Ce que nous voulons, c’est d’utiliser values juste pour retourner les résultats. C’est pourquoi je l’utilise uniquement dans les clauses d’arrêt.

En outre, puisque je dois retourner deux valeurs, il faut qu’à chaque appel de la fonction, ces valeurs soient prêtes à être retournées au cas où une clause d’arrêt serait vraie. Or remarquez que tel que nous avions codé nos clauses récursives, (+ 1 (div (- a b) b)), elles ne permettent de retenir ni la valeur du nouveau dividende ni celle du quotient, cette dernière n’était déterminé qu’à la fin. Il fallait donc modifier cette clause de sorte qu’elle puisse retenir les deux valeurs que nous voulons retourner. Puisque nous sommes obligés de passer le diviseur en argument de la fonction à chaque appel, la fonction a donc au moins un argument. Et comme nous voulons retourner deux autres valeurs, l’appel récursif doit donc accepter trois arguments. Notre fonction initial ne prenant que deux arguments — ce qui est logique — il nous fallait une fonction à trois paramètres. J’aurais bien pu modifier la fonction globale de sorte qu’elle ait trois paramètres mais cela n’aurait pas été logique car la division n’a que deux termes. Voilà pourquoi j’ai défini une fonction locale.

Remarquez que cette fois, j’accumule la valeur du quotient dans la variable acc, directement en argument de l’appel récursif, (div-rec (- a b) b (+ 1 acc)). La variable acc joue donc le rôle d’accumulateur et cette nouvelle manière de définir la clause récursive est appelée tail-récursif (cette traduction est imparfaite vu que c’est un terme purement anglais). Je ne rentrerai pas dans les détails de cette définition mais notez qu’elle est plus efficiente que l’autre manière de définir la clause récursive.

Mais, juste définir une fonction locale ne suffit pas, il faut l’appeler au moins une fois dans le corps de la fonction globale. C’est ce qu’il explique l’expression (div-rec a b 0). La valeur des deux premiers arguments est évidente, celle de l’accumulateur est mise à 0 car 0 est le premier nombre entier et il n’influence pas l’addition.

Vous savez maintenant le pourquoi de cette version sophistiquée. Voyons quelques applications :

> (div 27 4)
\(=>\) 6
3
> (div 18 3)
\(=>\) 6
0

Les définitions locales récursives sont tellement courantes que Racket nous offre un opérateur qui permet de simplifier la version précédente, c’est l’opérateur let. Afin de voir comment l’utiliser, écrivons directement la nouvelle version de div :

> (define (div a b)
     (let div-rec ([a a] [b b] [acc 0])
       (cond [(zero? b) (error "Division par zéro illégitime.")]
             [(zero? a) (values acc 0)]
             [(< a b) (values acc a)]
             [else (div-rec (- a b) b (+ 1 acc))])))

Remarquez que, cette fois, le nom de la fonction est directement passé en argument à let, il n’y a donc plus de define locale explicite. Le second argument de let est la liste des paramètres de la fonction locale div-rec, et à chacun d’eux est associé sa valeur initiale. C’est pourquoi l’appel (div-rec a b 0) a été supprimé. L’opérateur prend le soin de transformer cette nouvelle version en la précédente. C’est ce qu’on appelle en LISP une macro. L’opérateur let est donc une macro plutôt qu’une fonction. Les macros sont d’une octave supérieure aux fonctions, donc nous n’en parlerons dans cette introduction à Racket.

L’élévation à la puissance

Nous allons écrire ici une version simplifiée de l’algorithme que nous avons vu dans le cours d’Arithmétique sur l’élévation à la puissance. Je laisse en exercice la version complète.

On suppose cette fois que nous avons un opérateur multiplication. Voici donc la définition récursive de l’élévation à la puissance : la puissance d’un nombre entier (la base) à un autre (l’exposant) est égal au produit de la base par la puissance de la base à l’exposant qui est égal au précédent exposant moins l’unité.

Soit à déterminer la troisième puissance 5, c’est-à-dire \(5^3\). On procède récursivement comme suit :

  • \(5^3 = 5 \times 5^{(3 – 1)} = 5 \times 5^2\). On a donc réduit le problème à la détermination de \(5^2\).
  • \(5^2 = 5 \times 5^{(2 – 1)} = 5 \times 5^1\). On a donc réduit le problème à la détermination de \(5^1\). Or n’oublions pas le premier facteur 5. On a donc en tout : \(5^3 = 5 \times 5 \times 5^1\).
  • \(5^1 = 5 \times 5^{(1 – 1)} = 5 \times 5^0\). On a donc réduit le problème à la détermination de \(5^0\). Or tout nombre élevé à la puissance 0 est égal à 1. Donc on s’arrête là. Ce qui donne en tout : \(5^3 = 5 \times 5 \times 5 \times 5^0 = 5 \times 5 \times 5\).
  • Finalement, on calcule \(5 \times 5 \times 5\) et on obtient 125, qui est la troisième puissance de 5.

Voici le code de cette fonction :

> (define (puissance base exposant)
    (if (zero? exposant)
        1
        (* base (- exposant 1))))

Et la version tail-récursive avec let :

> (define (puissance base exposant)
    (let rec-puiss ([b base] [e exposant] [acc 1])
      (if (zero? e)
          acc
          (rec-puiss b (- e 1) (* acc b)))))

Remarquez que cette fois la valeur initiale de l’accumulateur est 1 puisque c’est le nombre qui n’a aucune influence sur la multiplication.

Voici quelques exemples d’application :

> (puissance 5 3)
\(=>\) 125
> (puissance 18 0)
\(=>\) 1
> (puissance 2 10)
\(=>\) 1024

 

C’est sur cette fonction que notre introduction à Racket prend fin. Je vous invite à écrire le code de l’algorithme du plus grand commun divseur (algorithme d’Euclide) comme exercice. Dans un prochain intermezzo, je parlerai de la syntaxe générale de Racket comme elle apparaît dans la doc afin de vous faciliter sa consultation.

J’espère que vous avez apprécié cette introduction au merveilleux langage Racket et à la fabuleuse famille des langages LISP. Que les plus curieux cherchent sur Internet l’implémentation de quelques fonctions dans d’autres langages. Ils comprendront que ce n’était pas une prétention quand je disais que la syntaxe de LISP est beaucoup plus simple. Du reste, je ne reporte pas ces implémentations ici pour ne pas allonger ce cours qui l’est déjà suffisamment.

Bon Lisping ! 😉

  •  
    15
    Shares
  • 15
  •  
  •  
  •  
  •  

Poster un Commentaire

avatar
  S’abonner  
Notifier de