Voici le quatriè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 également servi à 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 allons examiner les entrées / sorties, les fonctions de recherche dans les listes et les tables de hachage.
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 du langage. Notre introduction est plus une promenade soulevant certains points importants. D'excellents ouvrages en français sont donnés dans la bibliographie.
Introduction
Nous avons maintenant une bonne connaissance des principes de Scheme.
Dans cet article, nous énumérerons les fonctions relatives aux entrées / sorties proposées. Puis, nous examinerons les fonctions de recherche dans les listes. Nous constaterons que ces fonctions sont suffisantes pour construire de petites bases de données, mais inutilisables au-delà d'une centaine d'enregistrements.
Cela nous conduira à implémenter une bibliothèque de fonctions permettant de réaliser une base de données utilisable jusqu'à plusieurs millier d'enregistrements. Cette bibliothèque est basée sur les tables de hachage.
Argument facultatif
Dans cet article, nous allons rencontrer de nombreuses fonctions ayant un argument facultatif.
Par convention, nous placerons ces arguments entre crochets, comme dans :
(display objet [port])
où port est facultatif. Cela signifie que display peut être invoqué avec un ou deux arguments.
Entrées / sorties
Ouverture, prédicat
L'objet qui dans Scheme permet d'accéder aux fichiers est le port. Un port est crée à partir d'un nom de fichier représenté sous la forme d'une chaîne de caractères. On dispose de deux fonctions élémentaires pour lire et écrire dans un port :
(call-with-input-file fichier proc)
et :
(call-with-output-file fichier proc)
L'argument proc est une fonction à un argument et fichier un nom de fichier. Dans le premier cas, le fichier de nom fichier doit exister sur le disque. Dans le second cas, le résultat n'est pas spécifié si le fichier existe déjà ; cependant, en général, les implémentations de Scheme écrasent le contenu du fichier par le nouveau contenu.
La procédure proc est invoquée avec comme argument, respectivement un port d'entrée ou un port de sortie. Ce port peut être donné comme argument aux fonctions d'entrée sortie pour opérer sur ce port plutôt que sur la console. Le port est automatiquement refermé lorsque l'exécution de proc est terminée.
Le système Scheme définit le port d'entrée courant et le port de sortie courant. Ils sont retournés respectivement par les fonctions :
(current-input-port)
et :
(current-output-port)
Les ports d'entrée / sortie courant ne sont pas modifiés par des appels aux fonctions call-with-input-file et call-with-output-file. Par contre, ils sont modifiés par des appels aux fonctions :
(with-input-from-file fichier proc)
et :
(with-output-to-file fichier proc).
Là, fichier représente un nom de fichier et proc, une fonction sans argument. Lorsque le corps de cette fonction est exécutée, le port courant devient le port correspondant au fichier ouvert. Ainsi les fonctions d'entrée / sortie, comme display, opèrent sur ce nouveau port. Les ports sont automatiquement refermés lorsque l'exécution de proc est terminée.
Pour ouvrir et fermer des fichiers de manière explicite, Scheme propose les fonctions :
(open-input-file fichier)
et :
(open-output-file fichier)
qui retournent un port et :
(close-input-port port)
et
(close-output-port port)
pour refermer ces ports.
Nous disposons des prédicats :
(input-port? objet)
et :
(output-port? objet)
pour vérifier la nature des objets.
Entrée
La fonction :
(read [port])
permet de lire soit de l'entrée courant, soit du port spécifié, un objet Scheme. Cette fonction est très puissante car elle est capable de relire les structures composées, comme les listes et les vecteurs.
Lorsque la fin du fichier est rencontrée sur une opération de lecture, Scheme retourne un objet spécial. Cet objet spécial est passé en argument à la fonction eof-object?, elle retourne #t. Pour tout autre objet, elle retourne #f.
La fonction :
(read-char . [port])
lit un caractère du port courant ou du port spécifié. La fonction :
(peek-char . [port])
retourne le caractère qui serait lu par read-char, mais elle ne le supprime pas du port d'entrée.
La fonction :
(char-ready? . [port])
retourne #t si au moins un caractère est disponible sur le port considéré. Enfin, la fonction :
(load fichier)
lit le fichier donné et l'interprète. Le fichier doit contenir des expressions Scheme. Cela permet de construire des programmes modulaires.
Sortie
Les fonctions :
(write objet . [port])
et :
(display objet . [port])
écrivent dans le port spécifié l'objet donné en argument. La différence entre les deux fonctions concerne la représentation des chaînes de caractères. Pour afficher un saut à la ligne, il existe la fonction :
(newline [port])
Enfin, pour écrire un caractère, Scheme propose :
(write caractère . [port])
Exemple
Le premier exemple permet la recopie d'un fichier :
(define (copie source dest)
(call-with-input-file
source
(lambda (in)
(call-with-output-file
dest
(lambda (out)
(write-char (read-char in)
out))))))
La fonction suivante copie un fichier dans un autre en effectuant une conversion des caractères à l'aide de la fonction proc en argument :
> (define (convertit proc source dest)
(with-input-from-file
source
(lambda ()
(with-output-to-file
dest
(lambda ()
(write-char (proc (read-char))))))))
=> #unspecified
On remarque que les ports ne sont pas spécifiés car les ports par défaut sont modifiés le temps de l'appel aux procédures lambda. On pourra convertir les lettres minuscules d'un fichier en majuscules avec :
> (convertit char-upcase "source.txt" "dest.txt")
=> #unspecified
Recherche dans une liste
Extraction
Scheme propose en standard des fonctions de recherche d'informations dans les listes. Ces fonctions sont très pratiques et permettent de réaliser rapidement des mini bases de données.
La fonction Scheme (memq objet liste) retourne la première sous-liste de liste commençant par l'objet objet. Si objet n'est pas trouvé, #f est retourné. La comparaison est effectuée dans memq avec eq?.
On aura par exemple :
> (memq 3 '(1 2 3 4 5))
=> (3 4 5)
> (memq 6 '(1 2 3 4 5))
=> #f
La fonction memv est similaire à memq avec la différence que la comparaison est effectuée avec la fonction eqv?. De même, member fonctionne avec la fonction equal?.
Nous pourrions écrire la fonction memq nous-même avec :
(define (memq objet liste)
(if (eq? objet (car liste))
liste
(memq objet (cdr liste))))
On peut alors imaginer d'écrire une fonction générique de la forme :
(define (generic-mem cmp)
(define (mem objet liste)
(if (cmp objet (car liste))
liste
(mem objet (cdr liste))))
mem)
Cette fonction retourne une fonction de la famille de member, où la fonction de comparaison est l'argument de la fonction générique. Il ne reste plus qu'à implémenter les trois fonctions avec :
(define memq (generic-mem eq?))
(define memv (generic-mem eqv?))
(define member (generic-mem equal?))
Voilà un exemple de l'utilisation de la forme lambda !
Association
L'autre fonction de recherche (assq objet assocs) retrouve une association dans une liste d'associations assocs étant donné objet. Pour la comparaison, assq utilise la fonction eq?. Par exemple :
> (define assocs
'((1 . "un")
(2 . "deux")
(3 . "trois")
(4 . "quatre")))
=> #unspecified
> (assq 1 assocs)
=> (1 . "un")
> (assq 4 assocs)
=> (4 . "quatre")
> (assq 5 assocs)
=> #f
Lorsque l'on se souvient que la structure des environnements Scheme sont des couples (symbole valeur), on imagine mieux l'utilité de cette fonction.
Pour la comparaison, la fonction assv utilise quant à elle la fonction eqv? et assoc utilise equal?.
Le lecteur pourra programmer ces fonctions, en utilisant la forme générique, s'il le souhaite.
Table de hachage
Les fonctions de recherche précédemment citées opèrent sur les listes. Elles sont parfaitement utilisables lorsque le nombre d'éléments ne dépasse pas la cinquantaine. Au-delà, le temps de recherche devient prohibitif et on est amené à utiliser d'autres méthodes d'indexation.
Dans les moteurs de bases de donnée, la méthode d'indexation la plus souvent utilisée repose sur l'algorithme des b-arbres (b-tree). C'est un algorithme complexe qui garanti un temps maximum dans la recherche d'un élément.
Une autre technique couramment utilisée repose sur les tables de hachage, plus simples à réaliser.
L'élément de base d'une table de hachage est toujours un couple constitué d'un index et d'une valeur. Mais au lieu de conserver une liste unique de couples, une table de hachage est un tableau de taille constante contenant des listes de couples.
Les couples de chaque liste ont un point commun : la valeur de hachage de leur index est identique et vaut le numéro de la ligne du tableau.
Ainsi, au lieu de rechercher l'index dans tous les couples, on calcule d'abord sa valeur de hachage qui donne la ligne du tableau concernée. La recherche s'effectue alors dans la liste de couples de cette ligne du tableau.
Il en va de même pour le remplissage de la table : la valeur de hachage est préalablement calculée, ce qui retourne la ligne du tableau concernée. Le couple est alors ajouté dans cette liste.
Nous allons maintenant réaliser notre bibliothèque pour manipuler les tables de hachage.
Une table de hachage est définie comme étant un vecteur. Elle est construite avec :
(define (new-hash size)
(let ((hash (make-vector size)))
(vector-fill hash '())
hash))
On définit aussi un prédicat qui retourne #t si l'objet est une table de hachage :
(define (hash? object)
(vector? object))
Supposons que nous ayons à notre disposition une fonction hash. Cette fonction retourne un entier positif unique à partir d'un objet et d'une valeur maximale. L'entier retourné est le modulo de la valeur maximale. L'objet peut être un symbole, une chaîne de caractère ou un entier.
La fonction permettant de retrouver la valeur associée à un index s'écrit alors :
(define (hash-get index hash)
(let* ((offset (hash object
(vector-length hash)))
(value (assq object
(vector-ref hash offset))))
(if value
(cdr value)
#f)))
Notons la présence de let* qui permet d'utiliser la variable offset dans le calcul de value.
La fonction permettant d'ajouter une association entre un index et une valeur dans la table s'écrit alors :
(define (hash-put object value hash)
(let* ((offset (hash object
(vector-length hash)))
(assocs (vector-ref hash offset))
(old (assq object assocs)))
(if old
(set-cdr! old value)
(vector-set! hash
offset
(cons (cons object value) assocs)))))
Définissons maintenant la fonction hash. Pour une valeur et une longueur, elle retourne un entier constant inférieur à la longueur. Elle peut être réalisée comme suit :
(define (hash index len)
(cond ((symbol? index)
(hash (symbol->string index)))
((string? index)
(let ((somme 0))
(do ((i 0 (+ i 1)))
((>= i (string-length index)))
(set! somme
(+ somme
(char->integer
(string-ref index i)))))
(modulo somme len))))
((integer? index)
(modulo index len))))
Nous disposons maintenant d'une table de hachage permettant de réaliser une base de données. La technique du hachage reste utilisable jusqu'à plusieurs milliers d'enregistrements.
Notons aussi que la table de hachage peut être facilement sauvegardée et restaurée sur disque. Considérons :
> (define h (make-hash 100))
=> #unspecified
> (hash-put 'dupont
(construit-client "Dupont"
"Robert"
26)
h)
=> #unspecified
> …
=> #unspecified
>(with-output-to-file "client.db" (lambda () (write h)))
=> #unspecified
L'utilisation de write est nécessaire pour conserver les chaînes de caractères entre guillemets.
Quittons maintenant notre environnement Scheme, éteignons la machine serveur, allons boire un café :).
Après ce divertissement, revenons aux choses sérieuses, allumons le serveur, ouvrons une session Scheme et tapons :
> (define h #f
=> #unspecified
>(with-input-from-file "client.db" (lambda () (set! h (read)))
=> #unspecified
; notre base est maintenant restaurée!
Il est possible d'imaginer les choses de manière plus complexe, avec une pagination de la base, une répartition sur plusieurs machines, etc.
Guilhem de Wailly
Directeur de la société Erian Concept spécialiste Linux
Créateur de OpenScheme pour Linux et Windows
http : // www.erian-concept.com/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