As your projects become more sophisticated, you will need a better way to reuse and customize existing software. To facilitate code reuse, especially the reuse of algorithms, C# includes a feature called generics. Mark Michaelis discusses generics in C# in this sample chapter.
Using Generics in C# 2.0
About The Author
Eugenia Loli
Ex-programmer, ex-editor in chief at OSNews.com, now a visual artist/filmmaker.
Follow me on Twitter @EugeniaLoli
Can anyone tell me if C# generics are turing complete?
No, not AFAIK. Certainly not prior to “2.0”, and I still believe they are not (I have not been involved with C# for some time…)
Ok, that’s what I thought.
ormandj is correct, however this is generally seen as a good thing amongst the .Net developer crowd, i.e. C++ templates are turing complete, but that allows you to shoot your foot off quite easily, whereas the fact that C# generics are not lends itself to a stricter programming paradigm.
Just a footnote to ormandj’s comment (and you might already known this): the C# compiler was built from the ground up (meaning pre 1.0) with generics in mind, they just weren’t added to the C# language itself until C# 2.0…if you look through ROTOR for CLI 1.0 you can see it firsthand. So they’ll probably never be turing complete.
Ok, I was just curious. To be honest, I never liked the idea of templates or generics, but I can see why language designers would choose them rather than more elegant solutions to keep the language from becoming too radical.
Edited 2006-10-08 03:15
I’m genuinely curious: what’d be a more elegant solution, in your opinion?
Well, templates/generics aren’t really needed in a dynamically typed language.
Of course, a lot of people prefer static languages, in which case I suppose you would need some sort of generics construct, so I guess they aren’t inelegant in the context of static languages.
Generics aren’t completely unnecessary in dynamically typed languages. In a dynamically typed language, generics are useful for the opposite reason they are useful in a statically typed language: they all you to narrow a set of types. They allow you to express things like “foo is a list of T” within a type system that would otherwise only be able to express “foo is a list”. In many cases, you want homogenous containers, and generics allows you to express that.
Of course, in such situations, what you really want is predicate types, which are much more expressive than generics. They not only allow you to express things like “foo is a list of T”, but also things like “foo is a T when foo.x == 2”.
The inelegance of templates in C++ arises less from generics than from the fact that the template mechanism is perverted to act as a macro system. C# will probably get some form of macro support eventually, and if it keeps macros orthogonal to generics, it’ll have a substantially nicer design.
Generics aren’t completely unnecessary in dynamically typed languages. In a dynamically typed language, generics are useful for the opposite reason they are useful in a statically typed language: they all you to narrow a set of types. They allow you to express things like “foo is a list of T” within a type system that would otherwise only be able to express “foo is a list”. In many cases, you want homogenous containers, and generics allows you to express that.
Well, yes, although I can’t really see a situation where that’d be useful. You don’t really need it to improve type checking, since it’s going to happen at run time regardless. You can’t really use it to improve efficiency since, unless the compiler has inferred it, it might crash at run time, or worse, keep running in a messed up state.
Of course, in such situations, what you really want is predicate types, which are much more expressive than generics. They not only allow you to express things like “foo is a list of T”, but also things like “foo is a T when foo.x == 2”.
Again, I don’t really see a use for those in dynamic languages. Unless you go for soft typing, you can only check types at run time, which makes it trivial to implement something like that using properties and lambdas/blocks.
Well, yes, although I can’t really see a situation where that’d be useful. You don’t really need it to improve type checking, since it’s going to happen at run time regardless.
Without soft-typing, you can’t use it to do extra checking it compile-time, but it does improve the type-checking you can do at runtime. It lets you catch the error as soon as the contraint is violated, instead of later when some code tries to use the objects in the data structure.
You can’t really use it to improve efficiency since, unless the compiler has inferred it, it might crash at run time, or worse, keep running in a messed up state.
The efficiency argument is more relevant for languages with either soft-typing or generic methods. In that case, the compiler can generate code that assumes the type of the objects in the container, and generates an exception of the types don’t match. That costs one type-check at the insertion of each object, but can save accesses from having to hit the full generic object path.
Again, I don’t really see a use for those in dynamic languages. Unless you go for soft typing, you can only check types at run time, which makes it trivial to implement something like that using properties and lambdas/blocks.
Predicate types are useful in a CLOS/Dylan model, where types are involved in the definition of methods. They allow you to enrich the type system to express a wider range of properties. You can always approximate the result using a series of conditionals, but that’s true of OOP in general. It’s often cleaner and clearer to let the generic dispatch mechanism handle the selection of type-specific code (that’s what it’s there for).
Consider the example of parsing XML. Most XML formats have an object-oriented design, with various types of nodes. In order to leverage this object-orientation, you usually have to convert “XML node” objects into a corresponding object tree. At the heart of this conversion code is inevitably a big, ungainly select statement. However, if you could define classes that had predicates that checked the “type” attribute of the XML node object, then you could do the conversion in an entirely object-oriented manner. Or, you could dispense with the conversion altogether, and operate on the XML node objects directly, which would save time and memory.
Without soft-typing, you can’t use it to do extra checking it compile-time, but it does improve the type-checking you can do at runtime. It lets you catch the error as soon as the contraint is violated, instead of later when some code tries to use the objects in the data structure.
Yes, but you can get the same effect using properties for class variables and run-time asserts for pre-conditions. I personally prefer those rather than complicating the language with a type system, but I can see why you might prefer a consistent interface for constraints.
Also, it’s worth noting that, although you can’t do error checking at compile time with dynamically typed languages, you can do warnings. I’ve yet to see a dynamically typed language that uses this concept to its fullest extent, though.
Consider the example of parsing XML. Most XML formats have an object-oriented design, with various types of nodes. In order to leverage this object-orientation, you usually have to convert “XML node” objects into a corresponding object tree. At the heart of this conversion code is inevitably a big, ungainly select statement. However, if you could define classes that had predicates that checked the “type” attribute of the XML node object, then you could do the conversion in an entirely object-oriented manner. Or, you could dispense with the conversion altogether, and operate on the XML node objects directly, which would save time and memory.
I never liked the idea of dealing directly with XML. It seems like it would be a great output format for a generic serializer like python’s, though.
Yes, but you can get the same effect using properties for class variables and run-time asserts for pre-conditions. I personally prefer those rather than complicating the language with a type system, but I can see why you might prefer a consistent interface for constraints.
And you can get the same effect as OOP using structure variables and run-time assertions. But as I see it, the whole point of the type system is to be able to express such contraints (and with generic dispatching, dispatch on such properties).
I never liked the idea of dealing directly with XML. It seems like it would be a great output format for a generic serializer like python’s, though.
It’s not just XML, but any external representation, really. A lot of time, you don’t want to have to parse the whole semantics of the external representation into an object-oriented internal representation, just so you can do transformations on it. In such cases, using predicate types allow you to still leverage the type system when you otherwise could not*. Even if you do choose to parse the whole thing into an IR, predicate types make that parsing code easier by removing the large conditional statements that would otherwise result.
*) Of course, this specific example is just one of many. Predicate types (and predicate dispatch, which is somewhat related), is a fairly powerful concept, and quite elegant in how it generalizes the type system. At least its elegant in the context of dynamically-typed languages, which tend to have a much more pragmatic approach to typing than the more mathematical approach found in statically-typed languages like ML.
If you do not perform any static type checking at compile or link time, or any dynamic type checking at runtime then having a mechanism to express type parameters is obviously of little utility, however providing nothing hardly seems like a “more elegant solution” when any sort of constraint is to be applied at compile or runtime.
Actually I would suggest that any solution that entails manually adding type checks throughout the code using type casts or introspection is obviously inferior to any mechanism that permits the specification of the relevant type signature externally to the implementation. Whether it takes the syntactic form of Class<T> or if the pre-condition is expressed in terms of any other syntax.
I have found C# generics to be very useful and elegant solution for writing class libraries, frameworks etc. Once you are used to generics way of coding, its hard to not use it.
Are there other solutions the solve the problems that generics solve?
ccknight beat me to the question, and I’m honestly curious as well. The learning curve for generics is dead simple compared to templates, and IMO it’s a very elegant solution since the compiler does all of the work for you as far as type safety checks go. I’ve yet to see it’s equal in other languages.
C++ templates are probably its only saving grace; the language is otherwise without any redeeming value due to its overwhelming bug-inducing complexity. It’s hard to not like the idea of parameterized types, and it should be hard to not like many of the features present in C++ that are usually missing in other languages like specialization and partial specialization. D is also fairly respectable in this regard, but as we all suspect, it will never obtain any sort of popularity and so might as well not exist as far as the average programmer is concerned.
C#’s generic facilities suffer too much from their Java++ nature: they should have been part of the language from the beginning and used throughout the framework. That and some brain damage like using signed integers as the basis for indices and other such things where negative values make no sense and require manual error-handling to toss out superfluous exceptions so as to obtain interoperability with VB.NET are just some of the many reasons the .NET framework doesn’t impress me terribly. Blub, indeed.
Let’s say that you want to create a class with a type parameter with the constraint that operator +, operator -, operator /, and operator * are defined. So you create an interface IArithmetic but you can’t create instances with int or long as type parameters, because they do not implement the IArithmetic interface. Now you could handle this sort of type resolution structurally (which goes against the inheritance model of C#) or you can define an interface so that any kind of native numeric type can be the type parameter because someone is bound to want this. The former is the better solution, but not doing the latter is just retarded because your generic code can’t deal with those types. Without specialization, you can’t even shoe-horn it together so that the consumer of your library can just use it without caring that you’ve had to duplicate your effort because your development environment is retarded.
Another failing of C# generics is the absence of a feature like a “typedef” that would permit you to export instantiations of a parameterized type with a given type parameter with some typename. You can make your consumer create lots of ad-hoc typenames via the using keyword, but making your client’s life difficult by making them type in SomeClass<SomeType, SomeType2<SomeType> > somewhere in their source file when they don’t need to know/care that you were able to express your code generically is hardly advantageous.
Now these are just off the top of my head. I’m sure if I were to think about the issue I could come up with other topical weaknesses.
It’s hard to not like the idea of parameterized types, and it should be hard to not like many of the features present in C++ that are usually missing in other languages like specialization and partial specialization.
The idea of parameterized types is just dandy. Sane uses of it, like the STL, are great. It’s the idea of perverting the feature to serve as a macro system that bothers me. I didn’t use to feel this way, but the more I used stuff like Boost the more it pissed me off. That and the god-aweful syntax, which is hard for both humans and compilers to parse…
Let’s say that you want to create a class with a type parameter with the constraint that operator +, operator -, operator /, and operator * are defined. So you create an interface IArithmetic but you can’t create instances with int or long as type parameters, because they do not implement the IArithmetic interface
What makes this even more fun is that in c# operators are static and interfaces do not contain static members.
To get around this you end up having to definine an IOperations<T> interface and provide implementations of Add, Subtract, etc for each numeric type.
Then you can create a Number<T, O> where O : IOperations<T> that defines all the regular operators and then you can finally write:
public T Add<T, C>(T a, T b) where C : IOperations<T>
{
Number<T,C> a2 = a;
Number<T,C> b2 = b;
return a2 + b2;
}
…
int c = Add<int,Int32Ops>(10, 5);
Yay…. This article goes into more detail: http://www.osnews.com/story.php?news_id=7930
How would generics be Turing complete? Generics are an extension to the type system, and as such have no computational capability.
C++ templates are Turing complete, but that’s because they’re a hideous mixture of generics and a macro language in one feature.
I might be wrong, but generics in C# come directly from ML and Haskell (statically typed functional) languages. They are known as parametric polymorphism there, and they were never intended to be Turing complete or anything. Just a way to enrich the typing system. (These languages are VERY statically typed, so they had better have an expressive typing system).
Templates in C++ on the other hand are type-aware macros (an embedded language for macros) and it doesn’t hurt if this mini-language is Turing complete.
I am glad to see that C# tends to absorb useful features from other languages (even in a restricted form). From example, yield (from Python obviously, although Python “borrowed” from another language as well), generics and (a weak) form of type inference (var) from ML/Haskell. Nullable types? ML again.
Again, I think it’s a good thing to introduce such useful tools to a mainstream audience – as long they don’t try to get the credit for “innovation”. Try to explain that to the VB crowd…
Everything is inherited from something else, I didn’t think anyone was claiming that generics in C# is a breakthrough in computing technology; just a really good addition to C#. For a staticly typed language like C# generics are a must in my mind. Do you know how dirty I felt using an ArrayList or HashTable and having to set/get Object types *shivers*. Now, I can just use my List<> and Dictionary<> and be happily type safe