Résumé

Voici le sixiè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 servi aussi à 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 examinons les éléments du langages avancés comme la quasiquotation, l'application explicite de fonctions à des arguments, l'évaluation retardée. Puis nous expliquons le mécanisme des continuations et une méthode pour réécrire les structures de données essentielles comme la paire.

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 certains points importants. D'excellents ouvrages en français sont donnés dans la bibliographie.

Introduction

Cet article est le dernier de la série à présenter le langage Scheme d'une manière générale. Dans des prochains articles, nous présenterons une réalisation possible d'une machine virtuelle en Scheme. Puis nous décrirons le système de macro du langage qui permet d'étendre à l'infini le nombre des formes spéciales du langage. Nous présenterons ensuite un moteur à objet, puis des aspects de programmation graphique.

Ce mois-ci, nous allons compléter la description du langage avec les formes et écritures qui nous manquent. Puis nous montrerons que la structure de données élémentaire du langage, la paire, peut être réécrite à l'aide d'une lambda-expression.

Eléments du langage

Dans cette section, nous allons examiner des éléments du langage Scheme indispensables pour la suite.

Quasiquotation

Nous avons vu jusqu'à maintenant le mécanisme de quotation qui empêche l'évaluation d'une expression. Ce mécanisme est très utile pour construire des listes de constantes ou manipuler les symboles :

> '(1 2 3)

=> (1 2 3)

> '(1 2 (3 4))

=> (1 2 (3 4))

De même, la quotation permet d'utiliser les symboles en tant que tels, sans les évaluer au préalable. Ainsi :

> 'toto

=> toto

> (symbol? 'toto)

=> #t

> (symbol? toto)

=> ERROR: symbol `toto' is unbounded

Dans la dernière écriture, le système Scheme tente d'évaluer le symbole toto afin d'appliquer au résultat la fonction symbol?. Comme toto n'est pas défini, cette évaluation provoque une erreur.

La quotation est introduite avec une apostrophe ; elle peut aussi s'écrire à l'aide de la forme spéciale quote. Les deux expressions suivantes sont équivalentes :

'expression
(quote expression)

Scheme définit aussi la quasiquotation qui s'écrit comme la quotation, mais avec le caractère `. C'est une forme de quotation dans laquelle les expressions précédées d'une virgule sont évaluées. Ainsi :

> `(1 2 3)

=> (1 2 3)

> `(1 2 ,(+ 1 2 4))

=> (1 2 7)

Les deux expressions suivantes sont identiques :

,expression
(unquote expression)

Si la quotation avait été utilisée dans la dernière expression, au lieu de la quasiquotation, nous aurions eu :

> '(1 2 ,(+ 1 2 4))

=> (1 2 (unquote (+ 1 2 4)))

Lorsque la virgule est immédiatement suivie du caractère @, l'expression qui suit doit être une liste ; les éléments de cette liste sont alors concaténés à la liste principale :

> `(1 2 ,@ (list 3 4 5))

=> (1 2 3 4 5)

Les deux expressions suivantes sont identiques :

,@ expression
(unquote-slicing expression)

Sans le @, nous aurions :

> `(1 2 ,(list 3 4 5))

=> (1 2 (3 4 5))

La quasiquotation est introduite avec une apostrophe inverse ; elle peut aussi s'écrire à l'aide de la forme spéciale quasiquote. Les deux expressions suivantes sont équivalentes :

`expression
(quasiquote expression)

La quotation et la quasiquotation sont très utilisées pour construire des structure de listes de manière simple. En particulier, elles sont très employées dans l'écriture des interprètes ou compilateurs de langages.

Apply

La fonction apply permet d'appliquer une fonction à une liste d'arguments. Elle s'utilise comme dans les exemples ci-dessous :

> (apply + '(1 2 3))

=> 6

> (define une-liste '(1 2 3))

=> #unspecified

> (apply car une-liste)

=> 1

> (apply (lambda (a b c d) (+ a b c d 10))
(list 1 2 3 4))

=> 20

Cette fonction est utile lorsque les arguments d'une fonction sont disponibles sous la forme d'une liste. Ecrivons par exemple, une fonction qui calcule le produit scalaire deux listes de nombres a=(a1, …, an) et b=(b1, …, bn). Le produit scalaire est la somme a1b1+…+anbn. La fonction Scheme calculant un tel produit s'écrirait :

(define (produit-scalaire a b)
(apply + (map * a b)))

Evaluation paresseuse

Le langage Scheme est un langage en mode applicatif, ce qui signifie que les arguments des fonctions sont préalablement évalués avant que la fonction ne soit effectivement appelée (comme on l'a vu dans un article précédent, certaines formes spéciales échappent cependant à ce mode d'évaluation, comme if et define).

Il existe une autre famille de langages dits paresseux. Dans ces langages, les arguments de toutes les fonctions ne sont évaluées que lorsque cela est strictement nécessaire ; on appelle ce mode d'évaluation le mode normal.

Ce mode d'évaluation a montré qu'il était dans certain cas beaucoup plus performant que le mode applicatif, et surtout qu'il aboutit toujours à un résultat, lorsqu'il existe.

Les lecteurs souhaitant pousser un peu plus leur connaissances pourrons consulter les livres sur le lambda-calcul et les langages fonctionnels donnés en annexe.

En Scheme, il est possible de construire explicitement une structure qui conserve une expression sans l'évaluer afin de permettre une évaluation ultérieure. Cette structure est appelée promesse et se construit à l'aide de la fonction delay comme suit :

> (delay (+ 1 2))

=> #promise

Bien sûr, une promesse conserve l'environnement dans lequel elle a été construite.

Pour forcer l'évaluation d'une promesse, on utilise la fonction force :

> (define promesse (delay (+ 1 2)))

=> #unspecified

> (force promesse)

=> 3

Les promesses peuvent être utilisées pour construire des flots de données.

Le futur d'un programme

Les continuations sont en Scheme des fonctions qui représentent le futur de l'exécution d'un programme à un certain point de la continuation. Elles sont construites avec la fonction call-with-current-continuation aussi appelée call/cc. Cette fonction a comme argument une fonction à un argument qui recevra la continuation construite par call/cc :

(call/cc (lambda (continuation)
…))

La fonction passée à call/cc , ici, une lambda-expression, est invoquée avec comme argument la continuation. Si elle n'utilise pas cette continuation et se déroule jusqu'à la fin, la valeur de call/cc est la valeur de retour de la fonction. On aura par exemple :

> (call/cc (lambda (continuation)
(+ 1 2 3)))

=> 6

La continuation est elle-même une fonction à un argument. Si cette fonction est invoquée avec une valeur, cette valeur devient immédiatement la valeur de retour de l'appel à call/cc :

> (call/cc (lambda (continuation)
(continuation "toto")
; le reste n'est pas exécuté
(+ 1 2 3)))

=> "toto"

Utilisons une continuation dans une fonction qui retourne le premier élément de type caractère d'une liste quelconque, et la valeur fausse si aucun caractère n'est trouvé :

(define (premier-caractère liste)
(call/cc
(lambda (continuation)
(do ((ptr liste (cdr liste)))
((null? ptr) #f)
(if (char? (car ptr))
(continuation (car ptr)))))))

Notons que l'on aurait pu renommer la variable continuation en return, ou tout autre nom.

Mais où est le futur dans tout ça ?

Eh bien le futur est dans la continuation. En effet, une continuation est un objet de première classe, qui peut donc être manipulé comme tout autre objet. Il est donc possible d'affecter à une variable une continuation, et d'invoquer cette continuation de n'importe où.

Dans ce contexte, la continuation peut être vue comme une sorte de goto.

Réalisons un petit programme qui s'occupe de lire des nombre au clavier et de les afficher. Si autre chose qu'un nombre est lu, une erreur est provoquée :

; Continuation affectée plus bas.
; En cas d'appel, après l'init, va
; au retour du call/cc (A)
(define encore #f)

; lit des nombre au clavier
(define (lit)
(let ([valeur (read)])
(cond [(eof-object? valeur)
#f]
[(number? valeur)
valeur]
[else
(erreur "mauvais noombre!")]))

; traitement des erreurs
(let ([compteur 0]
[message
; A: retour du call/cc
(call/cc (lambda (cont)
(set! erreur cont)
#f))])
; à l'init, message vaut #f
(if message
(begin
(display "ERREUR(")
(display compteur)
(display "): ")
(display message)
(newline)))
(set! compteur (+ compteur 1)))

; boucle de programme
(do ([nombre (lit) (lit)])
((not nombre))
(display nombre)
(newline))

Lorsque l'on exécute ce programme, la variable encore reçoit la valeur de la continuation de l'appel à call/cc. Puis on entre dans une boucle.

Cette boucle lit un nombre au clavier, l'affiche et recommence. Lorsque la fion de fichier est rencontrée, la boucle et le programme se terminent.

Lorsque autre chose qu'un nombre est entré, la fonction erreur est invoquée. Elle affiche un message, puis invoque la continuation encore.

Cette invocation ramène l'exécution à la fin du call/cc, c'est à dire avant la boucle : en effet, le futur du call/cc, lors de sa première invocation est bien l'exécution de la boucle. Donc l'invocation de cette continuation ramène toujours avant ce futur.

Ce programme peut servir de structure pour construire un interprète plus complexe. Les continuations peuvent aussi servir à réaliser les fameux threads, pour peu que l'on dispose de timers.

La Paire

Cette présentation du langage Scheme a mis en évidence l'existence des types de données primitifs, comme les caractères, les entiers, les chaînes de caractères, et de deux type de données composées que sont la paire et le vecteur.

On imagine assez bien qu'un vecteur puisse être réalisé à l'aide d'une succession de paire : ce n'est pas un type de données essentiel. Pour la paire, aucune autre donnée, a priori, ne permet de la reconstruire : il semble que se soit un type de donnée essentiel.

En réalité, les deux paragraphes précédents sont basés sur une affirmation fausse, celle concernant les types de données. En effet, les lambda-expressions sont des types de donnée à part entière, et c'est une originalité de Scheme. Et bien évidemment, il est possible de reconstruire les paires à l'aide des lambda-expressions.

Rappelons-nous que Scheme est le langage le plus proche du lambda-calcul, un formalisme mathématique pour décrire les fonctions. Le lambda-calcul ne possède pas de type de données, et pourtant, il permet à l'aide des seules lambda-expressions de reconstruire tous les types de données, dont les paires. On retrouve cette possibilité en Scheme.

En ce qui concerne la paire, cinq fonctions sont nécessaires :

ï‚· Un constructeur qui avec deux arguments retourne une paire ;

ï‚· Deux sélecteurs qui retournent la tête ou la queue d'une paire ;

ï‚· Deux modificateurs qui modifient la tête ou la queue d'une paire.

Les fonctions standard sont cons, car, cdr, set-car! et set-cdr! qui s'utilisent comme suit :

> (define une-paire (cons 1 2)

=> #unspecified

> (car une-paire)

=> 1

> (cdr une-paire)

=> 2

> (set-car! une-paire 123)

=> #unspecified

> (set-cdr! une-paire 456)

=> #unspecified

> (car une-paire)

=> 123

> (cdr une-paire)

=> 456

Pour définir le constructeur de paire, nous allons utiliser la possibilité qu'ont les lambda-expressions (autrement dit, les fonctions) de capturer leur environnement (cette possibilité ne se retrouve que dans les langages fonctionnels).

Le constructeur est une fonction à deux arguments qui retourne une lambda-expression capturant l'environnement du constructeur :

(define (my-cons tête queue)
(lambda (action arg)
(case action
((donne-tête) tête)
((donne-queue) queue)
((change-tete) (set! tête args))
((change-queue) (set! queue args)))))

Ainsi, lorsque l'on appelle my-cons avec deux arguments, la tête et la queue, on obtient une fonction à deux arguments, un sélecteur de l'action à entreprendre et la valeur pour la modification des valeur.

Notons que dans le cas des sélecteur donne-tête et donne-queue, arg n'est pas utilisé et pourra prendre n'importe quelle valeur :

> (define une-paire (my-cons 1 2)

=> #unspecified

> (une-paire 'donne-tête #f)

=> 1

> (une-paire 'donne-queue #f)

=> 2

> (une-paire 'change-tête 123)

=> #unspecified

> (une-paire 'change-queue 456)

=> #unspecified

> (une-paire 'donne-tête #f)

=> 123

> (une-paire 'donne-queue #f)

=> 456

C'est gagné, nous avons récrit le constructeur de paire !

Il ne nous reste plus qu'à définir les sélecteurs et le modificateurs :

(define (my-car paire)
(paire 'donne-tête #f))

(define (my-cdr paire)
(paire 'donne-queue #f))

(define (my-car! paire nouveau)
(paire 'change-tête nouveau))

(define (my-cdr! paire nouveau)
(paire 'change-tête nouveau))

Dans cette proposition, nous n'effectuons pas de contrôle de type et reléguons cette tâche au système Scheme.

Maintenant que nous avons la paire, nous avons la liste. En effet, l'élément constituant des listes en Scheme est la paire. Avec les listes, nous pouvons construire les vecteurs. On pourrait aussi montrer que les types primitifs comme le caractère, les entiers, les réels, les chaînes de caractères peuvent être reconstruits à l'aide de lambda-expression (les lecteurs intéressés par la théorie trouveront quelques livres en annexe).

Certes le résultat serait effroyablement inefficace, et c'est la raison pour laquelle aucun système Scheme ne procède ainsi. Mais d'un point du vue théorique, cela facilite la formalisation du langage et des programmes qui conduit vers l'étude sémantique (étude du sens).

La méthode utilisée pour réaliser notre constructeur de paire est très utilisé en Scheme pour construire des structures de données intelligentes, et même des moteurs de programmation objets..

Ce qu'il faut retenir

Dans cet article, nous avons vu la quasiquotation qui permet de construire aisément des structures de liste complexes. Nous avons examiné aussi la fonction apply qui permet d'appliquer explicitement une fonction à des arguments placés dans une liste. Puis enfin les fonction delay et force nous donne un moyen de retarder l'évaluation des expressions.

Nous avons aussi parlé des continuations qui sont une originalité du langage Scheme. Une continuation est le futur de l'exécution d'un programme.

Enfin, nous avons montré que la paire qui nous semblait être la structure de donnée élémentaire peut être réalisée à l'aide des lambda-expression.

Les auteurs

Guilhem de Wailly, directeur de la société Erian Concept : support, formation, configuration, administration, développement Linux.

http://www.erian-concept.com

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

http://www.i3s.edu

Références

Lambda-calcul et langages fonctionnels

Mise en Å“uvre de langages de programmation
SL. Peyton Jones
MASSON

Lambda-calcul, types et modèles - JL. Krivine
Masson

Introduction à l théorie des langages de programmation
B. Meyer
InterEdition

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

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 plate-formes, extensible.

Stk - E. Gallesio
http://kaolin.unice.fr
Interprète Scheme avec une interface Objet et une interface TK, plus beaucoup d'autres 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 éditeur intégré.

OpenScheme - Erian Concept
http://www.erian-concept/osm
Environnement professionnel de programmation Scheme comprenant un interprète, un compilateur et un débogueur symbolique.
Existe en version libre et commerciale, pour Windows et Linux.