proj-oot-old-150618-ootNotes3

http://bartoszmilewski.com/2009/05/21/unique_ptr-how-unique-is-it/ :

some type properties:

• immutable "compiler, i demand that this cannot be mutated"
• mutable: not immutable
• const "compiler, i promise (and you must verify) that in this function i will not mutate this"
• unique (relevant to pointer only): "compiler, i promise that at any one time there will be only one copy of this pointer)
• lent "compiler, i promise (and you must verify) that in this function i will not alias (make an additional copy of without deleting the original) this pointer"
• owned: not lent
• owner: each object has an 'owner' object
  • if an object is self-owned, it can be accessed by multiple threads (he calls this a "monitor")
  • if an object is self-owned, all of its methods are implicitly synchronized
  • if an object is self-owned, it cannot have a thread-local member.
• by default, an object's owner is 'thread', meaning it is a threadlocal
• unique and immutable objects' owners are 'unique' and 'immutable' respectively
• instance variables are owned by their object, by default (another owner may be specified if desired, usually self-ownership e.g. monitors)
• the root of each ownership tree (except for unique, immutable, and threadlocals) is associated with a lock. this lock must be held in order to access any owned object (not just write, but also reading, esp b/c of sequential non-concurrency)
• except if an object is declared as 'lockfree', in which case no lock is necessary (but the compiler does ensure sequential concurrency; analogous to 'volatile' in Java or strong (not weak) atomics in C++). lockfree objects are not protected by the system, e.g. this is the way to escape from the system
• you cannot embed a threadlocal inside a monitor
• in his implementation, if you try to access an instance variable of a monitor without going thru its methods (which are implicitly synchronized), and without being within a synchronization block for that monitor (i.e. acquiring the lock for that monitor) you'll get a compile-time error. but for oot i think the compiler would just automatically enclose the statement within a synchronize block.
• if one object was owned by another object without the former being embedded in the latter, then the owner must be declared 'final'. This is because the ownership relation must be unchangable throughout the life of the program.
• Don’t share local (stack) variables—they might disappear
• note: 'immutable' and 'unique' must be deep (recursive), not shallow
• if immutable objects may be mutated during creation, make sure they aren't shared yet
• note that value types (like int) are by definition immutable

i believe the previous is a complete description of milewsky's system, (except for owner polymorphism, which i think can be done in a simple flexible way in Oot with annotations anyway), but should ask milewsky to be sure. according to http://fpcomplete.com/the-downfall-of-imperative-programming/ , he's since embraced functional programming to avoid data races, but i'm guessing he still thinks the above methodology would do the trick.

in oot:

• i think the 'lent' and 'const' could be inferred even if not declared
• we probably want to make 'shared' the default rather than 'threadlocal'

additional operation: ':=', called "move": x := y == x = y; y = null;. The idea is that x gets the pointer and y doesn't have it anymore; this can be applied even to unique pointers, whereas normal =, which means copy, cannot.

you can declare a pointer with the type propery (other examples of type properties are , meaning "compiler, i demand that this cannot be mutated" and const, meaning)

his type system apparently provably avoids race condititions (both 'low level' and 'high level' race conditions, whatever that means). it does not prevent deadlocks.

he also says "Such system would be incomplete without some support for lock-free programming. There are very good reasons for the language to enforce sequential consistency. For comparison, C++ committee, after a long struggle, decided to allow non-SC primitives (weak atomics). Java only enforces SC for volatile variables. " then goes on to introduce the lockfree qualifier, which means "A lockfree variable is guaranteed to be always atomically accessed in a sequentially consistent way." He has noted elsewhere that 'low level' race conditions defeat even lockfree algorithms.

not quite sure what this means. i guess sequential consistency is a guarantee that sequential code will always execute sequentially? is he saying this is good and that C++ has gone too far? or is he saying that you only need it when you are writing lockfree algorithms, which is why it seems his language has SC off by default but on when the lockfree qualifier is used? i think the latter. he notes this example which i don't entirely understand:

"

Speaking of lock-free programming, here’s the implementation of the infamous Double-Checked Locking Pattern:

class Singleton<T> { private: lockfree T _value; public: T get() lockfree { if (_value is null) { synchronized(this) { if (_value is null) _value = new T; } return _value; } } }

A lockfree variable is guaranteed to be always atomically accessed in a sequentially consistent way. A lockfree method is not synchronized, but it can only operate on lockfree variables (or use a synchronized section). Even though the use of lockfree doesn’t introduce low-level races, it may create high-level races when accessing more that one lockfree variable at a time. But we all know that lock free programming is only for desperadoes. "

"

Lessons learned from previous work

There are many commonalities in various approaches to race freedom.

    Ownership should be built into the type system. In OO languages each object must have an owner. In C-like languages each piece of data must have an associated lock.
    There should be efficient mechanisms for passing data between threads
        By value
        By reference. (The object being passed must be a monitor.)
        As immutable data, by const reference
        By unique reference using move semantics

Most of those ideas are expressible through type qualifiers. "

other sources: http://bartoszmilewski.com/2009/11/30/unique-objects/

http://bartoszmilewski.com/2009/09/22/ownership-systems-against-data-races/ http://bartoszmilewski.com/2009/06/15/race-free-multithreading-owner-polymorphism/ http://bartoszmilewski.com/2009/06/02/race-free-multithreading-ownership/ http://bartoszmilewski.com/2009/09/22/ownership-systems-against-data-races/

---

 "Andrei insists that "shared" should guarantee the absence of low level data races. Whenever I give examples of how this makes performance unpredictable, I hear the answer: "cast shared away". Currently nobody complains about it because this feature hasn't even been implemented. "

" D1 to be discontinued on December 31, 2012 (after the end of the world) by andralexin programming

[–]DrBartosz?