I know the answer (it's 42)

A blog on coding, .NET, .NET Compact Framework and life in general....

July, 2007

Posts
  • I know the answer (it's 42)

    Tail recursion on .NET

    • 4 Comments

    What's tail recursion

    If you know its nothing to do with any of your pet's tail then get onto the next section.

    Tail recursion is a special case of recursion where the last call in a method is a recursive call.

    The major issue with recursion is that with each recursive call the stack grows by the stack frame allocated to the function call and soon it hits a stack overflow in case the recursion is too deep. Consider the following code which recursively counts down from a given number. In case you call this method with 100000 or some such large number it'll crash on your face with a StackOverFlow exception.

    static void CountDown(int num)
    {
        Console.WriteLine("{0} ", num);
        if (num > 0)
            CountDown(--num);
    }

    Optimizing tail recursion

    Interestingly the above code is of the special tail-recursion form. Since the last call is the recursive call there is no need to preserve stack frame of the calling function and the compiler can easily use this information to generate machine instruction such that the stack doesn't grow at all.

    In C# terms the above code can be optimized by the compiler into something like

    static void CountDown(int num)
    {
    START:
        Console.WriteLine("{0} ", num);
        if (num > 0)
        {
            --num;
            goto START;
        }
    }

    In this code the parameter is replaced on the same stack and the execution is simply short-circuited to re-start on that.

    All of this is fine but does .NET support this

    Instead of a straight answer lets try to see ourselves. I'll first comment out the Console.WriteLine code in the first method to make it simply, build it and disassemble it using the trick mentioned in my previous post. The generated IL for this method looks something as follows

    .method private hidebysig static void  CountDown(int32 num) cil managed
      {
        // Code size       25 (0x19)
        .maxstack  2
        .locals init (bool V_0)
        IL_0000:  nop
        IL_0001:  ldarg.0
        IL_0002:  ldc.i4.0
        IL_0003:  cgt
        IL_0005:  ldc.i4.0
        IL_0006:  ceq
        IL_0008:  stloc.0
        IL_0009:  ldloc.0
        IL_000a:  brtrue.s   IL_0018
    
        IL_000c:  ldarg.0
        IL_000d:  ldc.i4.1
        IL_000e:  sub
        IL_000f:  dup
        IL_0010:  starg.s    num
        IL_0012:  call       void TailRecursion.Program::CountDown(int32)
        IL_0017:  nop
        IL_0018:  ret
      } // end of method Program::CountDown
    
    

    From the IL marked with red its evident that the C# compiler at-least doesn't do this optimization and emits a normal recursive call.

    However, .NET platform needs to support all sorts of languages including those like scheme where the only way to do iteration is to convert the code into tail-recursion and the compiler is supposed to do the above mentioned optimization.

    It's exactly for this reason there is a supported IL instruction named tail. Using this I can modify the above code to as follows.

    .method private hidebysig static void  CountDown(int32 num) cil managed
      {
        // Code size       25 (0x19)
        .maxstack  2
        .locals init (bool V_0)
        IL_0000:  nop
        IL_0001:  ldarg.0
        IL_0002:  ldc.i4.0
        IL_0003:  cgt
        IL_0005:  ldc.i4.0
        IL_0006:  ceq
        IL_0008:  stloc.0
        IL_0009:  ldloc.0
        IL_000a:  brtrue.s   IL_0029
    
        IL_000c:  ldarg.0
        IL_000d:  ldc.i4.1
        IL_000e:  sub
                  tail.
        IL_0023:  call       void TailRecursion.Program::CountDown(int32)
        IL_0029:  ret
      } // end of method Program::CountDown
    
    

    From CIL ECMA 335 spec "use a tail. prefix to specify that the current stack frame should be released before transferring control. If the call would transfer control to a method of higher trust than the original method the stack frame will not be released."

    This single instruction is very significant in this context. So now if I assemble this using ilasm and run it with as big a number I fancy it'll not crash (obviously it may take hours to compute though).

    Update: Through our internal C# DL I got to the gory details. Check out the links here and here

  • I know the answer (it's 42)

    Easy way to modify IL code

    • 3 Comments

    Sometimes I try to write a little bit of IL code or modify bits and pieces here and there (specially modify IL generated from say C# code).

    The problem is writing up the complete IL that compiles into an exe is a pain (specially because my usage is to tweak them). To work around this I use the following flow which I thought I'd share

    1. Write C# code that meets the need
    2. Build it
    3. Disassemble the exe by using the following command
      ildasm /out=file.il My.exe 
    4. Tweak the IL inside the file.il file
    5. Assemble it back again with
      ilasm file.il

    the neat part is the /out parameter which makes ildasm dump a single IL for the entire code. At the beginning I used to try patching the code up by copy-pasting from ILDASM UI which show separate IL code for every method :(

  • I know the answer (it's 42)

    Type cast to generic type

    • 6 Comments

     

    The following question got posted to one of the internal DLs.

    Why does the following fail to compile.

    public interface A { }
    public class B : A { }
    public class C : B { }
    
    class D
    {
        public void f()
        {
            C c = new B() as C; // Valid!
        }
    
        public void g<T>() where T : A
        {
            T t = new B() as T; // Invalid! Error CS0413
        }
    }

    The constraint (where T : A) clearly tells the compiler that T is A and B derives from A. So it should've been possible to cast B into T. However, the compiler fails with a "The type parameter 'T' cannot be used with the 'as' operator because it does not have a class type constraint nor a 'class' constraint".

    If the above was possible then I would've been able to do the following

    struct S1 : A { }
    D d = new D();
    d.g<S1>(); // meets the constraint that S1:A

    This means that effective we are doing  T t = new B() as S1. But the C# spec clearly calls out "In an operation of the form e as T, e must be an expression and T must be a reference type". This means that using a struct (value type) in an as statement is not allowed and would make the above illegal.

    The solution is to tell the compiler that I'd only send reference types for T and you do this by

    public void g<T>() where T : class, A
    {
        T t = new B() as T; // Invalid! Error CS0413
    }
  • I know the answer (it's 42)

    Difference in conversion of anonymous method and lambda expression

    • 4 Comments

    Consider the following class

    delegate void Moo(int a, int b, int c);
    
    class A
    {
        public event Moo moo;
    }

    In case I want to create a handler for the moo event where I don't care about the 3 parameters needed by the event handler I can easily write it as

    A a = new A();
    a.moo += delegate { count++; };

    However, in case I want to create the same handler with a lambda expression. I have to do it as

    A a = new A();
    a.moo += (a1,a2,a3) => count++;

    There is no shortcut to this. I can't use say a.moo += () => count++;

    The reason lies in the fact that both support a different set of conversions.

    From C# 2.0 spec (§21.3 - Anonymous methods conversions)

    An implicit conversion (§6.1) exists from an anonymous-method-expression to any compatible delegate type. If D is a delegate type, and A is an anonymous-method-expression, then D is compatible with A if and only if the following two conditions are met.

    • First, the parameter types of D must be compatible with A:

    o If A does not contain an anonymous-method-signature, then D may have zero or more parameters of any type, as long as no parameter of D has the out parameter modifier.

    In C# 3.0 spec for Lambda expression conversion it sez

    Specifically, a delegate type D is compatible with a lambda-expression L provided:
    • D and L have the same number of parameters.
    • If L has an explicitly typed parameter list, each parameter in D has the same type and modifiers as the
    corresponding parameter in L.
    • If L has an implicitly typed parameter list, D has no ref or out parameters.
    ...

    In both the cases the lines marked in red indicate why one is different from the other.

  • I know the answer (it's 42)

    A classic Daily WTF find

    • 1 Comments

    If you visit the Indian Railway site and press any of Ctrl/Alt keys it pops a message "Sorry, you do not have permission to press the key". Hey, it's my keyboard and I have all the permission in the world to press whatever I want.

    This is exactly like one of those WTF finds.

  • I know the answer (it's 42)

    Bestsellers list tells a lot

    • 1 Comments

    Right now on Amazon the third most selling book is 21 Pounds in 21 Days: The Martha's Vineyard Diet Detox. This says a lot about developed countries :)

  • I know the answer (it's 42)

    Writing in reverse

    • 4 Comments

    As a kid, like most other kids I used to spend time learning to do weird things like write in reverse (as text seen in mirror-reflection), or write flipped text so that the person seeing the paper from the other side could read it.

    Today I hit upon http://www.revfad.com/flip.html which can flip any text you give it. Like this ɐqɐuıɥqɐ. What it does is for every English character it finds another Unicode character whose glyph looks like the flipped version of that character.

    I tried to demo my weird writing skills to Amit. This is what I got writing at about 0.25 times the normal writing speed.

    signature

    Now my IM message is going to say ǝǝɹɟ ɯ,ı.

Page 1 of 1 (7 items)