Cyclic References in Fang

cyclic-references-in-fang.md

Cyclic References in Fang

Fang is a programming language I'm designing that is intended to make correct software easy for all developers to write. It features group borrow checking, which I highly recommend you read and understand before reading this article, to ergonomically check the use of multiple mutable aliases. This article explains how Fang safely represents data structures with cyclic references.

Getting up to Speed

Let's start with a quick tour of Fang. Parameters are passed by reference.

fn greetPerson(person: Person) { ... }

let you = Person{}

# `you` doesn't get copied or moved
greetPerson(you)

# and we can keep passing it
greetPerson(you)

# again and again
greetPerson(you)

Mutation is explicit and split into two categories. mut can mutate the value that it passed in, but is limited in what mutations it can perform.

fn giveDollarbucks(mut person: &Person, amount: U32) {
	# Safe mutation allowed
	person.dollarbucks += amount
}

fn removeCheaters(mut people: List[Person]) {
	# Invalidating mutation rejected on `mut` parameters
	people.clear()
}

# We're also explicit at the callsite
giveDollarbucks(mut you, 1) 

While mut! can perform all mutations, but will invalidate any references into the value.

fn removeCheaters(mut! people: List[Person]) {
	# Invalidating mutation allowed on `mut!` parameters
	people.clear()
}

# Still explicit at the callsite
let contestants: List[Person] = ...
removeCheaters(mut! contestants)

Link annotations describe how values alias each other.

let contestants: List[Person] = ...

# The `ref[contestants]` portion is the link annotation
#    it means `winner` can become invalid from operations on `contestants`
let winner: &Person ref[contestants] = selectPersonAtRandom(conestants)

# remove all of the cheaters, but `winner` could have been a cheater!
removeCheaters(mut! contestants)

# Thankfully, Fang stops us from awarding dollarbucks to cheaters.
giveDollarbucks(mut *winner, 1) # Compiler error

Link annotations only describe how values may alias, the annotated values aren't required to alias.

let contestants: List[Person] = ...
let organisers: List[Person] = ...

# `winner` isn't an organiser
let winner: &Person ref[contestants] ref[organisers] = selectAtRandom(contestants)

# even though we only remove organisers, the giveaway may have been rigged
removeCheaters(mut! organisers)

# Fang still stops us from awarding dollarbucks to cheaters!
giveDollarbucks(mut *winner, 1) # Compiler error

We can have multiple mutable aliases to a value.

# Now this is a rigged contest!
let winner1 = &you
let winner2 = &you
let winner3 = &you
let winner4 = &you

# This is allowed
giveDollarbucks(mut *winner1, 1)
giveDollarbucks(mut *winner2, 1)
giveDollarbucks(mut *winner3, 1)
giveDollarbucks(mut *winner4, 1)

The same thing works with mut! too, but we need to be more precise about aliasing.

# The `!` restricts aliasing to `contestants` directly,
#   not any of its children.
let contestants1: ref[contestants!] = &contestants
let contestants2: ref[contestants!] = &contestants
let contestants3: ref[contestants!] = &contestants
let contestants4: ref[contestants!] = &contestants

# This is allowed
removeCheaters(mut! *contestants1)
removeCheaters(mut! *contestants2)
removeCheaters(mut! *contestants3)
removeCheaters(mut! *contestants4)

Finally, the link and mutability annotations control whether values become invalid, not the body.

# Even though this function body is empty
fn removeCheaters(mut! people: List[Person]) { }

# The annotations still cause `winner` to be invalidated
let winner: &Person ref[contestants] = selectAtRandom(contestants)
removeCheaters(mut! organisers)
giveDollarbucks(mut *winner, 1) # Compiler error

Data Structures with Cyclic References

Now, onto cyclic data structures. The following snippet is an implementation of the observer pattern. The important part is the mut[self] link annotations. These annotations are how Fang knows within the body of giveDollarbucks that self.competition.person could alias self.

struct Person {
    competition: Optional[&Competition] mut[self]
    dollarbucks: U32
    
    fn giveDollarbucks(mut self, dollarbucks: U32) {
        self.dollarbucks += dollarbucks
        
        match self.competition {
            case None {}
            case Some{competition} {
                competition.onGiveDollarbucks(dollarbucks)
            }
        }
    }
}

struct Competition {
    person: Optional[&Person] mut[self]
    totalDollarbucksGiven: U32
    
    fn onGiveDollarbucks(mut self, dollarbucks: U32) {
        self.totalDollarbucksGiven += dollarbucks
    }
}

let person = Person{None, 0}
let competition = Competition{None, 0}

person.competition = Some{competition}
competition.person = Some{person}

person.giveDollarbucks(100)

print(competition.totalDollarbucksGiven) # Prints 100

You might be wondering, what happens if giveDollarbucks sets self.competition or self.competition.person to None? In this example, nothing would change, but mut doesn't let giveDollarbucks perform that kind of mutation because. You would have to use mut!, and after calling giveDollarbucks we would invalidate person.competition and competition.person in the global scope.

Fair enough, but if it works with mut!'s invalidating mutations, how does this work at all!? It works because person.competition and competition.person don't own anything. It doesn't matter what kind of mutation we perform in giveDollarbucks, it can never get an owning reference to person or competition to destroy them.

If that's the case, can we use mut to allow person.competition and competition.person to mutually own each other but prevent getDollarbucks from destroying those values? Yes, construction and destruction become extremely messy, but in principle it would be totally fine.

What we're really doing is making sure that a mutation through a cyclic reference cannot ever invalidate some "root" reference. This is the core idea I've been exploring to try and build out safe cyclic references in Fang. We've seen that we can do it by moving all of the owning references outside of the cyclic portion of the data structure and we can do it by preventing any invalidating operations, but are there other ways to do it?

Yes, view types that allow you to specify different access to different fields work.

# `giveDollarbucks` can use `mut!` operations on everything except `competition`.
fn giveDollarbucks(mut! self / {mut competition}, dollarbucks: u32) { ... }

# Can use `mut!` operations on everything.
fn removeFromCompetition(mut! self) { ... }

We can also invert the above with some inference so that so that mut! T doesn't allow mut! operations on fields with cyclic references.

fn giveDollarbucks(mut! self, dollarbucks: u32) { ... }

# We use view types to explicitly say we want to `mut!` competition
fn removeFromCompetition(mut! self / {mut! competition})