7. Autres formes pour les procédures

7.1 $\Lambda$

7.1.1 $\lambda$ -expression

En fait, les langages de la famille de Scheme ont été créés par des chercheurs qui travaillaient sur la notion mathématique de fonction au moyen de la théorie du $\lambda$ -calcul, évoquée au chapitre 1. La notation de la définition d'une fonction qui à x fait correspondre, par exemple, x . x, est la suivante :

$x \to x . x$

Scheme, à la suite du $\lambda$ -calcul, possède une notation équivalente :

(lambda (x) (* x x)) 92 97

Cette expression, qui est une forme spéciale nommée lambda , décrit une procédure parfaitement utilisable comme celles que nous avions vues précédemment :

: ((lambda (x) (* x x)) 3) 9

L'emploi de cette syntaxe nous permet d'utiliser le texte d'une procédure comme une expression banale, ce qui en fait tout l'intérêt. Le texte de la procédure tel qu'en $[\mathcal{A}]$ est appelé une lambda-expression ( $\lambda$ -expression).

La forme générale d'une $\lambda$ -expression est :

(lambda <liste de paramètres> <corps>)

La liste de paramètres peut prendre plusieurs formes dont les deux principales sont :

(p1 p2 p3 ...) : la procédure accepte un nombre fixe d'arguments ; lors de l'appel de la procédure, la valeur de chaque argument est liée au paramètre correspondant ;
L : la procédure accepte un nombre quelconque d'arguments ; lors de l'appel la suite des arguments est convertie en une liste et cette liste est liée à L.

7.1.2 Nommer une $\lambda$ -expression

Comme pour toute expression, il nous est bien sûr loisible de donner un nom à cette $\lambda$ -expression. Plus précisément, nous pouvons créer une liaison entre une variable nommée carre et la valeur de la $\lambda$ -expression :

: (define carre (lambda (x) (* x x))) 92 97

La variable carre a pour valeur une procédure, nous pouvons l'appliquer à un argument :

: (carre 6) 36

La définition $[\mathcal{B}]$ nous fait enfin apparaître en pleine clarté ce qu'est la valeur d'un objet procédure, évoquée au chapitre 5 : la valeur d'un tel objet, c'est une $\lambda$ -expression.

La syntaxe $[\mathcal{B}]$ est même la vraie façon de définir une procédure, celle que nous avons utilisée jusqu'à présent est une facilité d'écriture :

: (define (carre x) (* x x)) 92 97

Pour transformer la définition de la forme $[\mathcal{B}]$ en forme $[\mathcal{C}]$ la règle est la suivante :

supprimer le mot lambda, la parenthèse ouvrante qui le précède et la parenthèse fermante qui correspond à celle-ci ;
déplacer la parenthèse ouvrante qui précède le nom du premier paramètre devant le nom lié à la $\lambda$ -expression.

À l'inverse, pour passer de la forme $[\mathcal{C}]$ à la forme $[\mathcal{B}]$ il faut procéder ainsi :

déplacer la parenthèse ouvrante qui précède le nom de la procédure devant le nom du premier paramètre ;
écrire derrière le nom de la procédure un espace blanc suivi de « (lambda » ;
écrire la parenthèse fermante qui correspondra à l'ouvrante qui précède « lambda ».

L'écriture des programmes qui réalisent ces transformations sera un exercice délassant pour le lecteur, qui aura remarqué que :

: (cadr '(define (carre x) (* x x))) (carre x) : (cddr '(define (carre x) (* x x))) ((* x x)) : (cdadr '(define (carre x) (* x x))) (x)

7.1.3 `let` et `lambda`

Avec l'aide de let, voici une solution à l'exercice proposé à la fin du paragraphe précédent^7.1 7.1.2 :

Conversion de la forme « define » en forme « lambda »

(define (convertir->lambda definition)
  (let ((nom-proc (caadr definition))
        (L-parm (cdadr definition))
        (corps (cddr definition)))
    (list 'define nom-proc
          (append (list 'lambda L-parm) corps))))

1:=> (convertir->lambda '(define (carre x) (* x x)))
(define carre (lambda (x) (* x x)))

La forme let est un outil commode mais pas une construction fondamentale : on peut obtenir exactement le même résultat en employant lambda :

(define (surface-cercle rayon) (let ((pi 3.14159)) (* pi (carre rayon))))

se transforme facilement en :

(define (surface-cercle rayon) ((lambda (pi) (* pi (carre rayon))) 3.14159))

dont notre programme de transformation donne la traduction :

(define surface-cercle (lambda (rayon) ((lambda (pi) (* pi (carre rayon))) 3.14159)))

C'est plus fondamental mais moins facile à comprendre. Ceci dit, puisque la règle de transformation du let en lambda est un algorithme, rien ne nous interdit de la programmer :

Conversion de la forme « let » en forme « lambda »

(define (let-lambda un-let)
  (let* ((les-liaisons (cadr un-let))  ; \label{lisp:lla}
         (corps (cddr un-let))
         (les-variables (map car les-liaisons))  ; \label{lisp:llb}
         (les-valeurs (map cadr les-liaisons)))  ; \label{lisp:llc}
    (append (list
             (append
              (list 'lambda les-variables)
              corps))
            les-valeurs)))

On observe l'utilisation de let* qui permet d'utiliser en et une liaison établie en .

Appliquons notre nouvelle procédure 7.1.3 à convertir->lambda définie en 7.1.3 :

(let->lambda 
 '(let ((proc (caadr definition))
        (L-parm (cdadr definition))
        (corps (cddr definition)))
    (list 'define proc
          (append (list 'lambda L-parm) corps))))

((lambda (proc l-parm corps) (list 'define proc (append (list 'lambda
l-parm) corps))) (caadr definition) (cdadr definition) (cddr definition))

Cette présentation est peu lisible, beaucoup d'interprètes Scheme nous offrent une procédure pretty-print44 , ou pp41 , qui réalise les indentations souhaitables :

Conversion en forme « lambda » du programme de conversion

(pp (let->lambda 
       '(let ((proc (caadr definition))
              (L-parm (cdadr definition))
              (corps (cddr definition)))
          (list 'define proc
                (append (list 'lambda L-parm) corps))))

((lambda (proc l-parm corps)
   (list 'define proc 
         (append (list 'lambda l-parm) corps)))
  (caadr definition)
  (cdadr definition)
  (cddr definition))

Un exercice profitable pourra être de réécrire les programmes donnés en 7.1.3 et en 7.1.3 en utilisant les possibilités offertes par quasiquote, virgule et arobas (voir 6.6 page ).

7.2 Portée, environnements, fermetures

7.2.1 Portée lexicale

L'introduction de let met en lumière des questions que nos précédents exposés des notions de liaison et d'environnement (2.4 page et 5.2 page ) n'avaient pas traitées complètement. Nous avons dit que l'environnement était l'ensemble des liaisons visibles en un point du programme. Nous avons déjà vu que l'environnement pouvait être modifié par une redéfinition, avec define. Mais avec l'introduction d'un lieur comme let, nous pouvons trouver des situations que les notions acquises jusqu'à présent ne permettent plus de comprendre : il va falloir les étendre et les approfondir. Écrivons par exemple :

(define pi 3.14) 92 97 (define (surface-cercle rayon) (let ((pi 3.14159)) 92 97 (* pi (carre rayon)))) 92 97 pi 92 97 (surface-cercle 1) 92 97

Quelle valeur de $\pi$ va être utilisée pour le calcul défini par la procédure surface-cercle, en $[\mathcal{O}]$ par exemple ? Nous avons dit qu'une liaison créée dans l'environnement global par define était connue en tout point du programme (5.2 page ), mais aussi qu'une liaison créée par let était connue dans le corps (2.10 page ). La règle qui s'applique est celle des parenthèses imbriquées :

pour le calcul $[\mathcal{O}]$ , nous avons besoin de la valeur de la variable pi à la ligne $[\mathcal{M}]$ du programme ;
à partir de cette invocation de pi dans une expression, nous cherchons « en remontant » dans le texte de la procédure (de parenthèse englobante en parenthèse englobante) une liaison qui donne une valeur à pi ;
la première liaison que nous trouvons, celle qui est donc dans la paire de parenthèses la plus interne, nous la prenons pour la valeur de pi ;
si aucune parenthèse englobante ne lie pi, nous regardons l'environnement global : s'il contient une liaison pour pi, nous la prenons, sinon c'est une erreur, pi n'a pas de valeur et le calcul ne peut pas s'effectuer.

Dans cet exemple, nous trouvons un lieur convenable à la ligne $[\mathcal{L}]$ , c'est la valeur qu'il donne qui sera utilisée. Cette règle est très semblable à celle des blocs des langages « à la Algol ». Remarquons que son application se fait uniquement en regardant le texte du programme.

La valeur liée à pi par la ligne $[\mathcal{K}]$ est ignorée dans le corps du let : on dit que la liaison de la ligne $[\mathcal{L}]$ masque celle de $[\mathcal{K}]$ .

Par contre, à la ligne $[\mathcal{N}]$ l'interprète répondra 3.14 parce que de cet endroit la ligne $[\mathcal{L}]$ n'est pas visible, elle est « encapsulée » dans un let.

L'étendue du texte du programme où une liaison est visible est appelée la portée de cette liaison (en anglais scope). En Scheme cette portée est déterminée uniquement par le texte du programme, on dit que la portée est statique ou lexicale.

Les mécanismes du langage qui permettent de contrôler et de limiter la portée des liaisons sont essentiellement let et les lieurs apparentés let* et letrec. Le compilateur que nous utiliserons disposera de moyens supplémentaires : les modules.

Si nous n'avions aucun moyen de limiter la portée des liaisons, c'est à dire si toutes les liaisons étaient visibles de tous les points du programme, l'écriture de grands programmes serait rendue très hasardeuse à cause du risque de réutiliser un symbole déjà affecté à un autre usage, ce qui provoquerait des erreurs très pittoresques.

Dans certains langages la portée d'une liaison dépend des événements survenus lors de l'exécution du programme, on parle alors de portée dynamique.

7.2.2 Plus sur les environnements

La prise en compte de ces nouvelles notions de portée et de masquage d'information nous amène à perfectionner le modèle d'environnement que nous utilisons jusqu'à présent.

Nous avons toujours l'environnement global (Top-level environment) où nous trouvons les liaisons que nous avons définies par une forme define en réponse à l'invite de l'interprète.

Nous avons dit en 2.5.2 page que lors de l'appel d'une procédure, pour la durée de l'évaluation de la $\lambda$ -expression, les valeurs des arguments étaient liées aux noms des paramètres formels. De façon analogue, les liaisons établies dans un let durent le temps de l'évaluation du corps du let (en fait une $\lambda$ -expression).

Mais qu'en est-il des variables libres dans la $\lambda$ -expression ? Les principes de portée lexicale formulés à l'§ précédent stipulent qu'elles auront la valeur qu'elles possédaient, par application de la méthode ci-dessus, au moment de la définition de la $\lambda$ -expression, et non pas une valeur trouvée dynamiquement au moment de l'évaluation :

: (let ((n 10)) ; 92 97 (let ((n 0) ; 92 97 (proc (lambda (i) (* i n)))) (display n) (newline) (proc 2))) 0 20

[ On note la possibilité d'avoir une séquence d'évaluations dans un let, comme un begin implicite . ]

n est libre dans la $\lambda$ -expression proc, et liée dans chacun des let à une valeur différente. Lors de l'appel à proc, n dans le corps de proc vaut bien 10 comme au moment de la définition de proc, alors que dans le corps du let le plus interne n vaut 0.

En effet, rappelons-nous la sémantique du let : au cours des constructions des liaisons, les autres liaisons du même let ne sont pas visibles. En utilisant let* le résultat serait différent, parce que là la définition de proc se ferait en ayant connaissance des liaisons précédentes du let*, notamment celle qui lie n à 0 :

: (let ((n 10)) (let* ((n 0) (proc (lambda (i) (* i n)))) (display n) (newline) (proc 2))) 0 0

Mais alors, comment se rappeler tout cela, garder la trace des liaisons différentes du même symbole selon le contexte ? Ainsi : le système de programmation associe à chaque $\lambda$ -expression un pointeur sur l'environnement au moment de sa définition.

L'association d'une $\lambda$ -expression et d'un pointeur sur son environnement de définition s'appelle une fermeture (closure en anglais). Considérons par exemple l'expression suivante :

: (let ((n 10)) (let ((proc (lambda (i) (* i n)))) (proc 2))) 20

nous pouvons schématiser ainsi la fermeture associée à proc :

**Figure 7.1:** Fermeture
$\includegraphics{../Images/Lambda/fermeture.epsi}$ 59

Reprenons maintenant l'exemple $[\mathcal{P}]$ de la page pour représenter les différents environnements en cause :

: (let ((n 10)) (let ((n 0) (proc (lambda (i) (* i n)))) (proc 2))) 20

**Figure 7.2:** Environnements
$\includegraphics{../Images/Lambda/environnements.epsi}$ 59

La figure ci-dessus illustre ce qui se passe lors de l'évaluation de l'expression précédente : lors de l'élaboration de la liaison entre proc et la fermeture qui contient la $\lambda$ -expression, les liaisons de l'environnement $\mathcal{E}2$ ne sont pas visibles. La valeur de n est trouvée dans $\mathcal{E}1$ .

Ce qui est intéressant c'est que pour tout appel de proc la fermeture gardera cette valeur de n issue de $\mathcal{E}1$ , et que proc n'aura donc jamais besoin d'aller chercher une valeur de n dans l'environnement d'exécution courant. L'établissement d'une telle liaison entre une variable libre dans le corps d'une procédure et une valeur de l'environnement de définition s'appelle une capture de variable libre.

De par la syntaxe de Scheme et les principes de portée lexicale, proc ne pourra être utilisée qu'à l'intérieur de la paire de parenthèses qui enclosent le let le plus externe (ou dans une fermeture qui les contienne).

7.2.3 Modèle d'évaluation avec environnement

Munis de ces nouvelles notions nous pouvons compléter nos principes d'évaluation.

la définition d'une procédure se ramène toujours à la définition d'une $\lambda$ -expression. L'objet-procédure qui est créé est constitué du texte de la $\lambda$ -expression et d'un pointeur sur l'environnement dans lequel la procédure a été définie ;
lors d'un appel de procédure, c'est à dire de l'évaluation de la -expression correspondante, un environnement est créé qui pointe sur l'environnement de définition et :
- les valeurs des arguments sont liées aux noms des paramètres formels correspondants dans le nouvel environnement ;
- nous avons vu qu'un let était une $\lambda$ -expression déguisée : si la $\lambda$ -expression est le corps d'un let, les variables du let sont liées aux valeurs des expressions correspondantes dans le nouvel environnement ;
- les variables libres sont dotées des valeurs figurant dans l'environnement de définition ;
- chaque environnement de définition pointe vers l'environnement de définition de la $\lambda$ -expression englobante, ce jusqu'à l'environnement global (Top-level). Si une variable libre ne trouve pas sa valeur dans l'environnement de définition de la $\lambda$ -expression courante, on la cherche dans celui de la $\lambda$ -expression de niveau supérieur, et ainsi de suite jusqu'à l'environnement global (Top-level). Si on ne trouve toujours pas, c'est une erreur.

Considérons l'exemple $[\mathcal{P}]$ du programme en 7.2.2. La définition de let stipule bien que la construction de la liaison qui associe une $\lambda$ -expression à proc ne peut pas tenir compte des autres liaisons du même let, donc le n qui est défini en $[\mathcal{Q}]$ en 7.2.2 ne peut pas être utilisé et c'est bien celui de l'environnement de niveau supérieur défini en $[\mathcal{P}]$ qui sera pris en considération dans la définition de proc.

7.2.4 `eval`

Nous allons reprendre la procédure écrite en 7.1.3 page pour transformer une définition de procédure de la forme :

(define (<nom proc> <L params>) corps)

en la forme :

(define <nom proc> (lambda (<L params>) corps))

Nous voudrions modifier cette procédure afin qu'elle ne renvoie de la définition passée en argument que la $\lambda$ -expression, c'est à dire un objet procédural exécutable que nous pourrions appliquer à des arguments :

(lambda (<L params>) corps)

Soit extraire->lambda cette nouvelle procédure :

Extraire la $\lambda$ -expression d'une définition de procédure

(define (extraire-lambda definition)
  (let ((L-parm (cdadr definition))
        (corps (cddr definition)))
    (append (list 'lambda L-parm) corps)))

Essayons :

(extraire->lambda '(define (surface-cercle rayon) (let ((pi 3.14159)) (* pi (carre rayon))))) (lambda (rayon) (let ((pi 3.14159)) (* pi (carre rayon))))

Cette $\lambda$ -expression présente toutes les apparences de l'exécutabilité, essayons donc de l'exécuter :

1:=> ((extraire->lambda '(define (surface-cercle rayon) (let ((pi 3.14159)) (* pi (carre rayon))))) 4) *** ERROR:bigloo:eval: Not a procedure - (EXTRAIRE->LAMBDA (QUOTE (DEFINE (SURFACE-CERCLE RAYON) (LET ((PI 3.14159)) (* PI (CARRE RAYON))))))

extraire->lambda produit un résultat qui s'affiche comme une $\lambda$ -expression, mais qui n'est pas reconnu comme tel par notre interprète parce qu'il a été produit comme une liste. Pour que cette liste soit reconnue comme un objet procédural il faut l'évaluer.

Pourquoi cette liste n'a-t-elle pas été évaluée ? Parce qu'elle n'a pas été soumise au système par l'intermédiaire de la « boucle lire-évaluer-imprimer », mais renvoyée comme résultat de l'évaluation d'une expression.

Et, heureusement d'ailleurs, l'évaluateur ne « boucle » pas indéfiniment pour évaluer tous les résultats qu'il produit.

Disposons-nous d'un moyen de « réinjecter » le résultat d'une évaluation dans le système d'évaluation ? Oui, la procédure eval^7.2 va résoudre notre problème :

(eval expression <spécification d'environnement>)

L'argument <spécification d'environnement> (imposé par le R⁵RS [CKR98], mais que Bigloo laisse facultatif) permet de préciser l'environnement dans lequel sera évalué expression ; ce sera une valeur renvoyée par un des trois procédures ci-dessous :

(scheme-report-environment version) renvoie la spécification d'un environnement qui ne contient rien sauf toutes les liaisons définies par la norme du langage (ici [CKR98]) et qui sont soit exigées par la norme, soit facultatives et réalisées dans le système de programmation utilisé. Comme la norme actuelle est le « R⁵RS », version doit valoir 5.
(null-environment version) renvoie la spécification d'un environnement qui ne contient rien sauf les liaisons pour les mots-clés syntaxiques conformes à la norme et qui sont soit exigées par la norme, soit facultatives et réalisées dans le système de programmation utilisé. Comme la norme actuelle est le « R⁵RS », version doit valoir 5.
(interaction-environment) renvoie la spécification d'un environnement qui contient les liaisons définies par le système de programmation utilisé, en général un sur-ensemble des liaisons définies par la norme connu comme « l'environnement prédéfini » (voir 2.4.2.2 page ). Cette procédure permet d'obtenir un environnement où pourront être évaluées des expressions typées dynamiquement par le programmeur.

Par exemple :

1:=> ((eval (extraire-lambda '(define (surface-cercle rayon) (let ((pi 3.14159)) (* pi (carre rayon))))) (interaction-environment)) 4) 50.26544

Maintenant que nous connaissons le modèle d'évaluation avec environnement, chaque fois que nous nous apprêtons à évaluer quelque-chose nous devons nous poser la question « dans quel environnement ? ».

1:=>(define a 20) 1:=> (let ((a 5)) (eval (read) (interaction-environment))) a 20 1:=> (let ((a 5)) (eval (read) (null-environment 5))) a *** ERROR:bigloo:eval: Unbound variable - A #unspecified

7.3 Combiner autrement des $\lambda$ -expressions

7.3.1 Procédures comme valeurs

Nous avons déjà vu un exemple d'emploi d'une procédure comme paramètre, avec la procédure map en 6.3.3 page . Maintenant que nous avons réduit les procédures à un type à peine spécial d'expression, il nous est également loisible d'imaginer de nouvelles combinaisons, par exemple d'écrire des procédures qui renvoient comme valeur une procédure. Ces possibilités ne manqueront pas d'accroître le pouvoir d'abstraction et, partant, d'expression de notre langage favori.

Pour introduire ces notions, nous allons partir d'un exemple de programme de tri.

Le problème du tri consiste, étant donnés un certain nombre d'éléments fournis, par exemple, dans une liste, à les trier selon une relation d'ordre, par exemple si ce sont des nombres en ordre croissant, ou si ce sont des chaînes de caractères en ordre lexicographique^7.3.

7.3.2 Exemple : tri

7.3.2.1 Tri par insertion

L'algorithme de tri que nous allons utiliser pour cet exemple n'est ni le plus élégant ni toujours le plus efficace (il excelle sur des données déjà presque triées). Il est par contre facile à comprendre et à programmer.

Supposons que les données à trier soient les éléments d'une liste L de n éléments :

$L = (e_1\ e_2\ ...\ e_i\ ...\ e_n)$

L'idée est que si la sous-liste $(e_i\ e_{i+1}\ ... e_n)$ est triée, il suffit d'insérer e_i-1 entre les deux éléments qui l'encadrent dans $(e_i\ e_{i+1}\ ... e_n)$ pour que $(e_{i-1}\ e_i\ ...\ e_n)$ soit triée. Comme (e_n) est triée, on peut ainsi définir une procédure récursive :

La procédure tri-insere

(define (tri-insere liste-a-trier)
  (if (null? (cdr liste-a-trier))
      liste-a-trier
      (insere (car liste-a-trier)
              (tri-insere (cdr liste-a-trier)))))

Il faut définir la procédure insere :

La procédure insere

(define (insere elem liste)
  (if (null? liste)
      (list elem)
      (if (< elem (car liste))
          (cons elem liste)
          (cons (car liste)
                (insere elem (cdr liste))))))

Définir les deux procédures au Top-level est acceptable mais inélégant : clairement insere n'a d'usage que localement à tri-insere, il serait plus commode d'en faire une procédure locale, une sous-procédure en quelque sorte :

tri-insere avec insere comme sous-procédure

(define (tri-insere liste-a-trier)

  (define (insere elem liste)
    (if (null? liste)
        (list elem)
        (if (< elem (car liste))
            (cons elem liste)
            (cons (car liste)
                  (insere elem (cdr liste))))))

  (if (null? (cdr liste-a-trier))
      liste-a-trier
      (insere (car liste-a-trier)
              (tri-insere (cdr liste-a-trier)))))

Cette syntaxe avec imbrication de deux formes define est tout à fait légitime, mais on peut lui préférer une notation qui utilise la forme lambda : il suffit de lier le symbole insere à une $\lambda$ -expression définie localement.

Notre procédure de transformation de définition en $\lambda$ -expression nous donne la nouvelle forme de insere (sans oublier le pretty-printer pour que ce soit lisible) :

Conversion de la procédure insere en forme « $\lambda$ -expression »

1:=> (pp
      (convertir->lambda '(define (insere elem liste)
       (if (null? liste)
           (list elem)
           (if (< elem (car liste))
               (cons elem liste)
               (cons (car liste)
                     (insere elem (cdr liste))))))))

(define insere
  (lambda (elem liste)
    (if (null? liste)
        (list elem)
        (if (< elem (car liste))
            (cons elem liste)
            (cons (car liste) (insere elem (cdr liste)))))))

Pour introduire ce code dans la procédure tri-insere nous pourrions penser au lieur let, mais nous allons voir que cela ne marche pas. Remplaçons le define par un let :

(define (tri-insere liste-a-trier)
   (let
      ((insere
        (lambda (elem liste)
           (if (null? liste)
               (list elem)
               (if (< elem (car liste))
                   (cons elem liste)
                   (cons (car liste)
                         (insere elem (cdr liste))))))  ; æomarqueur£Rß£ß
                         ))
      
      (if (null? (cdr liste-a-trier))
          liste-a-trier
          (insere (car liste-a-trier)
                  (tri-insere (cdr liste-a-trier))))))

et essayons :

: (tri-insere '(1 3 2 7 5 8 6 4 5 3 1)) *** ERROR IN #[procedure #x31BF2E] - Unbound variable: insere

Que se passe-t-il ? insere est une procédure récursive qui s'appelle elle-même en $[\mathcal{R}]$ , or cette ligne appartient aux liaisons du let, une zone où justement les liaisons en cours de définition ne sont pas accessibles (voir 2.10 page ). Même let* ne ferait pas l'affaire, puisque la création d'insere ne fait pas appel à une liaison précédente, mais à la liaison en cours d'établissement elle-même.

7.3.2.2 `letrec`

Il existe pour résoudre ce problème la forme spéciale letrec41 destinée à créer des procédures récursives locales, de syntaxe analogue à celle de let :

(letrec (<liaisons>) <corps>)

avec liaisons de la forme :

(p₁ exp₁)

...

(p_k exp_k)

letrec41 enchaîne les opérations suivantes : les p_i sont créés avec des valeurs non spécifiées ; les exp_i sont évaluées dans l'environnement résultant de cet ajout des p_i à l'environnement courant ; chaque p_i reçoit la valeur de exp_i ; le corps est évalué dans l'environnement résultant ; la valeur de la dernière expression du corps est retournée.

Ainsi cela « va marcher » :

tri-insere correct avec letrec

(define (tri-insere liste-a-trier)
  (letrec
    ((insere 
     (lambda (elem liste)
       (if (null? liste)
           (list elem)
           (if (< elem (car liste))
               (cons elem liste)
               (cons (car liste)
                     (insere elem (cdr liste))))))
     ))

  (if (null? (cdr liste-a-trier))
      liste-a-trier
      (insere (car liste-a-trier)
              (tri-insere (cdr liste-a-trier))))))

: (tri-insere '(1 3 2 7 5 8 6 4 5 3 1)) (1 1 2 3 3 4 5 5 6 7 8)

La forme spéciale letrec41 sera employée de préférence pour la définition de sous-programmes. Bien que cela ne soit pas proscrit par la norme, nous éviterons d'utiliser letrec pour définir des variables ordinaires parce que cela risquerait d'introduire des ambiguïtés (voir [Que94] p. 54).

7.3.2.3 Abstraire avec des procédures qui fabriquent des procédures

Nous sommes maintenant munis d'un programme de tri de nombres en ordre ascendant. Il n'est pas très difficile d'imaginer qu'un tri en ordre descendant ressemblerait beaucoup à ce programme. Les prédicats char<? ou char>?, string<? ou string>? permettraient d'adapter ce tri aux caractères ou aux chaînes, sans préjudice de char-ci<? char-ci>? etc. qui permettent de faire des comparaisons insensibles à la casse^7.4.

Pour faire tous ces tris nous pouvons faire des copies du programme et en modifier la ligne 7 pour mettre le bon prédicat. Mais ne serait-il pas plus judicieux de faire faire ce travail fastidieux par un programme ? L'idée serait d'écrire non plus un tri, mais un générateur de programme de tri auquel on passerait en argument le prédicat désiré :

Générateur de tri make-tri-insere

(define (make-tri-insere predicat)
    (letrec 
      ((tri-insere 
         (lambda (liste-a-trier)
            (letrec 
              ((insere 
                 (lambda (elem liste)
                    (if (null? liste)
                        (list elem)
                        (if (predicat elem (car liste))
                            (cons elem liste)
                            (cons 
                                 (car liste) 
                                 (insere elem (cdr liste))))))))
              (if (null? (cdr liste-a-trier))
                  liste-a-trier
                  (insere (car liste-a-trier) 
                           (tri-insere (cdr liste-a-trier))))))))
    tri-insere))

: (define tri-caracteres (make-tri-insere char<?)) : (tri-caracteres '(#\s #\r #\a #\i)) 92 97 (a i r s)

Le programme make-tri-insere accepte en argument le nom du prédicat à utiliser dans l'opération d'insertion et renvoie un objet tri-insere de type procédure (c'est à dire une $\lambda$ -expression) qui attend un argument et que nous pouvons lier à un nom pour usage ultérieur comme en $[\mathcal{S}]$ . Nous pourrions bien sûr utiliser directement cet objet procédural :

: ((make-tri-insere >) '(1 2 7 8 6 4 5 3 1)) (8 7 6 5 4 3 2 1 1)

La définition de ce générateur de tri nous a fait gagner un niveau d'abstraction supérieur : nous possédons virtuellement un tri générique applicable à des données de types différents selon des ordres différents.

Nous pourrions aussi chercher dans notre imagination et dans la littérature d'autres algorithmes de tri et paramétrer notre générateur afin de pouvoir choisir l'algorithme le mieux adapté aux données du moment : le lecteur pourra accomplir cet exercice avec profit.

7.3.3 `let` nommé

La forme letrec41 est souvent utilisé pour définir des boucles itératives mais elle est pour ce faire assez lourde. On pourra lui préférer (quand c'est possible) une variante de let, dite « let nommé ». La forme générale de let nommé est :

(let <identifiant> (<liaisons>) <corps>)

où <liaisons> est de la forme :

(p₁ exp₁)

...

(p_k exp_k)

Cette syntaxe et sa sémantique sont tout à fait semblables à celles du let ordinaire (voir page ), sauf en ceci que identifiant est lié, dans corps, à une procédure dont les paramètres formels sont les variables liées décrites par liaisons et dont le corps est corps. Ainsi l'exécution de corps peut être répétée en invoquant le nom de la procédure identifiant. Cette procédure peut être récursive. Ainsi :

(let boucle ((nombres '(4 -6 1 5 -3))
             (posit-nul '())
             (negat '()))
   (cond ((null? nombres) (list posit-nul negat))
         ((>= (car nombres) 0)
          (boucle (cdr nombres)
                  (cons (car nombres) posit-nul)
                  negat))
         ((< (car nombres) 0)
          (boucle (cdr nombres)
                  posit-nul
                  (cons (car nombres) negat)))))

; ===>  ((5 1 4) (-3 -6))

Dans le cas simple d'un letrec qui déclare une $\lambda$ -expression et qui se contente de l'appeler à la suite, par exemple pour former une boucle, la transformation de letrec en let nommé est simple et nous pouvons la programmer. La procédure de transformation letrec->nom aura comme argument la liste correspondant à la forme letrec, y compris l'invocation de la $\lambda$ -expression, qui doit suivre immédiatement sa définition.

-: le nom de la $\lambda$ -expression deviendra l'<identifiant> du let nommé ;
-: les éléments respectifs de la liste de paramètres de la $\lambda$ -expression et de la liste d'arguments de son invocation seront appariés pour constituer la liste de <liaisons> du let nommé ;
-: le corps de la $\lambda$ -expression sera le corps du let nommé.

Tout ceci s'écrit selon le programme 7.3.3.

Transformation de letrec en let nommé.

(define (letrec->nom le-letrec)
   (let* ((definition (caadr le-letrec))
          (appel (cadddr le-letrec))
          (nom (car definition))
          (les-param (cadadr definition))
          (les-valeurs (cdr appel))
          (le-corps (cddadr definition))
          (les-liaisons (map list les-param les-valeurs)))
      (append (list 'let nom les-liaisons)
              le-corps)))

Le cas général est nettement plus complexe ; tout letrec n'est pas transformable en let nommé.

7.3.4 Itération avec `do`

La récursion terminale permet d'exprimer en Scheme toutes les formes souhaitables d'itération, notamment avec les formes letrec41 et let nommé. Pour ceux qui tiennent néanmoins aux formes des langages impératifs, Scheme offre une forme spéciale do analogue à ses homonymes pascalien ou fortranesque. Sa syntaxe est souvent décriée, même si elle a une certaine logique interne :

(do (<æemph£liaisonsß>)
    (<æemph£testß> . <æemph£résultatß>)
   . <æemph£corpsß>)

où <liaisons> est de la forme :

$\begin{eqnarray*}(<id_1>\ <init_1>\ <step_1>) \\ ... \\(<id_k>\ <init_k>\ <step_k>)\end{eqnarray*}$

<test> . <résultat> constitue le test qui déclenche, s'il dénote le vrai, la sortie de la boucle, suivi de l'évaluation de <résultat>. La notation pointée signifie que <résultat> comporte zéro, une ou plusieurs expressions qui seront évaluées dans l'ordre, la valeur de la dernière étant renvoyée comme résultat.

<corps> est une suite d'expressions évaluées à chaque itération qui forment un bloc begin implicite. La notation pointée signifie que ce bloc comporte zéro, une ou plusieurs expressions qui seront évaluées dans l'ordre.

Lors de l'initialisation de la forme do, des emplacements vierges sont alloués aux variables id_i, les expressions init_i sont évaluées dans un ordre non spécifié et leurs valeurs sont liées aux variables id_i. Puis commence la phase d'itération.

Chaque itération commence par l'évaluation de <test> ; si le résultat est faux le <corps> est évalué, puis les expressions step_i sont évaluées dans un ordre non spécifié et les résultats liés aux variables id_i, et la prochaine itération commence.

Si <test> vaut vrai, alors <résultat> est évalué et la valeur de la dernière expression est retournée comme résultat ; si résultat ne comporte aucune expression, le résultat est #unspecified.

Remarquons que <résultat> et <corps> peuvent ne comporter aucune expression, ce qui simplifie beaucoup la syntaxe des cas simples : si l'on veut juste faire itérer une variable index et modifier une variable indicée par cet index, deux liaisons et un test de fin suffisent, comme par exemple :

(define (fact n)
   (do ((i n (- i 1))
        (f 1 (* i f)))
         ((= i 0) f)))

La boucle do du programme ci-dessus a un corps vide et un résultat limité ... au résultat, le vrai travail est fait dans les expressions step_i.

Guy L. Steele Jr. et Richard P. Gabriel, grands maîtres de Scheme, écrivent dans [SG93] : « La beauté de cette construction est qu'elle permet l'initialisation et l'incrémentation de plusieurs variables sans besoin de mots-clés en pseudo-anglais. Le revers de la médaille, c'est qu'elle utilise comme délimiteurs de nombreux niveaux de parenthèses, et qu'il faut les placer correctement sous peine de comportements étranges ; seul un Lispien endurci peut apprécier une telle syntaxe.

Au-delà du débat sur la syntaxe, il convient de s'interroger et de reconnaître qu'une boucle qui n'incrémente qu'une variable est singulièrement inutile, quel que soit le langage. Presque toujours, une variable est utilisée pour générer des valeurs successives tandis qu'une autre accumule les résultats. Si la syntaxe de la boucle n'incrémente que la première, alors il faut incrémenter « à la main » celle qui accumule avec des affectations (comme en Fortran) ou quelque autre effet de bord. »

Le programme 7.3.4 illustre do et let nommé appliqués au calcul du triangle de Pascal par itération de ligne en ligne.

Construction du triangle de Pascal avec do et let nommé

(module pascal
   (main init))

(define (init argv)
   (pascal (string->number (cadr argv))))

(define (pascal n)
   (do ((i 0 (+ i 1))
        (L '(1) (ligne-suivante L)))
         ((> i n))
      (print L)))
      
(define (ligne-suivante Ligne)
   (let construct ((L Ligne)
                   (L+1 '(1)))
      (if (null? (cdr L))
          (reverse (cons 1 L+1))
          (let ((L+1 (cons (+ (car L) (cadr L))
                           L+1)))
             (construct (cdr L) L+1)))))

7.3.5 $\lambda$ -expressions à plusieurs paramètres : Curry

Il est parfaitement possible de définir des $\lambda$ -expressions à plusieurs paramètres :

(define insere
   (lambda (elem liste)
      (if (null? liste)
          (list elem)
          (if (< elem (car liste))
              (cons elem liste)
              (cons (car liste)
                    (insere elem (cdr liste)))))))

Mais le $\lambda$ -calcul traite plutôt des fonctions à un argument. La définition ci-dessus se transforme facilement en applications de procédures à un argument :

(define insere          ; æomarqueur£Tß£ß
   (lambda (elem)
      (lambda (liste)
         (if (null? liste)
             (list elem)
             (if (< elem (car liste))
                 (cons elem liste)
                 (cons (car liste)
                       ((insere elem) (cdr liste))))))))

La sémantique (et la syntaxe d'appel) diffèrent légèrement pour les deux formes. Le programme $[\mathcal{T}]$ définit une lambda qui attend un argument et renvoie une lambda qui attend elle-même un argument, d'où l'appel :

: ((insere 4) '(1 2 7 8 6 4 5 3 1)) (1 2 4 7 8 6 4 5 3 1)

Cette transformation des $\lambda$ -expressions à plusieurs paramètres en $\lambda$ -expressions à un paramètre s'appelle la « curryfication », du nom du logicien britannique Haskell Curry ; son intérêt est d'introduire de la régularité et de la simplicité dans l'espace des $\lambda$ -expressions.

7. Autres formes pour les procédures

7.1.2 Nommer une -expression

7.1.3 let et lambda

7.2.2 Plus sur les environnements

7.2.3 Modèle d'évaluation avec environnement

7.1.2 Nommer une $\lambda$ -expression

7.1.3 `let` et `lambda`