Le langage Scheme - Linux Magazine France No 2

Cette série d'articles dont voici aujourd'hui le premier est destinée à présenter le langage Scheme à des personnes ne le connaissant pas. L'accent est mis sur l'accessibilité de la lecture, sans pour autant écarter les concepts importants ou théoriques.

Scheme est 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 AutoCad. Plus récemment, l'éditeur de texte sur le puissant 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 il peut être également utilisé comme un véritable langage de programmation, tant son efficacité à la fois au niveau de la compacité, de la clarté du code et des performances est grande.
Ce mois-ci, nous allons présenter les bases du langage Scheme. Puis, au fur et à mesure, nous élargirons le cercle de nos connaissances. Au début, Scheme vous semblera être " un langage de plus ". Ce n'est que par la suite que nous nous apercevrons de son extraordinaire pouvoir d'expression, de sa grande simplicité et de sa compacité. Scheme procure le même sentiment de liberté que C procura à certains venant de Pascal.
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 d'ici et là certains points importants.

Scheme repose sur la théorie du lambda-calcul non typé. Le lambda-calcul est un formalisme mathématique créé dans les années quarante et dont le but est de formaliser le concept de fonction. Il est la base des nouveaux langages informatiques dits fonctionnels, comme Scheme et ML.
Scheme fut décrit pour la première fois en 1975 par GJ. Susman et GL. Steele. C'est un langage de la famille de Lisp doté d'un extraordinaire pouvoir d'expression. Scheme a été conçu pour être simple et efficace.
Simple parce qu'il est un langage à parenthèses sans presque aucune structure syntaxique. Il n'est pas nécessaire d'apprendre des formes syntaxiques plus ou moins complexes : tout en Scheme (ou presque) s'écrit de la même manière, en utilisant les parenthèses pour structurer le programme. L'accent est mis sur la sémantique, c'est-à-dire le sens des opérateurs, plus que sur leur syntaxe.
Simple aussi parce que tous les objets créés peuvent être manipulés de la même manière : on dit qu'ils sont tous de première classe. Par exemple, il est possible à une fonction de rendre une fonction ou de prendre comme argument une fonction. Il est aussi possible de manipuler " le futur " d'un programme avec les continuations.
Efficace parce que les variables de Scheme sont liées de manière statique : cela permet une meilleure compréhension des programmes, mais surtout une compilation plus efficace.

Programmer en Scheme suppose qu'il faille disposer d'un certain nombre d'outils. Le premier d'entre eux est un interprète Scheme (Les compilateurs Scheme ne nous seront pas très utiles pour l'instant). Il existe un certain nombre d'interprètes Scheme, du plus simple au plus complet. Nous proposons d'utiliser umb-scheme disponible en standard sur la distribution RedHat de Linux. C'est un interprète simple et rapide.
Il existe aussi des outils plus sophistiqués comme DrScheme qui contient un véritable environnement de programmation, STk qui utilise la bibliothèque tk. L'auteur a conçu OpenScheme qui est un compilateur/interprète/débogeur disposant d'une vaste bibliothèque de fonctions, disponible sous Windows et Linux. C'est l'un des seuls environnements Scheme gratuit proposant un déboggeur symbolique intégré.
L'une des dernières normes de Scheme est le Revised5 Report on the Algorithmic Language Scheme ou R5RS. Cette norme étant très récente, beaucoup d'environnements Scheme en sont encore à la R4RS. Nous n'aurons pas besoin pour l'instant des dernières nouveautés !
Il est possible de programmer en Scheme, soit directement sur la ligne de commande de l'interprète, soit par l'intermédiaire d'un fichier que l'on chargera dans l'interprète. Cependant, attention : programmer en Scheme sans un outil d'édition adapté tient du masochisme. En effet, comme nous l'avons dit plus haut, Scheme est un langage à parenthèses sans structure syntaxique. Sans un outil d'édition adapté, on passe plus de temps à compter les parenthèses qu'à réfléchir.
Il existe plusieurs éditeurs de texte sachant traiter les parenthèses. Le plus célèbre est sans doute Emacs, ou Xemacs. Mais il existe aussi jed qui est beaucoup plus petit (donc rapide). Ces éditeurs fonctionnent aussi assez bien dans un environnement Windows.
En général, un programme Scheme est écrit dans un fichier. Ce fichier est donné à l'interprète Scheme qui l'exécute et affiche ses résultats. Lors de nos premiers pas, nous n'aurons pas besoin d'écrire de fichier : nous utiliserons directement la ligne de commande de l'interprète. Comment alors bénéficier de l'aide de l'éditeur Emacs ? C'est très simple. Il suffit de lancer un shell à l'intérieur d'Emacs. Pour cela, lancer Emacs et taper la séquence de touches [ESCAPE], puis [X]. Emacs propose alors une invite en bas de sa fenêtre. Sur cette invite, taper shell, puis [ENTER]. Un shell appara"t à l'écran, avec son invite. Vous pouvez alors taper des commandes usuelles. Nous représenterons le prompt du shell par la lettre Î$'. Taper alors :
$ umb-scheme
Welcome to UMB Scheme, version 3.2 Copyright © 1988, 1996 William R Campbell.>
Ca y est, nous sommes dans l'interprète Scheme. Nous représenterons le prompt de Scheme par la lettre Î>'. Entrez par exemple :
> (+ 1 2)
=> 3
Nous introduirons les réponses de l'interprète par '=>'. En tapant (+ 1 2), on demande à Scheme de calculer (on dit évaluer) 1+2. La réponse est heureusement 3 !
Voilà, nous sommes maintenant parés pour partir à la découverte de Scheme !

Dans cette section, nous allons examiner quelques concepts de base du langage, comme les procédures, les types de données primitifs, la gestion des erreurs et l'alternative.

Avant de décrire succinctement les différent types de données de Scheme, introduisons les procédures. Une procédure ou fonction, est un objet qui peut être appliqué à des arguments. Par exemple, on écrira :
> (+ 1 2)
=> 3
qui signifie appliquer la procédure + aux arguments 1 et 2. On remarquera que Scheme utilise la notation infixe, ce qui signifie que l'opérateur est placé en premier. Cela procure au langage, on le verra, une grande homogénéité dans l'écriture des programmes.
En Scheme, les procédures peuvent avoir 0, 1 ou plusieurs arguments. Certaines procédures ont un nombre fixe d'arguments, d'autres ont un nombre variable d'arguments. C'est le cas de la procédure + qui permet les écritures :
> (+)
=>0
> (+ 1)
=> 1
(+ 1 2 3 4 5 6 7 8 9)
=> 45
Nous verrons plus tard comment définir nos propres procédures, avec un nombre d'arguments fixe ou variable.

Les booléens sont en général le résultat des comparaisons. En Scheme, " vrai " s'écrit #t et " faux " s'écrit #f. Se sont les deux seules valeurs possibles pour les booléens. Faisons un peu d'arithmétique binaire à l'aide des opérateurs booléens :

> (and #t #t)
=> #t
> (and #t #t #f #t)
=> #f
> (or #t #f #t)
=> #t
> (not #t)
=> #f
> (not #f)
=> #t
> (boolean ? #t)
=> #t
> (boolean? 1)
=> #f

Avec ces exemples, on remarque que and et or sont des fonctions avec un nombre d'arguments variable. Quant à not, elle n'accepte qu'un seul argument.
Nous introduisons aussi la notion de fonction prédicat. Ces fonctions retournent un booléen et permettent de savoir si l'argument est d'un certain type. Ainsi la fonction boolean? retourne " vrai " si son argument est #t ou #f, et " faux " dans les autres cas. Tous les types de base de Scheme sont associés à un prédicat. Par convention, le nom des fonctions retournant un booléen se termine par un point d'interrogation.

Les caractères s'écrivent #où x est le caractère souhaité. Par exemple, le caractère Îa' s'écrit en Scheme #.
Nous pouvons écrire :

> (char? #)
=> #t
> (char=? ##)
=> #f
> (char-ci=? ##)
=> #t
Les caractères peuvent principalement être comparés et convertis. La procédure char=? compare deux caractères, en tenant compte de la casse (majuscule, minuscule), alors que char-ci=? est insensible à la casse.
Dans le RxRS sont décrites toutes les autres fonctions relatives aux caractères.

Que se passe-t-il si nous tapons (char=? 1 #) ? Il devrait nécessairement y avoir une erreur signalée parce que la fonction char=? attend deux caractères et elle est appliquée à un entier et un caractère.
Eh bien cette écriture provoque une erreur de la forme :
> (char=? 1 #)
=> Error : wait a character instead of '1' in '(char=? 1 #)'.
Cette erreur provoque l'abandon de tout ce que l'interprète était en train de faire et le retour à l'invite. Notons toutefois que la forme du message d'erreur dépend de l'interprète utilisé.

Les chaînes de caractères s'écrivent entre guillemets. Il existe un certain nombre de fonctions pour les manipuler :

> "une-chaîne"
=> une-chaîne
> (string ###)
=> "abc"
> (string-set! "abc" 0 #)
=> "Xbc"
> (string-get "abc" 2)
=> #
> (string-set ! "ac" 2 #)
=> Error: index '3' out of range in '(string-set! "ac" 3 #)'
> (string=? "abc" "ABC")
=> #f
> (string-ci=? "abc" "ABC")
=> #t
> (string? (string ###))
=> #t

Le dernier exemple montre que les appels aux fonctions peuvent être imbriqués. C'est en fait vrai pour toutes les expressions Scheme, comme nous aurons l'occasion de le voir.

Les nombres s'écrivent pour la plupart naturellement : l'entier 1 s'écrit 1, le nombre réel 1,2.3 s'écrit 1.23. Scheme propose d'autres syntaxes plus ésotériques comme par exemple #b1001 qui représente l'entier binaire 9.
Comme nous le verrons plus loin, Scheme définit une tour des types numériques. Cette spécification lui permet de toujours donner le " meilleur " résultat possible. Ainsi, l'entier 4 divisé par l'entier 3 ne donne pas l'entier 1, comme c'est le cas avec la plupart des autres langages, mais le nombre rationnel 4/3. Ainsi, en Scheme, (4/3)*3 ne s'évalue pas en 3, mais en 4, ce qui est le résultat exact. Vérifions :
> (* (/ 4 3) 3)
=> 4
> (/ 4 3)
=> 4/3
Lorsque l'on dit que Scheme donne toujours un résultat le plus exact possible, vérifions-le encore avec :
> (* 9999999 9999999 9999999 9999999)
=> 9999996000000599999960000001
Cette fois-ci, le résultat a été converti en entier long. Peu de langages sont si soucieux de l'exactitude des résultats , n'est-ce pas ?

L'alternative permet d'effectuer un choix en fonction d'un prédicat. En Scheme, l'alternative s'écrit (if condition alors sinon), où condition, alors, sinon sont des expressions Scheme. La clause sinon peut être omise. Nous pourrions avoir :
> (if #t 1 2)
=> 1
> (if #f 1 2)
=> 2
> (if #f 1)
=> #unspecified
La première écriture peut être lue comme "Si vrai alors retourner 1 sinon, retourner 2 "
Notons qu'en Scheme, toutes les valeurs sont supposées vraies, à l'exception de #f. Ceci est une entorse à l'orthogonalité du langage, mais rend, en pratique, l'écriture bien plus lisible. Nous pouvons donc écrire :
> (if 1 3 4)
=> 3
> (if (not "e") ##)
=> #

Il existe en Scheme une fonction bien pratique : display permet d'afficher tous les objets existants. C'est une fonction dont le paramètre est l'objet à afficher. Par exemple :
(display 123)
123=> #unspecified
123 est l'affichage produit par display. #unspecified est sa valeur de retour.
Pour aller à la ligne après avoir affiché une valeur, on pourra utiliser la fonction newline, comme dans :
(display #t) (newline)
#t=> #unspecified
ou bien :
(display "1234") (newline)
1234=> #unspecified
Remarquons qu'un entier et une cha"ne ne contenant que des chiffres s'affichent de la même manière.
De plus, display est une fonction qui peut prendre des valeurs de n'importe quel type. Nous l'avons illustré avec un entier, un booléen et une cha"ne de caractères. Elle sera donc appelée fonction polymorphe.

Tout langage de programmation permet de donner des noms à des résultats. Sans ce procédé, il serait fastidieux de programmer, car on serait sans cesse obligé de répéter les expressions. C'est la première possibilité d'abstraction d'un langage.
Nommer en Scheme se fait à l'aide de la procédure define :
> (define un-nom 123)
=> #unspecified
Ici, un-nom est le nom que l'on souhaite définir; c'est un symbole. 123 est la valeur de définition.
En Scheme, tous les caractères imprimables mis à part les " blancs " peuvent être utilisés dans un nom, pour peu qu'il commence par une lettre. Scheme ne fait pas la différence entre les majuscules et les minuscules dans les symboles : il est insensible à la casse.
La valeur de retour de define est une valeur spéciale qui signifie qu'elle n'est pas spécifiée. Comme Scheme est un langage fonctionnel, l'évaluation de toutes les expressions doit avoir un résultat. Cependant, dans certain cas dont celui-ci, la valeur de retour n'est pas spécifiée ; #unspecified est alors retourné !
Comment vérifier que un-nom " vaut "maintenant 123 ? Entrons :
> un-nom
=> 123
Que se passe-t-il si on demande la valeur d'un symbole sans l'avoir défini :
> non-définit
=> Error: symbol Înon-définit' is unbounded in Înon-définit'.
La réponse est claire : Scheme n'accepte pas que l'on évalue des noms sans les avoir préalablement définis.

Dans cette section, nous allons apprendre à définir nos propres fonctions. Cette possibilité est très puissante car elle permet d'augmenter sans limite le nombre des fonctions offertes par le langage.
Define est aussi utilisé pour définir les fonctions, en utilisant la syntaxe suivante :
(define (nom param-1 param-2 ... param-m)
expression-1
expression-2
expression-n)
Ici, nom, param-1, param-2, ..., param-m sont des symboles et expression-1, expression-2, ..., expression-n sont des expressions Scheme.
Cette écriture crée une nouvelle fonction dont le nom est nom. Cette nouvelle fonction a m paramètres. Elle aurait tout aussi bien pu n'avoir aucun paramètre. Lorsque l'on applique cette fonction à des arguments, les paramètres prennent la valeur des arguments, puis, les expressions sont évaluées leur ordre dÎécriture. La valeur retournée par la fonction est la valeur de retour de la dernière expression. L'ensemble des expressions forment le corps de la nouvelle fonction.
Définissons une fonction qui retourne la somme de ses deux arguments en les ayant préalablement affiché à l'écran :
(define (somme a b)
(display "argument 1 = ")
(display a)
(newline)
(display "argument 2 = ")
(display b)
(newline)
(+ a b))
=> #unspecified
L'affichage de #unspecified nous indique que la fonction somme a bien été enregistrée. Nous pouvons donc maintenant l'appliquer à des arguments :
> (somme 3 4)
argument 1 = 3
argument 2 = 4
=> 7
Nous obtenons bien ce que nous pressentions. Essayons un appel composé :
> (somme 3 (somme 5 6))
argument 1 = 5
argument 2 = 6
argument 1 = 3
argument 2 = 11
=> 14
Cet exemple est très intéressant car il nous montre la manière dont fonctionne l'interprète Scheme.
Nous appliquons somme à deux arguments, 3 et (somme 5 6). Pour évaluer cette application, l'interprète évalue les trois composantes de cette application, c'est-à-dire le symbole somme, l'entier 3 et l'expression (somme 4 5). L'évaluation du symbole somme retourne la procédure que nous avons définie, l'évaluation de l'entier 3 donne l'entier 3. Enfin, l'évaluation de (somme 5 6), retourne l'entier 11. Mais pour obtenir ce dernier résultat, l'interprète a dû évaluer au préalable (somme 5 6) qui se décompose en l'évaluation de somme de 5 et de 6. Cette sous-évaluation provoque l'affichage des deux premières lignes et retourne l'entier 11. Maintenant que l'interprète dispose des composantes de la première application, il l'évalue, ce qui provoque l'affichage des deux dernières lignes et retourne l'entier 14.
Les affichages effectués avec les fonctions display et newline, nous permettent de conna"tre le fonctionnement de Scheme. Ce sont des fonctions à effets de bord, c'est-à-dire qu'elles modifient l'état du système, l'écran en l'occurrence.
Mode d'évaluation de Scheme

D'après la section précédente, lorsque l'interprète évalue une application, il évalue en premier les composantes de cette application, c'est-à-dire la procédure, puis les arguments. Avec ces résultats intermédiaires, il effectue alors l'application proprement dite : on dit que Scheme est en mode applicatif (évaluation préalable des arguments). D'autres langages sont dit en mode normal car ils n'évaluent pas les arguments au préalable. Les langages en mode normal sont aussi appelés langages paresseux, car ils n'effectuent les évaluations que lorsque c'est nécessaire.
Considérons par exemple l'écriture suivante :
(if (and #t #t)
(somme 1 2)
(somme 3 4))
argument 1 = 3
argument 2 = 4
argument 1 = 1
argument 2 = 2
=> 3
Nous constatons que tous les calculs intermédiaires ont été effectués, à savoir (and #t #t) qui retourne #t, (somme 1 2) et (somme 3 4). Ceci est conforme à ce que nous attendions, car Scheme est en mode applicatif, c'est-à-dire qu'il évalue les arguments au préalable.
Mais nous constatons aussi que le calcul de (somme 3 4) aurait pu être évité parce que son résultat n'est pas utilisé. Un langage en mode normal, (ce qui signifie qu'il n'effectue les évaluations que lorsque cela est nécessaire) , dans cet exemple, n'aurait évalué que (and #t #t) et (somme 1 2).
Scheme est en mode applicatif, comme la plupart des autres langages, car les interprètes et les compilateurs sont plus faciles à programmer et plus efficaces.

Dans cet article, nous avons introduit le langage Scheme. Nous avons commencé par indiquer qu'il ne faut jamais programmer en Scheme sans un éditeur de texte adapté. Nous avons proposé différents environnements de programmation Scheme.
Puis nous avons décrit les bases du langage, notamment les fonctions, les types de base, la gestion des erreurs et l'alternative. Puis nous avons succinctement parlé des possibilités de nommer des expressions qui existent en Scheme.
Enfin, nous avons défini notre première fonction. Elle nous a permis de constater la manière avec laquelle Scheme évalue les expressions. On en a déduit que Scheme est en mode applicatif.
Dans un prochain numéro, nous décrirons les structures de données composées, la définition des procédures et d'autres structures de contrôle.
Nous montrerons aussi pourquoi il est nécessaire que le langage Scheme possède des formes spéciales, comme define.

Avec la participation de Fernand Boéri et
Nat Makarevitch
Guilhem de Wailly gdw@linux-kheops.com

Réference
Structure et Interprétation des programmes
informatiques - H. Abelson, GJ. Sussman - InterEdition

Revised4 Report on the Algorithmic Language Scheme
W. Clinger, J. Rees
ftp://ftp.nj.nec.com/pub/kelsey

Editeur surpuissant du GNU, avec un mode
Scheme Xemacs SUN
http://www.xemacs.org

Version améliorée de emacs.
Ntemacs - J.Voelkerhttp
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'autre 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 editeur intégré.
OpenScheme - G. de Wailly
http://www.linux-kheops/netwave/osm

L'environnement de programmation de l'auteur comprenant un interprète, un compilateur et un déboggeur symbolique. Existe en version libre et commerciale, pour Windows et Linux.

© Copyright 2000 Diamond Editions/Linux magazine France - Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; A copy of the license is included in the section entitled "GNU Free Documentation License".