title: F# vs OCaml: Stack overflow
body: <p>I recently found a presentation about <a href="http://combiol.org/fs/FSUG_FS4PPv2.pptx" rel="nofollow noreferrer">F# for Python programmers</a>, and after watching it, I decided to implement a solution to the "ant puzzle" on my own.</p>
  
  <p><em>There is an ant that can walk around on a planar grid. The ant can move one space at a time left, right, up or down.  That is, from the cell (x, y) the ant can go to cells (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the x and y coordinates are greater than 25 are inaccessible to the ant. For example, the point (59,79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. The question is: How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?</em></p>
  
  <p>I implemented my solution in 30 lines of <a href="http://pastebin.com/EzMt466b" rel="nofollow noreferrer">OCaml first</a>, and tried it out:</p>
  
  <pre><code>$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
  $ time ./puzzle
  Points: 148848
  
  real    0m0.143s
  user    0m0.127s
  sys     0m0.013s
  </code></pre>
  
  <p>Neat, my result is the same as that of <a href="http://leonardo-m.livejournal.com/" rel="nofollow noreferrer">leonardo's implementation, in D and C++</a>. Comparing to Leonardo's C++ implementation, the OCaml version runs approx 2 times slower than C++. Which is OK, given that Leonardo used a queue to remove recursion.</p>
  
  <p>I then <a href="http://pastebin.com/0Vx5GTBQ" rel="nofollow noreferrer">translated the code to F#</a> ... and here's what I got:</p>
  
  <pre><code>Thanassis@HOME /g/Tmp/ant.fsharp
  $ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
  Microsoft (R) F# 2.0 Compiler build 2.0.0.0
  Copyright (c) Microsoft Corporation. All Rights Reserved.
  
  Thanassis@HOME /g/Tmp/ant.fsharp
  $ ./ant.exe
  
  Process is terminated due to StackOverflowException.
  Quit
  
  Thanassis@HOME /g/Tmp/ant.fsharp
  $ /g/Program\ Files/Microsoft\ F#/v4.0/Fsc.exe ant.fs
  Microsoft (R) F# 2.0 Compiler build 4.0.30319.1
  Copyright (c) Microsoft Corporation. All Rights Reserved.
  
  Thanassis@HOME /g/Tmp/ant.fsharp
  $ ./ant.exe
  
  Process is terminated due to StackOverflowException
  </code></pre>
  
  <p>Stack overflow... with both versions of F# I have in my machine...
  Out of curiosity, I then took the generated binary (ant.exe) and run it under Arch Linux/Mono:</p>
  
  <pre><code>$ mono -V | head -1
  Mono JIT compiler version 2.10.5 (tarball Fri Sep  9 06:34:36 UTC 2011)
  
  $ time mono ./ant.exe
  Points: 148848
  
  real    1m24.298s
  user    0m0.567s
  sys     0m0.027s
  </code></pre>
  
  <p>Surprisingly, it runs under Mono 2.10.5 (i.e. no stack overflow) - but it takes 84 seconds, i.e. 587 times slower than OCaml - oops. </p>
  
  <p>So this program...</p>
  
  <ul>
  <li>runs fine under OCaml</li>
  <li>doesn't work at all under .NET/F#</li>
  <li>works, but is very slow, under Mono/F#.</li>
  </ul>
  
  <p>Why?</p>
  
  <p><strong>EDIT:</strong> Weirdness continues - Using "--optimize+ --checked-" makes the problem disappear,  <strong>but only under ArchLinux/Mono</strong> ; under Windows XP and Windows 7/64bit, even the optimized version of the binary stack overflows.</p>
  
  <p><strong>Final EDIT</strong>: I found out the answer myself - see below.</p>