Bug Vanquisher

2 June 2007

The horrors within!

Filed under: Computer Theory — Tanveer Badar @ 3:00 PM

Have you ever given thought to the C# type system (For all purposes I will only say C# whenever I mean C#/VB.Net/C++-CLI/whatever languages.)? Ever opened a bank account which requires a reference of someone having previously opened an account at the same bank? Admitted to a school which requires previously students’ parents knew you? Got membership of a club where someone else had to recommend you? Or don’t forget the politics? Know what Russell’s paradox is. If every set is a subset of universal set, of which set universal set is a subset then?

Each of these examples has a main theme, the idea of a tree structured hierarchy. You must start at the root to enter the system. There must a path from you to root or a relation to root in order to be part of the system. The root is special. It has no parent and without some external help, it would not even be a part of that system. The system is inconsistent specifically for the root. You need boot strapping to make root part of the system. Given the rules which apply for something to be part of the system, root will always violate these rules. The invariants which hold for every other thing that is part of the system, root is the sole entity for which they do not hold. Let me explain all these points with reference to the questions I asked.

  1. C# type system: C# requires the each type must have a parent. If you do not specify a parent, it will implicitly inherit it from either Object if you define a class or from ValueType if you define a struct. ValueType in turn inherits from object. Therefore, whatever the construct you always inherit from Object. Java and many other languages suffer from the same problem. In my knowledge, C++ is the only language to avoid this problem by not requiring every class to inherit from one single class. Now, consider my claims.

    • You must start at the root to enter the system. There must a path from you to root or a relation to root in order to be part of the system.
      As said earlier, no matter how you define your type, you always inherit from object.
    • The root is special. It has no parent and without some external help, it would not even be a part of that system.
      object is special. It is the base class for every other class in C# but has no parent itself. Take a look at the disassembly we can peek at with reflector.

      [Serializable, ComVisible(true), ClassInterface(ClassInterfaceType.AutoDual)]
      public class Object
      {
          // Methods
          [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
          public Object();
          public virtual bool Equals(object obj);
          public static bool Equals(object objA, object objB);
          private void FieldGetter(string typeName, string fieldName, ref object val);
          private void FieldSetter(string typeName, string fieldName, object val);
          [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
          protected override void Finalize();
          private FieldInfo GetFieldInfo(string typeName, string fieldName);
          public virtual int GetHashCode();
          [MethodImpl(MethodImplOptions.InternalCall)]
          public extern Type GetType();
          [MethodImpl(MethodImplOptions.InternalCall)]
          internal static extern bool InternalEquals(object objA, object objB);
          [MethodImpl(MethodImplOptions.InternalCall)]
          internal static extern int InternalGetHashCode(object obj);
          [MethodImpl(MethodImplOptions.InternalCall)]
          protected extern object MemberwiseClone();
          [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
          public static bool ReferenceEquals(object objA, object objB);
          public virtual string ToString();
      }

      As I have highlighted, object has no base class. Even the IL does not have an .extends directive.

    • The system is inconsistent specifically for the root.
      If we try to compile the above define (suitable completed and removing internal dependencies for the sake for demonstration), C# compiler will derive it from object defined in mscorlib.
    • You need boot strapping to make root part of the system. Given the rules which apply for something to be part of the system, root will always violate these rules.
      Since, object cannot be defined in any HLL, we need something external to the targeting languages to define object. If we insist on defining it in C#, it will no longer be the object we intended it to be.

    • The invariants which hold for every other thing that is part of the system, root is the sole entity for which they do not hold.
      There is one invariant no type can violate. It must have a single parent. object has no parent

    I am going to clump all other example together as they are not related to programming. However, banking deserves special attention.

  2. Open a bank account/Get admitted to a school/Club membership/Politics
    • You must start at the root to enter the system. There must a path from you to root or a relation to root in order to be part of the system.
      You must know someone who is already a member. Someone must invite you into the system, you cannot enter solely on yourself.
    • The root is special. It has no parent and without some external help, it would not even be a part of that system.

      This is easiest to explain in terms of a bank account. Consider, if everyone needed a reference to someone who already had an account, how could the first person open his/her account in the first place? Something external to the system that transcends the requirement that you must know a person beforehand who is part of the system must have played a factor.

    • The system is inconsistent specifically for the root.
      If you demand relationship, root will fail the test and the whole system collapses.
    • You need boot strapping to make root part of the system. Given the rules which apply for something to be part of the system, root will always violate these rules.

      Root does not know anyone who previously had an account in a bank, he/she should not be allowed to open an account, but the system requires at least one member who will introduce others to the system.

    • The invariants which hold for every other thing that is part of the system, root is the sole entity for which they do not hold.
      System must not require root to fulfill relationship to some parent in order to bootstrap in the first place. Every object must have a parent, root is excluded. Period.

All these are examples of chicken and egg problem. Joel Spolsky has a very nice post somewhere (I found the link, it is here) buried in his valuable archives which discusses the same problem from marketing point of view. He talks about things like, a new application requires a large customer base to be economical and have sufficient customer feedback to achieve a high quality but most customers don’t have huge buying strengths and most won’t waste money on something that just came out of company yesterday.

Russell’s paradox asks for a set which is ever bigger than the universal set. The ‘one who is all’. That set must contain everything yet must be contained in a set which is a proper superset.

Consider another example that just jumped out in front of me. A class of languages which can be recognized by a particular machine can always be defined in terms of a sort of meta language. When that describing language is fed to this machine, it fails to recognize it. All regular languages can be defined in terms of any language which will not be regular itself. Next, PDAs can be defined in language which PDAs will never recognize but TM/PM/nPDAs will. Turing machines will never recognize the language which describes them. In general, when we define a meta language to encompass all language a particular machine can recognize that language will transcend that machine. This can be proven by Cantor’s diagonal argument.

[Edit: 11/10/2009]

As Eric Lippert points out, not every type is C# inherits from object. Interfaces and pointers.

Secondly, ponder this in mscorlib:

throw new ExecutionEngineException(“mscorlib.resources couldn’t be found! Large parts of the BCL won’t work!”);

This message can never be localized, try as you may.

Third: Thank microsoft for investing in minwin (aka kernelbase.dll) in Windows 7. Otherwise, ntoskrnl.exe and hal.dll both claim to be the root of dependency hierarchy in Win32 processes.

Advertisements

4 Comments »

  1. Great article! This guy deserves to be at Google!

    Comment by Usman — 2 June 2007 @ 11:25 PM

  2. Now he says so! He was the one who indulged me applying for MS.

    Comment by Tanveer Badar — 4 June 2007 @ 9:53 AM

  3. […] again proves my point that root in a hierarchy is always special. The rules used to build that hierarchy do not apply to […]

    Pingback by More Horrors « Bug Vanquisher — 11 November 2007 @ 3:48 PM

  4. […] one which causes the program to terminate is the most beautiful. It is the root which must withstand the worst of all. It is unique in the way that nothing passes […]

    Pingback by Catching the Exceptional « Bug Vanquisher — 23 December 2007 @ 4:53 PM


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: