Tail call optimization

I had posted about tail call and how .NET handles it before. However there was some email exchanges and confusion on internal DLs around it and so I thought I'd try to elaborate more on how .NET goes about handling tail calls

Let’s try to break this down a bit.

a) A piece of C# code contains tail recursion .

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

-

b) The C# compiler does not optimize this and generates a normal recursive call in IL

 IL_000c:  ...
 IL_000d:  ...
 IL_000e:  sub
 IL_000f:  dup
 IL_0010:  starg.s num
 IL_0012:  call void TailRecursion.Program::CountDown(int32)

-

c) The Jitter on seeing this call doesn’t optimize it in any way and just inserts a normal call instruction for the platform it targets (call for x86)

However, if any compiler is smart enough to add the tail. recursive IL statement then things change.

a) Scheme code

(define (CountDown n)
    (if (= n 0)
         n
      (CountDown (- n 1))))

-

b) Hypothetical IronScheme compiler will generate (note for scheme it has to do the optimization)

 IL_000c:  ...
 IL_000d:  ...
 IL_000e:  sub
  tail.
 IL_0023:  call void TailRecursion.Program::CountDown(int32)
 IL_0029:  ret

-

c) Based on which JIT you are using and various other scenarios the JIT now may honour the tail. IL instruction and optimize this with a jmp when generating machine instruction

Please note the may in the very last point and refer to here for some instances where the optimization still might not take place…

A* Pathfinding algorithm animation screen saver

I'm trying to learn WPF and IMO it is not a simple task. Previously whenever I upgraded my UI technology knowledge it had been easy as it build on a lot of pre-existing concepts. However, WPF is more of a disruptive change.

I decided to write some simple fun application in the effort to learn WPF. Since I cannot write a BabySmash application as Scott Hanselman has already done a awesome job out of it, I decided to code up a simulation of A* path finding algorithm and push it out as a screen saver. The final product looks as follows.

What it does is that it shows a source, a destination with blockages (wall, mountain?) in between and then uses A* algorithm to find a path in between them. This is the same kind of algorithm that is used in say games like Age of the Empires as workers move around collecting wood and other resources. The algorithm is documented here.

Features

1. It supports plugging in your own scenes with help of the awesome screen/board designer I blogged about
2. Comes with a WPF and a console client to show the animation
3. Algorithm can be played with easily to change or tweak it.
4. Shows full animation including start, end, obstacle, closed cells, current path being probed and the final path
5. Multi-screen support. Each screen shows a different board being solved.

Limitations:

Obviously this was more of a quick dirty hobby project and there remains a ton to work on. E.g.

1. Screen saver preview doesn't work.
2. Setting dialog is a sham.
3. The boards do not flip for vertically aligned screens
4. The XAML data binding is primitive and needs some work
5. The path can choose diagonally across cell even if it seems to cross over diagonal wall of obstacle.
6. Mouse move alone doesn't shut down the screen saver. You need to hit a
7. Many more :)

Download:

Download the final binaries from here. Unzip to a folder, right click on the *.scr and choose Install

Download sources (including VS 2008 sln) from here.

Enjoy.

How Many Types are loaded for Hello World

Consider the following super simple C# code

namespace SmartDeviceProject1
{
    class Program
    {
        static void Main(string[] args)
        {
            System.Console.WriteLine("Hello");
        }
    }
}

Can you guess how many managed Type gets loaded to run this? I was doing some profiling the .NET Compact Framework loader (for entirely unrelated reason) and was surprised by the list that got dumped. 87 types**, never could've guessed that...

1. System.Object
   
2. System.ValueType
   
3. System.Type
   
4. System.Reflection.MemberInfo
   
5. System.Delegate
   
6. System.MarshalByRefObject
   
7. System.SystemException
   
8. System.Exception
   
9. System.Attribute
   
10. System.Collections.Hashtable
    
11. System.Enum
    
12. System.Reflection.BindingFlags
    
13. System.MulticastDelegate
    
14. System.Reflection.MemberFilter
    
15. System.Reflection.Binder
    
16. System.Reflection.TypeAttributes
    
17. System.DateTime
    
18. System.Collections.IDictionary
    
19. System.UnhandledExceptionEventHandler
    
20. System.AppDomainManager
    
21. System.Version
    
22. System.Decimal
    
23. System.Runtime.InteropServices.ComInterfaceType
    
24. System.Collections.ICollection
    
25. System.Collections.IEqualityComparer
    
26. System.AppDomainManagerInitializationOptions
    
27. System.ArithmeticException
    
28. System.ArgumentException
    
29. System.MissingMemberException
    
30. System.MemberAccessException
    
31. System.AppDomainSetup
    
32. System.Reflection.AssemblyName
    
33. System.Globalization.CultureInfo
    
34. System.Reflection.Assembly
    
35. System.Configuration.Assemblies.AssemblyHashAlgorithm
    
36. System.Configuration.Assemblies.AssemblyVersionCompatibility
    
37. System.Reflection.AssemblyNameFlags
    
38. System.Globalization.CultureTableRecord
    
39. System.Globalization.CompareInfo
    
40. System.Globalization.TextInfo
    
41. System.Globalization.NumberFormatInfo
    
42. System.Globalization.DateTimeFormatInfo
    
43. System.Globalization.Calendar
    
44. System.Globalization.BaseInfoTable
    
45. System.Globalization.CultureTable
    
46. System.Globalization.CultureTableData
    
47. System.Globalization.NumberStyles
    
48. System.Globalization.DateTimeStyles
    
49. System.Globalization.DateTimeFormatFlags
    
50. System.Globalization.TokenHashValue
    
51. System.Globalization.CultureTableHeader
    
52. System.Globalization.CultureNameOffsetItem
    
53. System.Globalization.RegionNameOffsetItem
    
54. System.Globalization.IDOffsetItem
    
55. System.TokenType
    
56. System.Char
    
57. System.IO.TextReader
    
58. System.IO.TextWriter
    
59. System.IFormatProvider
    
60. System.Console
    
61. System.RuntimeTypeHandle
    
62. System.NotSupportedException
    
63. System.Globalization.EndianessHeader
    
64. System.Reflection.Missing
    
65. System.RuntimeType
    
66. System.Threading.StackCrawlMark
    
67. System.Globalization.CultureTableItem
    
68. System.Int32
    
69. System.Security.CodeAccessSecurityEngine
    
70. System.AppDomain
    
71. System.LocalDataStoreMgr
    
72. System.Threading.ExecutionContext
    
73. System.LocalDataStore
    
74. System.Collections.ArrayList
    
75. System.Threading.SynchronizationContext
    
76. System.Runtime.Remoting.Messaging.LogicalCallContext
    
77. System.Runtime.Remoting.Messaging.IllogicalCallContext
    
78. System.Threading.Thread
    
79. System.Collections.Generic.Dictionary`2
    
80. System.Runtime.Remoting.Messaging.CallContextRemotingData
    
81. System.RuApplication starting
    
82. System.Collections.Generic.IEqualityComparer`1
    
83. Runtime.Remoting.Messaging.CallContextSecurityData
    
84. System.Array
    
85. System.RuntimeFieldHandle
    
86. System.Globalization.CultureTableRecord[]
    
87. System.Text.StringBuilder

**This is for the compact framework CLR. Your mileage will vary if you run the same on the desktop CLR.

Designer for my path finding boards

I'm writing a small application (or rather a screen saver) that animates and demonstrates A* search algorithm. The idea is simple. On screen you see a start and end point and some random obstacles in between them. Then you see animation on how A* algorithm is used to navigate around the board to find a path (close to the shortest possible) between the two.

All of this is fairly standard. However, I got hit by a simple issue. I wanted to have the ability to design this board visually and also let my potential million users do the same. Obviously I don't have time to code up a designer and hence choose the all time manager's favorite technique. Re-use :)

So the final solution I took was to use Microsoft Office Excel as the WYSIWYG editor. I created a xlsx file with the following conditional formatting which colors cells based on the value of the cells.

So in this case

1. w = Wall marking the end of the table
2. b = blocks/bricks/obstacle
3. s = start
4. e = end

Using this I can easily design the board. The designer in action looks as follows

Since the excel sheet has conditional formatting the user just types in s, e, b, w in the cells and they all light up visually. At the end he/she just saves the file using File => Save As and uses CSV format. This saves the file shown above as

w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,b,,,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,s,,,,,,,,b,b,b,b,b,b,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,b,b,b,b,,b,b,b,b,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,b,,,,,,b,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,b,b,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,b,b,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,b,b,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,b,b,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,e,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w

As you see the format is simply a row per line and every column separated by a comma. My simulator reads this file and renders using whatever renderer is configured (console or WPF).

More about the A* simulator to come soon...

It's is easy to claim that the world won't get destroyed today

The clock is ticking and the Large Hadron Collider in Cern is going to get switched on today (9/10/2008). Even though there are speculations, CERN is claiming it's perfectly safe and the world won't end. But it's easy to claim that, who'll be around to prove them wrong in case they are :)

It's one of the coolest device at an operating temperature of < -270°C. But I'd get really angry if there's any disturbance to my Birthday celebrations!!