I recently found a presentation about F# for Python programmers, and after watching it, I decided to implement a solution to the "ant puzzle" on my own.
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?
I implemented my solution in 30 lines of OCaml first, and tried it out:
$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848
real 0m0.143s
user 0m0.127s
sys 0m0.013s
Neat, my result is the same as that of leonardo's implementation, in D and C++. 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.
I then translated the code to F# ... and here's what I got:
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
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:
$ 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
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.
So this program...
- runs fine under OCaml
- doesn't work at all under .NET/F#
- works, but is very slow, under Mono/F#.
Why?
EDIT: Weirdness continues - Using "--optimize+ --checked-" makes the problem disappear, but only under ArchLinux/Mono ; under Windows XP and Windows 7/64bit, even the optimized version of the binary stack overflows.
Final EDIT: I found out the answer myself - see below.