Linked by Eugenia Loli on Sat 7th Oct 2006 22:42 UTC
.NET (dotGNU too) 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.
Order by: Score:
turing complete
by bytecoder on Sun 8th Oct 2006 01:19 UTC
bytecoder
Member since:
2005-11-27

Can anyone tell me if C# generics are turing complete?

Reply Score: 3

RE: turing complete
by ormandj on Sun 8th Oct 2006 01:38 UTC in reply to "turing complete"
ormandj Member since:
2005-10-09

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...)

Reply Score: 3

RE[2]: turing complete
by bytecoder on Sun 8th Oct 2006 01:54 UTC in reply to "RE: turing complete"
bytecoder Member since:
2005-11-27

Ok, that's what I thought.

Reply Score: 2

RE: turing complete
by jayson.knight on Sun 8th Oct 2006 03:04 UTC in reply to "turing complete"
jayson.knight Member since:
2005-07-06

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.

Reply Score: 2

RE[2]: turing complete
by bytecoder on Sun 8th Oct 2006 03:14 UTC in reply to "RE: turing complete"
bytecoder Member since:
2005-11-27

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

Reply Score: 1

RE[3]: turing complete
by ckknight on Sun 8th Oct 2006 04:27 UTC in reply to "RE[2]: turing complete"
ckknight Member since:
2005-07-06

I'm genuinely curious: what'd be a more elegant solution, in your opinion?

Reply Score: 3

RE[4]: turing complete
by bytecoder on Sun 8th Oct 2006 13:11 UTC in reply to "RE[3]: turing complete"
bytecoder Member since:
2005-11-27

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.

Reply Score: 1

RE[5]: turing complete
by rayiner on Mon 9th Oct 2006 00:05 UTC in reply to "RE[4]: turing complete"
rayiner Member since:
2005-07-06

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.

Reply Score: 2

RE[6]: turing complete
by bytecoder on Mon 9th Oct 2006 01:17 UTC in reply to "RE[5]: turing complete"
bytecoder Member since:
2005-11-27


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.

Reply Score: 1

RE[7]: turing complete
by rayiner on Mon 9th Oct 2006 02:23 UTC in reply to "RE[6]: turing complete"
rayiner Member since:
2005-07-06

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.

Reply Score: 1

RE[5]: turing complete
by Get a Life on Mon 9th Oct 2006 18:07 UTC in reply to "RE[4]: turing complete"
Get a Life Member since:
2006-01-01

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.

Reply Score: 1

RE[3]: turing complete
by mank on Sun 8th Oct 2006 05:29 UTC in reply to "RE[2]: turing complete"
mank Member since:
2006-07-17

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?

Reply Score: 1

RE[3]: turing complete
by jayson.knight on Sun 8th Oct 2006 05:55 UTC in reply to "RE[2]: turing complete"
jayson.knight Member since:
2005-07-06

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.

Reply Score: 1

RE[3]: turing complete
by Get a Life on Mon 9th Oct 2006 17:47 UTC in reply to "RE[2]: turing complete"
Get a Life Member since:
2006-01-01

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.

Reply Score: 2

RE[4]: turing complete
by rayiner on Mon 9th Oct 2006 18:08 UTC in reply to "RE[3]: turing complete"
rayiner Member since:
2005-07-06

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...

Reply Score: 1

RE[4]: turing complete
by unthinkableMayhem on Tue 10th Oct 2006 05:40 UTC in reply to "RE[3]: turing complete"
unthinkableMayhem Member since:
2006-01-16

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

Reply Score: 1

RE: turing complete
by rayiner on Sun 8th Oct 2006 23:05 UTC in reply to "turing complete"
rayiner Member since:
2005-07-06

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.

Reply Score: 1

"Borrowed" features
by dimosd on Sun 8th Oct 2006 14:04 UTC
dimosd
Member since:
2006-02-10

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...

Reply Score: 2

RE: "Borrowed" features
by eggs on Mon 9th Oct 2006 15:45 UTC in reply to ""Borrowed" features"
eggs Member since:
2006-01-23

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 ;)

Reply Score: 1