Le langage Scheme
Deuxième partie

Par :
Guilhem de Wailly (gdw@linux-kheops.com)

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

Résumé
Voici le second 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 glu 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.
Ce mois-ci, nous allons continuer notre découverte de Scheme. Nous allons nous attacher à décrire les objets composés que sont la paire et le vecteur, puis nous verrons quelques structures de contrôle. Nous montrerons ensuite les mécanismes de quotation et la nécessité de l'existence des formes spéciales dans Scheme. Enfin, nous attirerons l'attention du lecteur sur la gestion de la mémoire des langages de la famille de Lisp.
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.
Correctif
Malgré plusieurs relectures attentives, deux erreurs se sont glissées dans l'article précédent, et nous remercions les lecteurs qui nous les ont signalées. 
Page 13 : Il faut lire que Scheme utilise la notation préfixée pour l'application des opérateurs aux arguments, ce qui signifie que l'opérateur est placé en premier.
Page 16 : Dans la description du mode d'évaluation de Scheme, le if est une forme spéciale qui n'évalue pas tous ses arguments. On a donc :
(if (and #t #t)
(somme 1 2)
(somme 3 4))
argument 1 = 1
argument 2 = 2
=> 3
ce qui signifie que la clause négative n'a pas été évaluée.
Introduction
Dans l'article précédent, nous avons présenté les aspects de bases du langage Scheme. Nous avons décrit les objets élémentaires, comme les booléens, les nombres, les chaînes de caractères et les fonctions. Nous avons aussi décrit le nommage des expressions pour terminer par l'ordre d'évaluation des expressions ainsi que la nécessité de formes spéciales.
L'objectif était de permettre au lecteur de commencer à définir ses propres fonctions.
Dans cet article, le lecteur aura la possibilité de construire par lui-même des programmes plus complexes. Nous invitons les lecteurs à programmer et nous sommes entièrement disponibles pour apporter une aide en cas de difficultés.
Les objets composés
Scheme possède deux types d'objets structurés : la paire qui permet de construire des listes et le vecteur.
La paire
La paire rassemble deux objets Scheme entre eux. La fonction cons permet de construire une paire.
Une paire est affichée entre parenthèses. Si le second élément n'est pas une paire, il est séparé du premier par un point. Si le second élément est une paire, il est séparé du premier par un espace, et les parenthèses qui l'auraient entouré sont supprimées :
> (cons 1 2)
=> (1 . 2)
> (cons 1 (cons 2 3))
=> (1 2 . 3)
> (cons (cons 1 2) (cons 3 4))
=> ((1 . 2) 3 . 4)
La fonction car retourne le premier élément d'une paire et la fonction cdr retourne le second élément :
> (car (cons 1 2))
=> 1
> (cdr (cons 1 2))
=> 2
Le prédicat pair? retourne #t (true = vrai) si son argument est une paire et #f (false = faux) sinon :
> (pair? (cons 1 2))
=> #t
> (pair? 1)
=> #f
Il est possible de construire et de manipuler des structures plus complexes à l'aide de ces fonctions élémentaires :
> (define (construit-client nom prénom age)
    (cons nom (cons prénom age)))
=> #unspecified
> (define (nom-de client)
     (car client))
=> #unspecified
> (define (prénom-de client)
     (car (cdr client)))
=> #unspecified
> (define (age-de client)
     (cdr (cdr client)))
=> #unspecified
> (define durand (construit-client 
                 "Durand"
                 "Yves"
                 26))
=> #unspecified
> durand
=> ("Durand" "Yves" . 26)
> (nom-de durand)
=> "Durand"
> (prénom-de durand)
=> "Yves"
> (age-de durand)
=> 26
Voilà de quoi construire des structures de données complexes. 
Il existe aussi deux fonctions utiles set-car! et set-cdr! permettant de modifier respectivement le premier et le second élément d'une paire :
> (define une-paire (cons 1 2))
=> #unspecified
> une-paire
=> (1 . 2)
> (set-car! une-paire 256)
=> #unspecified
> une-paire
=> (256 . 2)
Par convention, les fonctions dont le nom se termine par un point d'exclamation ne sont pas fonctionnelles. C'est à dire qu'elles ont un effet de bord et qu'elles modifient l'état du système. En général, elles retournent #unspecified. De même, par convention, les fonctions dont le nom se termine par un point d'interrogation retournent un booléen.
La liste
Les paires sont aussi utilisées pour construire les listes. Une liste est une paire dont tous les seconds éléments sont des paires et dont le dernier second élément est la paire vide.
Par convention, la paire vide s'écrit '(). Ecrivons :
> '()
=> '()
> (cons 1 '())
=> (1)
> (cons 1 (cons 2 '()))
=> (1 2)
Pour construire aisément des listes, Scheme définit aussi la fonction list :
> (list 1 2 3 4)
=> (1 2 3 4)
Pour accéder au nième élément d'une liste, nous avons la fonction list-ref qui prend comme argument une liste et un index :
> (list-ref (list 1 2 3 4) 0)
=> 1
> (list-ref (list 1 2 3 4) 3)
=> 4
> (list-ref (list 1 2 3 4) 4)
=> Error : index 4 is invalid
De la même manière, pour modifier le nième élément d'une liste, nous avons la fonction list-set! qui prend comme argument une liste, un index et la valeur :
> (define une-liste (list 1 2 3 4))
=> #unspecified
> une-liste
=> (1 2 3 4)
> (list-set! une-liste 0 256)
=> #unspecified
> une-liste
=> (256 2 3 4)
Pour savoir si un objet est une liste, nous avons le prédicat list? :
> (list? une-liste)
=> #t
> (list? (cons 1 (cons 2 3)))
=> #f
Pour savoir si un objet est la paire vide, Scheme définit null? :
> (null? '())
=> #t
On remarque que le prédicat pair? retourne faux s'il est appliqué à la paire vide '().

Il faut noter que les fonctions list-ref et list-set! parcourent à chaque fois les n premiers éléments de la liste et la fonction list? parcourt la totalité de la liste, ce qui peut être très inefficace dans certains cas. Pour améliorer les performances sur des structures de données complexes, Scheme définit les vecteurs.
Le vecteur
Un vecteur permet de regrouper dans une même structure plusieurs objets Scheme. Pour construire un vecteur en connaissant ses composantes, on utilise la fonction vector :
> (vector 1 2 3 4)
=> #(1 2 3 4)
Le vecteur est affiché comme une liste préfixée par un dièse. Lorsque l'on veut construire un vecteur en connaissant seulement le nombre de ses éléments, et éventuellement la valeur initiale de ses composantes, on utilise make-vector :
> (make-vector 3)
=> #(#unbounded #unbounded #unbounded)
> (make-vector 3 123)
=> #(123 123 123)
On remarque que cette fonction accepte un nombre d'arguments variable. Il est possible d'écrire un vecteur directement, comme dans :
> #(1 2 (+ 1 2))
=> #(1 2 3)
la fonction vector-ref permet d'accéder à la nième composante d'un vecteur :
> (vector-ref (vector 1 2 3) 0)
=> 1
> (vector-ref (vector 1 2 3) 2)
=> 3
> (vector-ref (vector 1 2 3) 3)
=> Error : index 3 is invalid
Pour modifier la nième composante, il existe la fonction vector-set! :
> (define un-vecteur (vector 1 2 3 4))
=> #unspecified
> un-vecteur
=> #(1 2 3 4)
> (vecteur-set! un-vecteur 0 256)
=> #unspecified
> un-vecteur
=> #(256 2 3 4)
Enfin, Scheme définit la fonction vector? comme prédicat.
Contrairement aux fonctions relatives aux listes, les fonctions concernant les vecteurs ne parcourent pas les éléments du vecteur pour effectuer leur traitement. Elles procèdent à des accès directs, ce qui les rend très efficaces.
Reprenons notre exemple client avec les vecteurs :
> (define (construit-client nom prénom age)
    (vector nom prénom age))
=> #unspecified
> (define (nom-de client)
     (vector-ref client 0))
=> #unspecified
> (define (prénom-de client)
     (vector-ref client 1))
=> #unspecified
> (define (age-de client)
     (vector-ref client 2))
=> #unspecified
> (define durand (construit-client 
                 "Durand"
                 "Yves"
                 26))
=> #unspecified
> durand
=> #("Durand" "Yves" 26)
Gestion de la mémoire
Dans les sections précédentes, nous avons appris à construire des structures composées avec les fonctions cons, vector, list et make-vector. Construire des structures implique que, quelque part, dans le système, de la mémoire est allouée. 
Nous avons introduit des fonctions d'allocation, mais nous n'avons pas parlé des fonctions de désallocation correspondantes. S'agit-il d'un oubli ?
C'est l'un des aspects les plus intéressant des langages de la famille de Lisp : il n'existe pas de fonctions de désallocation car c'est le système qui se charge de désallouer la mémoire qui n'est plus utilisée. Ce mécanisme est connu sous le nom ramasse miettes ou garbage collector. 
Dans les programmes écrits en C ou dans les langages sans ramasse miettes, le programmeur est responsable de libérer l'espace mémoire qu'il a alloué. Par exemple, le programme C suivant :
void main (void) {
 while (1) malloc (1000);
}
provoquera à coup sûr la saturation de la mémoire, parce que la mémoire allouée par l'appel à la fonction malloc n'est jamais libérée par un appel à la fonction free. Un programme similaire écrit en Scheme serait :
(define (f)
 (make-vector 1000)
 (f))
(f)
Il définit une fonction f qui construit un vecteur à mille composantes et qui se rappelle récursivement indéfiniment. Cependant, à la différence du programme C précédent, celui-ci ne provoquera jamais la saturation de la mémoire : en effet, les vecteurs construits ne sont pas conservés `` quelque part '', et le système Scheme libère au fur et à mesure l'espace qu'ils occupent.
Pour provoquer la saturation de la mémoire en Scheme, il faudrait écrire :
(define liste '())
(define (f)
 (set! liste 
       (cons (make-vector 1000)
             liste))
 (f))
(f)
Dans ce cas, les vecteurs construits sont utilisés pour construire une liste de plus en plus grande, qui, à un certain moment saturera la mémoire.
Le garbage collector permet une programmation très souple, surtout dans les programmes qui fabriquent beaucoup de structures de données dynamiques, comme des arbres ou des listes. C'est un mécanisme que l'on retrouve dans tous les langages de la famille de Lisp, dans SmallTalk, Eiffel et Java.
Structures de contrôle
Dans un langage, les structures de contrôle permettent de contrôler la manière avec laquelle le programme va s'exécuter ou la manière d'organiser le programme et les différentes déclarations.
Scheme est un langage suffisamment puissant pour permettre d'ajouter des structures de contrôle à l'aide des macros : il est par exemple possible de définir la forme while qui n'existe pas en standard. Pour l'instant, la définition des macros sort de notre cadre.
La forme begin
Cette forme est beaucoup utilisée avec le if : en effet, la clause alors et la clause sinon du if n'acceptent qu'une seule expression Scheme. Si on souhaite écrire plusieurs expressions dans l'une ou l'autre des deux clauses, il faut utiliser begin :
> (if condition
   (begin
     alors-1
     …
     alors-n)
   (begin
     sinon-1
     …
     sinon-m))
Variables locales et la forme let
Nous avons vu que pour nommer une variable, nous écrivons :
> (define symbole valeur)
Ainsi, symbole est `` rattaché '' à valeur. Pour définir des fonctions, nous utilisons l'écriture :
> (define (symbole param-1 param-n)
    expression-1
    …
    expression-m)
Pour déclarer des variables dans le corps de la fonction, nous pouvons utiliser define :
> (define (f a b)
     (define c (+ a b))
     (/ c 2))
=> #unspecified
Lorsque nous exécutons cette fonction, la variable c est déclarée et initialisée à a+b. Cette variable est ensuite utilisée pour retourner c/2.
Dans cette écriture, la variable c est définie dans toutes les expressions du corps de la fonction qui suivent la déclaration.
Il existe une manière plus commode pour déclarer un ensemble de variables locales, c'est la forme let :
> (define (f a b)
     (let ((c (+ a b)))
       (/ c 2)))
=> #unspecified
Let possède la structure suivante :
(let ((variable-1 valeur-1)
     (variable-2 valeur-2)
      …
     (variable-n valeur-n))
 expression-1
 …
 expression-m)
Les valeurs ne peuvent pas faire références aux variables dans la forme let. Le lecteur pourra consulter la définition des formes spéciales let* et letrec qui permettent de contourner cette limitation.
La forme cond
Pour effectuer des choix multiples, Scheme définit la forme cond qui s'écrit :
(cond (condition-1 expressions …)
     …
     (condition-1 expressions …))
L'évaluation commence par la première clause jusqu'à la dernière. A la première condition évaluée comme vrai, les expressions sont évaluées et le résultat est le résultat de l'évaluation de la dernière expression. Si une condition est le mot clef else, elle est considérée comme vraie.
Ecrivons :
> (define (nom-type objet)
    (cond ((char? objet)
           (display "caractère")
           (newline))
          ((integer? objet)
           (display "entier")
           (newline))
          ((number? objet)
           (display "nombre")
           (newline))
          ((string? objet)
           (display "chaîne")
           (newline))
          ((or (pair?   objet)
               (vector? objet))
           (display "composé")
           (newline))
          (else
           (display "autre type")
           (newline))))
=> #unspecified
> (nom-type 123.456)
=> "nombre"
> (nom-type '())
=> "autre type"
Le lecteur pourra consulter la définition de la forme spéciale case qui permet aussi d'effectuer des choix multiples avec des constantes.
Quotation, symboles et objets primitifs
Les symboles sont utilisés en Scheme pour associer un nom à une expression, ce qui nous permet d'utiliser le nom ailleurs.
Est-il possible de manipuler les noms en tant que tels, sans les associer à une valeur ? Essayons d'associer à un nom un autre nom :
> (define un-nom un-autre-nom)
=> Error: symbol 'un-autre-nom' is unbounded
Essayons encore :
> (define un-autre-nom 123)
=> #unspecified
> (define un-nom un-autre-nom)
=> #unspecified
> un-nom
=> 123
Nous n'avons pas réussi à manipuler un-autre-nom en tant que symbole. La seule chose que nous ayons fait est de donner une valeur à un-autre-nom pour pouvoir le manipuler sans erreur. Mais alors Scheme a considéré la valeur associée 123 au lieu du symbole lui-même : il a évalué un-autre-nom, et le résultat de cette évaluation est 123.
Pour empêcher cette évaluation, il faut utiliser la quotation qui interdit l'évaluation de Scheme :
> (define un-nom 'un-autre-nom)
=> #unspecified
> un-nom
=> un-autre-nom
La quotation s'écrit en plaçant une apostrophe devant l'expression à quoter. 
Cette fois-ci, nous avons réussi à associer à un-nom le symbole un-autre-nom. D'ailleurs, nous pouvons écrire :
> (symbol? un-nom)
=> #t
Attention, dans cette écriture, ce n'est pas un-nom qui est un symbole, mais le résultat de son évaluation, qui retourne, nous l'avons vu, un-autre-nom.
Toutes les expressions de Scheme peuvent être quotées. Si nous écrivons :
> (+ 1 2 3)
=> 6
Mais si nous utilisons la quotation, nous obtenons :
> '(+ 1 2 3)
=> (+ 1 2 3)
c'est à dire la liste formée du symbole + et des entiers 1, 2 et 3. Nous avons trouvé un autre moyen de construire les listes !
La quotation joue en Scheme un rôle important car elle permet de construire des structures complexes, qui peuvent être exécutables, de manière très simple. Nous commençons à apercevoir la puissance expressive de Scheme, où les données et les programmes ont la même représentation, ce qui donne au langage une puissance expressive hors du commun.
Les objets primitifs, comme les caractères, les chaînes de caractères, les nombres et les booléens n'ont pas besoin d'être quotés pour être utilisés. Cela provient du fait qu'ils sont évalués en eux-mêmes. On peut par exemple écrire :
> (+ '1 '3)
=> 3
ou bien :
> (+ 1 3)
=> 3
Formes spéciales
La forme define
Nous nous sommes aperçus de l'impossibilité de définir un symbole comme étant un symbole avec l'écriture :
> (define un-nom un-autre-nom)
=> Error : symbol un-autre-nom is unbounded
Cela est du au fait que Scheme évalue un-autre-nom, et comme il n'est pas défini, une erreur se produit. Pour remédier à ce problème, nous avons quoté le symbole afin de ne pas l'évaluer.
Mais si Scheme est en ordre applicatif (il évalue tous les arguments avant l'appel effectif à la fonction) et si l'évaluation de un-autre-nom provoque une erreur, pourquoi l'évaluation de un-nom ne provoque pas d'erreur dans :
> (define un-nom (+ 1 2 3))
=> #unspecified
C'est parce que define n'est pas une fonction, mais une forme spéciale. Dans l'écriture précédente, elle reçoit en fait un symbole et une expression. Cette expression est évaluée et le résultat est associé au symbole.
La forme set!
Il existe une autre forme spéciale similaire : il s'agit de set! qui permet de modifier la valeur associée à un symbole :
> (define un-nom 123)
=> #unspecified
> un-nom
=> 123
> (set! un-nom 456)
=> #unspecified
> un-nom
=> 456
C'est une forme spéciale pour les mêmes raisons que define en est une ; il ne faut pas évaluer le premier argument au préalable, mais bien donner à la forme spéciale set! un symbole.
La forme if
Nous connaissons aussi une autre forme spéciale. Les lecteurs de l'article précédent qui ont écrit les exemples proposés s'en sont aperçus : if est aussi une forme spéciale. Le if évalue en premier la condition, et en fonction du résultat de cette évaluation, il évalue l'une ou l'autre de ses clauses. Si le if était une fonction classique, l'écriture des fonctions récursives seraient impossible, comme nous le verrons dans un prochain article.
Ce qu'il faut retenir
Dans ce numéro, nous avons étendu notre connaissance des objets que Scheme peut manipuler. Notamment, nous avons examiné les objets composés que sont les paires et les vecteurs et les fonctions nécessaires à leur manipulation.
Nous avons vu comment construire des listes à l'aide des paires et de la paire vide.
Nous avons décrit le mécanisme de quotation qui permet d'interdire l'évaluation de Scheme. La quotation nous a permis de manipuler les symboles en tant que tels, ce qui nous ouvre les portes du calcul symbolique.
Nous avons mis en évidence l'existence de formes spéciales qui ont un mode d'évaluation différent de celui de fonctions standard.
Enfin, nous avons mis en évidence la gestion de la mémoire de Scheme basée sur le mécanisme de ramasse miettes, ou garbage collector. Avec ce mécanisme, le programmeur ne se préoccupe pas de libérer la mémoire allouée parce que c'est le système qui le fait pour lui.
L'auteur
	Guilhem de Wailly
Docteur en Informatique, et titulaire d'une MIAGE.
Directeur de la société Erian Concept spécialiste Linux.
Créateur de OpenScheme pour Linux et Windows
http://www.linux-kheops.com/erian/osm	
Références
Structure et Interprétation des programmes informatiques - H. Abelson, GJ. Sussman
InterEdition
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
The Scheme Programming Language - R.Kent Dybvig
Prentice Hall
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.linux-kheops/erian/osm
L'environnement de programmation de l'auteur comprenant un interprète, un compilateur et un débogueur symbolique. Existe en version libre et commerciale, pour Windows et Linux.