Het lastige aan references en pointers
Ik ben nu een tijdje bezig met mijn taal Ananke, en ik wil graag wat dingen delen betreft pointer/reference semantics.
Voorwoord over pointers en references
Als je niet weet wat pointers zijn, is deze alinea echt wat voor jou. Een pointer is een type variabele waar een geheugenadres in op wordt geslagen. Met de (soms onjuiste) implicatie dat op dat adres een object, bijvoorbeeld een getal (int), te vinden is.
Een reference is onder de motorkap ook een pointer. Maar erboven niet. Een reference kun je niet declareren zonder meteen een waarde toe te wijzen. Hierdoer MOET een reference per definitie altijd naar een geldig object verwijzen ten tijde dat de reference gemaakt/gedeclareerd wordt, terwijl een pointer kan wijzen naar niks (een NULL pointer die wijst naar adres 0, of een dangling pointer die verwijst naar geheugen dat al eerder vrij is gemaakt). References zijn ook niet aan te passen (eens verwezen naar a, altijd verwezen naar a) terwijl je het adres waar een pointer naar wijst wel kan veranderen (eerst een verwijzing naar a, daarna naar b). Een dangling reference kan echter WEL voorkomen! (zie voorbeeld bij kopje lifetimes)
References zijn dus gewoon const pointers, en hebben zodoende eigenlijk geen meerwaarde, behalve dat je ze niet expliciet hoeft te dereferencen. Maar is die syntax sugar voor references echt zo handig, of is het verwarrend dat derefs niet expliciet zijn? Ik ben persoonljk niet zo van de magische dingen die "gewoon werken".
In dit artikel is het woord "verwijzing" een synoniem voor zowel pointer als reference.
Pointer aliasing
Dit is wanneer je 2 verwijzingen hebt naar hetzelfde object. Wat is hier zo erg aan? Nou, als er aliasing is dan moet je bij elke dereference het object opnieuw laden, omdat het arme ding in de tussentijd misschien via de andere reference of pointer is aangepast.
int x = 1;
int* y = &x; // y verwijst naar x
int* z = &x; // z verwijst naar x
x += *y; // wordt x += x wordt x += 1
x += *z; // *z = nieuwe x = 2, dus het wordt x += 2
// als je z (x) niet herladen had, dan was er x += 1 gebeurd (fout)
Dit constante herladen is duur.
In C heb je het restrict keyword om aan te geven dat je weet wat je doet, en dat je weet dat een pointer niet aliast met een andere. In C++ en Rust, mits je de talen juist gebruikt, mag je simpelweg niet meerdere verwijzingen maken naar 1 object, of je moet dit via een speciaal pointer/reference type doen waardoor het alsnog duidelijk is voor de compiler of er mogelijk sprake is van een alias of niet.
Mutable references bestaan niet; references naar een mutable wel.
(Van mutatie; mutable: object kan aangepast worden; immutable/const: object is read-only)
Dit heeft met het voorgaande te maken. Stel je hebt een object a. Je neemt een mutable reference mut& mr = &a en een constant reference const& cr = &a De hele const& wordt nutteloos omdat je toch niet kan aannemen dat het object waar cr naar verwijst constant is; het kan immers op elk moment aangepast worden via mr. Mutability moet dus onderdeel zijn van het type van het object a zelf, en niet de reference. En wil je een verwijzing maken naar een int EN de belofte dat je het object niet aan zal passen via die verwijzing? Neem dan een const int *, een pointer naar een const int. De originele int hoeft dan niet eens const te zijn, maar dat weet de gebruiker van die pointer-naar-const niet. Nog een spijker in de grafkist van references waaruit blijkt dat ze geen voordeel bieden over pointers.
Lifetimes
Wat het allemaal nog lastiger maakt is het feit dat objecten automatische lifetimes hebben: alle lokale variabelen worden vernietigd als je een scope uit gaat. Maar de verwijzingen naar die variabele niet. Zo kun je een functie maken die lokaal een int maakt, en dan een pointer naar die int returnt. Tegen de tijd dat de functie call dan over is, danglet de pointer.
int* demo(){
int x = 5;
return &x; // pointer naar het adres van x
// x wordt hier vernietigd omdat het een lokale variabele is
}
int* y = demo(); // y is een dangling pointer
Maar deze automatische destructie geldt niet altijd! Dingen die gemallocd zijn, blijven actief totdat je ze weer free't. En dat moet je dan ook niet vergeten, anders krijg je memory leaks.
Het overkoepelende probleem
We willen onze taart tegelijk bewaren en opeten. We willen absolute, arbitraire controle over het geheugen. Tegelijkertijd willen we dat er automatisch achter ons wordt opgeruimd, alsof het een hotel is, en dat we worden behoed voor domme fouten als dangling dereferences.
Oplossing 1: ownership semantics (A.K.A. move semantics)
Move semantics: wederom een misnomer vanuit C++. Hier is wat die semantics doen: stel, alle objecten in het geheugen zijn honden. Honden hebben maar 1 halsband en dus maar 1 lijn. Er kan dus maar 1 baasje (pointer) tegelijk zijn die de hond vast houdt. Moven (C++) of borrowen (Rust) is het verwisselen van baasje. Een borrow checker kan door middel van statische analyse afdwingen dat alle honden maar door 1 baasje tegelijk worden vastgehouden. Op het moment dat het baasje out of scope gaat, wordt het hondje automatisch mee verwijderd (C++ noemt dit RAII, Resouce Acquisition is Initialization, inderdaad, slaat nergens op, we gaan verder).
N.B. Je hebt ook shared objects, in Rust gebruik je hier reference counting voor. Je hebt een halsband met meerdere lijnen (jep, de analoog gaat hier inderdaad gruwelijk op zijn bek), maar er wordt op elk moment bijgehouden hoeveel baasjes er aan de hond trekken, en voor zover ik weet mag alsnog maar 1 baasje tegelijk de hond aanpassen.
Ownership semantics voorkomen een hele klasse geheugen-gerelateerde problemen: bijvoorbeeld 2 pointers naar 1 hond nemen, en via de ene pointer de hond vrijlaten, om vervolgens via de andere pointer (die nu danglet) iets proberen te doen met de hond. Oeps!
int* x = malloc(sizeof(int)); // claim een stukje geheugen voor een int
int* y = x; // het adres waar y naar verwijst is gelijk gesteld aan het adres waar x naar verwijst
free(x); // geef het stukje geheugen weer vrij
*y = 5; // oeps, we schrijven nu naar een stuk geheugen wat niet meer van ons is
Maar, dat er meerdere pointers naar 1 object wijzen hoeft niet per se een treinramp te zijn. Je kan er ook gewoon voor kiezen om geen fouten te maken. Genuanceerder: er zijn legitieme gevallen waar 2 of meer verwijzingen gewoon prima zijn, zoals bij doubly linked list. Alle dingen die een borrow checker toe laat zijn sowieso veilig. Maar niet alle dingen die een borrow checker tegenhoudt, zijn onveilig. Een borrow checker kan dus soms heel beperkend werken. Ananke is een taal die de programmeur vertrouwt en ervan uit gaat dat die weet wat hij doet, dus eigenlijk past een borrow checker niet in Ananke. Maar toch zou ik een borrow checker willen voor wanneer ik de extra veiligheid blief: in dat geval moet het onderdeel van het type van het object worden of het object ge borrow checked moet worden of niet.
Maar dan krijg je het probleem dat je er niet vanuit kan gaan dat de compiler je beschermt tegen zulke domme fouten. Immers weet je niet altijd of een object geborrowchecked is of niet. Nu snap je meteen waarom Rust het unsafe keyword heeft, exact om aan te geven dat er o.a. geen borrow checking is. Oh, wacht! unsafe is fundamenteel kapot! Ja, je kan nog zo'n grote fout netjes in een unsafe block stoppen, maar de overkoepelende scope, bijvoorbeeld functie, blijft volgens Rust gewoon safe. Als ik dus een library gebruik, moet ik elke keer opnieuw source code lezen om te kijken of er iets unsafes gebeurt in een functie. unsafe is dus schijnveiligheid, tenzij je het propageert (wat Rust dus niet doet): als een functie een unsafe block bevat, zou de hele functie unsafe moeten worden. Maar ja, dat is weer onergonomisch. Je snapt natuurlijk dat 1 klein unsafe'je dan compleet omhoog "bubbelt", en vrijwel alles unsafe wordt. En dat is exact juist. unsafe is unsafe. unsafe is niet zo maar, ineens, magisch safe door het in een functie te wikkelen. Dit is echt iets wat Rust heeft verknald, maar de community lijkt er niet op te letten, in plaats daarvan lijkt men te denken dat alles in Rust automatisch 100% memory safe is (nee dus).
N.B. 12x unsafe in deze paragraaf, nu 13x.
Oplossing 2: garbage collection
Verreweg de makkelijkste oplossing is om garbage collection te gebruiken. Dat maakt dingen gewoon ziek makkelijk voor de programmeur. Alle vrijheid van een onbelemmerd geheugenmanagementsysteem zoals in C, met alle veiligheid van een systeem zoals in Rust. Het nadeel van garbage collection is dat dit ook CPU kost: nu moet het programma, terwijl het draait, gaan bijhouden welke objecten het in geheugen heeft, en op hoe veel plekken naar die objecten wordt verwezen. Daarnaast moet het eens in de zo veel tijd, conform de boekhouding, objecten waarnaar geen verwijzingen meer bestaan vrijmaken, wat kan leiden tot stotteringen. Allemaal uren op de klok die niet worden besteed aan werk, maar aan bureaucratie. Zonde!
Nog erger, sommige vormen van garbage collection, bijvoorbeeld reference counting, kunnen alsnog geheugen lekken, bij circulaire verwijzingen bijvoorbeeld (object a en b: a bevat een pointer die wijst naar b, b bevat een pointer die wijst naar a). En de reden dat Python zo slecht te multithreaden is, en een van de redenen dat de taal algeheel zo traag is, is de reference counting garbage collector! Maar je kan het ook goed doen: zelden hoor ik geklaag over de mark and sweep garbage collector van Java, behalve wanneer het gaat over hoeveel geheugen (een paar megabyte als ik het me goed herinner) een hello world programma in beslag neemt. Het ding is echter dat dit een miniscule kostenpost is in het hedendaagse computerlandschap. Maar ik snap dat voor mensen die voor embedded platforms programmeren elke byte kan tellen, en dat die dus graag handmatig het geheugen beheren. Maar voor de common use case is garbage collection stiekem best wel nice, zoals we nu allemaal hopelijk gezien hebben.
Conclusie
Er is in Ananke geen plek voor references, het mag blijken dat pointers voldoen. Ten tweede voeg ik een optionele garbage collector toe. Ten derde voeg ik een safe keyword toe, voor array bound checks en borrow checking. En als je je hele programma safe wil maken, zal je er voor moeten werken. Want dat is het, hard werk. Voor de rest wordt alle memory management handmatig, zoals in C. Of een object garbage collected wordt, zal afhangen van zijn storage specifier (heap, stack, static, garbage, auto). Via escape analysis krijgt een ongeannoteerd object automatisch de garbage specifier als er een pointer naar gemaakt wordt. Anders wordt het een stack variabele, tenzij het heel groot is, dan wordt het heap, en wordt het net als bij C++ automatisch opgeruimd als de scope voorbij is.
2021-09-26 in blog #programmeren #pointers #Ananke