Le langage Scheme

Voici le cinquiè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 différentes formes de let, et les fonctions ayant un nombre d'arguments variables.

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

Notre apprentissage du langage Scheme commence à toucher à sa fin. Nous avons encore quelques détails à examiner avant d'entamer des aspects plus pratiques, comme la programmation orientée objet ou la programmation graphique.

Dans cet article, nous allons revenir en détail sur les différentes formes let. Nous verrons ensuite une forme let particulière qui simplifie l'écriture des itérations.

Tout au long de cette description, nous montrerons comment les formes let peuvent être réécrites à l'aide de formes plus simple. En continuant les simplifications au maximum, le lecteur constatera qu'il aboutit toujours à une forme basée sur la forme lambda. Cette possibilité simplifie grandement l'écriture des interprètes et des compilateurs Scheme.

Nous utiliserons alors nos connaissances pour définir une fonction de tri générique d'un vecteur d'éléments, dont les éléments peuvent être ordonnés par une fonction passée en argument. Cette fonction permettra de trier les éléments d'un vecteur dont les éléments seront de n'importe quel type pourvu qu'ils puissent être comparés à l'aide de la fonction de comparaison.

Par la suite, nous montrerons comment définir nos propres fonctions avec un nombre d'arguments variable. Les fonctions ayant un nombre d'arguments variable simplifient souvent les écritures en autorisant les arguments facultatifs.

Les formes let

La forme let a été présentée au cours des articles précédents. Elle permet de définir des variables de manière locale. A cette occasion, nous avons aussi indiqué l'existence des formes let* et letrec, et laissant le soin au lecteur de vérifier leur définition dans la norme du langage.

Nous allons maintenant préciser leur différence.

Let

La forme let s'écrit :

(let ((var₁ exp₁)

(var₂ exp₂)

...

(var_n exp_n))

corps)

Dans le langage Scheme, les parenthèses et les crochets sont équivalents à condition qu'il y ait correspondance. Il est d'usage d'écrire les formes let de la manière suivante (cette syntaxe est très utilisée au MIT) :

(let ([var₁ exp₁]

[var₂ exp₂]

...

[var_n exp_n])

corps)

Cette forme est utilisée pour définir un certain nombre de variables locales var_i avec le résultat de l'évaluation des expressions exp_i correspondantes.

Le corps du let est ensuite évalué et le résultat de l'évaluation de la dernière expression du corps devient le résultat du let tout entier.

La particularité de let est que les expressions exp_ine peuvent pas utiliser les variables var_i. On en comprend mieux la raison en constatant que la forme let est une réécriture à base de lambda. En fait :

(let ((var₁ exp₁)

(var₂ exp₂)

...

(var_n exp_n))

corps)

peut être réécrit en :

((lambda (var₁ var₂ ... var_n)

corps)

exp₁ exp₂ ... exp_n)

qui est l'application d'une forme lambda à des arguments. Dans ce cadre, on constate que les variables var_i sont bien inaccessibles aux expressions exp_i. On rappelle que Scheme fonctionne en mode applicatif, c'est à dire que les arguments sont évalués avant l'appel effectif à la fonction.

Par exemple :

> (let ((a 4) (b -3))

; corps du premier let

(let ((a-au-carre (* a a))

(b-au-carre (* b b)))

; corps du second let

(+ a-au-care b-au-carre)))

=> 25

Ce qui se réécrit en :

((lambda (a b)

; corps du premier let

((lambda (a-au-carre b-au-carre)

; corps du second let

(+ a-au-care b-au-carre))

(* a a) ; valeur de a-au-carre

(* b b))) ; valeur de b-au-carre 4 ; valeur de a -3) ; valeur de b

Let*

La forme let* est construite un peu à la manière du let :

(let* ((var₁ exp₁)

(var₂ exp₂)

...

(var_n exp_n))

corps)

La différence est que cette fois-ci, les expressions exp_i peuvent utiliser les variables var₁, ..., var_i-1 définies avant. Ceci s'explique en constatant que la forme let* est une simplification syntaxique de l'écriture :

(let ((var₁ exp₁))

(let* ((var₂ exp₂)

...

(var_n exp_n))

corps))

Dans cette écriture, on remarque clairement que les expressions exp₂ ... exp_n peuvent utiliser la variable var₁.

En remplaçant les let* intérieurs de la même manière, on constate que les expressions exp_i peuvent utiliser les variables var₁, ..., vari_-1.

Par exemple :

> (let* ((a 4)

(b -3)

(a-au-carre (* a a))

(b-au-carre (* b b)))

(+ a-au-care b-au-carre))

=> 25

Cette écriture pourrait être réécrite en:

((lambda (a)

((lambda (b)

((lambda (a-au-carre)

((lambda (b-au-carre)

(+ a-au-care b-au-carre))

(* b b)))

(* a a)))

-3))

4)

Les environnements Scheme savent optimiser ce genre d'écritures de telle sorte que les lambda expressions intérieures sont remplacées par des extensions d'environnements plus efficaces en terme de performance.

Letrec

La forme letrec utilise la même syntaxe :

(letrec ((var₁ exp₁)

(var₂ exp₂)

...

(var_n exp_n))

corps)

Dans cette écriture, les expressions exp_i peuvent utiliser toutes les variables var_i à la différence du let* ou seules les variables situées au-dessus peuvent être utilisées.

L'écriture letrec est une simplification syntaxique de l'écriture :

(let ((var₁ 'unbounded)

(var₂ 'unbounded)

...

(var_n 'unbounded))

(set! var₁ exp₁)

(set! var₂ exp₂)

...

(set! var_n exp_n)

corps)

On constate que toutes expressions exp_i peuvent effectivement utiliser les variables var_i. La valeur 'unbounded est utilisée ici car Scheme ne donne pas de représentation externe de la valeur non-definie.

Cette écriture n'est vraiment utile que si les expressions sont des fonctions mutuellement référencées, comme dans :

> (letrec ((f (lambda (x) (g (* x 10)))) (g (lambda (a) (* a a))))

(f 7))

=> 4900

La plupart des implémentations Scheme permettent de remplacer :

(let ( )

(letrec ((var₁ exp₁)

(var₂ exp₂)

...

(var_n exp_n))

corps))

par :

(let ( )

(define var₁ exp₁)

(define var₂ exp₂)

...

(define var_n exp_n))

corps)

Cette écriture est plus naturelle et donc souvent utilisée.

Let nommé

Nous présentons maintenant une autre forme de let permettant l'écriture d'expressions récursives.

Cette écriture permet des constructions très évoluées. Elle s'écrit :

(let variable ((var₁ exp₁)

(var₂ exp₂)

...

(var_n exp_n))

corps)

Dans le corps de l'expression, variable est une fonction à n paramètres qui peut s'appeler récursivement. L'écriture correspondante est :

(letrec ((variable (lambda (var₁ var₂ ...var_n) corps)))

(variable exp₁ exp₂ ... exp_n))

Réécrivons par exemple la fonction length qui retourne le nombre d'éléments d'une liste :

(define (length list)

(let loop ([pointeur list]

[résultat 0])

(if (null? pointeur)

résultat

(loop (cdr pointeur)

(+ résultat 1)))))

Nous pourrions tenter de donner une réécriture de la forme itérative do :

(do ([var₁ init₁ exp₁]

[var2 init2 exp2]

...

[var_n init_n exp_n]

(stop res)

corps)

peut être réécrit :

(let loop ([var₁ init₁]

[var₂ init₂]

...

[var_n init_n]

(if stop

res

(begin

corps

(loop exp₁ exp₂ ... exp_n))))

où var_i, exp_i, stop, res et corps sont remplacés tels quels.

Dans la réalité, le remplacement est à peine plus complexe car il doit tenir compte du fait que les expressions exp_i ainsi que l'expression résultat res sont facultatives.

Ainsi, nous constatons au fur et à mesure de notre progression, que finalement, le langage Scheme est défini avec peu de choses. La forme lambda vers laquelle aboutissent toutes nos tentatives de réécritures semble bien être la pierre angulaire de ce langage : Souvenons-nous que Scheme est bâti sur un formalisme mathématique appelé le lambda-calcul !

Ces possibilités de réécritures sont importantes car elles simplifient l'écriture d'un interprète ou d'un compilateur Scheme. Dans la pratique, il doit savoir traiter un nombre limité d'expressions parmi lesquelles on trouve define, set! if, lambda, call/cc (dont nous parlerons prochainement) et les applications. Les autres expressions comme do, let, let*, cond, case sont transformées par un pré-processeur lui-même écrit en Scheme.

Exemple

Cet exemple montre une réalisation possible d'une fonction de tri. Ses arguments sont un vecteur dont les éléments sont à trier par rapport à une fonction de comparaison, elle aussi en argument.

Cette fonction montre une utilisation conjointe des formes let, let* et do.

La fonction sort parcourt l'ensemble des éléments du vecteur, du premier au dernier. Elle parcourt alors les éléments à partir du dernier, en comparant avec la fonction compare l'élément courant à l'élément précédent. S'il est plus petit, il est déplacé :

(define (sort vec compare)

; test des arguments

(if (and (vector? vec)

(procedure? compare))

; variables locales

(let* ([len (vector-length vec)]

[len-1 (- len 1)])

; parcourt du premier au dernier

(let loop-i ([i 0])

(if (>= i len-1)

; la fin est atteinte ; retourner le vecteur

vec

(begin

; parcourt du dernier vers le courant

(do ([j len-1 (- j 1)])

((<= j i))

(let ([j-1 (- j 1)])

; comparaison

(if (compare (vector-ref vec j)

(vector-ref vec j-1))

; plus petit : décalage

(let ([temp (vector-ref vec j)])

(vector-set! vec

j

(vector-ref vec j-1))

(vector-set! vec

j-1

temp)))))

; continuer sur le reste des éléments

(loop-i (+ i 1))))))

; les arguments sont invalides

#f))

Utilisons cette fonction pour trier des vecteurs :

> (display (sort #(1 3 2 4 6 5 0) <))

(newline)

=> #(0 1 2 3 4 5 6)

> (display (sort #(1 3 2 4 6 5 0) >))

(newline)

=> #(6 5 4 3 2 1 0)

> (display (sort #("dsd" "aa" "sde") string>?))

(newline)

=> #("sde" "dsd" aa")

Ainsi, l'utilisateur peut trier ses propres structures de données avec cette fonction si elles peuvent être ordonnées à l'aide de la fonction de comparaison compare passée en argument qui traduit la relation d'ordre des éléments du tableau.

Fonction à « arguments variables »

Le langage Scheme permet de définir facilement des fonctions avec un nombre d'arguments variable.

Cela peut être utile dans les cas suivants :

• Simplification des appels à une fonction lorsque certains arguments sont rarement nécessaires ;

• Modification de la signature d'une fonction sans compromettre le code existant ;

• Le nombre d'arguments ne peut être connu à l'avance.

Nous avons déjà rencontré de telles fonctions. C'est le cas des opérateurs arithmétiques comme +. On a par exemple :

> (+)

=> 0

> (+ 1)

=> 1

> (+ 1 2 3 4)

=> 10

D'autres fonctions, comme display et newline, read-char, acceptent aussi un argument facultatif qui est le port d'entrée / sortie.

Une fonction ayant un nombre d'arguments variable est créée avec la forme lambda de la manière suivante :

(lambda (a1 a2 . av) corps)

où a1 et a2 sont des paramètres réguliers et av représente un paramètre qui contiendra la liste des arguments supplémentaires.

Bien sûr, il est possible de définir la fonction avec 0, 1 ou plusieurs paramètres réguliers et les noms des paramètres sont libres.

Nous pouvons aussi utiliser la forme compacte de define où :

(define f (lambda (a1 a2 . av) corps))

représente la même fonction que :

(define (f a1 a2 . av) corps)

Ecrivons une fonction ayant un nombre d'arguments variable. Il s'agit d'une fonction qui calcule la moyenne des arguments avec au moins un argument :

> (define (moyenne premier . autres)

(let ((somme premier))

(for-each (lambda (n)

(set! somme (+ somme n)))

autres)

(/ somme (+ 1 (length autres)))))

=> #unspecified

> (moyenne 13)

=> 13

> (moyenne 13 14 15)

=> 14

Pour affiner la détection des erreurs, il serait possible d'ajouter un test dans l'itération qui vérifierait avec number ? que n est bien un nombre.

Pour les fonctions dont tous les arguments sont optionnels, on utilisera la forme contractée suivante :

(lambda (. av) corps)

qui peut aussi s'écrire :

(lambda av corps)

On pourrait ainsi définir une fonction qui affiche la valeur de ses arguments et retourne leur nombre avec:

(define (compte . arguments)

(let loop ([arguments arguments] [n 0])

(if (null? arguments)

n

(begin

(display (car arguments))

(newline)

(loop (cdr arguments) (+ 1 n))))))

Ce qu'il faut retenir

Nous avons vu qu'il existe plusieurs formes de let : let, let* et letrec. Elles se différencient par la possibilité d'utilisation des noms des variables locales dans les expressions d'initialisation.

Il existe une forme particulière de let, letrec, qui permet l'écriture d'expressions récursives.

Nous avons montré comment les formes let ainsi que la forme do peuvent être réécrites à l'aide de la forme lambda. Bien que ce ne soit pas le sujet de cette série d'articles, nous constatons que la forme lambda joue un rôle très important dans Scheme.

Enfin, nous avons terminé cet article avec la description de l'écriture des fonctions ayant un nombre d'arguments variable.

Guilhem de Wailly (gdw@erian-concept.com)

http://www.erian-concept.com

avec la participation de : Fernand Boéri (boeri@unice.fr)