Introducing Built Collections

[David Morgan ☯]

Hi everyone,

http://www.dartdocs.org/documentation/built_collection/0.0.1/index.html#built_collection/built_collection

I'm pleased to announce a new open source library for those who like a bit of immutability in their collections.

The link has lots more info, but the short of it is: the library provides new types splitting the SDK collection interfaces in half:

 + List --> BuiltList (immutable) and ListBuilder (mutable)

 + Set --> BuiltSet (immutable) and SetBuilder (mutable)

 + Map --> BuiltMap (immutable) and MapBuilder (mutable)

Code example:

var list = new BuiltList<int>([1, 2, 3]);

var updatedList = (list.toBuilder()..add(4)..add(5)).build();

var updatedMoreList = (updatedList.toBuilder()..where((x) => (x > 2))).build();

And a few nice points:

MyClass(this.builtList); // no need to copy defensively, it's immutable!

if (builtList1 == builtList2) { ... // deep comparison

var lists = new Set<BuiltList<int>>(); // deep hashCode, can be used in sets/maps

new BuildList<int>([null]); // throws, nulls aren't allowed

Background:

I work at Google on a project that uses Dart, rather than the Dart team itself. We've found this approach to collections to be very useful in building immutable data types to represent UI state and for RPCs. We decided to rewrite the custom collections we were using for open source release in the hope that others would find them useful. So, enjoy :) ... and please do provide feedback, to me directly or on the github issue tracker: https://github.com/google/built-collection-dart

Regards

Morgan

[Cristian Garcia]

ᐧ

David,

Deep comparison and immutability sound sweet! I'd take that there is a performance penalty to get these benefits, do you have any benchmarks on this?

Thanks.

[David Morgan ☯]

That depends on precisely what you're doing with it.

If, for example, using BuiltList means you save doing lots of defensive copies, it might well be faster than List.

It's not intended for use in computation, but rather for publishing results. So your inner loop should be using List or ListBuilder rather than creating lots of new BuiltLists. Once you've used mutable lists to do the heavy lifting, you can use immutable lists to safely publish them / pass them around.

BuiltList and ListBuilder do work together to save copying where possible. This could be improved, still, so I'm interested in hearing about use cases where it's not yet fast enough.

For what we're using them for, for data models of things displayed in a the browser, they're certainly fast enough: if you're going to be rendering something, just putting it in a collection is always going to be comparatively cheap. Under the hood the built collections use the SDK ones, so performance is basically a matter of the SDK base + the extra null/type checks.

[Cristian Garcia]

Can you use BuiltList with AngularDart?

ᐧ

[David Morgan ☯]

Yes, binding with AngularDart is a big part of how we use them. Immutable collections make it clear when you're updating something, because it's always a field assignment.

This goes with the "mutable to calculate, build to publish" idea.

[Alex Tatumizer]

There are classes UnmodifiableMapView,, UnmodifiableListView  in dart:collection library.

Probably, your classes are slightly "more unmodifiable"... are you sure this is a sufficient justification?

. 

[David Morgan ☯]

Thanks Alex, yes, I'm quite sure ;) we've been using this approach for well over a year, but have only just got around to rewriting for an open source version. So you can consider the ideas well tested, even if the implementation is new.

Here are a few comparisons with the unmodifiables:

// Creating an updated version with an extra element.

new UnmodifiableListView<int>(new List<int>.from(unmodifiableList)..add(1));

(builtList.toBuilder()..add(1)).build();

// Interaction with APIs that take "List".

UnmodifiableListView --> throws on mutate

builtList.toList() --> copies on mutate, so read-only use is efficient, but mutates still work

// Efficiency.

UnmodifiableListView --> requires a full copy per update, or you keep the mutable version around and break immutability

Build Collections --> manages hiding the mutable version for you, for correctness + efficiency; it would be possible to support e.g. adding single elements with no copying at all

In general, the Built Collections are exactly what we need for our use case: collections that are part of a complex data model, e.g. things that will be displayed to and edited by the user, or sent/received by RPC.

Hope that answers your question :)

Cheers

Morgan

[Alex Tatumizer]

Is it the same as http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/ImmutableMap.html?

(The argument can be made that calling immutable map "ImmutableMap", however straightforward, may have some cognitive advantages over "BuiltMap", no?).

Basically, from logical perspective, it's the same as the aforementioned UnmodifiableMap. In both cases, it's a value object. If you want to (kind of) modify it, you have to create another object.

(which suggests another possible style of naming,  like MapValue, ListValue .. never mind. I just don't like "Built", to be honest).

[David Morgan ☯]

Yes, it's partly inspired by the Guava collections. In particular, rejecting nulls is directly from Guava.

There are a few differences, largely due to Java/Dart differences:

 + Dart has a very expressive, non-mutating Iterable interface. So, instead of implementing mutable interfaces and throwing on attempt to mutate, we can create new interfaces based on Iterable. For cases where you need the mutable interfaces we use copy-on-write for efficient toList, toMap, toSet.

 + Java has no need for runtime type checking, so this isn't a question for Guava. We've gone for runtime type checks as a good default, we'll revisit that if it turns out to be too expensive.

The best name for BuiltList would be just "List", but that was taken ;)

There is a reason for "Built": deep immutability requires immutable value types, and we create those following the builder pattern. So, it's built all the way down: built values containing built collections containing more built values. We like builders :) ... and Dart's cascade operator makes them particularly easy to implement and use.

Cheers

Morgan

[Cogman]

So, just throwing this in here.  If I were to design a language and a library for that language.  I wouldn't call my collections "immutable".  Rather, a List would be immutable by default and if you wanted a mutable list you would have the interface "MutableList".

In my experience, most interfaces don't care about getting mutable collections, so why make mutability the default?  It also helps with the hierarchy of things.  Because immutability fundamentally implies less functionality than mutability, it makes sense that immutable data structures are higher on the hierarchy than mutabible ones.

I'll get off my soapbox now :).

--
For other discussions, see https://groups.google.com/a/dartlang.org/
 
For HOWTO questions, visit http://stackoverflow.com/tags/dart
 
To file a bug report or feature request, go to http://www.dartbug.com/new

To unsubscribe from this group and stop receiving emails from it, send an email to misc+uns...@dartlang.org.

[Alex Tatumizer]

Hi Cogman, how would you populate such immutable object? I don't like builder - too much ceremony.
I was thinking about it lately, and my best take so far is this: provide initialization function in constructor, e.g.

var firstMap=new ImmutableMap((map) {

   // inside this function, it's a normal, modifiable map

   map["foo"]="bar";

   // etc.

});

Another constructor would provide a way to create ImmutableMap based on existing map:

var secondMap = new ImmutableMap(firstMap, (map) {

   map.remove("foo");

   map["bar"]="baz";

}

No builders required.

Or maybe there is a better way?

Making everything immutable by default is too late anyway (remember discussion about "final" by default?).

[Cogman]

@Alex, Yeah, it is too late for the discussion in dart.  Just voicing my opinion in case anyone goes off and makes a new language.

For the population problem, there are a couple of ways to tackle it.  You could always throw on the mutable collection a "Make immutable" or some other method that copies out the elements of the mutable list into a immutable list.  You could use the builder, though I get that you don't like it, they aren't too terrible usually.

If you had the hierarchy I suggested (List is immutable and then you have MutableLists that are subtypes) then you probably wouldn't use either of them, you would simply have all of your methods demand immutable collections and then give them mutable collections.  The parameter type would be the contract that says "I will not modify this".

[Alex Tatumizer]

I understand that this is purely theoretical discussion. Nonetheless, here's my rationale for encapsulating all modification logic in a function.

Essentially, Builder pattern is trying to create kind of brackets begin ... end

E.g., in the parent's lib, if you want to "modify" a BuiltMap, you first call "toBuilder()" and then "builder.build()".

So the whole pattern is about begin...end. In java, you may need it, for the lack of better options, but in dart, you pass a function that does the whole population - so "begin" is where function starts executing, and end is where it returns. We have same thing without any extra words/concepts.

[David Morgan ☯]

Yes, it's partly inspired by the Guava collections. In particular, rejecting nulls is directly from Guava.

There are a few differences, largely due to Java/Dart differences:

 + Dart has a very expressive, non-mutating Iterable interface. So, instead of implementing mutable interfaces and throwing on attempt to mutate, we can create new interfaces based on Iterable. For cases where you need the mutable interfaces we use copy-on-write for efficient toList, toMap, toSet.

 + Java has no need for runtime type checking, so this isn't a question for Guava. We've gone for runtime type checks as a good default, we'll revisit that if it turns out to be too expensive.

The best name for BuiltList would be just "List", but that was taken ;)

There is a reason for "Built": deep immutability requires immutable value types, and we create those following the builder pattern. So, it's built all the way down: built values containing built collections containing more built values. We like builders :) ... and Dart's cascade operator makes them particularly easy to implement and use.

Cheers

Morgan

On Sunday, 12 April 2015 17:20:57 UTC+2, Alex Tatumizer wrote:

[David Morgan ☯]

Nice idea!

You can still combine it with the cascade operator, e.g.:

list = list.with((b) { b..add(4)..add(5); });

c.f.

list = (list.toBuilder()..add(4)..add(5)).build();

For me the extra {} is a little unfortunate for inline use. Maybe:

list = list.with((b) => b..add(4)..add(5));

What do you think?

[Alex Tatumizer]

@David: not sure this can be of any interest for you, but here are some other comments on your design:

> Built Collections do a deep comparison against other Built Collections of the same type, only. Hashing is used to make repeated comparisons fast. Built Collections are Hashable ... Built Collections do compute, and cache, a deep hashCode...

The library is trying to do the impossible. There's no guarantee that keys/values are immutable. Just because they are placed in immutable container doesn't make them immutable themselves. Making this deep equals/hashCode a default means that library promises more than it can accomplish. But even if it could, there's a big question whether such default would be warranted. I can't think of too many common use cases where such "deep treatment" is necessary (except testing).

> Built Collections Reject Nulls ... Built Collections Require Generic Type Parameters... Built Collections Reject Wrong-type Elements, Keys and Values

This is an attempt to create a small island of java in dart. I don't think it's a good idea - it's inconsistent with the rest of the language/libs. It's like trying to be more pious than the Pope.

Take it lightly though, you can always say: this is what we needed, so that's what we implemented. I can't argue with that.

P.S. Good quote:
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away (Antoine de Saint-Exupery)

[Jonas Kello]

I agree with Thomas, this should have been the built in default from the start. It may not be perfect for the theorist, but for those who actually practise programming in large multi-person projects this is essential. I have been in projects where defensive copying was a pattern and it was not pretty at all. Basically for all projects where multiple persons are involved you will have code that you write that is published to be consumed by someone else's code which in turn will publish that to be consumed by someone else's code etc. If you don't know if things are mutable in those scenarios you will fall in to the defensive copy pattern.

It is also useful for caching. You do not want to cache things that are mutable. If someone keeps a reference around and then mutates it, the cache will also be updated which is probably not what you want. Been there done that too.

So anyway, thanks a lot for publishing this package! :-)

/Jonas

[Alex Tatumizer]

> list = list.with((b) => b..add(4)..add(5));

Yes, basically, that's what I meant. I like this variant :-)

[David Morgan ☯]

Thanks Alex :) all feedback is appreciated. Answers inline.

 

@David: not sure this can be of any interest for you, but here are some other comments on your design:

> Built Collections do a deep comparison against other Built Collections of the same type, only. Hashing is used to make repeated comparisons fast. Built Collections are Hashable ... Built Collections do compute, and cache, a deep hashCode...

The library is trying to do the impossible. There's no guarantee that keys/values are immutable. Just because they are placed in immutable container doesn't make them immutable themselves. Making this deep equals/hashCode a default means that library promises more than it can accomplish. But even if it could, there's a big question whether such default would be warranted. I can't think of too many common use cases where such "deep treatment" is necessary (except testing).

It's useful for what we're doing, more detail below.

I'm comfortable with breaking for things that can't work with mutable types; if you come from the Java world, at least, you're used to this. There, all the containers that use hashing assume immutability.

 

> Built Collections Reject Nulls ... Built Collections Require Generic Type Parameters... Built Collections Reject Wrong-type Elements, Keys and Values

This is an attempt to create a small island of java in dart. I don't think it's a good idea - it's inconsistent with the rest of the language/libs. It's like trying to be more pious than the Pope.

Indeed, this is very strict. I'm not 100% sure about all these decisions, but I wanted to release with everything as strict as possible. It's easier to loosen up later than tighten up later.

 

Take it lightly though, you can always say: this is what we needed, so that's what we implemented. I can't argue with that.

:)

Our use case is for structured data that the user will interact with.

Here, you frequently need a type with a handful of fields, one or two of which might be collections; and in those collections, you often need more structured types.

So, pretty much, it's immutable types from top to bottom, with collections as part of that. Because you might use any of these structured types in a set or map, it's useful if they're immediately hashable and comparable.

Re: strictness, we have a big codebase and lots of developers, and we find more strictness makes things more maintainable at scale.

P.S. Good quote:
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away (Antoine de Saint-Exupery)

Yes :) ... unfortunately the requirements gathering process is sometimes neverending ;)

[David Morgan ☯]

On Tuesday, 14 April 2015 17:18:24 UTC+2, Alex Tatumizer wrote:

> list = list.with((b) => b..add(4)..add(5));

Yes, basically, that's what I meant. I like this variant :-)

I think we can add something along those lines, I will take a look. Thanks!

I do think "toBuilder" and "build" still have a place, for when you want to pass around the builder. But hopefully that should be a minority of cases.

[David Morgan ☯]

On Tuesday, 14 April 2015 08:31:34 UTC+2, Jonas Kello wrote:

I agree with Thomas, this should have been the built in default from the start. It may not be perfect for the theorist, but for those who actually practise programming in large multi-person projects this is essential. I have been in projects where defensive copying was a pattern and it was not pretty at all. Basically for all projects where multiple persons are involved you will have code that you write that is published to be consumed by someone else's code which in turn will publish that to be consumed by someone else's code etc. If you don't know if things are mutable in those scenarios you will fall in to the defensive copy pattern.

Yes, I think the need for something like this gets bigger the more people you have committing code. It's also a matter of the type of code. We're building business logic over complex structured data, we really felt the need for a strict approach to data.

 

It is also useful for caching. You do not want to cache things that are mutable. If someone keeps a reference around and then mutates it, the cache will also be updated which is probably not what you want. Been there done that too.

So anyway, thanks a lot for publishing this package! :-)

You're welcome, please send feature requests / bug reports :)

[Alex Tatumizer]

@David: it seems that the word "with" is already hijacked by java and others, where it is assigned a meaning diametrically opposite to our intentions.
Pattern of its usage in java is: returning "this" after change, thus allowing cascade of modifications.
E.g.
http://docs.aws.amazon.com/AWSJavaSDK/latest/javadoc/com/amazonaws/services/ec2/model/InstanceState.html#withCode%28java.lang.Integer%29

In dart, this kind of "with" is unnecessary (that's what cascade operator is for), but still, maybe there's another word lurking somewhere, which can be even better than "with"? (In dart, there's a couple of people very skilled in naming, maybe someone can comment?).

General problem description (of which we have a trivial variant):
In a class Foo, provide a method that sets property x and returns NEW instance of Foo containing the modification (old instance is not affected). Find the best name for the method (which still might be "with", but I'm note sure).

[David Morgan ☯]

I was pondering using "call":

list = list((b) => b.add(1));

It's minimal :) ... not particularly self-explanatory, but the whole thing is already not very self-explanatory ... (nor is the cascade operator, for that matter).

[Alex Tatumizer]

Plot thickens. Turns out,"with" is a reserved word in dart, so it won't work anyway. "call" is not intuitive, as you noticed. Damn.

Instead of writing heavy tomes on design patterns, could people just publish API designer vocabulary or something?

It's the same thing, just much shorter. That's probably why no one bothered writing one: no money to be made on short book.

[David Morgan ☯]

How about

var list = new BuiltList<int>.build((b) => b..add(1)..add(2));

list = list.rebuild((b) => b..add(3)..add(4));

?

[Alex Tatumizer]

"build" looks ok. "rebuild" ... Hm. Maybe not bad either. :-). If you call the thing BuiltList, it's only logical to name operations "build" and "rebuild"

Maybe we have a winner?

[Alex Tatumizer]

Another variant of naming is FixedList, with methods "fix" and "refix"

[kc]

The Fletch project is using the diff-an-immutable tree strategy. Maybe they could use something like this.

K.

[Alex Tatumizer]

Strong(er) typing is coming? https://code.google.com/p/dart/source/detail?r=45190

[Paul Brauner]

Fatal Warnings would be a good name for a band :)

On Thu, Apr 16, 2015 at 5:54 AM Alex Tatumizer <tatu...@gmail.com> wrote:

Strong(er) typing is coming? https://code.google.com/p/dart/source/detail?r=45190

[Karl Klose]

The fatal warnings flag is a tool to ensure that the code does not have any static type warnings (for example, in a build step). It has the same effect as running the analyzer with fatal warnings first and only compile the code if that succeeded, but it does not change the way dart2js analyzes the program and generates JavaScript code.

On Thu, Apr 16, 2015 at 5:54 AM, Alex Tatumizer <tatu...@gmail.com> wrote:

Strong(er) typing is coming? https://code.google.com/p/dart/source/detail?r=45190

[David "Morgan" Morgan]

Unfortunately the analyzer currently has some big holes for type safety.

In particular, methods that take an Iterable are vulnerable to the "Iterable<dynamic> is Iterable<anything>" problem:

new ListBuilder<int>().addAll(['string']);

The analyzer doesn't complain about this: a List<dynamic> can contain String and a List<dynamic> is a List<int>.

It would be possible to skip checking every element if a List<int> is passed in, and do individual element checks only for List<dynamic>. That would encourage you to write:

new ListBuilder<int>().addAll(<int>['string']);

I'm not sure that's a good solution either because it adds boilerplate.

I'm hopeful that something will come along from the Dart team that helps here, and the runtime type checks are just an interim solution.

Cheers

Morgan

[David Morgan ☯]

Just published v0.1.0 with "build" and "rebuild".

[David Morgan ☯]

And now with BuiltListMultimap :)

BuiltSetMultimap to follow at some point. Quicker if someone asks for it :)

[Ron Gonzalez Lobo]

Awesome!

Mit freundlichen Grüßen

Ron Gonzalez Lobo

[Alex Tatumizer]

Meanwhile, dart added unmodifiable maps and unmodifiable lists
https://code.google.com/p/dart/source/detail?r=45733
(list was added a bit earllier).

Apparently, dart at some point became sentient and learned how to read our posts. If it likes something, it just silently adds it to the implementation.

[David Morgan ☯]

...and now with BuiltSetMultimap :)

Dart will continue to evolve, of course. But true immutable types (i.e. different interface to the mutable ones, as with the Built Collections) won't be going into the SDK any time soon, there's pretty strong agreement on that from the Dart team.

I do have a couple of issues open for changes to the SDK, there are a few subtle points about providing immutable collections:

https://github.com/dart-lang/sdk/issues/23328 -- EfficientLenth: currently the internal collections code uses a private interface to mark efficient iterables. This means collections that don't implement List/Set sometimes lead to unnecessary copying when used as Iterable with the SDK. (With Built Collections you can use .toList(), .toSet() to avoid copying because they use copy-on-write wrappers, but this is very non-obvious; you'd have to inspect the SDK code to find out when it's needed).

https://github.com/dart-lang/sdk/issues/23327 -- const collection literals: (actually just const lists): there's no way to tell at runtime if a List is a const literal, so you can't avoid defensive copying when initializing from a List literal, even if it's const.

Const Map literals do end up as a different type, so you can avoid copying those if you like. But const Map literals have linear-time lookup, so I'm not convinced it's better to reuse them than to copy into a hash map. Not quite sure what the best solution is there.