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.
Nous examinons les éléments du langage avancé 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.
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 structures 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 de 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és 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 leurs connaissances pourront 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 ?
Et 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 nombres 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 fin 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 types 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ées à 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 :
l Un constructeur qui, avec deux arguments,
retourne une paire ;
l Deux sélecteurs qui retournent la tête ou la queue
d'une paire ;
l Deux modificateurs qui modifient la tête ou la queue
d'une paire.
Les fonctions standards sont cons, car, cdr, set-car! et set-cdr! et 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 valeurs.
Notons que dans le cas des sélecteurs 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 modificateur :
(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-expressions (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ée 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 fonctions 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ées élémentaire peut être réalisée à l'aide des lambda-expressions.
Guilhem de Wailly,
Directeur de la société Erian Concept :
support, formation, configuration, administration,
développement Linux.
Fernand Boéri,
Professeur à l'Université de Nice-Sophia-Antipolis,
Spécialiste en modélisation, évaluation de performances
et architectures parallèles.
References Lambda-calcul et langages fonctionnels
Mise en œuvre de langages de programmationSL.
Peyton Jones - Masson
Lambda-calcul, types et modèles
JL. Krivine - Masson
Introduction à la théorie des langages de programmation
B. Meyer - InterEdition