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 :

Osm> (define une-paire (cons 1 2)
  => #unspecified

Osm> (car une-paire)
  => 1

Osm> (cdr une-paire)
  => 2

Osm> (set-car! une-paire 123)
  => #unspecified

Osm> (set-cdr! une-paire 456)
  => #unspecified

Osm> (car une-paire)
  => 123

Osm> (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 :

Osm> (define une-paire (my-cons 1 2)
  => #unspecified

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

Osm> (une-paire 'donne-queue #f)
  => 2

Osm> (une-paire 'change-tête 123)
  => #unspecified

Osm> (une-paire 'change-queue 456)
  => #unspecified

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

Osm> (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..