The spaceship is neither a bird of prey (Klingon) nor a warbird (Romulan). Yes, I'm a Star Trek fan :) But the poster was indeed inspired by the look of the The Next Generation computer terminals, called LCARS (Library Computer Access and Retrieval System). For obvious reasons, we didn't go with the actual design, but we tried to keep the spirit of the Okudagrams.
Channel 9 is probably the biggest factor why I applied for a job at Microsoft. Watching the interviews gave me a very unqiue preview of how working at Microsoft looks like. But not only did Channel 9 provide great insight into how Microsoft builds the product, the interviews and shows also offer a very intimate view of the personalities behind the code.
Special thanks to Charles. I've deeply enjoyed your "going deep" series long before I joined and I was humbled by being interviewed by you.
This community is truly amazing. Keep it up -- you guys just rock!
Yes, I believe that's the paper we referred to during the interview.
I like language innovation a lot but things that affect the type subsystem in such a fundamental way are very hard to incorporate into an existing language like C#. It seems impossible to this on "on the side" as immutability is quite sticky; meaning you those sort of constraints need to be propagated around in the entire system to be beneficial.
Also, applying this to the hundreds of thousands of APIs in the .NET FX might be prohibitively expensive...
Why not allow user to select implementation using a factory function? The allocator most often knows how the collection will be used. For example that indexer or add must be O(1). The current AVL solution doesn't sound too good for paging and slicing. How would I create a slice of an ImmutableList? Did you look at Dlang ranges?
I haven't looked at Dlang ranges -- Andrew might have more context there. In general, we are not convinced that offering a knob for every option is the right thing. In the end, our goal is delivering a list of collection types that work for a wide variety while still being easy to use and agree upon. The Roslyn use case we brought up is quite special -- Roslyn has super tight perf constraints that most developers will not have. Once you are in this boat, chances are you want to have more control than what we can realistically offer in the BCL.
For those case we still offer the immutable interfaces as the exchange currency.
And .ToList() is commonly used on IEnumerables to materialize them from linq or other enums to make sure they are O(1) indexed. Not only to get a safe copy to foreach over. Will you add a ToImmutableList()? And will that be a noop if the IEnumerable is already an ImmList?
Our library offers an extension method for IEnumerable<T> that provides ToImmutableList().
If you call ToImmutableList() on an immutable list, you will get back the same instance, assuming it uses the default comparer. If it doesn't we change the comparer. In any case, that's an O(1) operation.
Is that what you are looking for?
An immutable list where add/indexer is O(1) with an array backing store would be nice. The allocation time would be amortized. The extra space created in array realloc could be used for non concurrent adds or adds in creator thread.
We still entertain the idea of ImmutableArray<T>. The type would be a struct wrapper around an array. Constructing would copy the array once to avoid anybody can violate the immutability guarantee. Indexer would be O(1). However, we wouldn't support persistent operations. In other words, adding or changing items would not be supported.