Single ownership, move semantics, and a new memory layout - [merged]

yorickpeterse commented 3 years ago

Merges single-ownership -> master

This MR drastically changes the way Inko works, how memory is managed, the memory layout, etc. It's too much to cover in this MR, instead I'll cover it in the release notes. But in short: Inko will use a form of single ownership like Rust, but a more flexible version of it. For concurrency we're borrowing some ideas from Pony, but again in a more flexible/accessible manner.

yorickpeterse commented 3 years ago

Passing references around may require additional increments. For example:

def store(value: ref String) {}

let a = 'foo'
let b = ref a

store(a)
store(b)

If store() were to store the ref somewhere (e.g. in an Array that outlives store), each store requires an additional increment. Without this, dropping b (which would decrement the ref count) would result in an incorrect ref count (= not enough).

This probably requires some form of escape analysis to determine if a ref T escapes, and if so increment it automatically.

yorickpeterse commented 3 years ago

In case I forget about the link/name, the implementation here is based on the paper https://researcher.watson.ibm.com/researcher/files/us-bacon/Dingle07Ownership.pdf.

yorickpeterse commented 3 years ago

In this MR, Option uses NULL as the None signal. This doesn't work when a None is copied to another process, as this fails when checking if the NULL pointer is a permanent pointer. The use of NULL here was a quick hack to get rid of the singleton/global, but we need something better. Getting rid of this also removes the need for all the some? checks in the current Option implementation.

To solve this, we need to revisit turning Option into a trait, with two classes (Some and None) implementing it. The None class would be generic (None!(T)) but not actually use the type parameter. This way we can treat it like a Option!(T). This requires some type inference changes to support code like this:

x.if(true: { None.new }, false: { Some.new(10) })

Currently the inferred return type would be Option!(T) instead of Option!(Integer).

yorickpeterse commented 3 years ago

We also need to turn Equal into a generic trait. This way we can define Option like so:

trait Option!(T): Equal!(Option!(T)) {
  ...
}

If we keep Equal as-is, it requires the operand to be of type Self. When implementing the trait, that translates to the class implementing it. This means that for a Some, you'd only be able to compare it with another Some. But at the trait level Equal would expose ==(Self), translating to ==(Option!(T)). This could then result in a == implementation being defined for type A, while it may also be given type B.

yorickpeterse commented 3 years ago

Variable assignments should return the old value, not the new value. We'll need to load these values anyway to drop/decrement them. Returning them (and dropping them if unused) makes an attribute swap trivial:

class Container!(T) {
  @value: T

  def swap(with: T) -> T {
    @value = with
  }
}

Meanwhile in Rust you'd have to do something like this:

use std::mem::swap;

pub struct Container<T> {
    value: T,
}

impl<T> Container<T> {
    pub fn swap(&mut self, mut with: T) -> T {
        swap(&mut self.value, &mut with);
        with
    }
}

yorickpeterse commented 3 years ago

added 1 commit

b3dbd8c2 - WIP: new memory layout and move semantics

inko-lang / inko

Single ownership, move semantics, and a new memory layout - [merged] #483