Définition du sous‑type

Le principe de substitution de Liskov stipule qu’un type S est sous‑type de T si chaque valeur de type S peut être employée dans tous les contextes où l’on attend une valeur de type T. Cette exigence est absolue : la moindre situation où le comportement diffère viole la relation de sous‑typage et le vérificateur de types doit le détecter.

Contrat d’immuabilité et conséquences

Pour un couple immuable, les opérations sont limitées à la construction et à la lecture :

(cons a d)   ; crée un couple immuable
(car p)      ; renvoie la première composante
(cdr p)      ; renvoie la seconde composante

Le contrat associé garantit que car et cdr renvoient toujours les mêmes valeurs pour un même objet. Cette stabilité rend possible le calcul de hachage fiable, la mise en cache ou le « hash‑consing », car le code peut supposer que le résultat ne changera jamais tant que le couple existe.

Pourquoi la sous‑typage échoue

Un couple mutable ajoute les mutateurs :

(set-car! p a)   ; modifie la première composante
(set-cdr! p d)   ; modifie la seconde composante

Bien que toutes les opérations d’un couple immuable soient présentes dans le mutable, le contrat d’immuabilité n’est plus respecté. Un contexte qui s’appuie sur la constance du résultat (par exemple, stockage dans une table de hachage) pourrait recevoir un couple dont le contenu a changé entre deux appels, ce qui violerait la spécification attendue du type immuable. Ainsi, un mutable ne peut pas être substitué partout où un immuable est requis, sinon la garantie de stabilité serait rompue.

Solutions via polymorphisme ad hoc

Les langages statiquement typés introduisent souvent des type classes (ou interfaces, traits) pour regrouper les opérations communes sans imposer de relation de sous‑typage. On définit une classe Pair avec car et cdr. Les implémentations ImmutablePair et MutablePair fournissent chacune leurs versions respectives (icar/icdr et mcar/mcdr). Le système de types vérifie que les mutateurs ne sont pas appelés lorsqu’une fonction ne spécifie que le contrat Pair. Cette approche conserve la sécurité du contrat d’immuabilité tout en permettant le partage d’une API commune.