Borrow Checking: Zero-Cost Cyclische Mutabiliteit

Ante is een low-level[^1] functionele taal gebaseerd op eigendomsemantiek (ownership semantics) en lenen (borrowing), vergelijkbaar met Rust.

In tegenstelling tot Rust is een kerndoel van Ante om coulanter te zijn in de borrow checker. Met name wil Ante de regel van Rust versoepelen die stelt dat je een referentie ofwel mag aliassen (meerdere referenties naar hetzelfde object) of mag muteren, maar nooit beide tegelijkertijd.

// In Rust:
let mut my_tuple = (1, 2);
let first_elem = &my_tuple.0;
// error[E0506]: cannot assign to `my_tuple` because it is borrowed
my_tuple = (3, 4);
println!("{first_elem}");

Ik wilde code zoals hierboven toestaan, terwijl ik nog steeds code verbied die zou leiden tot dangling pointers, en ik wilde dit volledig statisch in het typesysteem realiseren.

Dit is inmiddels oud nieuws; het allereerste blogbericht op deze site behandelde dit al. Dat bericht is inmiddels behoorlijk verouderd. In de afgelopen jaren is de aanpak van Ante aanzienlijk veranderd en zijn er veel toevoegingen gedaan om het flexibeler te maken. Nu is het opnieuw veranderd, waarbij elementen van group borrowing zijn gecombineerd met mijn eigen ideeën om tot een radicaal veiliger geheel te komen.

In dit artikel wil ik het nieuwe ontwerp toelichten en laten zien hoe dit leidt tot een flexibelere vorm van veilige, gedeelde mutabiliteit die expressief genoeg is om cyclische mutabiliteit en complexe datastromen veilig te ondersteunen.

Waarom gedeelde mutabiliteit?

Aangezien veel Rust-gebruikers sceptisch zijn over de waarde van gedeelde mutabiliteit, is het de moeite waard om te herhalen waarom meer coulantheid hierin nuttig is. Meer coulantheid betekent:

• Minder borrow checker-fouten. Minder fouten verlaagt de leercurve voor nieuwe gebruikers en versnelt de iteratietijden voor ervaren gebruikers.
• Meer design patterns zijn toegestaan. Het observer pattern is moeilijk te implementeren zonder gedeelde mutabiliteit. Cyclische types kunnen ook directer worden gerepresenteerd.
• Bestaande design patterns hebben minder workarounds nodig. In het bijzonder minder gedwongen indexering in vectoren. Hoewel dit een nuttig patroon kan zijn, vind ik niet dat de taal gebruikers tot deze aanpak moet dwingen.
• Eenvoudigere interoperabiliteit met andere talen die ook gedeelde mutabiliteit ondersteunen.

Dat laatste punt is belangrijker dan het lijkt. Ante is bedoeld om in zekere mate opt-in te zijn voor eigendom (ownership), zodat het gebruik ervan standaard meer aanvoelt als C# dan als Rust. Dit is een ambitieus doel, maar het toestaan van gedeelde mutabiliteit helpt hierbij enorm.

Terzijde: Wat was er mis met de vorige regels van Ante?

Voor wie nieuw is aan Ante, kan deze sectie worden overgeslagen. Voor de nieuwsgierigen leg ik hier uit waarom de regels zijn veranderd.

Het oorspronkelijke artikel beschreef de ref en mut referenties van Ante als analogen van &Cell<T>. De meeste uitbreidingen waren bedoeld om dit te verruimen, met name door de introductie van "lokale uniciteit". Dit hield in dat een gedeelde muteerbare referentie alleen lokaal uniek hoefde te zijn om gebruikt te worden waar een uniq referentie (denk aan &mut T in Rust) werd verwacht. De compiler hoefde alleen aan te tonen dat elke variabele die tegelijkertijd met een mut String werd gebruikt, deze niet muteerbaar aliaste.

Dit kreeg de vorm van een Distinct a b trait, die werd geïmplementeerd als a nergens binnen b voorkwam. Bijvoorbeeld, als je een Vec I32 gebruikt terwijl een mut String wordt behandeld als een uniq String, controleerde de compiler op de achtergrond een Distinct String (Vec I32) constraint. Omdat een String niet in een Vec I32 kan voorkomen, is de code toegestaan en is de String lokaal uniek.

Het toestaan van wat in feite een conversie van &Cell<T> naar &mut T is, was geweldig voor de flexibiliteit, maar had enkele grote gebreken:

1. Veelvoorkomende types zoals String komen vaker voor in andere types, waardoor ze moeilijker te gebruiken waren in vergelijking met minder voorkomende types bij conversie naar een lokale uniq referentie.
2. Distinct a b recurseert in elk veld van b, inclusief private velden. Dit betekende dat het toevoegen van een privaat veld aan een publieke struct in een library een breaking change was, omdat het voorheen geldige lokale unieke conversies ongeldig kon maken.
3. Conversies tussen mut en lokale uniq gebeurden vaak en waren verwarrend, ook al deed de compiler dit automatisch.
4. Het vertrouwde op vier referentietypes: ref en mut (die gedeelde mutabiliteit toestaan) en imm en uniq (die dat niet doen).

Het was niet alleen maar slecht. Het was krachtig genoeg om veilige, cyclische mutabiliteit te coderen, met het voorbehoud dat sommige Rc-waarden gekloond moesten worden (de referentieteller verhoogd) tijdens het traverseren.

Om bovenstaande redenen was het duidelijk dat het ontwerp moest veranderen. Het nieuwe ontwerp lost deze problemen op, terwijl de goede aspecten, zoals veilige cyclische mutabiliteit[^2] en thread-veiligheid, behouden blijven.

Het kernprobleem

Waarom zijn sommige gevallen van gedeelde mutabiliteit veilig, zoals:

my_safe_fn (var pair: String, String) =
  name = ref pair.first
  pair.first := "Foo"
  println name  // Ok!

Terwijl andere dat niet zijn:

my_unsafe_fn (vec: mut Vec t) =
  elem = vec.get 1
  vec.clear ()
  println elem  // Dangling ref!

Het verschil zit in wat ik vormstabiliteit (shape stability) noem. Als de vorm van een type stabiel is, is er geen manier om het te muteren zodanig dat een voorheen geldige referentie ernaar ongeldig wordt.

Kijk naar hoe pair en name in het geheugen liggen:

Vóór mutatie: name → pair: ((firstptr, firstlen, ..), (secondptr, secondlen, ..))

Na mutatie: name → pair: ((firstptr, firstlen, ..), (secondptr, secondlen, ..))

Elke String is een unboxed tuple van ptr, len en metadata, en elk component van de outer pair is ook unboxed. Met deze layout is er geen manier om pair te muteren waardoor name ongeldig wordt.

Kijk we echter naar vec en elem, dan zien we een duidelijk verschil:

Vóór mutatie: vec: (data_ptr, length, capacity) → [0, 1, 2, 3] $\leftarrow$ elem

Na mutatie: vec: (data_ptr, length, capacity) → [] (waarbij elem nu naar een ongeldige locatie wijst)

elem is duidelijk een dangling reference. Het probleem is dat het muteren van vec de data_ptr kan muteren, waardoor deze potentieel elders gaat wijzen bij herallocatie. De vorm is veranderd, waardoor elem gestrand is.

Het zou ideaal zijn als een referentietype kon onthouden of het wijst naar iets dat stabiel of onstabiel is. Dan kunnen we uniciteit vervangen door een accuratere restrictie die minder geldige programma's afwijst.

"Places" in plaats van "Lifetimes"

Het eerste deel van de oplossing is het gebruik van places (plaatsen) in plaats van lifetimes.

In tegenstelling tot een lifetime, wat een abstract symbool is voor een regio in de code, is een place de exacte set van zaken waar een referentie van mag lenen:

foo (x: I32) (y: I32): Unit =
  r1: ref 'x I32 = ref x
  r2: ref 'y I32 = ref y
  r3: ref '(x, y) I32 =
    if true then ref x else ref y

Hierboven leent r1 alleen van x, dus heeft het de place 'x. Evenzo heeft r2 de place 'y. r3 kan lenen van x of y, dus is de place de unie van beide: '(x, y). Places kunnen ook paden zijn, zoals 'z.bar, om een referentie te representeren die leent van het struct-veld bar op variabele z.

Er zijn ook anonieme places, zoals voor een referentie naar een tijdelijke waarde (bijv. ref 2).

Dit maakt borrow checking in het algemeen eenvoudiger. In Ante is het principe simpel: wanneer een waarde wordt gebruikt, geef dan een fout als elke place waarnaar deze verwijst al is verplaatst (moved).

Onstabiele plaatsen (Unstable Places)

Nu we places hebben, kunnen we onstabiele plaatsen modelleren met een eenvoudige marker: !. Een onstabiele plaats zoals a! wordt ongeldig gemaakt door elke mutatie aan de plaats a.

Dit betekent ook dat als we 20 variabelen hebben met place a!, we ze allemaal gelijktijdig kunnen muteren, aangezien het muteren ervan alleen variabelen met place a!! zou ongeldig maken.

Laten we zien hoe dit in de praktijk werkt met een voorbeeld van Rust-code die veilig zou moeten zijn, maar door de compiler wordt afgewezen:

fn rejected(v: &mut Vec<String>) {
    // error: cannot borrow `*v` as mutable more than once at a time
    let (first, last) = (v.first_mut().unwrap(), v.last_mut().unwrap());
    *first = "Mutate first".to_string();
    println!("{last}");
}

De Rust-compiler wijst dit af, hoewel er geen manier is om first te muteren waardoor last ongeldig wordt. Theoretisch zou deze code zelfs geldig moeten zijn als het eerste element ook het laatste is[^3].

In Ante modelleren we dit door elke referentie naar geretourneerde elementen van een vector als onstabiel te markeren:

// Declareer een `first_mut` methode die een muteerbare vector neemt
// en een onstabiele referentie binnen 'v naar het eerste element retourneert
Vec.first_mut (v: mut Vec t): mut 'v! t can Fail = ...
Vec.last_mut  (v: mut Vec t): mut 'v! t can Fail = ...

not_rejected (v: mut Vec String) =
  first, last = v.first_mut (), v.last_mut ()
  first.* := "Mutate first"
  println last  // ok!

Hier hebben first en last beide het type mut 'v! String. Wanneer we first muteren, zou dit alles met een place v!![^4] blokkeren, maar er is niets met die place. We kunnen dus beide gebruiken, zelfs als ze naar hetzelfde object wijzen (alias).

Of een referentie onstabiel is, wordt in de praktijk afgeleid. Referenties via een tagged union of elementen van een collectietype zijn bijvoorbeeld altijd onstabiel.

Lussen (Loops)

Lussen en vertakkingen zijn vrij straightforward. Ze volgen grotendeels dezelfde regels als ownership: er volgt een fout als een variabele die buiten de lus is gedeclareerd, binnen de lus ongeldig wordt gemaakt:

var v = Vec.of [1, 2, 3]
one = v.get 0
for _ in 0 .. 3 do
  println one  // error: one kan ongeldig worden gemaakt door een latere mutatie in de for-loop
  v.clear ()   // let op: one wordt hier ongeldig

Hetzelfde geldt voor closures die een deel van hun gevangen omgeving (captured environment) ongeldig maken; deze worden behandeld als FnOnce in Rust-termen, wat voorkomt dat ze vaker dan één keer worden aangeroepen.

Ante heeft ook effect handlers. De control-flow hiervoor is complexer; de regels voor de interactie met onstabiele plaatsen zijn elders gedocumenteerd, maar kunnen nog veranderen.

Exclusiviteit

Het is mogelijk om functies te schrijven die alleen geldig zijn als bepaalde parameters niet naar hetzelfde object wijzen (niet aliassen):

a_and_b_cant_alias (a: mut Vec String) (b: mut Vec String) =
  elem = a.first_mut ()
  b.clear ()
  println elem  // ok! Maar hoe?

In dergelijke gevallen heeft de compiler nog steeds een vorm van exclusiviteitsregel nodig. Wanneer een parameter wordt gemuteerd, moet de compiler ervoor zorgen dat de aanroeper van de functie een unieke waarde hiervoor geeft:

bad_caller (c: mut Vec String) =
  // error: 'a kan niet aliasen met 'b in dit gebruik van a_and_b_cant_alias,
  // maar 'c werd voor beide gebruikt
  a_and_b_cant_alias c c

Om dit te controleren, genereert de compiler bij elke mutatie een Mutate 'p effect, dat een functie markeert met de plaatsen die gemuteerd kunnen worden. Op de aanroeplocatie moet elke plaats die gemuteerd kan worden, verschillend zijn van andere geïnstantieerde plaatsen[^5]. Let op: mut zelf staat nog steeds willekeurig aliasing toe. Pas wanneer er een daadwerkelijke mutatie plaatsvindt en Mutate 'p wordt uitgezonden, controleert de compiler of een generieke waarde niet p wordt terwijl deze nog in scope is.

Gebruik versus Vermelding (Use vs Mention)

Mutate 'p is een voorbeeld van het onderscheid tussen gebruik en vermelding. Code die mutabiliteit enkel vermeldt, is niet onderhevig aan uniciteitsrestricties. Dit is vooral merkbaar omdat places paden kunnen zijn; we kunnen een volledige mut Context aan een functie doorgeven, terwijl deze wellicht alleen Mutate 'ctx.field uitvoert.

Dit scenario komt vaak voor bij het muteerbaar itereren over een veld van een context-waarde:

type Entity = name: String, health: I32
type Context = entities: Vec Entity, events: Vec String, score: U32

Context.on_death (ctx: mut Context) (entity: ref Entity): Unit
can Mutate 'ctx.events
=
  ctx.score += 10
  ctx.events.push "${entity.name} died"

iterate_example (ctx: mut Context) =
  for entity in ctx.entities do
    entity.health -= 1
    if entity.health <= 0 then
      ctx.on_death entity  // ok!

In Rust zou bovenstaande code worden afgewezen, maar Ante biedt verschillende opties. Je kunt Mutate 'ctx.events exposeren op Context.ondeath, waarmee je garandeert dat alleen dat veld gemuteerd mag worden (het muteren van integers zoals ctx.score maakt referenties nooit ongeldig). Of je kunt ondeath vertellen dat entity oorspronkelijk binnen ctx kan zijn opgeslagen:

Context.on_death (ctx: mut Context) (entity: ref 'ctx.entities! Entity): Unit
can Mutate 'ctx
=
  ctx.score += 10
  ctx.events.push "${entity.name} died"

Hier zeggen we dat alles van 'ctx gemuteerd mag worden. In dit specifieke voorbeeld is dit minder wenselijk, omdat het zou betekenen dat entity als onstabiele referentie niet meer geldig is na de aanroep van on_death. Voor andere patronen is het echter precies wat we willen, of we kunnen het opaak houden[^6].

Complexe datastromen

Door borrow checking te herformuleren in termen van places en mutaties in plaats van lifetimes, wordt het systeem veel krachtiger. Omdat lifetimes in Rust gebonden zijn aan een regio code, heeft Rust soms moeite met complexe datastromen:

fn get_default<'r, K: Hash + Eq + Branch, V: Default>(
    map: &'r mut HashMap<K, V>,
    key: K,
) -> &'r mut V {
    match map.get_mut(&key) {
        // --- eerste mutable borrow vindt hier plaats
        Some(value) => value,
        None => {
            map.insert(key, V::default());
            //  ^~~~~~ error[E0499]: cannot borrow `*map` as mutable more than once at a time
            map.get_mut(&key).unwrap()
        }
    }
}

Om dit in Rust werkend te krijgen, is een nieuwe generatie borrow checker nodig (Polonius), die lifetimes modelleert als iets dat veel dichter bij places (alias sets) ligt dan bij regio's van broncode.

In Ante werkt dit gewoon:

get_default
(map: mut 'r HashMap k v)
(key: k)
{Hash k} {Eq k} {Copy k} {Default v}
: mut 'r! v can Mutate 'r, Panic =
  match try do map.get_mut key
  | Some value -> value
  | None ->
    map.insert key (default ())  // ok!
    map.get_mut key ~> panic_on_fail

De borrow checker van Ante is al gebaseerd op places en probeert referenties niet aan een specifieke regio code te koppelen. Aangezien de geretourneerde elementreferentie van map.get_mut in de None-branch niet wordt gebruikt, hoeft deze niet geverifieerd te worden. Als een referentie nooit wordt gebruikt, maakt het niet uit of deze dangling is of niet.

Nog een voorbeeld:

struct Thing;
impl Thing {
    fn maybe_next(&mut self) -> Option<&mut Self> { None }
}
fn main() {
    let mut temp = &mut Thing;
    loop {
        match temp.maybe_next() {
            //    ^^^^ error: `*temp` was mutably borrowed here in the previous iteration
            Some(v) => { temp = v; }
            None => { }
        }
    }
}

Hier denkt Rust dat de maybe_next borrow langer kan duren dan de lus zelf, vanwege de toewijzing temp = v aan een variabele buiten de lus.

In Ante is de equivalente code oké:

type Thing = x: Unit
Thing.maybe_next (_: mut Thing): Maybe (mut Thing) = None

main () =
  var temp = mut Thing ()
  while true do
    match temp.maybe_next ()  // ok!
    | Some v -> temp := v
    | None -> ()

Dit werkt omdat temp een anonieme place 'p krijgt, maybe_next dezelfde 'p retourneert, en de mutatie alleen onstabiele referenties naar 'p ongeldig zou maken.

Gedeelde Mutabiliteit

We kunnen onstabiele plaatsen gebruiken om veilig het muteren van gedeelde pointers toe te staan, zoals een Rc<T> (reference-counted pointer) in Rust.

De eerste realisatie is dat, omdat onze analyse is gebaseerd op places, Rc een place nodig heeft om het gedeelde element te representeren: Rc 'p t. Dit is niet nodig bij andere pointertypes zoals Box, maar voor Rc is deze extra parameter 'p noodzakelijk om separate klonen van dezelfde waarde te koppelen aan dezelfde interne waarde.

Bij het modelleren van een muteerbare referentie naar de binnenkant van een Rc, maken we gebruik van een unie van places:

Rc.get (rc: mut 'outer (Rc 'inner t)): mut '(outer!, inner) t = ...

Dit type zegt dat als we een muteerbare referentie naar een Rc hebben, we een muteerbare referentie naar het interne element kunnen krijgen. Deze referentie heeft twee places: outer! (onstabiel omdat we door een gedeelde pointer-boundary gaan en de Rc-waarde zelf vervangen kan worden) en inner (de gedeelde waarde waar elke kloon van deze Rc naar wijst).

Een voorbeeld:

mutate_rc_bad (rc1: mut Rc 'p (Vec String)) (rc2: mut Rc 'p (Vec String)) =
  // string_ref: mut '(rc1!!, p!) String
  string_ref = rc1.get () |> Vec.first_mut
  // Mutates 'p, so string_ref with unstable 'p! is invalidated
  rc2.get () |> Vec.clear
  // error: string_ref may have been invalidated by an earlier mutation
  println string_ref

We kunnen dus veilig muteren via een Rc-waarde zonder runtime checks, en de compiler waarschuwt ons nog steeds als we iets onveiligs proberen te doen. Is dit voldoende om zelfs cyclische referenties te representeren?

Cyclische Mutabiliteit

Voor cyclische mutabiliteit hebben we... niets extra's nodig! We kunnen gewoon Rc gebruiken om cycli te vormen[^7].

type List 'p t =
| Nil
| Cons t (Rc 'p (List 'p t))

main () =
  var f = Rc.of (Cons false (Rc.of Nil))  // false -> []
  var t = Rc.of (Cons true f)             // true -> false -> []
  if f is Cons _ tail then
    // tail's places zijn '(f!!, a!), dus het wordt ongeldig gemaakt
    // door elke mutatie aan f of de gedeelde place 'a.
    tail := t
    emit_list t
    |> take 5
    |> iter println  // true, false, true, false, true

emit_list (l: ref List t) = do
  if l is Cons elem tail then
    emit elem
    emit_list tail

Dit patroon lijkt sterk op het gebruik van GhostCell in Rust, maar dan op een ergonomischere, ingebouwde manier (geen GhostToken meer nodig). Deze controles zijn volledig statisch; er zijn geen runtime checks.

Opmerking over Multi-threading

Hoe behoudt Ante de thread-veiligheid met deze permissievere gedeelde mutabiliteit?

Het antwoord is simpel: Ante kopieert de Send/Sync traits van Rust. ref/mut referenties staan beide gedeelde mutabiliteit toe en implementeren daarom geen van beide traits. In plaats daarvan heeft Ante aanvullende referentietypes imm en uniq, die overeenkomen met & en &mut in Rust. Deze worden zelden gebruikt; ze zijn voornamelijk bedoeld voor multi-threaded code, waar ze na het passeren van een thread-boundary kunnen degraderen naar ref/mut om functies aan te roepen.

In de toekomst zal het type van een referentie worden gekoppeld aan de place-variabele, om het makkelijker te maken code te schrijven die polymorf is over elk referentietype.

Samenvatting

Dit was veel informatie! Het hoofdmodel is het bijhouden van de places waar een referentie van leent, en of deze onstabiel zijn. Dit artikel is grotendeels een herformulering van de documentatie over de gedeelde mutabiliteitsregels van Ante, maar geschreven als artikel om de motivatie achter de wijzigingen toe te lichten.

***

[^1]: "Low-level" wordt hier gebruikt voor een taal met standaard unboxed types en geen alomtegenwoordige Garbage Collector (GC). [^2]: Het nieuwe ontwerp is daadwerkelijk efficiënter voor cyclische mutabiliteit; het vereist niet de klonen die het vorige ontwerp wel nodig had. [^3]: Dit zou in Rust niet veilig zijn omdat meerdere &mut referenties naar dezelfde data de aliasing-aannames schenden, maar in onze doelsemantiek zou dit moeten kunnen. [^4]: ! op places kan nesten! 'foo! is een onstabiele plaats binnen 'foo', terwijl 'foo!! een onstabiele plaats binnen die vorige onstabiele plaats is. Dit kan bijvoorbeeld een String element van een Vec zijn (Vec String). [^5]: Elke place die al 'p was, is in feite oké. De body van de functie zou deze gevallen al herkennen en controleren. Dit maakt patronen mogelijk waarbij een onveranderlijke container en een muteerbare referentie binnen diezelfde container worden doorgegeven. [^6]: Toekomstige versies van Ante zullen 'abstracte places' toestaan, waarbij structs een set places binnen hen kunnen declareren om te exposeren, onafhankelijk van hun werkelijke velden. [^7]: Het gebruik van Rc om cycli te vormen leidt nog steeds tot geheugenlekken! Er is een ander collectiemechanisme nodig om lekken te voorkomen, maar dat is een apart probleem van de mutabiliteit van een cyclus.