11. Le Vrai Langage Scheme
1 Exercice 11.7.1
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...
2 Exercice 11.7.2
(define (sans-repetitions L) |
(cond ((null? L) #t) |
((member (car L) (cdr L)) (sans-repetitions (cdr L))) |
(else (cons (car L) (sans-repetitions (cdr L)))))) |
(define (zip . LL) ; LL est une liste non vide de listes de memes longueurs |
(if (null? (car LL)) |
'() |
(cons (map car LL) (apply zip (map cdr LL))))) |
3 Exercice 11.7.3
a) Le diagramme de boîtes et pointeurs dessiné à la page 236 du livre correspond à la liste :
((a) ((a . a) a a) ((a () . a) . a) a) |
Il s’agit bien d’une liste reconnue par list?, puisque le dernier cdr (le plus haut le plus à droite) est vide, représenté par une croix !
b) On obtient à la main le schéma suivant :
c) Attention à la programmation naïve suivante :
(define (nb-doublets x) ; pas de circularite !!! |
(if (not (pair? x)) |
0 |
(+ 1 (nb-doublets (car x)) (nb-doublets (cdr x))))) |
> (nb-doublets '((a) ((a . a) a a) ((a () . a) . a) a)) ; cf b) |
12 ; ok |
> (define d1 (cons (cons 1 2) (cons 1 2))) |
> (nb-doublets d1) |
3 ; ok |
> (define d2 (let ((p (cons 1 2))) (cons p p))) |
> (nb-doublets d2) |
3 ; incorrect ! |
d) En effet, l’architecture d2 ne contient que 2 doublets, il s’agit de :
Il faut donc détecter le partage de doublets. Je vous laisse y réfléchir, sachant que (eq? p q) permet de comparer les adresses en mémoire des doublets p et q, donc de savoir si l’on a déjà visité un certain doublet...
4 Exercice 11.7.4
(define (foo n L) |
(let ((x (+ n 1))) ; réservez si possible les define internes aux fonctions !! |
(define (truc L) |
(if (null? L) |
x |
(cons (+ 1 (car L)) (truc (cdr L))))) |
(truc L))) |
5 Exercice 11.7.5
(define (val0 f) |
(with-handlers ([exn:fail:contract:divide-by-zero? |
(lambda (e) (printf "Erreur : on attendait une fonction unaire !\n") '?)] |
[exn:fail:contract:arity? |
(lambda (e) (printf "Erreur : mauvaise arité !\n") '?)]) |
(f 0))) |
Notez que l’on attrape bien l’exception, ce n’est pas une erreur, l’évaluation n’est pas stoppée ! Attention donc au traitement effectué dans le handler... Vous pouvez remplacer printf par error si le but n’est que proposer votre propre message d’erreur, et déclencher une erreur fatale !
> (list (val0 /) (val0 expt) 2012) |
Erreur : on attendait une fonction unaire ! |
Erreur : mauvaise arité ! |
(? ? 2012) |
6 Exercice 11.7.6
Un peu difficile... L’écriture du module lisp.rkt se lit assez bien. Son provide dit en substance : j’exporte tout de racket sauf la primitive car, et j’exporte aussi ma nouvelle primitive mon-car mais en lui donnant le nom de car. So far so good.
Les choses se compliquent avec la violente syntaxe du #lang. Le fichier essai-lisp.rkt débute par la ligne teintée de mystère et non expliquée dans le livre (on ne peut pas tout faire, hein !) :
#lang s-exp "mon-lisp.rkt" |
and I can only send you to the on-line Racket documentation, ask for the word s-exp. If you feel uncomfortable with all that stuff, please don’t use it. You’ll maybe come back later, who knows ?...
7 Exercice 11.7.7
Les arguments de paramcount ne sont pas évalués !
(define-syntax paramcount |
(syntax-rules () |
((paramcount x ...) (length '(x ...))))) ; attention à la quote ! |
N.B. Pour les macros, je vous conseille la présentation de Robby Findler sur YouTube : Macros Matter.
8 Exercice 11.7.8
La seconde règle syntaxique du $and est indispensable si l’on veut que ($and 1 2 3) donne 3 comme en vrai Scheme. Attention avec les macros récursives à veiller à ce que l’expansion termine !!
(define-syntax $and |
(syntax-rules () |
(($and) #t) |
(($and x) x) |
(($and x y ...) (if x ($and y ...) #f)))) ; macro récursive |
Attention avec or de ne pas calculer deux fois la même quantité ! Ici, (or 1 2 3) donne 1.
(define-syntax $or |
(syntax-rules () |
(($or e) e) |
(($or e1 e2 ...) (let ((v1 e1)) (if v1 v1 ($or e2 ...)))))) |
Le let* s’expanse en une suite de let emboîtés pour simuler le séquencement :
(define-syntax $let* |
(syntax-rules () |
((let* () e ...) (let () e ...)) |
((let* ((x1 v1) (x2 v2) ...) e ...) (let ((x1 v1)) (let* ((x2 v2) ...) e ...))))) |
Ce mécanisme est phénoménal, non ? Le plus beau système de macros du monde :-) Quand même autre chose qu’un #define...
if avec cond, je vous le laisse... Quant au cond avec le else obligatoire :
(define-syntax $cond |
(syntax-rules (else) |
(($cond (else e ...)) (begin e ...)) |
(($cond (test1 e1 ...) c2 ...) (if test1 (begin e1 ...) ($cond c2 ...))))) |
9 Exercice 11.7.9
Au risque d’une complexité un peu élevée si la liste est longue (sinon, on expanse en une boucle do par exemple) :
(define-syntax list-of |
(syntax-rules (: in with) |
((list-of expr : x in L with test) (map (lambda (x) expr) (filter (lambda (x) test) L))))) |
10 Exercice 11.7.10
(define-syntax foo |
(syntax-rules () |
((foo x) (let ((i (+ x 1))) ; i est muet |
(* x 2))))) |
> (define i 2) |
> (foo i) |
4 |
L’expansion de (foo i) au toplevel semble être (let ((i (+ i 1))) (* i 2)) et devrait donner 6, qui serait faux. En effet, la variable i étant muette dans la lambda, elle sera hygiéniquement renommée en autre chose, par exemple j45, auquel cas l’expansion sera (let ((j45 (+ i 1))) (* i 2)), dont la valeur sera bien 4. Les macros de Scheme utilisant define-syntax sont hygiéniques, ce qui permet d’éviter des clash avec les variables de l’utilisateur ! Propre.
11 Exercice 11.7.11
Le let nommé (named let) s’expanse en letrec. Je laisse la parole au R5RS...