PCPS : errata, compléments et solutions d’exercices
Cette page Web - écrite en Scheme avec la librairie Scribble - contient des compléments, des errata et des solutions d’exercices pour mon livre :
Si vous voyez des erreurs dans le livre, indiquez-les moi SVP...
Dans les sections ci-dessous, un clic sur le titre de la section envoie vers les corrigés ! Le source d’une page HTML comme 17.html se trouve dans 17.scrbl (demandez dans votre navigateur un encodage UTF-8 pour les accents)...
1 Les Expressions Préfixées
Il est important de garder présent à l’esprit que les chapitres 1 à 10 du livre sont rédigés dans un esprit de débutant} en programmation fonctionnelle. Au lieu d’aborder de front le langage Scheme dans sa complexité, c’est un niveau de langage Etudiant avancé qui a été choisi, avec un teachpack [bibliothèque d’enseignement] valrose.rkt].
Pour l’installation du niveau de langage et du teachpack, voir les pages 23-24 et 31 du livre.
(local [(define var val) |
...] |
expr) |
Autre chose à savoir, sur le plan numérique. Le niveau de langage Etudiant avancé considère que la notation avec virgule flottante comme dans 1.75 représente un nombre réel [ou rationnel, c’est pareil !] exact. En conséquence de quoi, 1.75 est absolument identique à 7/4. Par contre #i1.75 est une approximation inexacte de 7/4.
Par contre, en vrai Scheme [à partir du chapitre 11], 1.75 sera inexact et distinct du rationnel exact 7/4.
2 Les Fonctions
Les fonctions forment le coeur du langage Scheme. Puisqu’un nom de fonction est une variable comme une autre, la même primitive define permet de définir un nombre ou une fonction.
printf pour faire afficher le résultat d’un calcul.
check-expect pour vérifier que vous obtenez bien le résultat attendu.
check-within lorsque le résultat comporte une certaine tolérance numérique.
check-error pour vérifier que l’on déclenche bien une erreur sur une certaine donnée.
Exemple :
(define (foo x) |
(cond ((> x 0) (* x 2)) |
((< x 0) (* x 0.45)) |
(else (error 'foo "x vaut 0 !")))) |
|
(printf "(foo -6) vaut ~a\n" (foo -6)) |
(check-expect (foo -6) -2.7) |
(check-within (foo -6) -2.65 0.1) ; à 0.1 près |
(check-error (foo 0) "foo: x vaut 0 !") |
dont l’exécution produit au toplevel :
(foo -6) vaut -27/10 |
Tous les 3 tests ont réussi ! |
3 Construire des Images
La documentation en ligne vous fournira bien d’autres formes d’images et d’opérations sur les images, en plus de celles décrites dans le livre. Ce chapitre traite de la construction d’images fixes, le chapitre 4 proposera de les animer.
4 Animer le Monde
Le teachpack universe offre la possibilité de procéder à une modélisation purement fonctionnelle d’une animation, en mettant l’accent sur la séparation logicielle entre le modèle mathématique du monde, le rendu [la vue] du monde dans une image, et le contrôle de l’animation, en particulier l’interaction avec le clavier et la souris. Ce modèle décentralisé est connu sous le nom de MVC [Modèle-Vue-Contrôleur] et a été popularisé par le langage Smalltalk à la fin des années 1970. Il reste un passage obligé pour les programmeurs Mac/iPhone/iPad avec le système Cocoa d’Apple.
Le modèle mathématique n’est autre que l’ensemble des variables mathématiques [si possible indépendantes] décrivant l’état du système [système <==> monde]. Monde qui sera mis à jour à chaque image à travers une fonction nommée (suivant m) dans le livre. La fonction suivant prend un monde m et retourne le monde suivant.
La vue est une image transformant le monde mathématique en une scène agréable à contempler. Dans le livre, nous avons nommé (dessiner m) la fonction prenant un monde m et retournant l’image correspondante.
La fin du monde est traitée par un prédicat nommé (final? m) dans le livre, prenant un monde m et retournant true ou false suivant que le monde est ou non dans un état final [fin de l’animation].
Enfin, les évènements clavier seront traités par une fonction (clavier m k) où m est un monde dans lequel la touche k a été pressée. Les évènements souris seront quant à eux traités par une fonction (souris m x y evt) où m est un monde dans lequel un évènement souris evt [clic, déplacement, etc] a eu lieu au point (x,y) du canvas.
5 Les Structures
La différence entre une structure et un vecteur [chapitre 12] est le fait que les composantes d’une structure ont des noms, voir l’exercice 1.
Bien comprendre que lorsqu’on utilise define-struct pour définir un type de structure à N champs, Racket définit automatiquement N+2 fonctions : un constructeur, un reconnaisseur et N accesseurs (plus quelques autres, les modificateurs, qui n’appartiennent pas à la programmation fonctionnelle).
La plupart des animations sont gérées par un nombre fini > 1 de variables indépendantes. Par exemple, une balle dans un canvas sera repérée par sa position x,y et son vecteur vitesse dx,dy. Le Monde mathématique sera alors une structure à 4 champs (x,y,dx,dy). A chaque top d’horloge, cette structure sera mise à jour.
6 Programmation par Récurrence
Thème central s’il en est. La programmation itérative elle-même [les boucles] sera vue plus tard comme un cas particulier de récurrence, c’est dire l’importance de celle-ci !!
7 Compléments sur la Récursivité
Tenez compte du fait qu’en Scheme, tout passe par l’appel de fonction, donc la récursivité [ou récurrence] est omniprésente. L’itération elle-même n’est qu’un cas particulier de récursivité : la récursivité terminale. En anglais récurrence se dit induction.
Dans ce chapitre un peu avancé, il est question de trois concepts : liaison statique, fermeture et CPS. La notion de fermeture (en anglais closure) est particulièrement importante, car elle suscite actuellement beaucoup de réflexion dans les autres langages, qui s’y mettent peu à peu, avec plus ou moins de bonheur... Le dernier en date est l’Objective-C d’Apple avec ses blocs et Java-8 avec ses lambdas. Et oui, la programmation fonctionnelle pénètre les masses :-)
8 Les Listes Chaînées
Il s’agit d’une structure de donnée centrale en Scheme. Il suffit de voir que le texte d’une fonction est... une liste !!!
Complément sur l’exportation des structures, à rajouter à la page 218.
Un module peut exporter un type de structure de la manière suivante. Dans le module foo.rkt, j’exporte la structure de triangle:
(define-struct triangle (p1 p2 p3)) |
(provide (struct-out triangle)) |
9 Les Arbres
Le source des fonctions détaillées dans le chapitre 9 du livre se trouvent dans le fichier chap9.rkt.
10 Programmer avec des Arbres
Quelques applications de la notion d’arbre, sans ambition démesurée, mais dont les prolongements peuvent s’avérer fort intéressants et profonds...
11 Le Vrai Langage Scheme
Commençons par corriger les exercices 8.13.18 et 8.13.19 (ERRATUM, mal placés) sur les fonctions d’arité variable qui sont hors de portée du niveau de langage Etudiant avancé !
Exercice 8.13.18
Afin de produire une itération et d’éviter un appel à reverse, la liste est produite directement dans le bon ordre.
(define ($iota n . L) |
(local [(define (iter n last step acc) |
(if (<= n 0) |
acc |
(iter (- n 1) (- last step) step (cons last acc))))] ; de droite à gauche |
(cond ((empty? L) (iter n (- n 1) 1 empty)) |
((empty? (rest L)) (iter n (+ (first L) (- n 1)) 1 empty)) |
(else (iter n (+ (first L) (* (- n 1) (second L))) (second L) empty))))) |
> (iota 4) ; j'en veux quatre à partir de 0 |
(0 1 2 3) |
> (iota 4 2) ; j'en veux 4 à partir de 2 |
(2 3 4 5) |
> (iota 4 2 3) ; j'en veux 4 à partir de 2 espacés de 3 |
(2 5 8 11) |
Exercice 8.13.19
On rappelle que le logarithme de base a du réel x est défini par log(x)/log(a) où log est le logarithme népérien (de base e).
(define (log-base x . L) ; seul l'argument x est obligatoire |
(if (empty? L) |
(log x) |
(/ (log x) (log (first L))))) |
> (log-base 2) |
0.6931471805599453 ; nombre inexact en vrai Scheme ! |
> (log-base 1024 2) ; 1024 = 2^10 |
10.0 |
La fonction minimax est plus délicate, elle utilise map et apply :
(define (minimax . LL) ; LL est une liste de listes |
(apply min (map (lambda (L) (apply max L)) LL))) |
> (minimax '(5 2 9 3 1) '(3 7 -3 5) '(7 0 1 0 12)) |
7 ; <------ (min 9 7 12) |
************** PASSAGE AU VRAI SCHEME **************
En Scheme, les vrais noms des fonctions empty?, first et rest sont respectivement null?, car et cdr, en provenance de LISP. Ce sont elles que nous utiliserons dorénavant. Les nombres comme 0.5 sont inexacts, sans avoir besoin de les préfixer par #i. Donc 5.0 n’est pas 5, ils sont = mais pas equal?. De toutes façons, l’utilisation de = avec une donnée inexacte est absurde... La forme local est encore autorisée mais pas utile en général, on utilise plutôt des define internes. La primitive list? a un coût en O(n), tandis que pair? - qui reconnaît les doublets - travaille en O(1). Enfin, member n’est plus un prédicat, il renvoie #f en cas d’échec, et la portion de liste débutant à l’élément cherché sinon (en Scheme, tout ce qui n’est pas #f est considéré comme vrai dans un test !)...
A partir de maintenant, vous serez dans un fichier débutant par la ligne #lang racket, et qui sera enregistré en tant que langage déterminé par le source, ce qui signifie que le #lang exprimera quel est le langage utilisé [racket puis plus tard racket/gui]. Nous oublions définitivement le niveau Etudiant avancé !
Vous pouvez télécharger les modules adt-pile.rkt, adt-fbf.rkt, adt-file.rkt, et adt-arbre23.rkt. Vous utiliserez un require pour les charger si besoin...
Complément sur l’exportation des structures, à rajouter à la page 218.
Un module peut exporter un type de structure de la manière suivante. Dans le module foo.rkt, j’exporte la structure de triangle:
(define-struct triangle (p1 p2 p3)) |
(provide (struct-out triangle)) |
12 La Mutation
ATTENTION DANGER !
Vous trouverez les codes du chapitre 12 dans le fichier chap12.rkt. Il est conseillé de requérir le module show.rkt pour bénéficier de la macro show bien pratique pour les tests...
13 Le Texte et les Entrées-Sorties
Vous trouverez tous les codes-sources du chapitre 13 dans le fichier chap13.rkt, qui utilise les boucles while et for qui se trouvent dans le module while-for.rkt, et la macro show du module show.rkt. Nous utiliserons dans certaines solutions le module adt-arbre23.rkt... Le script de la page 309 se trouve dans le module mon-script.rkt
A la section 13.3.1, il est question de la fonction format de Racket. Elle est en général suffisante pour construire une chaîne contenant des valeurs Scheme. Cependant, si vous avez besoin d’un affichage de nombres inexacts comme avec le printf de C, il vous faudra utiliser la librairie SRFI-48. Exemple :
> (require srfi/48) ; extension de la fonction format |
> (format "~10,5F" 12.345678901) ; 10 chiffres en tout, dont 5 après la virgule |
" 12.34568" |
ERRATUM : Il faut rectifier dans le livre la ligne 459 de la page 309, en :
(length (filter def? (cadddr x)))
En effet, la véritable structure cachée d’un fichier module est (module xxx yyy (#%module-begin ...)) et non plus le (module xxx yyy ...) d’une ancienne version de Racket. Il faut savoir s’adapter aux changements, et lorsqu’on écrit un livre sur un logiciel très vivant, croyez-moi, c’est... la galère :-)
14 Les Objets et l’API graphique
Les codes-sources du livre sont dans le module chap14.rkt que vous voudrez sans doute télécharger... La doc de l’API graphique de Racket peut être consultée en ligne. Un module utilisant cette API débutera par la ligne:
#lang racket/gui |
Vous pouvez aussi télécharger les modules suivants, qui sont les exemples d’utilisation de l’API graphique développés dans le chapitre 14 du livre:
- api1.rkt, pour la section 14.4.1 (page 319)
- api2.rkt, pour la section 14.4.2 (page 322)
- api3.rkt, pour la section 14.4.3 (page 326)
- api4.rkt, pour la section 14.4.4 (page 329)
- api4-on-char.rkt, (page 333 ligne 188)
- api5.rkt, pour la section 14.4.6 (page 334)
- api5-db.rkt, pour la section 14.4.7 (page 335)
- api5-timer.rkt, pour la section 14.4.8 (page 336)
15 Des Analyseurs Syntaxiques
Vous pouvez télécharger les sources suivants du chapitre 15 : parser1.rkt [section 15-1 et 15-2], parser2.rkt [section 15-3], et parser3.rkt [section 15-4 sur Nano-C].
16 Interprétation d’un Sous-Ensemble de Scheme
Il ne s’agit pas de programmer un interprète en grandeur nature, seulement de pénétrer doucement dans ce qui fait le coeur d’un langage de programmation : les variables, les fonctions, les environnements. Un accent particulier est mis sur le concept de fermeture. Il n’est pas question de listes, seulement de nombres et de booléens. Si besoin, les couples [donc les listes] s’implémentent vite en lambda-calcul sous la forme de fermetures, voir par exemple l’exercice 2.7.10...
Le source de l’interprète MISS incomplet est dans le module chap16-exos.rkt. Les exercices 16.14.2 à 16.14.7 ont pour but de le compléter...
La référence sur l’interprétation de Scheme reste le livre de Christian Queinnec chez ParaCamplus, dont la lecture est de niveau Master Informatique.
Si vous voulez vous amuser à coder en C, je vous conseille de partir du 61c-lisp de Brian Harvey, qui enseigne Scheme à Berkeley University. Regardez juste les définitions des types de base, implantez cons, car, cdr, etc. et collez à mon interprète MISS écrit en Scheme, quitte à remplacer les tables de hash par des A-listes ordinaires. Si vous voulez étudier le source C entièrement commenté d’un vrai système Scheme, regardez le livre Scheme9 from Empty Space de Nils Holm.
17 La prise en Main du Contrôle
Chapitre plus difficile et à utiliser avec parcimonie dans une première étude. Essentiellement, il s’agit de revisiter l’instruction GOTO des anciens langages comme FORTRAN ou BASIC, dans une optique moderne, en manipulant des valeurs de type continuation. Les continuations soft du style CPS avaient été introduites au § 7.2.4 [la technique remonte à Algol-60]. Ce chapitre 17 s’intéresse plutôt aux continuations hard, valeurs de première classe, avec leur constructeur call/cc, popularisé par Scheme, et que l’on commence à trouver dans d’autres langages comme CAML ou Ruby (avec plus ou moins de bonheur). Le langage C propose une construction de bas niveau avec son setjmp.
L’instruction GOTO a été fortement décriée par l’école de programmation structurée dans les années 70, mais revient drapée de neuf avec les mécanismes modernes d’exceptions et de continuations, soutenus par des travaux théoriques [lambda-calcul] d’approche souvent ardue...
Le livre termine par la programmation paresseuse. Fera-t-elle sa niche ? Wait and see...
Les codes-sources du chapitre 17 sont dans le fichier chap17.rkt. Vous pouvez aussi telecharger les fichiers amb.rkt, haskell.hs, lazy-racket.rkt, lazy-miss.rkt, et streams.rkt.