Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is C# 4.0 compile-time turing complete?

There is a well-known fact that C++ templates are turing-complete, CSS is turing-complete (!) and that the C# overload resolution is NP-hard (even without generics).

But is C# 4.0 (with co/contravariance, generics etc) compile-time turing complete?

like image 343
wizzard0 Avatar asked Aug 16 '12 09:08

wizzard0


People also ask

Is C+ Same as C?

C++ was developed by Bjarne Stroustrup in 1979. C does no support polymorphism, encapsulation, and inheritance which means that C does not support object oriented programming. C++ supports polymorphism, encapsulation, and inheritance because it is an object oriented programming language. C is (mostly) a subset of C++.

What is C is used for?

C programming language is a machine-independent programming language that is mainly used to create many types of applications and operating systems such as Windows, and other complicated programs such as the Oracle database, Git, Python interpreter, and games and is considered a programming foundation in the process of ...

What does %c mean in C?

%d is used to print decimal(integer) number ,while %c is used to print character . If you try to print a character with %d format the computer will print the ASCII code of the character.

Is C -- a language?

C-- (pronounced C minus minus) is a C-like programming language. Its creators, functional programming researchers Simon Peyton Jones and Norman Ramsey, designed it to be generated mainly by compilers for very high-level languages rather than written by human programmers.


1 Answers

Unlike templates in C++, generics in C# (and other .net lang) are a runtime generated feature. The compiler does do some checking as to verify the types use but, actual substitution happens at runtime. Same goes for Co and contravariance if I'm not mistaken as well as even the preprocessor directives. Lots of CLR magic.

(At the implementation level, the primary difference is that C# generic type substitutions are performed at runtime and generic type information is thereby preserved for instantiated objects)

See MSDN

http://msdn.microsoft.com/en-us/library/c6cyy67b(v=vs.110).aspx

Update: The CLR does preform type checking via information stored in the metadata associated with the compiled assemblies(Vis-à-vis Jit Compliation), It does this as one of its many services,(ShuggyCoUk answer on this question explains it in detail) (others include memory management and exception handling). So with that I would infer that the compiler has a understanding of state as progression and state as in machine internal state (TC,in part, mean being able to review data (symbols) with so reference to previous data(symbols) , conditionally and evaluate) (I hesitated to state the exact def of TC as I, myself am not sure I have it fully grasped, so feel free to fill in the blanks and correct me when applicable ) So with that I would say with a bit of trepidation, yes, yes it can be.

like image 91
Terrance Avatar answered Oct 05 '22 01:10

Terrance