在OCaml中评估期间堆栈溢出

Question

我在实现Heron of Alexandria的平方根近似算法时遇到了堆栈溢出问题,如下所示:

我们从一个初始(差)近似答案开始,平方根为1.0,然后继续改进猜测,直到我们在真实答案的三角形内.通过用x/guess平均当前猜测来实现改进.答案准确到delta = 0.0001.

我的实施尝试如下:

let squareRoot (x : float) : float =
  let rec aux input guess =
    if abs_float(guess**2. -. input) < 0.0001 then guess
    else aux input (guess +. input/.guess)/.2. in
  aux x 1.;;

但是,这会# Stack overflow during evaluation (looping recursion?).在OCaml REPL中引发错误.我尝试在Python中实现一个相同的算法,如下所示:

def squareRoot(x):
  def aux (s, guess):
    if abs(pow(guess,2) - s) < 0.0001:
      return guess
    else:
      return aux (s, (guess + s/guess)/2)
  return aux (x, 1)

...运行得很好.所以我玩了OCaml代码,并改变了我原来的尝试:

let squareRoot (x : float) : float =
  let improve i g = (g +. i/.g)/.2. in
  let rec aux input guess =
    if abs_float(guess ** 2. -. input) < 0.0001 then guess
    else aux input (improve input guess) in
  aux x 1.;;

我改变的是将算法的改进部分包装在一个单独的函数中,但现在代码运行成功,没有任何堆栈溢出错误!

我很感激,如果有人能够解释为什么会这样,并且OCaml REPL /编译器背后的机制可能无法在我的第一次代码迭代中识别递归调用中的终止条件等.

Answer 1

aux input (guess +. input/.guess)/.2. 

^{(应用在分裂前aux发生......)2.}

被解析为

  (aux input (guess +. input/.guess))/.2

你真的想要

  aux input ((guess +. input/.guess)/.2.)

甚至(阅读关于A-normal表格的内容)

  let newguess = (guess +. input/.guess)/.2. 
  in
      aux input newguess

^{(这可能更具可读性,有些人会使用这样的名字guess')}

顺便说一句,有些人会编码

  let guess =  aux input ((guess +. input/.guess)/.2.)
  in aux input guess

^{(没有递归,但是词法范围)}

但我不喜欢这样的编码(重复使用相同的名称guess)

根据经验,不要害羞使用括号(或begin...... end相同)和中间let绑定.两者都使您的代码更具可读性.