我最近发现了一个针对Python程序员的关于f#的演示，看完之后，我决定自己实现一个解决"蚂蚁难题"的方法。
有一只蚂蚁可以在平面网格上行走。蚂蚁可以一次移动一个空间，向左、向右、向上或向下。也就是说，蚂蚁可以从单元格(x, y)前往单元格(x+1, y)、(x, y+1)和(x, y-1)。蚂蚁无法到达x和y坐标的数字之和大于25的点。例如，点(59,79)是不可访问的，因为5 + 9 + 7 + 9 = 30，大于25。问题是:如果蚂蚁从(1000,1000)开始，包括(1000,1000)本身，它可以访问多少个点?
我首先在30行OCaml中实现了我的解决方案，并进行了尝试:
$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848
real 0m0.143s
user 0m0.127s
sys 0m0.013s
很好，我的结果与leonardo在D和c++中实现的结果相同。与Leonardo的c++实现相比，OCaml版本的运行速度大约比c++慢2倍。考虑到Leonardo使用队列来消除递归，这是可以的。
然后我把代码翻译成f#…这是我得到的:
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
堆栈溢出……我的机器上有两个版本的f#…出于好奇，我把生成的二进制文件(ant.exe)放在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
令人惊讶的是，它在Mono 2.10.5下运行(即没有堆栈溢出)-但它需要84秒，即比OCaml慢587倍-哎呀。
所以这个程序…
- 在OCaml 下运行良好
- 在。net/f# 下根本不起作用
- 工作，但非常慢，在单声道/f#下。
为什么?
编辑:奇怪的继续-使用"——优化+——检查-"使问题消失，但仅在ArchLinux/Mono;在Windows XP和Windows 7/64bit下，即使是优化版本的二进制堆栈也会溢出。
最终编辑:我自己找到了答案-见下文
执行摘要:
- 我写了一个简单的算法实现…这不是尾部递归。
- 我在Linux下用OCaml编译。
- 运行正常，0.14秒完成
是时候移植到f#了。
- 我把代码(直接翻译)翻译成f#。
- 我在Windows下编译，并运行它-我得到了一个堆栈溢出。
- 我将二进制文件放在Linux下，并在Mono下运行它。
- 可以，但是运行非常慢(84秒)。
然后我在Stack Overflow上发帖-但是有些人决定关闭这个问题(叹气)。
- 我尝试用——optimize+——checked- 编译
- …但在Linux/Mono下运行良好(并在0.5秒内完成)。
是时候检查堆栈大小了:在Windows下，另一个SO帖子指出它默认设置为1MB。在Linux下，"uname -s"和测试程序的编译清楚地显示它是8MB。
这解释了为什么该程序在Linux下而不是在Windows下运行(该程序使用了超过1MB的堆栈)。它没有解释为什么优化的版本在Mono下运行得比未优化的版本好得多:0.5秒vs 84秒(尽管——optimize+似乎是默认设置，参见Keith的评论"Expert f#"摘录)。可能与Mono的垃圾收集器有关，它在某种程度上被第一个版本推向了极端。
Linux/OCaml和Linux/Mono/f#执行时间的差异(0.14 vs 0.5)是因为我测量它的简单方法:"time ./binary…"也测量启动时间，这对Mono/来说很重要。. NET(对于这个简单的小问题很重要)。
无论如何，为了一劳永逸地解决这个问题，我编写了一个尾递归版本——函数末尾的递归调用被转换为循环(因此，不需要使用堆栈——至少在理论上)。
新版本在Windows下也运行得很好，并且在0.5秒内完成。
所以，这个故事的寓意:
- 注意你的堆栈使用，特别是如果你使用了很多并且在Windows下运行。使用EDITBIN和/STACK选项将二进制文件设置为更大的堆栈大小，或者更好的是，以一种不依赖于使用太多堆栈的方式编写代码。OCaml在尾部递归消除方面可能比f#更好，或者它的垃圾收集器在这个特定问题上做得更好。
- 不要对粗鲁的人关闭你的Stack Overflow问题感到绝望，如果问题真的很好，善良的人最终会抵制他们:-)
注:Jon Harrop博士的一些补充输入:
…你只是很幸运OCaml没有溢出。您已经确定了平台之间的实际堆栈大小是不同的。同一问题的另一个方面是不同的语言实现以不同的速率占用堆栈空间并具有不同的性能深烟囱存在时的特征。OCaml, Mono和。net它们都使用不同的数据表示和GC算法这些结果……(a) OCaml使用带标签的整数来区分指针;给出紧凑的堆栈帧，并遍历堆栈上的所有内容寻找指示。标签基本上只传达了足够的信息为了OCaml运行时能够遍历堆(b) Mono处理单词在堆栈上保守地作为指针:如果，作为指针，一个字将指向到堆分配的块中，那么该块被认为是可访问的。(c)我不知道。net的算法，但我不会感到惊讶，如果它吃堆栈空间更快，仍然遍历堆栈上的每个单词(当然如果一个不相关的线程有深栈!)…此外，使用堆分配元组意味着您将快速填充托儿所代(例如第0代)，因此，
让我试着总结一下答案。
有三点需要说明:
- 问题:栈溢出发生在递归函数
- 它只在windows下发生:在linux上，对于检查的问题大小，它工作
- OCaml作品中相同(或类似)的代码
- 优化+编译器标志，对于检查的问题大小，works
堆栈溢出异常通常是由递归值引起的。如果调用位于尾部位置，编译器可能会识别它并应用尾部调用优化，因此递归调用不会占用堆栈空间。尾部调用优化可能发生在f#、CRL或两者中:
CLR尾部优化1
f#递归(更一般)2
f#尾部调用3
正确的解释"在windows上失败，而不是在linux"如前所述，是两个操作系统上默认保留的堆栈空间。或者更好的是，两个操作系统下的编译器使用的保留堆栈空间。默认情况下，vc++只保留1MB的堆栈空间。CLR(很可能)是用vc++编译的，所以它有这个限制。保留的堆栈空间可以在编译时增加，但我不确定它是否可以在编译的可执行文件上修改。
编辑:事实证明这是可以做到的(参见这篇博客文章http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx)我不建议这么做，但至少在极端情况下是可能的。
OCaml版本可能工作，因为它是在Linux下运行的。但是，在Windows下测试OCaml版本也会很有趣。我知道OCaml编译器在尾部调用优化方面比f#更积极。它甚至可以从原始代码中提取尾部递归函数吗?
我猜"——优化+"它仍然会导致代码重复出现，因此在Windows下它仍然会失败，但可以通过使可执行文件运行得更快来缓解问题。
最后，最终的解决方案是使用尾部递归(通过重写代码或依赖于积极的编译器优化);这是避免递归函数堆栈溢出问题的好方法。