Reimplementing LINQ to Objects: Part 44 – Aspects of Design

I promised a post on some questions of design that are raised by LINQ to Objects. I suspect that most of these have already been covered in other posts, but it may well be helpful to talk about them here too. This time I’ve thought about it particularly from the point of view of how other APIs can be built on some of the same design principles, and the awkward choices that LINQ has thrown up.

The power of composability and immutability

Perhaps the most important aspect of LINQ which I’d love other API designers to take on board is that of how complicated queries are constructed from lots of little building blocks. What makes it particularly elegant is that the result of applying each building block is unchanged by anything else you do to it afterwards.

LINQ doesn’t enforce immutability of course – you can start off with a mutable list and change its content at any time, for example, or change the properties of one of the objects referenced within it, or pass in a delegate with side-effects – but LINQ itself won’t introduce side-effects.

The Task-based Asynchronous Pattern takes a similar approach, allowing composable building blocks of tasks. I’ve seen this pattern in various guises over the years – if you find yourself thinking in terms of a pipeline of some kind, it may well be appropriate, especially if each state in the pipeline emits the same type as it consumes.

General immutability is a somewhat different design trait of course, but one which can make such a difference. The java.util.{Date,Calendar} classes are horrible, not least because they’re mutable – you can never stash a value away without being concerned that it may get changed by something else. Joda Time has some mutable implementations, but typically the immutable classes are used in a fluent way. Of course, .NET uses value types for various core types to start with, but also makes TimeZoneInfo immutable. For genuine "values" I would highly encourage API designers to at least strongly consider immutable types. They’re not always appropriate by any means, but they can be hugely useful where they fit nicely.

Extension methods on interfaces

It’s no surprise that extension methods are heavily used in LINQ, given that they were effectively introduced into the language in order to enable LINQ in the first place. However, they do work particularly well with interfaces as a way of adding common behaviour.

It also plays very nicely with the pipeline pattern above for creating pipelines in a fluent manner. Even if you just create extension methods which call a constructor to wrap/compose the previous stage in the pipeline, you can still end up with more readable code.

One problem with this is that you can’t "override" behaviour in particular implementations or interfaces which extend the original one – which is why Enumerable.ElementAt() has to detect that a sequence is actually a list, for example. If interfaces allowed method implementations, this wouldn’t be as much of a problem in the situation where you’re in control of the interface – I wouldn’t be at all surprised to find that as a feature of C#’s successor.

The lack of extension properties is also a bit of a handicap in some places, although not as many as one might expect at first glance. For example, even if we could have made Enumerable.Count() a property, would it have been a good idea to do so? Properties give a natural expectation of speed, and Count() is usually an O(n) operation.

Delegates for custom behaviour

In .NET 1.0 and 1.1, most developers used delegates for two purposes:

  • Handling events in UIs
  • Passing around behaviour to be executed in a different thread (either via Control.Invoke, or new Thread(ThreadStart), or ThreadPool.QueueUserWorkItem).

.NET 2.0 increased the range of uses of delegates somewhat, particularly with List.ConvertAll and the ability to create delegates relatively easily using anonymous methods.

However, LINQ really brought them into the mainstream. If you’re building an API which benefits from small pieces of custom behaviour, delegates can be a real boon. More complicated behaviour is still often best represented via an interface, and sometimes it’s worth having both interface and delegate representations, like Comparison<T> and IComparable<T>. It’s generally easy to convert between the two – especially if you use a method group conversion from an interface implementation’s method to the delegate type.

Laziness

One aspect of LINQ which is both a blessing and a curse is its laziness, both in terms of deferred execution (not reading from the input sequence at all until the result sequence is read) and in terms of streaming the data (only reading as much information from the input sequence as is required to answer the immediate needs of the caller).

This is great in various ways, particularly as it means you can build a complex query and use it multiple times, sometimes as a basis for other queries, knowing that it won’t actually do anything until you ask for real results. It also means that you can iterate over huge data sets, so long as you’re careful.

On the other hand, it leads to subtle issues over when code is actually executing, makes debugging harder to understand, makes it easier to accidentally change the values of captured variables between the point at which you create the query and the point at which you execute it, and basically messes with your head. This is probably the aspect of LINQ which confuses newbies more than any other.

I’m not saying it was the wrong decision for LINQ – but I would caution API designers to think carefully before introducing laziness, and to document it really thoroughly. Likewise if your API might end up returning a result which is "gradually evaluated" (streaming data etc), this should be made clear.

When names collide: options for consistency

Just in case you’ve forgotten, this is irritation with the meaning of source.Contains(element). In order to check whether a sequence contains an element or not, there has to be some idea of equality – for example, if you’re trying to find one string in a sequence of strings, are you trying to match in a case sensitive manner or not?

There’s an overload for Enumerable.Contains which allows you to specify the equality comparer to use, but the question is what should happen when you let the implementation pick the comparer.

For every other method in Enumerable, the default equality comparer for the sequence type – i.e. EqualityComparer<TSource>.Default – is picked. That sounds like source.Contains(element) should use the element type’s default comparer too, right? Well, in some cases that’s what will happen… but not if the source implements ICollection<T>, which has its own Contains method which doesn’t take an equality comparer. If that’s the case, LINQ to Objects delegates to the collection’s Contains method.

So, we have three kinds of consistency here:

  • Consistency of compile-time type: it would be nice if the behaviour of source.Contains(element) was the same whether "source" is of type IEnumerable<T> and ICollection<T>
  • Consistency of API: it would be nice if Contains behaved the same way as other methods which have overloads with and without equality comparers
  • Consistency of model: if you consider "source" to be just a sequence of elements, it shouldn’t affect the result (not just the speed) if the object actually implements ICollection<T>

I should point out that this will only be a problem if the collection uses a different notion of equality to the default equality comparer for the type. The most obvious example of this is if you have a HashSet<string> which uses a case-insensitive equality comparer. But it’s still a valid concern.

So what should the API designer do in this kind of case? Admittedly LINQ to Objects is already in a slightly unusual position as it’s based on an existing interface with known and very common interfaces extending that core one… it’s less likely to come up with other APIs. However, I think it might be enough of a smell to suggest that changing the name of the method to "ContainsElement" or something similar would be worthwhile. It’s unfortunate that "Contains" really is the obvious choice…

This issue raises another aspect of API decision I’ve considered in the past… if there’s a common way of doing something in the framework you’re building on top of, but you consider it to be broken, should you abide by that breakage for the sake of familiarity and consistency, or should you strive to be as "clean" as possible? I think it needs to be considered on a case-by-case basis, but I suspect I would usually come down on the side of cleanliness.

Documentation details

Almost all APIs are badly documented – it’s a fact of life, even with some of the best APIs I’ve worked with. I doubt that Noda Time will be a shining example either. However, at the risk of being hypocritical I’ll say that documentation is worth spending significant thought on. Not just the time taken to document your code – but the time taken to consider what you want to guarantee, what should be left unstated, and what should be explicitly left open.

For example, there’s no indication in the documentation of Cast that it will sometimes return the original source value, nor in its companion OfType method that that will never return the original source reference. This might be important to someone – why not state it? It’s possible to state the possibility without saying what cases it applies to of course, leaving some wiggle room in the future. You might consider some of the optimizations in the same way – when should an optimization be documented and when should it be implicit? Sometimes it can make a difference beyond just performance, even if only in "odd" situations (such as a predicate throwing an exception).

If you’re used to defensive coding with Code Contracts, it’s much the same type of decision – and again, it’s similar to deciding whether a method should return IEnumerable<T>, IList<T> or List<T>. There’s a balance between caller convenience, design cleanliness (where you only want to emphasize one interface aspect, even if it also happens to always return a particular type), and room for the implementation to change in the future.

Another example of considering the level of detail to document is when it comes to how input sequences are used in LINQ to Objects. What does it mean to say "this method uses deferred execution" exactly? If I call GetEnumerator() eagerly but defer the call to MoveNext(), is that still "deferred execution"? Should the documentation state when a sequence is buffered and when it’s streamed? Should it guarantee the order of the result sequence when the natural implementation makes that order easy to describe (e.g. for Distinct)? In this series I’ve tried to be as clear as possible about what actually happens – but that’s not to say that in some cases, the documentation wasn’t left deliberately ambiguous.

Conclusion

There are many other design considerations that I haven’t gone into here – particularly optimization, which I’ve already covered twice, probably saying everything I wanted to say here anyway.

I may add a few more bits to this post over time… but aside from that, I think I’m fundamentally done. I’ll write one more conclusion post, then declare Edulinq closed…

3 thoughts on “Reimplementing LINQ to Objects: Part 44 – Aspects of Design”

  1. > If interfaces allowed method implementations

    What would be the difference between an interface and an abstract class then?

    The remaining differences (struct can implement an interface; interfaces can be implemented explicitly) seem to be quite minor, unless I missed something. And the fact that class can implement multiple interfaces would bring C++’s multiple inheritance to C#.

    I don’t really see the reason to go this way.

  2. The problem with multiple inheritance is shared state. If interface method implementations are similar to extension methods, then there really isn’t an issue. In fact, I think this is the direction Java is heading.

Comments are closed.