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…

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.

<Updated> 

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 177 types**, never could've guessed that...

1. System.Object
2. System.ValueType
3. System.Enum
4. System.Void
5. System.Boolean
6. System.Char
7. System.SByte
8. System.Byte
9. System.Int16
10. System.UInt16
11. System.Int32
12. System.UInt32
13. System.Int64
14. System.UInt64
15. System.Single
16. System.Double
17. System.String
18. System.Type
19. System.Reflection.MemberInfo
20. System.RuntimeType
21. System.Array
22. System.IntPtr
23. System.UIntPtr
24. System.Text.StringBuilder
25. System.Delegate
26. System.MulticastDelegate
27. System.DateTime
28. System.Exception
29. System.MarshalByRefObject
30. System.AppDomain
31. System.__ComObject
32. System.Decimal
33. System.SZArrayHelper
34. System.Collections.IEnumerable
35. System.Collections.IEnumerator
36. System.Nullable`1
37. System.SystemException
38. System.Security.VerificationException
39. System.Runtime.InteropServices.CurrencyWrapper
40. System.Runtime.InteropServices.UnknownWrapper
41. System.Runtime.InteropServices.DispatchWrapper
42. System.Runtime.InteropServices.ErrorWrapper
43. System.Runtime.InteropServices.CustomMarshalerHelper
44. System.Attribute
45. System.Runtime.InteropServices.InterfaceTypeAttribute
46. System.Runtime.InteropServices.GuidAttribute
47. System.Runtime.InteropServices.ComVisibleAttribute
48. System.Runtime.InteropServices.ComEventInterfaceAttribute
49. System.Runtime.InteropServices.ComSourceInterfacesAttribute
50. System.Runtime.InteropServices.LCIDConversionAttribute
51. System.Runtime.InteropServices.ComDefaultInterfaceAttribute
52. System.Runtime.InteropServices.DispIdAttribute
53. System.CorPubObject
54. System.Char[]
55. System.Collections.Hashtable
56. System.Reflection.BindingFlags
57. System.Reflection.MemberFilter
58. System.Reflection.Binder
59. System.Type[]
60. System.Reflection.TypeAttributes
61. System.Void*
62. System.Int32[]
63. System.IntPtr[]
64. System.Collections.IDictionary
65. System.UnhandledExceptionEventHandler
66. System.AppDomainManager
67. System.Version
68. System.Runtime.InteropServices.ComInterfaceType
69. System.Collections.ICollection
70. System.Collections.IEqualityComparer
71. System.AppDomainManagerInitializationOptions
72. System.ArithmeticException
73. System.ArgumentException
74. System.MissingMemberException
75. System.MemberAccessException
76. System.AppDomainSetup
77. System.Runtime.InteropServices.Marshal
78. System.PInvoke.EE
79. System.Reflection.AssemblyName
80. System.Byte[]
81. System.Globalization.CultureInfo
82. System.Reflection.Assembly
83. System.Configuration.Assemblies.AssemblyHashAlgorithm
84. System.Configuration.Assemblies.AssemblyVersionCompatibility
85. System.Reflection.AssemblyNameFlags
86. System.Globalization.CultureTableRecord
87. System.Globalization.CompareInfo
88. System.Globalization.TextInfo
89. System.Globalization.NumberFormatInfo
90. System.Globalization.DateTimeFormatInfo
91. System.Globalization.Calendar
92. System.Globalization.BaseInfoTable
93. System.Globalization.CultureTable
94. System.Globalization.CultureTableData
95. System.Globalization.CultureTableData*
96. System.UInt16*
97. System.Globalization.NumberStyles
98. System.Globalization.DateTimeStyles
99. System.String[]
100. System.Globalization.DateTimeFormatFlags
101. System.Globalization.TokenHashValue
102. System.Globalization.TokenHashValue[]
103. System.Byte*
104. System.Globalization.CultureTableHeader
105. System.Globalization.CultureTableHeader*
106. System.Globalization.CultureNameOffsetItem
107. System.Globalization.CultureNameOffsetItem*
108. System.Globalization.RegionNameOffsetItem
109. System.Globalization.RegionNameOffsetItem*
110. System.Globalization.IDOffsetItem
111. System.Globalization.IDOffsetItem*
112. System.TokenType
113. System.Int32&
114. System.IO.TextReader
115. System.IO.TextWriter
116. System.IFormatProvider
117. System.Console
118. System.Char&
119. System.Char*
120. System.ArgumentNullException
121. System.PInvoke.NSLIntl
122. System.ArgumentOutOfRangeException
123. System.RuntimeTypeHandle
124. System.NotSupportedException
125. System.PlatformNotSupportedException
126. System.String&
127. System.TypeLoadException
128. System.Globalization.EndianessHeader
129. System.Globalization.EndianessHeader*
130. System.Globalization.GlobalizationAssembly
131. System.BCLDebug
132. System.PInvoke.TableData
133. System.InvalidProgramException
134. System.Collections.HashHelpers
135. System.Globalization.CultureTableItem
136. System.UInt32&
137. System.Security.CodeAccessSecurityEngine
138. System.LocalDataStoreMgr
139. System.Threading.ExecutionContext
140. System.LocalDataStore
141. System.Collections.ArrayList
142. System.Threading.SynchronizationContext
143. System.Runtime.Remoting.Messaging.LogicalCallContext
144. System.Runtime.Remoting.Messaging.IllogicalCallContext
145. System.Threading.Thread
146. System.Object[]
147. System.Collections.Generic.Dictionary`2
148. System.Runtime.Remoting.Messaging.CallContextRemotingData
149. System.Runtime.Remoting.Messaging.CallContextSecurityData
150. System.Collections.Generic.IEqualityComparer`1
151. System.InvalidOperationException
152. System.Globalization.CultureTableRecord[]
153. System.Threading.Monitor
154. System.Globalization.CultureTableRecord&
155. System.Object&
156. System.Threading.Interlocked
157. System.Runtime.CompilerServices.RuntimeHelpers
158. System.RuntimeFieldHandle
159. System.PInvoke.PAL
160. System.IndexOutOfRangeException
161. System.IntPtr&
162. System.Buffer
163. System.NullReferenceException
164. System.OutOfMemoryException
165. System.InvalidCastException
166. System.OverflowException
167. System.DivideByZeroException
168. System.ArrayTypeMismatchException
169. System.MissingMethodException
170. System.FormatException
171. System.RankException
172. System.Security.SecurityException
173. System.StackOverflowException
174. System.Threading.ThreadAbortException
175. System.Threading.ThreadTerminateException
176. System.MethodAccessException
177. SmartDeviceProject1.Program

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

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

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