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 est 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 s'en est une.

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.