Le Mémento du SCHEMEUR [1-2]

Ces notes forment [seulement] un mémento fixant la terminologie et permettant de ne pas s'ennuyer dans les bus. Pour les livres de référence, consulter la bibliographie. Le dialecte utilisé dans ces notes est Racket, version 5.0.2

1^ère partie : Nombres, expressions, fonctions

Dans un langage fonctionnel, la structure de base permettant de contrôler le déroulement d'un programme est l'application d'une fonction à ses arguments. Le rôle principal n'est plus tenu par la notion d'instruction, mais par celle d'expression : au lieu d'exécuter des instructions, on compose des fonctions. Le seul intérêt [à notre niveau] est le degré de rigueur que l'on peut alors se permettre, l'activité de programmation devenant quasiment une mathématique appliquée, avec les techniques démonstratives usuelles [notamment la récurrence].

Je suppose que vous avez sous la main mon livre Premiers Cours de Programmation avec Scheme [Ellipses, 2010] et que vous êtes en niveau de langage racket :

#lang racket         ; langage déterminé par le source

Scheme utilise la notation préfixée complètement parenthésée pour former les expressions :

(f x₁ x₂ ... x_n) au lieu de  f(x₁,x₂,...,x_n) 

On peut demander l'évaluation d'une expression au toplevel interactif :

Cette très pratique boucle-toplevel est un processus infini :

... -> lecture -> évaluation -> écriture -> lecture -> ...

Il faut connaître les primitives arithmétiques suivantes :

• dans les ENTIERS :

  (modulo p q)	q > 0
  (quotient p q)	p >= 0, q > 0
  (gcd n1 n2 ...)	le pgcd
  (lcm n1 n2 ...)	le ppcm
  (random n)	dans [0,n-1]
  (zero? n)	n = 0 ?
  (even? n)	pair?
  (odd? n)	impair ?

• dans les RATIONNELS :

  (numerator r)	le numérateur du rationnel r
  (denominator r)	le dénominateur du rationnel r
  (rationalize x y)	le rationnel le plus "simple" ne différant de x qu'au plus de y.

• dans les REELS (0.5 est réel inexact en vrai Racket mais rationnel exact égal à 1/2 en langage Etudiant Avancé) :

  (abs x)	valeur absolue
  (floor x)	le plus grand entier <= x
  (ceiling x)	le plus petit entier >= x
  (round x)	arrondi
  (min x1 x2 ...)	minimum
  (max x1 x2 ...)	maximum
  (random)	résultat réel dans ]0,1[
  (< x1 x2 ...)	suite strict. croissante
  (<= x1 x2 ...)	suite croissante
  (> x1 x2 ...)	suite strict. décroissante
  (>= x1 x2 ...)	suite décroissante

• dans les COMPLEXES :

  (+ z1 z2 ...)	z1+z2+...
  (* z1 z2 ...)	z1z2...
  (- z1 z2)	z1-z2
  (/ z1 z2)	z1/z2
  (/ z)	1/z
  (sqrt z)	la racine carrée principale de z
  (exp z)	l'exponentielle de base e
  (expt z1 z2)	z1z2
  (log z)	le logarithme de z
  (sin z)	sin, cos, tan, acos, asin, atan
  (= z1 z2 ...)	suite constante (inexacts --> danger !)

De plus, les manipulations de nombres complexes se font avec les primitives suivantes :

(real-part z)	partie réelle
(imag-part z)	partie imaginaire
(angle z)	argument dans ]-pi,pi]
(magnitude z)	module
(make-rectangular x y)	le complexe x+yi
(make-polar r t)	le complexe reit

Chaque type numérique a un prédicat associé. Pour tout objet obj, on peut poser les questions suivantes :

(number? obj)

(complex? obj)

(real? obj)

(rational? obj)

(integer? obj)

avec les inclusions mathématiques usuelles : un entier est aussi un réel ! Notez l'écriture +i pour la racine carrée de -1.

> (and (rational? -2/3) (complex? -2/3) (complex? +i))
#t

En plus des types de nombres, il existe une distinction subtile entre nombres exacts et nombres inexacts [ou approchés]. En niveau Etudiant Avancé,  -1998, 2/3 ou 5+2i sont exacts, mais aussi 3.14 équivalent à 314/100. Par contre #i3.14 est inexact, tout comme #i5 ou 3+#i5.3i. Penser à un nombre inexact comme le résultat d'une mesure physique approchée. Un nombre entier peut être inexact [par ex. #i5], par exemple la partie entière de pi est un nombre entier inexact, car issue d'une opération portant sur une donnée inexacte [l'inexactitude est contagieuse]. Par contre, une opération exacte portant sur des données exactes fournira un résultat exact. On passe d'un nombre exact à un nombre inexact [et vice-versa] via les fonctions exact->inexact et inexact->exact :

> (floor pi)
#i3.0
> (inexact->exact (floor pi))
3

On peut convertir une constante exacte en constante inexacte [ou vice versa] avec les notations #i ou #e :

> (list #i2/3 #e3.14)
(0.66666666666666 157/50)

En vrai Racket [en utilisant #lang racket], les nombres flottants sont inexacts, comme 3.14 ou 1.0.

Les deux constantes booléennes sont notées #t [vrai] et #f [faux]. On peut utiliser les synonymes true ou false.

> (integer? (sqrt 2))
#f
> (rational? (sqrt 2))
#t
> (and (real? 1996) (real? (sqrt 2)))
#t

Notez bien qu'il n'existe pas de nombre réel non rationnel, puisque les nombres flottants n'ont qu'un nombre fini de chiffres après la virgule !

Les fonctions comme integer? dont le résultat est #t ou #f sont des prédicats. Par convention, le nom d'un prédicat se termine en général par un point d'interrogation '?'.

En vrai Racket, toute valeur distincte de #f est réputée vraie dans un test. Mais en langage Etudiant Avancé, seuls #t et #f sont des booléens !

Les expressions conditionnelles sont construites avec les mots-clés if, cond, and, or :

(cond (t1 e1) ... (else en))	; conditionnelle générale
(if p q r)	; <=> (cond (p q) (else r))
(and e1 e2 ...)	; de la gauche vers la droite
(or e1 e2...)	; de la gauche vers la droite

On insiste sur le fait que and , or et cond sont court-circuitées, ce ne sont pas des fonctions : or [resp. and] retourne la valeur de la première expression e_i [de gauche à droite] qui ait une valeur vraie [resp. fausse], ou bien celle de e_n. La forme cond retourne la première valeur e_i telle que t_i soit vrai, ou bien e_n. Dans tous les cas, le résultat est la dernière valeur calculée. Par contre, not est bien une fonction.

A quoi reconnaît-on que la forme (f x₁ x₂ ... x_n) est un appel de fonction ? Au fait que la valeur de f est un objet de type procédure :

• (+ 1 2) est un appel de fonction. En effet :

  > + #<primitive:+> > (procedure? +) #t

• lambda construit des fonctions. Ci-dessous, (carré 5) est un appel de fonction:

  > (define carre (lambda (x) (* x x))) > carre #<procedure:carre> > (procedure? carre) #t

Par contre, (if (odd? 1) 2 3) n'est pas un appel de fonction. En effet :

Les fonctions [primitives ou écrites en Scheme] sont des objets de type procedure. Les symboles comme if, cond, and, or, define, let,... sont des mots-clés de formes spéciales [keywords], et définitivement pas des noms de fonctions !

Qu'est-ce qui distingue les appels de fonctions des formes spéciales ? Leur mode d'évaluation :

• Dans un appel de fonction (f x₁ ... x_n), la valeur de f est une procédure F, les arguments e₁,...,e_n sont évalués [dans un ordre inconnu] et donnent des valeurs E₁,..., E_n. Le résultat est l'application de la procédure F aux valeurs E₁,...,E_n. C'est l'ordre applicatif d'évaluation.

• Dans une forme spéciale (m x₁ ... x_n) où m est un mot-clé comme if, and, or... c'est SPECIAL ! Chaque forme spéciale décide quels seront les arguments évalués et dans quel ordre. Vous ne pouvez pas créer de nouvelles formes spéciales avec define, il faut des macros.

La forme spéciale define permet de nommer le résultat de l'évaluation d'une expression :

(define <symbole> <expression>)

> (define degre (/ pi 180))   ; au toplevl
> degre
#i1.7453292519943278e-2

La forme spéciale lambda permet de construire une fonction anonyme, en évaluant une lambda-expression. Une fonction peut avoir plusieurs paramètres, mais retourne en principe un seul résultat [peut-être un couple, ou un autre objet structuré, mais sous la forme d'une seule valeur] :

La forme (compose f₁ ... f_n) retourne la fonction composée f₁ o ... o f_n :

On appelle fonction d'ordre supérieur une fonction dont le domaine de départ ou d'arrivée contient des fonctions. Exemple : l'opérateur de dérivation D : f -> f'. La programmation à l'ordre supérieur consiste à passer des fonctions en paramètre de manière à obtenir des traitements les plus généraux possibles [notion de "fonctions à textes isomorphes"]. Parmi les fonctions primitives d'ordre supérieur, citons map, filter et apply.

Les symboles primitifs ont une valeur au toplevel [dans l'environnement global] :

Cet environnement global G est réduit à un dictionnaire de couples <symbole,valeur>. De manière générale, un environnement E est une suite finie de dictionnaires :

D_n --> D_n-1 --> ... --> D₀=G

où G est le dictionnaire global. Typiquement, let construit un dictionnaire temporaire. Pour obtenir la valeur d'un symbole s dans un tel environnement E, on cherche [en commençant par D_n] le premier dictionnaire D_k contenant une liaison pour s, et l'on obtient l'erreur Undefined identifier si le symbole en question n'est lié dans aucun D_k, y-compris G.

L'application d'une lambda-expression (lambda (s₁ ... s_n) e) à des arguments x₁, ..., x_n, demandée dans un environnement E, consiste à étendre E par un petit dictionnaire D={<s₁,v₁>,...,<s_n,v_n>} où v_i est la valeur de l'argument x_i dans E. Le résultat de l'application sera la valeur de l'expression e dans l'environnement étendu :

E' = D --> E

Les variables locales sont construites par la forme spéciale de mot-clé let, avec la syntaxe :

Il s'agit seulement d'une douceur syntaxique [en réalité une macro] pour noter une application de lambda-expression :

((lambda (s₁ ... s_n) expr) x₁ ... x_n)

N.B. En programmation purement fonctionnelle, on peut considérer que les calculs des valeurs des variables locales ainsi définies se font en même temps [gasp].

La variante let* [le let séquentiel] permet de forcer le calcul des liaisons de la gauche vers la droite. Elle équivaut à une série de let emboîtés. C'est elle que l'on trouve en Java/C.

équivaut à :

(let ((s1 x1))
    (let ((s2 x2))            
      ...
        (let ((sn xn))
          expr)))

Avec Racket, on utilise très souvent la forme (local [(define...)] ...) pour construire des variables et fonctions locales. On peut imaginer qu'il s'agit d'un petit toplevel local embarqué dans la fonction. Les variables locales sont définies en séquence comme avec let*, mais on peut en plus définir des fonctions récursives locales, contrairement à let et let*.

Pour définir une fonction, on dispose de deux styles équivalents :

• le style puriste qui insiste sur le fait qu'une fonction est construite en évaluant une lambda :

(define carre (lambda (x) (* x x)))

• le style MIT, plus proche des autres langages, qui abstrait la forme d'appel :

(define (carre x) (* x x))

Dans un programme, il est sain de cacher les détails, en utilisant des fonctions internes. L'exemple typique est donné par la racine carrée de x par la méthode de Newton [[A&S] p. 25] :

C'est la notion de structure de blocs : la portée d'une variable est lexicale: en regardant simplement le texte du programme, on voit d'où provient sa dernière déclaration. En vrai Racket, on peut utiliser directement des define internes [en éliminant le mot local] ou bien un letrec plus précis mais plus lourd à écrire...

Une conséquence de la portée lexicale est la manière de calculer la valeur des variables figurant dans le corps d'une lambda-expression lors de l'application de cette lambda. Dans la fonction suivante :

(define add-a (lambda (x) (+ x a)))

x est une variable liée : elle sera liée à la valeur de l'argument lors de l'application de la lambda. Par contre, + et a sont des variables libres : leur valeur dépend du contexte. Quel contexte ? Le contexte lexical : leur valeur sera cherchée dans l'environnement dans lequel la lambda-expression a été évaluée, et non dans l'environnement dans lequel elle sera appliquée ! Un exemple :

La valeur d'une lambda-expression dans un environnement E est donc un couple ‹T,E› formé du texte T de la lambda, et d'un [pointeur vers l']environnement E, dit environnement de création. C'est dans cet environnement privé que seront cherchées les valeurs des variables libres de la lambda [ci-dessus les variables libres sont + et a]. Un tel couple ‹T,E› se nomme une FERMETURE [closure en anglais]. La valeur d'une lambda-expression est donc une fermeture. Toute fonction Scheme est soit une primitive soit une fermeture !

Une fonction est récursive si elle fait appel à elle-même [elle est définie par récurrence]. Ceci est une définition purement grammaticale et ne préjuge en rien de ce qui se passera dans la machine lors de l'exécution de la fonction. Scheme précise qu'il peut se passer deux choses distinctes :

(define (fac n)
  (if (zero? n) 1 (* n (fac (- n 1)))))

Cette fonction fac est dite récursive enveloppée, car l'appel récursif (fac (- n 1)) est enveloppé [par une multiplication *]. L'existence d'une enveloppe - donc d'un calcul à mettre en attente - a pour conséquence d'obliger le système à utiliser une pile pour exécuter un calcul (fac x). Une telle pile étant de hauteur bornée, il se peut qu'elle explose [boum] :

Par contre, la fonction facit est dite récursive terminale, car l'appel récursif à facit n'est pas enveloppé : il n'est suivi de rien d'autre dans le corps de la fonction [if a déjà joué !]. Aucune pile n'étant nécessaire - il n'y a rien à mettre en attente - Scheme qui est intelligent n'en utilise pas. On dit que l'on a affaire à un processus itératif de calcul, et par abus de langage, que la fonction facit est itérative [~ boucle while en Java]. Le concept de boucle est donc un cas particulier de récursivité [dans les langages comme Scheme qui optimisent la récursivité], ce qui explique au passage l'absence de mots-clé superflus for, while, do, etc. nécessaires aux langages [Java, Python, Ruby, etc] qui ne savent pas optimiser la récursivité alors que cette technologie date des années 70 notamment grâce aux Français...

N.B. Ce que dit très précisément la norme de Scheme, c'est qu'une récursivité terminale sera traitée comme une itération, donc sans pile. Rien n'empêche bien entendu l'état de la science d'avancer et d'éliminer la pile dans certains cas de récursivité profonde [par exemple lorsque l'enveloppe est associative], mais cette optimisation supplémentaire n'est pas garantie par la norme !

Les fonctions itératives sont plus efficaces [en espace de pile, pas forcément en temps de calcul] mais aussi plus difficiles à programmer, à prouver et à analyser que les fonctions récursives enveloppées. Commencez plutôt par penser de manière récursive profonde, comme en mathématique : posez votre sac à dos, posez l'hypothèse de récurrence, croisez les doigts et en général ça marche [ni plus ni moins qu'en maths]...

Les fonctions récursives locales se construisent en Scheme pur avec la forme spéciale letrec. Evaluée dans un environnement E, la forme :

commence par construire un dictionnaire local :

D = ((s₁ ?) ... (s_n ?))

où ? est une valeur non spécifiée [indéfinie]. Les expressions x₁,...,x_n [normalement des lambda-expressions] sont ensuite évaluées [dans un ordre quelconque] dans l'environnement étendu E' = D --> E et les valeurs obtenues vont remplacer les ?. Enfin, le corps e est évalué dans E' et sa valeur devient celle de la forme letrec. On dit que letrec est un opérateur de point fixe car il résoud en réalité des équations du type f = F(f). Un let serait faux dans la définition [correcte] suivante :

N.B. Les itérations locales se font aussi avec une boucle do masquant un letrec. Les définitions internes sont quand même bien plus agréables à lire...

La boucle do [version fonctionnelle] permet d'exprimer des itérations simples. Elle est automatiquement transformée en un letrec équivalent :

(do ((x1 i1 step1) ...)     <==>    (letrec ((iter (lambda (x1 ...)
  (test resultat))                                   (if test
                                                         resultat
                                                         (iter step1 ...)))))
                                       (iter i1 ...))

Le style CPS [Continuation Passing Style] : le style de programmation par passage à la continuation. L'idée consiste à prendre totalement en main le contrôle du calcul, de manière complètement itérative, afin d'éliminer à tout instant la pile de récursion, pour faire bien entendu des choses savantes, pas pour le simple plaisir...

Au lieu d'écrire une fonction (f x) qui calcule le résultat à partir de la donnée x, j'ajoute un argument k et je programme (f x k) où k [comme kontinuation] est une fonction à une variable. L'appel (f x k) calcule f(x) mais continue en appliquant la fonction k au résultat obtenu, donc en clair elle calcule k(f(x)). En prenant pour k l'identité (lambda (x) x), on retrouve la fonction f usuelle. Il s'agit donc d'une généralisation.

Prenons l'exemple de la factorielle, bestiole à tout faire. Au lieu de me contenter de programmer (fac n), je programme (fac n k) en CPS. Il est usuel de nommer k-fac la version CPS de fac :

Pour l'utiliser, il suffit de dire par quoi on continuera le calcul [vous sentez la morale : on passe au calcul un pointeur sur le calcul suivant, ce qui les chaîne entre eux] :

Il est facile de vérifier qu'une fonction écrite en CPS est AUTOMATIQUEMENT ITERATIVE. Comme d'autre part, la traduction en CPS d'une fonction récursive enveloppée ne requiert aucune intelligence [c'est parfaitement mécanique], on en déduit que l'on sait rendre itératif n'importe quel programme récursif. Et on aurait bien tort de s'en réjouir car le programme itératif obtenu est en général plus lent, à cause de la création de nombreuses lambda dans la mémoire-tas de l'application. En réalité, il s'agit là d'une première étape dans le processus de compilation, et CPS peut être considéré comme un langage intermédiaire. Mais pour ceci et les [très belles] applications du style CPS, vous êtes invités à lire un bon livre [PCPS bien entendu]... ou suivre un cours avancé :-)

Scheme possède de vraies continuations, utilisables avec la primitive call/cc, d'abord plus délicat.

2^ème partie : Doublets et Listes

La structure de base permettant de construire des données hiérarchiques est le doublet. C'est l'analogue de la notion de couple en maths. Mais en Scheme, on note (a . b) au lieu du traditionnel (a,b) des matheux. ATTENTION : en niveau de langage Etudiant Avancé, le second argument de cons doit obligatoirement être déjà une liste, et cons ne construira que des listes !

Une donnée Scheme est un doublet si elle répond #t au prédicat pair? :

> (and (pair? d) (pair? L))
#t
> (or (pair? (car d)) (pair? (first L)))
#f

Un triplet se construit à l'aide de doublets. Par exemple, mathématiquement :

(a,b,c) <==> ((a,b),c)

Supposons [hum] que l'on travaille avec un Scheme non muni des nombres rationnels. Un nombre rationnel r non nul pourrait alors se modéliser par un doublet (n . d) où n et d sont des entiers uniques tels que d > 0 et n premier avec d. Idem avec les complexes, matrices, etc.

En programmant avec les rationnels ci-dessus par exemple, on définit un type abstrait nombre rationnel muni d'opérations vérifiant certaines relations [les axiomes du type abstrait]. Puis on oublie la manière dont les rationnels ont été implémentés et l'on se force à programmer uniquement avec les opérations du type abstrait, qui pourraient être ici :

(créer-rationnel p q)	le rationnel p/q
(numerateur r)	le numérateur du rationnel r
(dénominateur r)	le dénominateur du rationnel r
(rationnel? x)	l'objet x est-il un rationnel ?

N.B. Si l'on souhaite alors programmer l'addition de deux rationnels, il serait très mal vu d'utiliser cons, car ou cdr !... Ceci est analogue à la situation du mathématicien qui travaille avec des nombres réels sans avoir vraiment besoin de savoir de quoi ils sont faits : seules leurs propriétés sont importantes. Sinon, vous seriez passible de violation d'abstraction de type [brrr]...

Si l'on souhaite construire des doublets contenant des symboles, il faut prendre garde à ne pas évaluer inutilement ces derniers, à les considérer comme des données à l'état brut et non comme des variables. On utilise pour cela le mécanisme de citation [la quote ou accent aigu] :

La forme abrégée 'expr est équivalente à (quote expr). La forme spéciale quote est une sorte d'identité non évaluante [comparez avec id]. On ne fait en principe aucune distinction majuscule-minuscule dans les lettres d'un symbole [qui n'est pas une chaîne de caractères !].

On peut quoter [citer] n'importe quelle expression pour empêcher son évaluation :

Ne confondez pas la quote [accent aigu] avec la quasiquote ou backquote [accent grave] !

Les symboles répondent #t au prédicat symbol? et leur égalité se teste avec le prédicat equal? :

Rien ni personne ne vous empêche de construire un doublet dont le car et/ou le cdr est lui-même un doublet, à la manière des poupées russes :

Mais le doublet boris ne s'affichera pas sous la forme attendue (1 . (2 . 3)) :

C'est LA CONVENTION DU '.(' : tout point suivi d'une parenthèse ouvrante est effacé, ainsi que la parenthèse ouvrante en question et la fermante correspondante.

Il existe un objet spécial s'affichant () et nommé liste vide [analogue de l'objet null de Java]. On est obligé de quoter la liste vide. Enfin, c'est le seul objet répondant #t au prédicat null?. En langage Etudiant Avancé, son synonyme est empty?.

L'existence conjointe des doublets et de la liste vide conduit à la notion de liste. Le concept de liste est défini par récurrence. Une liste est :

• ou bien la liste vide.

• ou bien un doublet (x . y) dont le cdr y est une liste.

Autrement dit, une liste non vide s'écrit (x₁ ... x_n) où les x_i sont des objets quelconques. Les listes répondent #t au prédicat list? dont le coût est cependant proportionnel à la longueur :

La fonction (build-list n f) retourne une liste de longueur n dont l'élément numéro i est f(i). Attention, le premier élément a pour numéro 0 :

Si L est une liste non vide, (car L) est le premier élément de L, tandis que (cdr L) est la liste privée de son car :

En langage Etudiant Avancé, first et rest utilisés sur des listes sont des synonymes de car et cdr.

Relisez encore une fois le § précédent, cela vous évitera beaucoup d'ennuis pénibles.

Plutôt que (car (cdr (cdr L))) etc. on utilise des notations contractées, ici (caddr L)...

La longueur d'une liste L s'obtient par la fonction (length L). Le coût en temps d'un calcul(length L) est d'ordre O(n), proportionnel à (length L). On s'efforcera donc de ne pas utiliser length dans les programmes sous peine de faire chuter les temps de calcul et d'obtenir très facilement des algorithmes de complexité O(n²)...

Le principe de RECURRENCE SUR LES LISTES s'énonce de la manière suivante. Pour prouver une propriété P(L) portant sur une liste L :

• on commence par prouver que la propriété est vraie pour la liste vide '().

• on montre que si la propriété est vraie pour toutes les listes de longueur strictement inférieure à la longueur d'une liste L, donc en particulier pour (cdr L) alors elle est vraie pour L.

La définition d'une fonction récursive se conduit comme une démonstration. Dans la plupart des cas, il suffit de supposer que si la fonction calcule ce qu'elle doit calculer pour (cdr L), alors on peut parvenir à lui faire calculer ce qu'elle doit calculer pour L.

N.B. : '(), L et (cdr L) jouent le rôle de 0, n et (- n 1) dans les entiers naturels.

La fonction de concaténation (append L₁ ... L_n) construit une liste dont les éléments sont les mêmes que ceux de L₁, ..., L_n. Plus précisément, elle procède par recopie des listes L₁, ..., L_n-1 donc son coût en temps et en espace est proportionnel à la somme des (length L_i), pour i=1..n-1 :

La fonction (reverse L) construit une liste dont les éléments sont les mêmes que ceux de la liste L, mais à l'envers. Son coût en temps et en espace est O(n), proportionnel à (length L) :

Les définitions de length, append et reverse [voir PCPS] sont à connaître quasiment par coeur. Récitez-les chaque soir avant la prière ou mieux le matin au réveil après le jus d'orange, l'esprit est plus frais...

Chaque appel à cons consomme un doublet [deux mots-mémoire]. La zone mémoire réservée aux doublets étant bornée, elle finira par être saturée. Lorsque cela se produit, le gestionnaire automatique de mémoire [alias Garbage Collector ou GC] se met en marche et rend les doublets non référencés à la mémoire libre. Cette opération dure une fraction de seconde. Si le recyclage a été couronné de succès, le programme continue son exécution, sinon qu'IL soit avec vous, et avec vos octets...

Les fonctions (equal? L₁ L₂) et (eq? L₁ L₂) permettent de tester l'égalité de deux listes. Mais attention :

- Deux listes sont dites equal? si elles s'affichent de la même manière au toplevel:

- Deux listes sont dites eq? si elles ne sont qu'un seul et même objet en mémoire [égalité de pointeurs]. Elles sont alors a fortiori equal?  :

N.B. En réalité, eq? teste l'égalité des références [adresses en mémoire]. Les symboles sont testés par eq? car un symbole n'apparaît qu'une seule fois dans la table des symboles. Ce n'est pas le cas des grands entiers qui peuvent être dupliqués en mémoire.

Une A-liste [ou "liste d'associations"] est une liste de listes :

où les c_i sont les clefs et les v_i les objets associés. Le plus souvent ce sont des listes à deux éléments. La fonction (assoc c AL) retourne la première association (c v) trouvée dans une A-liste AL, ou bien #f si la clef c n'y figure pas :

Plutot que d'emboîter les doublets à la manière des poupées russes, on utilise des diagrammes de boîtes et pointeurs. Par exemple, la liste (a b c d), qui pourrait être construite par :

(define L (cons 'a (cons 'b (cons 'c (cons 'd empty)))))

se présente ainsi en mémoire [occupation = 4 doublets] :

Dans un tel diagramme, chaque flèche est une référence [un pointeur] : la case contient en réalité l'adresse en mémoire de la case suivante [qui n'a aucune raison d'être physiquement contigüe, comme c'est le cas pour un tableau]. C'est cette organisation de la mémoire en spaghettis qui procure l'essentiel de la souplesse des listes, à savoir la facilité d'insérer ou supprimer un élément, contrairement à la rigidité d'un tableau. L'inconvénient est l'accès en temps O(k) à l'élément numéro k, ce qui n'est pas grave si le traitement de la liste est séquentiel.

Il se peut que le champ car d'une cellule de liste contienne lui même une liste, c'est le cas par exemple d'une A-liste. Dans ce cas, on fait sortir un pointeur vertical du car :

La fonction d'ordre supérieur (map f L₁ ... L_n) applique en parallèle la fonction n-aire f aux n-uplets formés des éléments de L₁,...,L_n de même rang. Toutes les listes L_i doivent être de même longueur :

La fonction d'ordre supérieur (filter p? L) retourne la liste des éléments de L vérifiant le prédicat p? :

La fonction d'ordre supérieur (apply f L) permet d'appliquer une fonction f d'arité n à une liste d'arguments L de longueur n. Utilisée avec map, elle permet entre autres d'effectuer des sommations :

Une lambda-fonction acceptant un nombre quelconque d'arguments s'écrit :

et non (lambda (L) expr). Le paramètre symbolique L sera lié à la liste des valeurs des arguments lors de l'application de la lambda. Il s'agit alors d'une fonction d'arité variable. Voici une fonction qui compte le nombre d'arguments :

Une fonction ayant par exemple au moins 2 arguments prendra comme liste de paramètres (a b . L) où L sera lié à la liste [éventuellement vide] des valeurs des arguments à partir du troisième.

Les structures chaînées dont "le dernier cdr" n'est pas vide sont des listes généralisées. Par exemple la liste :

(a (b () c) ((d e) . f) . g)

qui répond #f au prédicat list? [oui, bizarrement, une liste généralisée n'est pas forcément une liste ! Personnellement, je n'aime pas cette terminologie et préfère parler d'un "chaînage de doublets" quelconque]:

Il est essentiel de savoir passer de la représentation "boîtes et pointeurs" à la représentation linéaire parenthésée et réciproquement, ainsi que de savoir calculer le nombre de doublets occupés par un chaînage. Ce dernier problème n'est pas toujours évident à cause d'un possible partage de mémoire : combien y a-t-il de doublets dans chacune des listes construites ci-dessous ?

La possibilité que certains éléments d'une liste soient eux-mêmes des listes permet d'imaginer des parcours arborescents, où il peut être nécessaire de faire une hypothèse de récurrence à la fois sur le car et sur le cdr. Un exemple typique est donné par la fonction qui calculerait la liste des symboles d'une structure générale, et retournerait (a b c d e f g) pour un certain parcours [en profondeur et préfixe] de l'exemple ci-dessus.

Dernières corrections en date du 07.02.2011

Jean-Paul Roy
Département Informatique
Faculté des Sciences de Nice