Het artikel legt uit waarom onveranderlijke (immutable) en veranderlijke (mutable) datastructuren in programmeertalen geen subtype-relatie kunnen hebben. Centraal staat het substitutieprincipe van Liskov, dat stelt dat een subtype in elke context van het supertype gebruikt moet kunnen worden.
De auteur illustreert dit aan de hand van een pair-datastructuur:
\rightarrow$ Mutable:** Een onveranderlijke pair kan geen subtype zijn van een veranderlijke pair, omdat deze de noodzakelijke mutatie-operaties (zoals set-car!) mist, wat leidt tot typefouten.
\rightarrow$ Immutable:** Een veranderlijke pair kan geen subtype zijn van een onveranderlijke pair omdat dit het impliciete contract van onveranderlijkheid schendt. Dit is cruciaal voor zaken als hash consing, waarbij men erop vertrouwt dat een waarde nooit wijzigt.
Om toch gemeenschappelijke functionaliteit te delen, adviseert de auteur het gebruik van ad-hoc polymorfisme via type classes, interfaces of traits. Hiermee kunnen operaties worden gedeeld zonder de strikte contracten van mutabiliteit te schenden. In dynamisch getypeerde talen gebeurt dit vaak via duck typing, al is dit risicovoller omdat er zelden expliciet wordt gecontroleerd op de afwezigheid van mutatoren.
FAQ: Waarom is 'mutable' geen subtype van 'immutable', of vice versa?
"Ik herinner me het moment dat ik over onveranderlijkheid (immutability) leerde. Het veranderde alles."
— Denis Defreyne
Het substitutieprincipe van Liskov
Om te begrijpen waarom dit niet werkt, moet je het definitie van een subtype onthouden, namelijk het substitutieprincipe van Liskov: een type $S$ is een subtype van $T$ als een waarde van type $S$ gebruikt kan worden in elke context waar een waarde van type $T$ wordt verwacht.
Bij formele zaken wordt deze definitie strikt geïnterpreteerd. "Elke" betekent hier echt elke, niet alleen de meeste. (Je hebt het substitutieprincipe wellicht geleerd als een aanbevolen design pattern voor OO-klassen, maar formeel gezien moet een echt subtype aan dit criterium voldoen.) Een statisch typesysteem dat subtyping ondersteunt, moet dit voor je kunnen bewijzen om je programma door de type checker te laten gaan.
Voorbeeld: De Pair-datastructuur
Om dit te illustreren nemen we de simpelste samengestelde datastructuur die we ons kunnen voorstellen: de bescheiden pair. Hier zijn de operaties voor een onveranderlijke versie:
(cons a d): construeert een nieuwe pair die a en d bevat en geeft deze terug.(car p): geeft de waarde van a terug zoals opgegeven bij de constructie van pair p.(cdr p): geeft de waarde van d terug zoals opgegeven bij de constructie van pair p.
De veranderlijke (mutable) variant voegt hier twee nieuwe operaties aan toe:
(set-car! p a): verandert de waarde van a binnen de pair p.(set-cdr! p d): verandert de waarde van d binnen de pair p.
(Er is ook een nieuwe constructor, maar die behandelen we hieronder.)
Het zou nu duidelijk moeten zijn dat een onveranderlijke pair niet kan worden aangeboden waar een veranderlijke pair wordt verwacht. Een plek die een veranderlijke pair nodig heeft, zal waarschijnlijk een van deze twee mutatie-operaties proberen te gebruiken, die niet gedefinieerd zijn voor een onveranderlijke pair. Dit leidt tot een typefout.
Waarom kan het niet andersom?
Men zou kunnen denken dat het wel andersom kan. Alle operaties die een onveranderlijke pair biedt, worden immers ook geboden door een veranderlijke pair. Het lijkt dus alsof we een veranderlijke pair zouden moeten kunnen gebruiken overal waar een onveranderlijke pair wordt verwacht.
De reden hiervoor is subtieler. Het substitutieprincipe strekt zich verder uit dan de set operaties (methoden) die een type biedt; het omvat ook het impliciete contract dat bij die operaties hoort.
Wanneer we de car of cdr van een onveranderlijke pair opvragen, kunnen we vertrouwen op het contract dat zegt dat het resultaat altijd hetzelfde zal zijn, elke keer dat we het op die pair aanroepen. Dit contract betekent dat we bijvoorbeeld veilig de hashwaarde van de pair kunnen berekenen op basis van de inhoud, deze kunnen opslaan in een andere datastructuur, en kunnen weten dat deze niet anders zal zijn wanneer we deze later opnieuw berekenen om de pair terug te vinden. (Met andere woorden: onveranderlijkheid is een voorwaarde voor hash consing!)
De noodzaak van volledig verschillende types
Vanwege dit verschil moeten onveranderlijke en veranderlijke pairs volledig verschillende types zijn:
Onveranderlijke pair:
(icons a d): construeert een nieuwe onveranderlijke pair met a en d.(icar i): geeft de waarde van a terug.(icdr i): geeft de waarde van d terug.
Veranderlijke pair:
(mcons a d): construeert een nieuwe veranderlijke pair met a en d.(mcar m): geeft de waarde van a terug.(mcdr m): geeft de waarde van d terug.(set-mcar! m a): verandert de waarde van a.(set-mcdr! m d): verandert de waarde van d.
Het is een typefout als een i een veranderlijke pair is, of als een m een onveranderlijke pair is.
Bezwaar: "Ik muteer hem niet en het contract van onveranderlijkheid is niet relevant voor mijn use case"
Omdat de twee types pair geen subtype-hiërarchie vormen, moeten ze volledig gescheiden types zijn met aparte sets operaties.
Gelukkig bieden veel talen een mechanisme voor ad-hoc polymorfisme, waarbij dezelfde operaties op meerdere types kunnen worden gedefinieerd, zelfs als ze geen hiërarchie vormen. Als Schemer ben ik geneigd te denken dat dit een slecht idee is in een dynamisch getypeerde context, omdat het de redenering over de flow van datatypes veel complexer maakt en dus moeilijker correct uit te voeren is. In de praktijk bieden de meeste talen echter een mechanisme hiervoor, of ze nu dynamisch of statisch getypeerd zijn.
Statisch getypeerde talen
Wadler en Blott introduceerden een mechanisme om formeel te redeneren over ad-hoc polymorfisme en om te garanderen dat de type checker dit daadwerkelijk als correct (sound) kan bewijzen. In hun terminologie zijn veranderlijke en onveranderlijke pairs verschillende types, maar kunnen ze beide behoren tot een gemeenschappelijke pair type class, waarvan de operaties de oorspronkelijke car en cdr zijn. Bij veranderlijke pairs verwijzen deze naar de onderliggende mcar- en mcdr-operaties, en bij onveranderlijke pairs naar de icar- en icdr-operaties.
Dit is formeel nog steeds correct omdat de pair type class een nieuw contract definieert dat niets zegt over mutabiliteit. In een correcte implementatie van type classes zal het typesysteem je tegenhouden om mutatoren te gebruiken in een methode waar het enige dat je hebt gedefinieerd over het inputtype is dat het een soort pair is (veranderlijk of onveranderlijk). Het voorkomt niet dat je car- en cdr-operaties gebruikt in de verwachting dat ze onveranderlijk zijn terwijl dat misschien niet zo is – maar het stelt je wel in staat om de granulariteit expliciet te kiezen. Je kunt het inputtype van je functie declareren als een veranderlijke pair, een onveranderlijke pair, of beide, afhankelijk van het contract dat je functie verwacht. Een subtype-relatie zou slechts één richting toelaten, maar niet de andere: je zou je functie kunnen declareren als toestaand onveranderlijke pairs, maar dan impliciet (en potentieel onjuist) ook veranderlijke pairs includeren; of andersom, veranderlijke pairs toestaan maar onterecht onveranderlijke pairs includeren. Men zou geen van beide types consistent kunnen uitsluiten zonder het substitutieprincipe te schenden.
Dingen die lijken op type classes zijn beschikbaar in diverse statisch getypeerde talen, waar ze vaak interfaces, traits of roles worden genoemd. De striktheid waarmee real-world typesystemen dit controleren, varieert echter sterk.
Dynamisch getypeerde talen
In dynamisch getypeerde, objectgeoriënteerde talen neemt dit meestal de vorm aan van duck typing, waarbij we simpelweg methoden met dezelfde naam op verschillende types definiëren en de run-time type dispatch het werk laten doen. We kunnen de voordelen hiervan behalen door expliciete checks toe te voegen voor de aanwezigheid of afwezigheid van mutatie-operaties voordat een functie wordt aangeroepen. In de praktijk is het vrij ongebruikelijk om dit te doen – zeker het controleren op de afwezigheid van mutatoren – en dit is de reden waarom ad-hoc polymorfisme in dynamisch getypeerde talen vaak tot problemen leidt.
FAQ: Waarom is 'mutable' geen subtype van 'immutable', of vice versa?
"Ik herinner me het moment dat ik over onveranderlijkheid (immutability) leerde. Het veranderde alles."
— Denis Defreyne
Het substitutieprincipe van Liskov
Om te begrijpen waarom dit niet werkt, moet je het definitie van een subtype onthouden, namelijk het substitutieprincipe van Liskov: een type $S$ is een subtype van $T$ als een waarde van type $S$ gebruikt kan worden in elke context waar een waarde van type $T$ wordt verwacht.
Bij formele zaken wordt deze definitie strikt geïnterpreteerd. "Elke" betekent hier echt elke, niet alleen de meeste. (Je hebt het substitutieprincipe wellicht geleerd als een aanbevolen design pattern voor OO-klassen, maar formeel gezien moet een echt subtype aan dit criterium voldoen.) Een statisch typesysteem dat subtyping ondersteunt, moet dit voor je kunnen bewijzen om je programma door de type checker te laten gaan.
Voorbeeld: De Pair-datastructuur
Om dit te illustreren nemen we de simpelste samengestelde datastructuur die we ons kunnen voorstellen: de bescheiden pair. Hier zijn de operaties voor een onveranderlijke versie:
(cons a d): construeert een nieuwe pair die a en d bevat en geeft deze terug.(car p): geeft de waarde van a terug zoals opgegeven bij de constructie van pair p.(cdr p): geeft de waarde van d terug zoals opgegeven bij de constructie van pair p.
De veranderlijke (mutable) variant voegt hier twee nieuwe operaties aan toe:
(set-car! p a): verandert de waarde van a binnen de pair p.(set-cdr! p d): verandert de waarde van d binnen de pair p.
(Er is ook een nieuwe constructor, maar die behandelen we hieronder.)
Het zou nu duidelijk moeten zijn dat een onveranderlijke pair niet kan worden aangeboden waar een veranderlijke pair wordt verwacht. Een plek die een veranderlijke pair nodig heeft, zal waarschijnlijk een van deze twee mutatie-operaties proberen te gebruiken, die niet gedefinieerd zijn voor een onveranderlijke pair. Dit leidt tot een typefout.
Waarom kan het niet andersom?
Men zou kunnen denken dat het wel andersom kan. Alle operaties die een onveranderlijke pair biedt, worden immers ook geboden door een veranderlijke pair. Het lijkt dus alsof we een veranderlijke pair zouden moeten kunnen gebruiken overal waar een onveranderlijke pair wordt verwacht.
De reden hiervoor is subtieler. Het substitutieprincipe strekt zich verder uit dan de set operaties (methoden) die een type biedt; het omvat ook het impliciete contract dat bij die operaties hoort.
Wanneer we de car of cdr van een onveranderlijke pair opvragen, kunnen we vertrouwen op het contract dat zegt dat het resultaat altijd hetzelfde zal zijn, elke keer dat we het op die pair aanroepen. Dit contract betekent dat we bijvoorbeeld veilig de hashwaarde van de pair kunnen berekenen op basis van de inhoud, deze kunnen opslaan in een andere datastructuur, en kunnen weten dat deze niet anders zal zijn wanneer we deze later opnieuw berekenen om de pair terug te vinden. (Met andere woorden: onveranderlijkheid is een voorwaarde voor hash consing!)
De noodzaak van volledig verschillende types
Vanwege dit verschil moeten onveranderlijke en veranderlijke pairs volledig verschillende types zijn:
Onveranderlijke pair:
(icons a d): construeert een nieuwe onveranderlijke pair met a en d.(icar i): geeft de waarde van a terug.(icdr i): geeft de waarde van d terug.
Veranderlijke pair:
(mcons a d): construeert een nieuwe veranderlijke pair met a en d.(mcar m): geeft de waarde van a terug.(mcdr m): geeft de waarde van d terug.(set-mcar! m a): verandert de waarde van a.(set-mcdr! m d): verandert de waarde van d.
Het is een typefout als een i een veranderlijke pair is, of als een m een onveranderlijke pair is.
Bezwaar: "Ik muteer hem niet en het contract van onveranderlijkheid is niet relevant voor mijn use case"
Omdat de twee types pair geen subtype-hiërarchie vormen, moeten ze volledig gescheiden types zijn met aparte sets operaties.
Gelukkig bieden veel talen een mechanisme voor ad-hoc polymorfisme, waarbij dezelfde operaties op meerdere types kunnen worden gedefinieerd, zelfs als ze geen hiërarchie vormen. Als Schemer ben ik geneigd te denken dat dit een slecht idee is in een dynamisch getypeerde context, omdat het de redenering over de flow van datatypes veel complexer maakt en dus moeilijker correct uit te voeren is. In de praktijk bieden de meeste talen echter een mechanisme hiervoor, of ze nu dynamisch of statisch getypeerd zijn.
Statisch getypeerde talen
Wadler en Blott introduceerden een mechanisme om formeel te redeneren over ad-hoc polymorfisme en om te garanderen dat de type checker dit daadwerkelijk als correct (sound) kan bewijzen. In hun terminologie zijn veranderlijke en onveranderlijke pairs verschillende types, maar kunnen ze beide behoren tot een gemeenschappelijke pair type class, waarvan de operaties de oorspronkelijke car en cdr zijn. Bij veranderlijke pairs verwijzen deze naar de onderliggende mcar- en mcdr-operaties, en bij onveranderlijke pairs naar de icar- en icdr-operaties.
Dit is formeel nog steeds correct omdat de pair type class een nieuw contract definieert dat niets zegt over mutabiliteit. In een correcte implementatie van type classes zal het typesysteem je tegenhouden om mutatoren te gebruiken in een methode waar het enige dat je hebt gedefinieerd over het inputtype is dat het een soort pair is (veranderlijk of onveranderlijk). Het voorkomt niet dat je car- en cdr-operaties gebruikt in de verwachting dat ze onveranderlijk zijn terwijl dat misschien niet zo is – maar het stelt je wel in staat om de granulariteit expliciet te kiezen. Je kunt het inputtype van je functie declareren als een veranderlijke pair, een onveranderlijke pair, of beide, afhankelijk van het contract dat je functie verwacht. Een subtype-relatie zou slechts één richting toelaten, maar niet de andere: je zou je functie kunnen declareren als toestaand onveranderlijke pairs, maar dan impliciet (en potentieel onjuist) ook veranderlijke pairs includeren; of andersom, veranderlijke pairs toestaan maar onterecht onveranderlijke pairs includeren. Men zou geen van beide types consistent kunnen uitsluiten zonder het substitutieprincipe te schenden.
Dingen die lijken op type classes zijn beschikbaar in diverse statisch getypeerde talen, waar ze vaak interfaces, traits of roles worden genoemd. De striktheid waarmee real-world typesystemen dit controleren, varieert echter sterk.
Dynamisch getypeerde talen
In dynamisch getypeerde, objectgeoriënteerde talen neemt dit meestal de vorm aan van duck typing, waarbij we simpelweg methoden met dezelfde naam op verschillende types definiëren en de run-time type dispatch het werk laten doen. We kunnen de voordelen hiervan behalen door expliciete checks toe te voegen voor de aanwezigheid of afwezigheid van mutatie-operaties voordat een functie wordt aangeroepen. In de praktijk is het vrij ongebruikelijk om dit te doen – zeker het controleren op de afwezigheid van mutatoren – en dit is de reden waarom ad-hoc polymorfisme in dynamisch getypeerde talen vaak tot problemen leidt.
Groetjes,