11. Le Vrai Langage Scheme
1 Exercice 11.7.1
2 Exercice 11.7.2
3 Exercice 11.7.3
4 Exercice 11.7.4
5 Exercice 11.7.5
6 Exercice 11.7.6
7 Exercice 11.7.7
8 Exercice 11.7.8
9 Exercice 11.7.9
10 Exercice 11.7.10
11 Exercice 11.7.11
6.0.1.11

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...