Résumé

Nous quittons momentanément le monde des fenêtres pour revenir sur un exemple classique d'algorithmique : la réalisation d'une pile en Scheme. Cet article pourra être comparé à l'article sur le langage C du mois précédente de Linux Magazine traitant de la réalisation d'une pile en C. Le lecteur pourra comparer les deux langages en terme d'efficacité de la programmation et d'efficacité du code.

Nous présentons ici trois exemples de réalisation d'une bibliothèque pour gérer des piles, basés sur trois méthodes de programmation différentes : la méthode classique, le passage de message et la programmation orientée objets.

L'environnement OpenScheme est disponible sur le CDROM de Linux Magazine. Il est aussi disponible sur www.open-scheme.com. Cet environnement existe en version libre ou commerciale.

Fonctionnalités

Une pile est une structure de donnée assez simple qui est inspirée des piles d'assiettes. Les actions que l'on peut effectuer sur une pile sont l'empilage d'une assiette au sommet de la pile et le dépilage du sommet de la pile. Cette structure de données est utilisée dans tous nos ordinateurs pour programmer les fonctions des langages impératifs. La pile permet d'associer à chaque appel de fonctions un environnement où sont placés les arguments. Comme cet espace est alloué dynamiquement, la fonction peut être récursive. La pile des ordinateurs est implémentée par le processeur lui-même, donnant des performances optimales.

Voici les fonctionnalités que l'on attend de la bibliothèque :

ï‚· pile-créer(): retourne une nouvelle pile vide.

ï‚· pile?(objet) : retourne vrai si l'objet est une pile, faux sinon.

ï‚· pile-vide?(pile) : retourne vrai si la pile est vide, faux sinon.

ï‚· pile-détruire(pile) : détruit la pile donnée en argument.

ï‚· pile-empile(pile,élément) : place l'élément au sommet de la pile.

ï‚· élément<-pile-dépile(pile) : retourne l'élément au sommet de la pile.

ï‚· pile-affiche(pile) : affiche à l'écran le contenu de la pile.

En Scheme, la destruction de la pile est gérée par le système. Nous n'avons donc pas à nous préoccuper de cette fonction. A première vue, cela ne fait pas une grande différence avec les langages traditionnels comme C, mais en réalité, le fait de s'affranchir des fonctions de destruction enlève une grande partie de la complexité des programmes. En effet, il peut devenir très complexe de libérer correctement des structures de données cycliques. En Scheme, le mécanisme rammasse-miètes (garbage collector) est capable à tout moment de savoir quelles données ne sont plus utilisées, et donc de les libérer. Le programmeur est donc complètement affranchi de cette tache.

Nous présentons ici trois réalisations en Scheme de la pile. La première utilise des objets Scheme standard, la seconde utilise une méthode couramment utilisée en Scheme, par envoi de message, et enfin la troisième utilise le système orienté objets d'OpenScheme.

Réalisation en Scheme

Réalisation de base

La première réalisation utilise du Scheme pur et des objets existants, ici la liste :

; fonction de création
(define (pile:crée)
  (list 'pile))

; fonction prédicat
(define (pile? pile)
  (and (list? objet)
       (eq? (car objet) 'pile)))

; fonction prédicat
(define (pile:vide? pile)
  (null? (cdr pile)))

; fonction d'empilage
(define (pile:empile! pile élément)
  (set-cdr! pile
            (cons élément (cdr pile))

; fonction de dépilage
(define (pile:dépile! pile)
  (set-cdr! pile (cddr pile)))

; fonction retournant le sommet
(define (pile:sommet pile)
  (cadr pile))

; fonction d'affichage
(define (pile:affiche pile)
 (for-each (lambda (donnée)
             (display donnée)
             (display #\space)
             (newline))
            (cdr pile)))

La pile est, dans cette réalisation, une paire formée du symbole pile et des paires constituant la pile. Plus simplement, elle est une liste dont le premier élément est le symbole pile. En Scheme, l'appel (cddr objet) est équivalent à (cdr (cdr objet)) et l'appel (cadr objet) est équivalent à l'appel (car (cdr objet)).

Le nom des fonctions d'empilage et de dépilage est suivi du point d'exclamation qui indique, par convention, que la fonction modifie l'état de la pile.

Les fonctions n'effectuent aucun contrôle des arguments, ce qui n'est pas gênant car les fonctions appelées le font pour nous. Cependant, les messages d'erreur seront affichés par les primitives utilisées et ne seront pas explicites. La fonction pile? va permettre de placer des tests dans les programmes pour vérifier les arguments. Il faut remarquer que toute liste ayant en première position le symbole pile est considérée comme une pile et peut être manipulée par les fonctions relatives aux piles. Cette fonction est assez lente car la fonction list? qu'elle utilise doit parcourir la totalité de la liste avant de décider si c'est une pile.

Test des arguments

Avec le prédicat pile?, nous pouvons renforcer le contrôle des arguments et, en cas d'erreur, afficher des messages plus adéquats :

(define (pile:crée)
  (list 'pile))

; fonction prédicat
(define (pile? pile)
  (and (list? objet)
       (eq? (car objet) 'pile)))

; fonction prédicat
(define (pile:check pile)
  (if (not (pile? pile))
    (error "mauvaise pile `~w'" pile)))

; fonction prédicat
(define (pile:vide? pile)
 (pile:check pile)
  (null? (cdr pile)))

(define (pile:empile! pile élément)
 (pile:check pile)
  (set-cdr! pile
            (cons élément (cdr pile))

(define (pile:dépile! pile)
 (pile:check pile)
 (if (null? (cdr pile))
    (error "la pile est vide"))
  (set-cdr! pile (cddr pile)))

(define (pile:sommet pile)
 (pile:check pile)
 (if (null? (cdr pile))
    (error "la pile est vide"))
  (cadr pile))

(define (pile:affiche pile)
 (pile:check pile)
 (for-each (lambda (donnée)
             (display donnée)
             (display #\space)
             (newline))
            (cdr pile)))

L'inconvénient de placer les tests de cette manière est qu'ils sont toujours actifs et qu'ils dégradent les performances. Lorsque le logiciel utilisant cette bibliothèque sera en production, il est supposé bien testé et ces vérifications ne sont plus nécessaires.

Assertion

OpenScheme propose pour palier cet inconvénient une forme spéciale check qui peut être désactivée en mode production. Lorsqu'elle est active, elle provoque une erreur si l'évaluation de son argument retourne faux. On aura donc :

(define (pile:crée)
  (list 'pile))

; fonction prédicat
(define (pile? pile)
  (and (list? objet)
       (eq? (car objet) 'pile)))

; fonction prédicat
(define (pile:vide? pile)
 (check (pile? pile))
  (null? (cdr pile)))

(define (pile:empile! pile élément)
 (check (pile? pile))
  (set-cdr! pile
            (cons élément (cdr pile))

(define (pile:dépile! pile)
 (check (and (pile? pile))
        (not (null? (cdr pile))))
  (set-cdr! pile (cddr pile)))

(define (pile:sommet pile)
 (check (and (pile? pile))
        (not (null? (cdr pile))))
  (cadr pile))

(define (pile:affiche pile)
 (check (pile? pile))
 (for-each (lambda (donnée)
             (display donnée)
             (display #\space)
             (newline))
            (cdr pile)))

Si le programme est interprété ou compilé avec l'option --ncheck, la forme spéciale check est inactive donc ses arguments le sont pas évalués. Le rôle de la macro check est identique à la macro assert() du langage C.

Utilisation

La bibliothèque de pile que nous avons créée s'utilise simplement :

(define pile (pile:crée))
(pile:affiche pile)
(pile:empile! pile 123)
(pile:affiche pile)
(pile:empile! pile (list 1 2 3 4))
(pile:affiche pile)
(pile:dépile! pile)
(pile:affiche pile)

Le programme affichera :

()
123
(1 2 3 4) 123
123

Ce que l'on remarque tout de suite, en comparant avec le programme en C, c'est que les objets empilés peuvent être de toute nature, et cela, sans complication du code. En fait, nous n'avons absolument pas à nous préoccuper de la mémoire et la seule chose qui nous importe est la construction des objets.

Réalisation par Messages

La première réalisation proposée utilise une structure de données classique. Nous allons maintenant utiliser la programmation par messages pour réaliser la pile.

La programmation par messages est une première approche de la programmation orientée objet. Elle permet de définir des entités informatiques capables de réagir à des messages comportant ou non des arguments. Lorsqu'un message est reconnu, il est traité ; lorsqu'il n'est pas reconnu, il est ignoré. On peut donc utiliser des noms de messages génériques, et les envoyer aux objets, sans savoir si, a priori, ils sauront les traiter.

Voici un exemple de réalisation de la pile par envoi de messages :

; fonction de création
(define (pile:crée)
  ; variable locale : le contenu
  ; de la pile
  (let ([données '()])
    ; valeur de retour : une fonction
    ; représentant l'objet pile
    (lambda (message . arguments)
      ; nombre d'arguments supplémentaires
      (let ([n (length arguments)])
      ; cas selon le message
       (case message
        ; prédicat
       [(vide?)
         (null? données)]
        ; message d'empilage
       [(empile)
         (check (eq? n 1))
         (set! données (cons valeur
                             données))]
        ; message de dépilage
        [(dépile)
         (check (zero? n))
         (check (not (null? données)))
         (set! données (cdr données))]
        ; retourne le sommet
        [(sommet)
         (check (zero? n))
         (check (not (null? données)))
         (car données)]
        ; affiche le contenu de la pile
        [(affiche)
         (check (zero? n))
         (for-each (lambda (donnée)
                    (display donnée)
                   (display #\space))
                   données)
         (newline)]
        ; retourne le nom de l'objet
        [(nom)
         (check (zero? n))
         'pile]))))

; fonction prédicat
(define (pile? objet)
 (and (procedure? objet)
       (eq? (objet 'nom) 'pile)))

Dans cet exemple, la pile est une fonction répondant à des messages. Elle utilise le fait que les fonctions Scheme sont des objets de première classe (comme les autres) et qu'elles sont reliées à l'environnement (les variables visibles) au moment de leur création.

La fonction commence par déclarer la variable locale données qui contient la liste des valeurs dans la pile. Puis elle définit sa valeur de retour qui est une fonction (forme lambda). Cette fonction a au moins un argument, le message, puis des arguments optionnels. Ce qui est intéressant et qui donne au langage Scheme toute sa puissance, c'est que la forme lambda retournée continue de pouvoir accéder à la variable locale donnée.

La fonction de traitement des messages commence par compter le nombre des arguments pour effectuer dans chaque message une vérification. Nous rappelons que si cette fonction est appelée sans argument, le paramètre arguments vaudra la liste vide ; sinon, sa valeur sera la liste de tous les arguments supplémentaires.

Ensuite, nous entrons dans le traitement des messages avec un traitement par cas. Un message est un symbole. Un traitement est effectué en fonction du type de message reçu.

Par rapport à la spécification, nous avons ajouté le message nom qui retourne le nom de l'objet et permet de réaliser la fonction prédicat.

Lorsqu'un message n'est pas reconnu, cela n'est pas considéré comme une erreur : dans ce cas, le message est ignoré et la valeur #unspecified est retournée car elle est la valeur par défaut du case.

Nous avons donc construit une bibliothèque pour les piles. Voila un exemple d'utilisation :

(define pile (pile:crée))
(pile 'affiche)
(pile 'empile 123)
(pile 'affiche)
(pile 'empile! (list 1 2 3 4))
(pile 'affiche)
(pile 'dépile)
(pile 'affiche)

Le programme affichera le même résultat que dans la réalisation précédente.

Cette manière de programmer est assez utilisée en Scheme car elle permet d'avoir une programmation orientée objet à moindre frais. De plus, le code est assez compact, ce qui est une constante dans les programmes en Scheme.

Réalisation par Objets

Notre dernière réalisation pour la pile utilise le système orienté objets d'OpenScheme, OO, basé sur CLOS, le Common Lisp Object System. En utilisant ce système, on bénéficie d'un véritable système orienté objet méta-circulaire permettant la définition de classes, l'héritage, l'agrégation, la définition de méthodes. La documentation d'OO est disponible sur le WEB soit dans les anciens numéros de Linux Magazine (www.linuxmag-france.org), soit sur le site d'OpenScheme (www.open-scheme.com).

Nous proposons la réalisation suivante :

; définition de la classe
(define-class <pile> #f
  [données :initform '()])

; déclaration des fonctions génériques
(define-generic vide?)
(define-generic empile)
(define-generic dépile)
(define-generic sommet)
(define-generic affiche)

; prédicat
(define-method (vide? (pile <pile>))
  (null? (<pile>:données pile)))

; méthode d'empilage
(define-method (empile (pile <pile>) élément)
  (<pile>:données! pile
                   (cons élément
                         (<pile>:données pile))))

; méthode de dépilage
(define-method (dépile (pile <pile>))
  (check (not (vide? pile)))
  (<pile>:données! pile
                   (cdr (<pile>:données pile))))

; retourne le sommet
(define-method (sommet (pile <pile>))
  (check (not (vide? pile)))
  (car (<pile>:données pile)))

; méthode d'affichage
(define-method (affiche (pile <pile>))
  (for-each (lambda (donnée)
             (display donnée)
             (display #\space))
             données)
  (newline))

Nous avons maintenant une nouvelle classe <pile>. Avant d'être définies, les méthodes doivent être déclarées avec la macro define-generic. Cette déclaration doit avoir lieu une seule fois par programme.

Le prédicat <pile>? est défini avec la classe. La méthode d'empilage prend comme argument une pile et un élément dont la classe n'est pas spécifiée. Elle ajoute l'élément à la liste des valeurs. La méthode de dépilage se contente de supprimer la tête de la liste des données, après avoir vérifié que la liste n'est pas vide. De même, la méthode retournant le sommet de la pile vérifie que la pile n'est pas vide. La méthode prédicat vide? retourne vrai si la pile est vide et faux sinon. Enfin, la méthode d'affichage affiche le contenu de la pile.

Une utilisation pourrait être :

(define  pile (build <pile>))
(affiche pile)
(empile  pile 123)
(affiche pile)
(empile  pile (list 1 2 3 4))
(affiche pile)
(dépile  pile)
(affiche pile)

Le programme affichera les mêmes résultats que dans les réalisations précédentes.

Maintenant, on pourrait définir une pile d'entiers exclusivement. Pour cela, il faut définir une nouvelle classe, et surcharger la méthode d'empilage :

; définition de la classe
(define-class <pile-entier> <pile>)

; méthode d'empilage
(define-method (empile (pile <pile-entier>) élément)
  (check (<integer>? élément))
  (next-method))

La classe <pile-entier> hérite des propriétés de la classe <pile> ; elle ne définit pas de nouveaux attributs.

La méthode empile est redéfinie pour la nouvelle classe. Elle contrôle que son argument élément appartient à la classe <integer> en utilisant le prédicat <integer>?. Si l'argument est un entier, la méthode suivante est invoquée ; dans ce cas, ce sera la méthode empile pour la classe <pile>. Les autres méthodes de la classes <pile> sont applicables aux objets de la classe <pile-entier>.

Les auteurs

Guilhem de Wailly, directeur de la société Erian Concept : support, formations, configurations, administration, développements Linux. Environnement OpenScheme.

http://www.erian-concept.com

Pr Fernand Boéri, Professeur à l'Université de Nice - Sophia-Antipolis, membre de l'unité SPORTS du laboratoire I3S, spécialiste en modélisation, évaluation de performances et architectures parallèles.

http://www.i3s.unice.fr

Références

Scheme

 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

Environnements Scheme

 Scm - A. Jaffer
http://www-swiss.ai.mit.edu/~jaffer
La référence des interprètes Scheme. Très petit, rapide, pour beaucoup de plates-formes, extensible.

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

 DrScheme - Rice University
http://www.cs.rice.edu/CS/PLT/
Environnement Scheme libre très avancé.

 ChezScheme - Cadence, Inc
http://www.scheme.com/
Environnement Scheme très performant.

 Inlab Scheme - Inlab Software GmbH
http://www.munich.net/inlab/scheme/
Environnement commercial

 EdScheme, 3Dscheme - Scheme, Inc
http://www.schemers.com/
Environnement de programmation Scheme pour Windows.

 OpenScheme - Erian Concept
http://www.open-scheme.com
Environnement professionnel de programmation Scheme comprenant un interprète, un compilateur et un débogueur symbolique.
Existe en version libre et commerciale, pour Linux, FreeBSD, Solaris, Windows et BeOS, sur systèmes Intel.