Kimundi/smartpointersugarv2.md

## smartpointersugarv2.md

      
    Raw
  

              smartpointersugarv2.md
            
          
    Custom Smartpointer Sugar (v2)

Reading the Meeting notes at https://github.com/mozilla/rust/wiki/Meeting-2013-06-07, it seems that there is general agreement with the idea to move @T and @mut T from build-in constructs to library types, provided it's possible to keep the same semantic with the help of lang items and traits.
This proposal is about the '@ vs Gc<>' issue mentioned at the end of those notes, to which I say:
"Why not both?"
To elaborate, I propose that the current 'hardcoded-to-gc-@'-ptr syntax disappears, and that the @-sigil gets re-purposed as special sugar for (custom) library types:
let g: @Gc int  = @Gc 5;            // Immutable tracing-collected box
let r: @Rc char = @Rc '5';          // Immutable reference-counted box
let m: @GcMut T = @GcMut foo();     // Mutable tracing-collected box

let mut ar      = Arena::new(1024); // Create a memory pool
let t: @Ar T    = @(ar)Ar bar();    // Immutable Arena allocation in `ar`

Compared to how it could be written today:
let g: @int = @5;       
let r: Rc<char> = Rc::new(|| '5'); // I'll talk about why that should take a closure below
let m: @mut T = @mut foo(); 

let mut ar = Arena::new(1024);        
let t: Ar<T> = ar.allocate(|| bar());      

Compared to just going with ad-hoc P<T> forms it would offer many benefits:

All custom Smartpointers become first-class citizen in usage.
With higher kinded types, generics could become generic over allocations: fn foo<T, A: Allocation>(@A T){ ... }
Syntactic similar type-, construction- and pattern-matching form, like for the build-in structural types.
It's a syntactic distinct construct to hang semantic specialities like auto-borrowing, dynamic freezing, etc from.
It visually separates types with memory management and memory allocation semantics from other types.
Lightweight syntax without type-param nesting hell (especially for the expression form).
Because a @T has a associated sigil, it 'looks like a memory-thing' (In the sense that & and ~ are also sigils associated with specific memory semantics).
But more important: Consistency with the type and construction syntax for & and ~.
The syntax for the build-in Gc Smartpointers becomes slightly heavier (@ -> @Gc), thus discouraging its use unless necessary.
But if necessary, the syntax is still easier to decipher and use than Gc<T>, especially if T is some generic type with a few layers of nesting.

Problems

There are a few syntactic ambiguities to be careful about:
First of all, some trickery in required to make paths work for @P T. Just having P and T expand to a path leads to the problem of deciding where one path ends and the other starts:
@::std::Gc ::foo::bar::MyType
@::std::Gc::foo ::bar::MyType
@::std::Gc::foo::bar ::MyType

This could be resolved by making the @-sigil not a prefix of the path, but of the type at the end of it, like this:
::std::@Gc ::foo::bar::MyType 

here the @-sigil acts as a anchor for the end of the first path.
Another problem exists with in-object allocation: There needs to be a way to cram an optional second expression in the expression form for accessing the object-to-allocate-in. I first considered
@<ident>(<expr>) <expr>  -  Example: @Foo(bar) baz()

But this (I think?) has the problem that (<expr>) is itself a valid expression, so there is ambiguity after the <ident>.
What I think would work is this:
@(<expr>)<ident> <expr>  -  Example: @(bar)Foo baz()

which would be unambiguous because '(' is not a valid start of an identifier.
However, I'm unhappy with that form because it breaks the unit of @Ptr. Maybe another form could be found that's just as concise? Here are a few possible candidates:
@(<ident>, <expr>) <expr>   - @(Ar, ar) foo()   // Only jams a '(' between type and sigil.
@<ident> <expr> in <expr>   - @Ar foo() in ar   // Needs a keyword
@<ident> from <expr> <expr> - @Ar from ar foo() // Needs a keyword
<expr>.@<ident> <expr>      - ar.@Ar foo()      // Allocation as method call on the object
@<ident>:<expr> <expr>      - @Ar:ar foo()      // ':' is usually a type-value separator in rust

Implementation

Why a closure for initialisation?

In my examples above I used Foo::new(|| bar() ) for initializing an allocation with the result of an expression, rather than Foo::new( bar() ). The reason for that is that the latter form would always do an shallow copy of the expression, which is inefficient for large structs. However, with a cheap stack closure the result of the expression can be optimised to write directly to the target memory address, turning f = || foo(); ... *ptr = f(); into a 'guaranteed-write'-version of f = |ptr| {*ptr = foo()}; ... f(ptr);.
According to graydon, this optimisation can be guaranteed to happen with a bit of work.
Traits

The sugar would probably be implemented with the help of a few traits:

An Allocation-trait, that represents an handle to some allocated memory - basically todays @T, Rc<T>, ...-smartpointer. Types implementing it could then be augmented with more trait impls for enabling things like borrows etc.
Allocator-traits for performing the allocation. Would need two different versions, one with a static allocation function, and one where there allocation is a method on &mut self

Example definitions:
#[lang="allocator"]
trait Allocator<T, U: Allocation<T>> {
    fn alloc(v: &once fn() -> T) -> U; 
}

#[lang="object_allocator"]
trait ObjectAllocator<T, U: Allocation<T>> {
    fn alloc(&mut self, v: &once fn() -> T) -> U; 
}

#[lang="allocation"]
trait Allocation<T> { }

#[lang="borrowable_allocation"]
trait BorrowableAllocation<T>: Allocation<T> {
    fn borrow<U>(&self, f: &once fn(&T) -> U) -> U; 
}

#[lang="mut_borrowable_allocation"]
trait MutableBorrowableAllocation<T>: Allocation<T> {
    fn borrow_mut<U>(&self, f: &once fn(&mut T) -> U) -> U; 
}

Types like Gc<T>, RcMut<T> would implement both Allocation and Allocator, while something like an Arena would separate them out in two types: The memory container (Allocator) and the handles to it (Allocation).
(The question is whether borrow() and borrow_mut() should take &self or &mut self. Some type might mutate self for borrowing, some might not. Just always making it &mut self would mean a smartpointer would need to be mutable for borrowing. For comparison, the current Rc and RcMut use &self and mutate a box behind a unsafe ptr for setting flags.)
If you then use custom smartpointers in your code like for example this:
let foo = @Gc 8;
let b: &int = foo;
print(fmt!("%?", b)); 

// Lifetime of b ends here

let foo = @GcMut (*foo).clone();
bar(&*foo);
baz(&mut *foo);

// ...

rustc desugars and rewrites the code to work something like this:
let foo = Allocator::alloc::<int, Gc<int>>( || 8 );

do foo.borrow |r| {
    let b: &int = r;
    print(fmt!("%?", b));
    // Lifetime of b ends here
}

let _tmp = do foo.borrow |r| {
    (*r).clone()
};

let foo = Allocator::alloc::<int, GcMut<int>>( || _tmp );

do foo.borrow |r| {
    bar(r);
}

do foo.borrow_mut |r| {
    baz(r);
}

// ...

(no guarantees for correctness and feasibility here, it's just intended as an example)
Omissions

Dynamic sized types

One thing this proposal doesn't talk about is how to support dynamic sized types like [T].
It would require additional allocation functions that take an size parameter, and a safe way to use them.
I haven't yet found an satisfying solution for that, but if I find one I will include it in this document.
Borrowed references

In-object-allocations might need additional lifetime parameters to chain their lifetimes to their allocator.
This could be done with a general lifetime parameter on Allocation: Unbounded allocations like Gc would get the static lifetime, bounded ones the lifetime of their allocator.
Transition

Transitioning to this syntax from the current one could be done in one of at least two ways:
A)

Deprecate @T, introduce Gc<T>.
Remove @T completely.
Introduce @S T as optional syntax.
Make @S T the only allowed form for Smartpointers.

B)

In one operation, change the parser from @T to @S T, ignoring the S token, and replace all @T with @Gc T.
Slowly build up the general support for the new syntax from behind the scenes.