Le langage Scheme
Cinquième partie

Par :
Guilhem de Wailly (gdw@erian-concept.com)

avec la participation de :
Fernand Boéri (boeri@unice.fr)

Résumé
Voici le cinquième article d'une série destinée à présenter le langage Scheme..
Scheme est un langage de la famille de Lisp, langage de prédilection de l'intelligence artificielle. Lisp fut utilisé pour définir les premières versions de SmallTalk, l'un des plus fameux langages à Objets. Il a servi aussi à programmer des composantes d'AutoCad. Plus récemment, l'éditeur de texte surpuissant Emacs est écrit en Lisp.
Scheme est un dialecte de Lisp datant de 1975. C'est un langage alliant simplicité et efficacité. Il existe de nombreux interprètes et compilateurs performants pour Scheme.
Les domaines d'application de Scheme sont nombreux et variés. Il peut être utilisé dans la phase préliminaire d'un projet, pour tester les algorithmes mis en œuvre ou comme un langage de glue liant plusieurs autres langages, mais encore comme un véritable langage de programmation, tant son efficacité à la fois en ce qui concerne la compacité et la clarté du code que des performances est grande.
Dans cet article nous examinons les différentes formes de let, et les fonctions ayant un nombre d'arguments variable.
Ce document ne saurait être exhaustif : il doit plus être vu comme une introduction générale à Scheme. Le lecteur aura intérêt à consulter la spécification officielle de langage. Notre introduction est plus une promenade soulevant certains points importants. D'excellents ouvrages en français sont donnés dans la bibliographie.
Introduction
Notre apprentissage du langage Scheme commence à toucher à sa fin. Nous avons encore quelques détails à examiner avant d'entamer des aspects plus pratiques, comme la programmation orientée objet ou la programmation graphique. 
Dans cet article, nous allons revenir en détail sur les différentes formes let. Nous verrons ensuite une forme let particulière qui simplifie l'écriture des itérations.
Tout au long de cette description, nous montrerons comment les formes let peuvent être réécrites à l'aide de formes plus simple. En continuant les simplifications au maximum, le lecteur constatera qu'il aboutit toujours à une forme basée sur la forme lambda. Cette possibilité simplifie grandement l'écriture des interprètes et des compilateurs Scheme.
Nous utiliserons alors nos connaissances pour définir une fonction de tri générique d'un vecteur d'éléments, dont les éléments peuvent être ordonnés par une fonction passée en argument. Cette fonction permettra de trier les éléments d'un vecteur dont les éléments seront de n'importe quel type pourvu qu'ils puissent être comparés à l'aide de la fonction de comparaison.
Par la suite, nous montrerons comment définir nos propres fonctions avec un nombre d'arguments variable. Les fonctions ayant un nombre d'arguments variable simplifient souvent les écritures en autorisant les arguments facultatifs.
Les formes let
La forme let a été présentée au cours des articles précédents. Elle permet de définir des variables de manière locale. A cette occasion, nous avons aussi indiqué l'existence des formes let* et letrec, et laissant le soin au lecteur de vérifier leur définition dans la norme du langage.
Nous allons maintenant préciser leur différence. 
Let
La forme let s'écrit :
(let ((var1 exp1)
     (var2 exp2)
      …
     (varn expn))
 corps)
Dans le langage Scheme, les parenthèses et les crochets sont équivalents à condition qu'il y ait correspondance. Il est d'usage d'écrire les formes let de la manière suivante (cette syntaxe est très utilisée au MIT) :
(let ([var1 exp1]
     [var2 exp2]
      …
     [varn expn])
 corps)
Cette forme est utilisée pour définir un certain nombre de variables locales vari avec le résultat de l'évaluation des expressions expi correspondantes.
Le corps du let est ensuite évalué et le résultat de l'évaluation de la dernière expression du corps devient le résultat du let tout entier.
La particularité de let est que les expressions expi ne peuvent pas utiliser les variables vari. On en comprend mieux la raison en constatant que la forme let est une réécriture à base de lambda. En fait :
(let ((var1 exp1)
     (var2 exp2)
      …
     (varn expn))
 corps)
peut être réécrit en :
((lambda (var1 var2 … varn)
   corps)
 exp1 exp2 … expn)
qui est l'application d'une forme lambda à des arguments. Dans ce cadre, on constate que les variables vari sont bien inaccessibles aux expressions expi. On rappelle que Scheme fonctionne en mode applicatif, c'est à dire que les arguments sont évalués avant l'appel effectif  à la fonction.
Par exemple:
> (let ((a 4) (b -3))
    ; corps du premier let
    (let ((a-au-carre (* a a))
          (b-au-carre (* b b)))
       ; corps du second let
       (+ a-au-care b-au-carre)))
=> 25
Ce qui se réécrit en :
((lambda (a b)
  ; corps du premier let
 ((lambda (a-au-carre b-au-carre)
     ; corps du second let
    (+ a-au-care b-au-carre))
  (* a a)        ; valeur de a-au-carre
  (* b b)))      ; valeur de b-au-carre
4                ; valeur de a
-3)              ; valeur de b
Let*
La forme let* est construite un peu à la manière du let :
(let* ((var1 exp1)
      (var2 exp2)
       …
      (varn expn))
 corps)
La différence est que cette fois-ci, les expressions expi peuvent utiliser les variables var1, …, vari-1 définies avant. Ceci s'explique en constatant que la forme let* est une simplification syntaxique de l'écriture :
(let ((var1 exp1))
 (let* ((var2 exp2)
        …
        (varn expn))
   corps))
Dans cette écriture, on remarque clairement que les expressions exp2 … expn peuvent utiliser la variable var1.
En remplaçant les let* intérieurs de la même manière, on constate que les expressions expi peuvent utiliser les variables var1, …, vari-1.
Par exemple:
> (let* ((a          4)
        (b          -3)
        (a-au-carre (* a a))
        (b-au-carre (* b b)))
   (+ a-au-care b-au-carre))
=> 25
Cette écriture pourrait être réécrite en:
((lambda (a)
  ((lambda (b)
     ((lambda (a-au-carre)
        ((lambda (b-au-carre)
           (+ a-au-care b-au-carre))
         (* b b)))
      (* a a)))
   -3))
4)
Les environnements Scheme savent optimiser ce genre d'écritures de telle sorte que les lambda expressions intérieures sont remplacées par des extension d'environnements plus efficaces en terme de performances.
Letrec
La forme letrec utilise la même syntaxe :
(letrec ((var1 exp1)
        (var2 exp2)
         …
        (varn expn))
 corps)
Dans cette écriture, les expressions expi peuvent utiliser toutes les variables vari à la différence du let* ou seules les variables situées au-dessus peuvent être utilisées.
L'écriture letrec est une simplification syntaxique de l'écriture :
(let ((var1 'unbounded)
     (var2 'unbounded)
      …
     (varn 'unbounded))
 (set! var1 exp1)
 (set! var2 exp2)
 …
 (set! varn expn)
 corps)
On constate que toutes expressions expi peuvent effectivement utiliser les variables vari. La valeur 'unbounded est utilisée ici car Scheme ne donne pas de représentation externe de la valeur non-defini.
Cette écriture n'est vraiment utile que si les expressions sont des fonctions mutuellement référencées, comme dans :
> (letrec ((f (lambda (x) (g (* x 10)))) 
          (g (lambda (a) (* a a))))
   (f 7))
=> 4900
La plupart des implémentations Scheme permettent de remplacer :
(let ()
 (letrec ((var1 exp1)
          (var2 exp2)
           …
          (varn expn))
   corps))
par :
(let ()
 (define var1 exp1)
 (define var2 exp2)
 …
 (define varn expn))
 corps)
Cette écriture est plus naturelle et donc souvent utilisée.
Let nommé
Nous présentons maintenant une autre forme de let permettant l'écriture d'expressions récursives.
Cette écriture permet des constructions très évoluées. Elle s'écrit :
(let variable ((var1 exp1)
              (var2 exp2)
              …
              (varn expn))
 corps)
Dans le corps de l'expression, variable est une fonction à n paramètres qui peut s'appeler récursivement. L'écriture correspondante est :
(letrec ((variable (lambda (var1 var2 … varn)
                     corps)))
 (variable exp1 exp2 … expn))
Réécrivons par exemple la fonction length qui retourne le nombre d'éléments d'une liste :
(define (length list)
 (let loop ([pointeur list]
            [résultat 0])
    (if (null? pointeur)
       résultat
       (loop (cdr pointeur)
             (+ résultat 1)))))
Nous pourrions tenter de donner une réécriture de la forme itérative do :
(do ([var1 init1 exp1]
    [var2 init2 exp2]
    …
    [varn initn expn]
   (stop res)
 corps)
peut être réécrit :
(let loop ([var1 init1]
          [var2 init2]
          …
          [varn initn]
 (if stop
   res
   (begin
     corps
     (loop exp1 exp2 … expn))))
où vari, expi, stop, res et corps sont remplacés tels quels.
Dans la réalité, le remplacement est à peine plus complexe car il doit tenir compte du fait que les expressions expi ainsi que l'expression résultat res sont facultatifs.
Ainsi, nous constatons au fur et à mesure de notre progression, que finalement, le langage Scheme est défini avec peu de choses. La forme lambda vers laquelle aboutissent toutes nos tentatives de réécritures semble bien être la pierre angulaire de ce langage : Souvenons-nous que Scheme est bâti sur un formalisme mathématique appelé le lambda-calcul !
Ces possibilités de réécritures sont importantes car elles simplifient l'écriture d'un interprète ou d'un compilateur Scheme : Dans la pratique, il doit savoir traiter un nombre limité d'expressions parmi lesquelles on trouve define, set! if, lambda, call/cc (dont nous parlerons prochainement) et les applications. Les autres expressions comme do, let, let*, cond, case sont transformées par un pré-processeur lui-même écrit en Scheme.
Exemple
Cet exemple montre une réalisation possible d'une fonction de tri. Ses arguments sont un vecteur dont les éléments sont à trier par rapport à une fonction de comparaison, elle aussi en argument.
Cette fonction montre une utilisation conjointe des formes let, let* et do.
La fonction sort parcourt l'ensemble des éléments du vecteur, du premier au dernier. Elle parcourt alors les éléments à partir du dernier, en comparant avec la fonction compare l'élément courant à l'élément précédent. S'il est plus petit, il est déplacé :
(define (sort vec compare)
 ; test des argumenents
(if (and (vector?    vec)
         (procedure? compare))
   ; variables locales
  (let* ([len   (vector-length vec)]
         [len-1 (- len 1)])
    ; parcourt de premier au dernier
   (let loop-i ([i 0])
    (if (>= i len-1)
       ; la fin est atteinte ; retourner le vecteur
      vec
      (begin
        ; parcourt du dernier vers le courant
       (do ([j len-1 (- j 1)])
           ((<= j i))
         (let ([j-1 (- j 1)])
           ; comparaison
          (if (compare (vector-ref vec j)
                       (vector-ref vec j-1))
             ; plus petit : décalage
            (let ([temp (vector-ref vec j)])
             (vector-set! vec 
                          j
                          (vector-ref vec j-1))
             (vector-set! vec 
                          j-1
                          temp)))))
        ; continuer sur le reste des éléments
       (loop-i (+ i 1))))))
   ; les arguments sont invalides
  #f))
Utilisons cette fonction pour trier des vecteurs :
> (display (sort #(1 3 2 4 6 5 0) <))
 (newline)
=> #(0 1 2 3 4 5 6)
> (display (sort #(1 3 2 4 6 5 0) >))
 (newline)
=> #(6 5 4 3 2 1 0)
> (display (sort #("dsd" "aa" "sde") string>?))
 (newline)
=> #("sde" "dsd" aa")
Ainsi, l'utilisateur peut trier ses propres structures de données avec cette fonction si elles peuvent être ordonnées à l'aide de la fonction de comparaison compare passée en argument qui traduit la relation d'ordre des éléments du tableau.
Fonction à `` arguments variables ''
Le langage Scheme permet de définir facilement des fonctions avec un nombre d'arguments variable.
Cela peut être utile dans les cas suivants :
·	Simplification des appels à une fonction lorsque certains arguments sont rarement nécessaires ;
·	Modification de la signature d'une fonction sans compromettre le code existant ;
·	Le nombre d'arguments ne peut être connu à l'avance.
Nous avons déjà rencontré de telles fonctions. C'est le cas des opérateurs arithmétiques comme +. On a par exemple :
> (+)
=> 0
> (+ 1)
=> 1
> (+ 1 2 3 4)
=> 10
D'autres fonctions, comme display et newline , read-char acceptent aussi un argument facultatif qui est le port d'entrée / sortie.
Une fonction ayant un nombre d'arguments variable est créée avec la forme lambda de la manière suivante :
(lambda (a1 a2 . av) corps)
où a1 et a2 sont des paramètres réguliers et av représente un paramètre qui contiendra la liste des arguments supplémentaires.
Bien sûr, il est possible de définir la fonction avec 0, 1 ou plusieurs paramètres réguliers et les noms des paramètres sont libres.
Nous pouvons aussi utiliser la forme compacte de define où :
(define f (lambda (a1 a2 . av) corps))
représente la même fonction que :
(define (f a1 a2 . av) corps)
Ecrivons une fonction ayant un nombre d'arguments variable. Il s'agit d'une fonction qui calcule la moyenne des arguments avec au moins un argument :
> (define (moyenne premier . autres)
  (let ((somme premier))
    (for-each (lambda (n)
                (set! somme (+ somme n)))
               autres)
    (/ somme (+ 1 (length autres)))))
=> #unspecified
> (moyenne 13)
=> 13
> (moyenne 13 14 15)
=> 14
Pour affiner la détection des erreurs, il serait possible d'ajouter un test dans l'itération qui vérifierait avec number? que n est bien un nombre.
Pour les fonctions dont tous les arguments sont optionnels, on utilisera la forme contractée suivante :
(lambda (. av) corps)
qui peut aussi s'écrire :
(lambda av corps)
On pourrait ainsi définir une fonction qui affiche la valeur de ses arguments et retourne leur nombre avec:
(define (compte . arguments)
 (let loop ([arguments arguments]
            [n         0])
   (if (null? arguments)
     n
     (begin
      (display (car arguments))
      (newline)
      (loop (cdr arguments) (+ 1 n))))))
Ce qu'il faut retenir
Nous avons vu qu'il existe plusieurs formes de let: let, let* et letrec. Elles se différencient par la possibilité d'utilisation des noms des variables locales dans les expressions d'initialisation.
Il existe une forme particulière de let, letrec, qui permet l'écriture d'expressions récursives.
Nous avons montré comment les formes let ainsi que la forme do peuvent être réécrites à l'aide de la forme lambda. Bien que ce ne soit pas le sujet de cette série d'articles, nous constatons que la forme lambda joue un rôle très important dans Scheme.
Enfin, nous avons terminé cet article avec la description de l'écriture des fonctions ayant un nombre d'arguments variable.
L'auteur
Guilhem de Wailly, directeur de la société Erian Concept: support, formation, configuration, administration, développement Linux.
http://www.erian-concept.com
Références
Structure et Interprétation des programmes informatiques
H. Abelson, GJ. Sussman
InterEdition
The Scheme Programming Languages - Ansi Scheme 
R. Kent Dybvig
Prentice Hall
Les langages Lisps - Christian Queinnec
InterEdition
Programmer avec Scheme - J. Chazarin
Thomson Publishing
Revised4 Report on the Algorithmic Language Scheme
W. Clinger, J. Rees
ftp://ftp.nj.nec.com/pub/kelsey
Editeurs de texte et environnements Scheme
Emacs - GNU
http://www.gnu.org
Editeur sur-puisant du GNU, avec un mode Scheme
Xemacs - SUN
http://www.xemacs.org
Version amméliorée de emacs.
Ntemacs - J. Voelker
http://www.cs.washington.edu/homes/voelker/ntemacs.html
Version Windows 95, 98, NT de emacs
Jed - JE. Davis
ftp://space.mit.edu/pub/davis/jed
Petit éditeur reprenant les fonctionnalités de Emacs, mais beaucoup plus petit, avec un mode Scheme.
Scm - A. Jaffer
http://www-swiss.ai.mit.edu/~jaffer/SCM.html
La référence des interprètes Scheme. Très petit, rapide, pour beaucoup de plate-formes, extensible.
Stk - E. Gallesio
http://kaolin.unice.fr
Interprète Scheme avec une interface Objet et une interface TK, plus beaucoup d'autres choses.
Bigloo - M. Serrano
http://kaolin.unice.fr
Compilateur Scheme->C très performant. 
PCScheme - Texas Instrument
ftp://cui.unige.ch/public/pcs/pcscheme.exe
Un très bon environnement de programmation Scheme pour DOS, avec éditeur intégré.
OpenScheme - Erian Concept
http://www.erian-concept/osm
L'environnement professionnel de programmation Scheme comprenant un interprète, un compilateur et un débogueur symbolique. 
Existe en version libre et commerciale, pour Windows et Linux.