Voici le troisiè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 oeuvre 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 allons nous pencher un peu plus sur les fonctions de Scheme. Nous décrirons notamment les fonctions récursives et la récursivité terminale. Puis nous donnerons en exemple des fonctions de la bibliothèque standard, que nous écrirons lorsque cela est possible de manière récursive. Puis nous aborderons les fonctions anonymes qui donnent à Scheme toute sa puissance expressive. Dans cette partie, nous aborderons aussi la notion d'environnement d'exécution.
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
Les articles précédents ont permis au lecteur de se familiariser à Scheme : Il est désormais capable d'écrire en Scheme des programmes simples, de définir ses propres fonctions. Pour l'instant cependant, rien ne semble clairement différencier Scheme des autres langages de programmation.
Dans cet article, nous commençons à aborder des points qui font la particularité de Scheme, comme les fonctions anonymes.
Itération
Scheme définit une structure de contrôle permettant d'écrire facilement des itérations. C'est la forme spéciale do qui s'écrit :
(do ((var1 init1 incrément1)
(var2 init2 incrément2)
...
(varm initm incrémentm))
(test-fin résultat)
expr1 exp2 expn)
L'évaluation de cette expression débute par l'évaluation des expressions initi dont le résultat initialise les variables vari.
L'expression test-fin est évaluée :
Si le résultat est #t, l'expression résultat est évaluée et le résultat retourné. L'expression résultat est facultative. Si elle n'est pas présente, #unspecified est retourné.
Si le résultat est #f, les expressions expi sont évaluées de la première à la dernière. Puis les expressions incrémenti sont évaluées et le résultat est affecté aux variables correspondantes.
Le processus recommence alors.
Par exemple, la fonction suivante affiche tous les éléments d'un vecteur( Dans le code Scheme suivant, les noms des fonctions standard seront écrits en gras) :
> (define (display-vector v)
(let ((len (vector-length v)))
(do (; variables
(i 0 (+ i 1)))
; test de terminaison
((eq? i len))
; corps de l'itération
(display (vector-ref v i))
(newline))))
=> #unspecified
> (display-vector #(1 '(2 3) 4))
1
(2 3)
4
#unspecified
Fonctions récursives
Une fonction récursive est une fonction qui s'appelle elle-même dans sa définition. Considérons la fonction factorielle :
fact(0) = 1
fact(1) = 1
fact (2) = 2 x 1= 2
fact(3) = 3 x 2 x 1 = 6
fact(4) = 4 x 3 x 2 x 1 = 24
Une définition mathématique possible de la factorielle est la suivante :
Cette expression signifie Quel que soit n, entier positif ou nul, la factorielle de zéro vaut un, et la factorielle de tout autre nombre vaut ce nombre multiplié par la factorielle de ce nombre diminué de un.
Cette définition est récursive car la factorielle de tout nombre strictement positif est exprimée en fonction de la factorielle elle-même.
La fonction factorielle pourrait s'écrire en Scheme comme cela :
(define (factorielle n)
(if (zero? n)
1
(* n (factorielle (- n 1)))))
Pour être exact, il faudrait tester si n est bien un entier positif ou nul, et provoquer une erreur dans le cas contraire.
On remarque que le nom factorielle est utilisé dans le corps de la fonction factorielle elle-même, ce qui indique une récursivité (Dans certains des cas, la récursivité est plus difficile à metttre en évidence, car elle peut se produire via plusieurs fonctions).
La plupart des langages de programmation qui possèdent la notion de fonction permettent d'écrire des fonctions récursives. C'est le cas de Pascal, C, Lisp, Scheme, Eiffel. Par contre, Basic, dans les premières versions, ne le permet pas, tout comme les langages d'assemblage classiques.
Récursivité terminale
L'usage de la récursivité simplifie les écritures, mais elle a un coût en terme de performance. Cependant, il existe une forme de récursivité qui se traduit par une exécution itérative ne diminuant pas les performances. Cette forme de récursivité est très recherchée, car elle conserve l'élégance de l'écriture récursive tout en ne pénalisant pas les performances.
D'une manière simple, une récursivité entraînant une exécution itérative est reconnaissable lorsque le résultat de l'appel récursif est le résultat de la fonction.
Reconsidérons la définition de la factorielle. Est-ce une fonction à récursivité terminale ? Pour cela, considérons l'appel récursif (* n (factorielle (- n 1))). Nous constatons que le résultat de l'appel récursif (factorielle (- n 1)) n'est pas le résultat de la fonction car il est ensuite multiplié par n. La fonction factorielle ainsi définie n'est pas à récursivité terminale (Il est possible d'écrire la fonction factorielle de manière à ce qu'elle soit à récursivité terminale.).
Considérons maintenant la fonction :
(define (pgcd a b)
(cond ((> b a)
(pgcd b a))
((zero? b)
a)
(else
(pgcd b (modulo a b)))))
Cette fonction est-elle à récursivité terminale ? Pour cela, considérons les deux appels récursifs. Le résultat de ces appels est-il encore utilisé dans le corps de la fonction ou est-il directement retourné ? Comme dans les deux cas il est directement retourné, cette fonction est à récursivité terminale. Elle va donc être exécutée par le système Scheme de manière itérative comme si les appels internes à pgcd étaient traduits par des sauts inconditionnels (goto). Il en résulte un accroissement de performances.
Opérations sur les listes
Dans cette section, nous allons mettre en pratique nos connaissances pour écrire en Scheme quelques fonctions de la bibliothèque standard.
Retournement : reverse
La fonction reverse prend une liste comme argument et retourne une nouvelle liste dont les éléments sont placés en ordre inverse :
> (reverse (list 1 2 3))
=> (3 2 1)
La fonction reverse peut être écrite en Scheme de la manière suivante :
(define (reverse liste)
(let ((résultat '()))
(do ((ptr liste (cdr ptr)))
((null? ptr))
(set! résultat
(cons (car ptr)
résultat)))
résultat))
Cette fonction commence par définir le résultat comme étant la liste vide. Puis elle parcourt tous les éléments de la liste et construit le résultat au fur et à mesure. Comme le premier élément est placé dans le résultat en premier, la liste obtenue est dans l'ordre inverse de la liste donnée en argument.
Ce n'est pas une fonction récursive car rien dans sa définition ne fait appel à la fonction qui est en train d'être définie.
Longueur : length
La fonction length calcule la longueur d'une liste, c'est à dire le nombre d'éléments qu'elle contient. Elle s'utilise comme suit :
> (length (list 1 2 3))
=> 3
Cette fonction provoque une erreur si son argument n'est pas une liste. Ecrivons nous-mêmes la fonction length :
(define (length object)
(cond ((null? ojbect) ; cas 1
0)
((pair? object) ; cas 2
(+ 1 (length (cdr object))))
(else ; cas 3
(car object))))
La fonction length est une fonction où l'on distingue trois cas :
1. l'objet est la liste est vide : dans ce cas, le résultat est la longueur de la liste vide, c'est à dire zéro ;
2. l'objet est une paire : dans ce cas, le résultat est 1 additionné à la longueur du reste de la liste ;
3. l'objet n'est ni la liste vide, ni une paire : c'est un cas
d'erreur que nous provoquons en appliquant la fonction car à l'objet, ce qui va à coup sûr provoquer une erreur.
Cette fonction est une fonction récursive : en effet, la fonction définie se rappelle elle-même dans le deuxième cas. Décrivons les appels successifs à cette fonction sur un cas concret :
(length (list 1 2 3))
= (+ 1 (length (cdr '(1 2 3)))
= (+ 1 (length '(2 3))
= (+ 1 (+ 1 (length '(cdr 2 3))))
= (+ 1 (+ 1 (length '(3))))
= (+ 1 (+ 1 (+ 1 (length (cdr '(3)))))
= (+ 1 (+ 1 (+ 1 (length '())))
= (+ 1 (+ 1 (+ 1 0))
= 3
On remarque que le système Scheme conserve les additions successives jusqu'à ce que le calcul de la longueur de la liste vide ne soit effectué. C'est la raison pour laquelle cette fonction n'est pas à récursivité terminale. On comparera la liste des appels successifs à ceux produit par la fonction for-each décrite plus bas.
Concaténation : append
La fonction append permet de concaténer plusieurs listes entre elles et retourne la nouvelle liste ainsi formée. La fonction décrite dans la norme permet de donner à append un nombre quelconque de listes à concaténer.
> (append (list 1 2 3)
(list 4 5 6)
(list 7 8 9))
=> (1 2 3 4 5 6 7 8 9)
Pour notre part, nous nous contenterons d'écrire la fonction append-2 qui concatène seulement deux listes :
(define (append-2 l1 l2)
(cond ((null? l1) ; cas 1
(if (list? l2)
l2
(car l2)))
((pair? l1) ; cas 2
(cons (car l1)
(append-2 (cdr l1) l2)))
(else ; cas 3
(car l1))))
Cette fonction est aussi définie par trois cas :
l1 est las liste vide : dans ce cas, le résultat est la seconde liste. La fonction vérifie que l2 est bien une liste bien formée;
l1 est une paire : là, le résultat est une nouvelle paire formée du premier élément de l1 et de la concaténation de reste de l1 et de l2 ;
l1 n'est ni une paire, ni la liste vide : il s'agit d'un cas d'erreur qui va être provoqué par l'application de car à l1.
La fonction qui vient d'être définie est récursive car elle s'applique elle-même dans le second cas.
Application d'une fonction aux éléments : for-each
Avec for-each, il est possible d'appliquer une fonction à tous les éléments d'une ou plusieurs listes :
> (define (f-1 x)
(display x)
(newline))
=> #unspecified
> (for-each f-1 (list 1 2 3))
1
2
3
=> #unspecified
> (define (f-2 x y)
(display x)
(display #\,)
(display y)
(newline))
=> #unspecified
> (for-each f-2 (list 1 2 3)
(list #\a #\b #\c))
1,a
2,b
3,c
=> #unspecified
Pour notre part, nous nous contenterons d'écrire la fonction for-each-1 qui applique une fonction à une seule liste :
(define (for-each-1 fonction liste)
(if (pair? liste)
(begin
(fonction (car liste))
(for-each-1 fonction (cdr liste)))))
Quels sont les appels successifs à cette fonction sur un cas concret :
(for-each-1 f-1 (list 1 2 3))
= (for-each-1 f-1 (cdr '(1 2 3))
= (for-each-1 f-1 '(2 3)
= (for-each-1 f-1 (cdr '(2 3))
= (for-each-1 f-1 '(3)
= (for-each-1 f-1 (cdr '(3))
= (for-each-1 f-1 '()
Les appels à la fonction f-1 ne sont pas indiqués dans la mesure où ils n'interviennent pas dans le processus récursif. On remarque qu'un appel à la fonction for-each-1 se traduit par plusieurs appels à cette même fonction. Mais, contrairement à length, aucun résultat intermédiaire n'est conservé. On aurait pu écrire for-each-1 en C de la manière suivante :
void
for-each-1 (void (* fonc)(Objet),
Objet liste) {
Label:
if (pair? (liste)) {
fonc (car liste);
goto Label;
}
}
Dans cette définition, l'appel récursif a été supprimé et remplacé par un saut goto. Les environnements Scheme détectent ce type de récursivité terminale et la remplacent de manière interne par un saut ( On ne peut cependant pas utiliser explicitement le saut en Scheme, comme on peut le faire en C avec l'instruction goto).
Application d'une fonction aux éléments, avec capture des résultats : map
La fonction map fonctionne de manière similaire à for-each. Mais elle retourne une liste formée des résultats des applications aux éléments de la ou des listes :
> (define (f x)
(+ x 10))
=> #unspecified
> (map f (list 1 2 3))
=> (11 12 13)
Ici, on va définir la fonction map-1 qui applique une fonction à une seule liste :
(define (map-1 fonction liste)
(if (pair? liste)
(cons (fonction (car ptr))
(map-1 fonction (cdr liste)))
'()
Comme le résultat de l'appel récursif est utilisé pour construire la liste résultat, cette fonction n'est pas à récursivité terminale. Donc, dans les cas où l'on n'a pas besoin de conserver les résultats intermédiaires, on préfèrera for-each.
Egalité
L'égalité peut sembler de prime abord une question simple : deux choses sont égales ou pas. En réalité, il faut s'entendre sur ce que l'on compare.
Quittons un instant Scheme pour C. Que signifie en C la comparaison de deux chaînes de caractères ? S'agit-il simplement de comparer la valeur de deux pointeurs ou d'appeler une fonction strcmp ? Si nous optons pour l'appel à la fonction, appelons-nous strcmp ou strcasecmp qui ne tient pas compte des majuscules minuscules ?
On retrouve cette multiplicité en Scheme. On a par exemple char=?, char-ci=?, string=?, string-ci=?. La fonction char=? compare deux caractères et retournent #t s'ils sont identiques. Le lecteur se réfèrera au Revised4 Report on the Algorithmic Language Scheme pour connaître les autres fonctions de comparaison.
Scheme définit aussi trois autres fonctions de comparaisons à usage général. Ce sont eq?, eqv? et equal?. Elles permettent de comparer n'importe quel objet Scheme sans provoquer d'erreur si leur type est différent.
La fonction eq? compare deux objets. Elle retourne vrai si les objets comparés sont immuables et identiques (liste vide, booléens, caractères et entiers) ou s'ils sont physiquement identiques (ils occupent le même emplacement mémoire). Par exemple :
> (eq? 1 1)
=> #t
> (eq? 1.2 1.2)
=> #f
> (eq? "chaîne" "chaîne")
; Les chaînes sont physiquement
; différentes
=> #f
> (define x "chaîne")
=> #unspecified
> (eq? x x)
; x est évalué en "chaîne". Les objets
; comparés sont donc identiques.
=> #t
La fonction eqv? est une extension de la fonction eq? dans le sens où elle considère immuables les réels et les chaînes de caractères. On aura :
> (eqv? 1.2 1.2)
=> #t
> (eqv? "chaîne" "chaîne")
=> #t
> (define x (list 1 2 3))
=> #unspecified
> (eqv? x x)
=> #f
On notera que si deux objets sont égaux par eq?, ils le sont par eqv?.
Enfin, la fonction equal? permet de comparer les objets composites que sont les paires et les vecteurs. Par exemple, deux vecteurs sont égaux par equal? si toutes leurs composantes sont égales deux à deux par equal?. On a :
> (define x (list 1 2 3))
=> #unspecified
> (equal? x x)
=> #t
On notera que si deux objets sont égaux par evq?, ils le sont par equal?.
L'usage de equal? peut être dangereux si les structures sont récursives. Par exemple :
> (define x (list 1 2))
=> #unspecified
> (set-car! x x)
=> #unspecified
> (equal? x x)
=> ; ne se termine jamais
En règle générale, la fonction eq? est la plus utilisée. D'une part elle ne présente pas le même danger que equal? et elle est souvent la plus efficace que eqv?.
La comparaison des nombres se fait soit à l'aide de =? si l'on teste plus de deux nombres, soit avec eq? si l'on teste deux nombres.
Fonctions anonymes
Forme lambda
Les fonctions anonymes sont des fonctions sans nom que l'on peut manipuler comme tout autre objet Scheme. Cette notion est directement issue du lambda calcul, la théorie mathématique sous-jacente à Scheme et aux langages fonctionnels.
Le lambda calcul est un formalisme dont la grammaire contient seulement trois définitions, l'application, l'abstraction et la définition. A l'aide de ces seuls éléments, il est possible de définir les nombres entiers et l'arithmétique, les autres nombres, les listes, les vecteurs, On retrouve cette capacité à s'auto définir dans les langages comme Scheme ; nous avons vu par exemple comment réécrire quelques fonctions de la bibliothèque standard. Il serait aussi possible de redéfinir les fonctions cons, car et cdr, puis les vecteurs.
L'application du lambda calcul correspond à l'application en Scheme. La définition correspond à la forme spéciale define de Scheme. L'abstraction correspond aux fonctions anonymes de Scheme, autrement appelées forme lambda, ce qui montre clairement l'origine de Scheme.
Une fonction anonyme est définie à l'aide de la forme spéciale :
(lambda (p1 p2 pm) exp1 exp2 expn)
où p1, p2, pn sont des symboles représentant les paramètres de la fonction, et exp1, exp2, expn les expressions du corps de la fonction. La forme lambda retourne une fonction anonyme qui peut être manipulée comme tout autre objet Scheme.
Ecrivons par exemple :
> (lambda (a b) (+ a b 10))
=> #procedure
> ((lambda (a b) (+ a b 10)) 5 8)
=> 23
Dans la seconde écriture, nous avons appliqué la fonction anonyme
(lambda (a b) (+ a b 10))
aux arguments 5 et 8, ce qui retourne le résultat 23. Il est possible de définir une variable comme étant une fonction anonyme :
> (define f (lambda (a b) (+ a b 10)))
=> #unspecified
Maintenant, f est une fonction anonyme. Appliquons-la à des arguments :
> (f 4 3)
=> 17
Jusqu'à maintenant, nous croyions que Scheme avait deux formes spéciales define, l'une pour les variables, avec l'écriture :
(define variable valeur)
et l'autre pour les fonctions, avec l'écriture :
(define (fonction p1 p2 ... pm)
exp1 exp2 ... expn).
Nous venons de constater que la seconde écriture est en réalité une simplification syntaxique de l'écriture:
(define fonction
(lambda (p1 p2 ... pm)
exp1 exp2 ... expn))
Environnement
D'une manière simplifiée, un environnement peut être considéré comme l'ensemble des couples {variable, valeur} vus à un certain endroit du programme. Le contenu de l'environnement change au fur et à mesure de l'exécution du programme.
Considérons l'écriture :
(define f (lambda (a b)
; point 2
(+ a b 10)))
; point 1
(f 1 2)
Lorsque le programme se situe au point 1, il existe un environnement contenant notamment toutes les fonctions standards de Scheme et toutes les fonctions que l'utilisateur a définies comme f. On appelle cet environnement racine l'environnement toplevel.
Lorsque l'on applique f à 1 et 2, l'exécution passe par le point 2. En ce point, l'environnement est constitué du toplevel augmenté des couples {a, 1} et {b, 2}. Lorsque l'on quitte la fonction f, l'environnement redevient le toplevel.
Les formes spéciales que nous avons vues et qui affectent l'environnement sont define, set!, let1, do
1) Ainsi que les formes spéciales dérivées let * et letrec, décrites dans le Revised Report on the Algorithmic Language Scheme), .
Nous devons donc maintenant ajouter la forme spéciale lambda ( en réalité, les seules formes spéciales essentielles sont Lamda et set!, toutes les autres étant des règles de réecritures. On retrouve ici la capacité de Scheme à s'auto-définir).
La puissance de l'abstraction en Scheme, représentée par la forme spéciale lambda, et sa capacité à conserver l'environnement dans lequel elle est définie. Considérons :
> (define f (lambda (a)
; point 2
(lambda (b)
; point 3
(+ a b))))
=> #unspecified
La fonction f retourne une fonction anonyme qui additionne les arguments a et b. Essayons :
> f
=> #procedure
> (define x (f 10))
=> #unspecified
> x
=> #procedure
> (x 123)
=> 133
La variable x est associée à une fonction qui ajoute 10 à son argument. Le point remarquable est que la valeur 10 est en fait l'argument qui a servi à construire la fonction associée à x. Cette dernière retient dans un environnement privé le couple {a, 10}. Cette caractéristique est propre aux langages fonctionnels et ne se retrouve pas dans les langages impératifs comme C. Elle permet des écritures extrêmement puissantes, comme la définition d'un formalisme objet basé sur les messages. Nous aurons l'occasion d'utiliser cette possibilité.
Ce qu'il faut retenir
Cet article insiste particulièrement sur les fonctions de Scheme. Il montre la possibilité d'écrire facilement des fonctions récursives et montre l'intérêt de la récursivité terminale.
On montre comment écrire quelques fonctions de la bibliothèque standard du langage.
Enfin, il présente les fonctions anonymes et leur pouvoir expressif. L'usage des fonctions anonymes suppose l'existence d'un environnement qui contient des couples variable-valeur.
Guilhem de Wailly de la société Erian Concept (gdw@erian-concept.com)
avec la participation de : Fernand Boéri (boeri@unice.fr)