Scheme 01

Résumé

Voici le premier article d'une série destinée à présenter le langage Scheme. Nous nous attacherons à la clarté de l'exposé, sans pour autant négliger les concepts 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 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 au niveau de la compacité et la clarté du code que 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 en venant de Pascal.

Ce document de 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.

Introduction

Scheme repose sur la théorie du lambda-calcul non typé¹. Le lambda-calcul est un formalisme mathématique créé dans les années 30 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 que Scheme 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 des opérateurs, c'est-à-dire leur sens, plutôt 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.

Les outils

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 serons 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 / debugeur 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ébogueur 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, 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 soumis à 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.
>

Ça 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 !³

Premiers pas...

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

Les fonctions

Avant de décrire succinctement les différents types de donnée de Scheme, introduisons les fonctions. Une fonction est un objet qui peut être appliqué à des arguments. Par exemple, on écrira :

> (+ 1 2)

=> 3

qui signifie appliquer la fonction + 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 fonctions peuvent avoir 0, 1 ou plusieurs arguments. Certaines fonctions ont un nombre fixé d'arguments, d'autres ont un nombre variable d'arguments. C'est le cas de la fonction + qui permet les écritures :

> (+)

=>0

> (+ 1)

=> 1

(+ 1 2 3 4 5 6 7 8 9)

=> 45

Nous verrons plus tard comme définir nos propres fonctions, avec un nombre d'arguments fixe ou variable.

Les booléens

Les booléens sont en général le résultat des comparaisons. En Scheme, `` vrai '' s'écrit #t (pour true) et `` faux '' s'écrit #f (pour false). 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 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

Les caractères s'écrivent #\x où x est le caractère souhaité. Par exemple, le caractère `a' s'écrit en Scheme #\a.

Nous pouvons écrire :

> (char? #\a)

=> #t

> (char=? #\a #\A)

=> #f

> (char-ci=? #\x #\X)

=> #t

Les caractères peuvent principalement être comparés et convertis. La fonction 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.

Les erreurs

Que se passe-t-il si nous tapons (char=? 1 #\a) ? 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 #\a)

=> Error : wait a character instead of `1' in `(char=? 1 #\a)'.

Cette erreur conduit à 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

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 #\a #\b #\c)

=> abc

> (string-set! "abc" 0 #\X)

=> Xbc

> (string-get "abc" 2)

=> #\c

> (string-set ! "ac" 2 #\Z)

=> Error: index `3' out of range in `(string-set! "ac" 3 #\Z)'

> (string=? "abc" "ABC")

=> #f

> (string-ci=? "abc" "ABC")

=> #t

> (string? (string #\a #\b #\c))

=> #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

Les nombres s'écrivent pour la plupart naturellement : l'entier 1 s`écrit 1, le nombre réel 1.23 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é convertit en entier long. Peu de langages sont si soucieux de l'exactitude des résultats, n'est-ce pas ?

L'alternative

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") #\a #\b)

=> #\b

Affichage

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.

Abstraire en nommant

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 fonction 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 à par 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.

Abstraire par les fonctions

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.

La forme define est aussi utilisée 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 forme 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 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 fonction 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 du é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'elle modifient l'état du système, l'écran en l'occurrence.

Ordre 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 fonction, 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, il n'aurait évalué que (and #t #t) et (somme 1 2).

Ce qu'il faut retenir

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 fonctions 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.

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 plateformes, extenssible.

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ébogeur symbolique. Existe en version libre et commerciale, pour Windows et Linux.