CODEWITHSUNDEEP
recursionocamlstack-overflow
user5835083
user5835083

Reputation:

Stack overflow during evaluation in OCaml

I encountered a stack overflow issue when implementing a square root approximation algorithm by Heron of Alexandria, given as follows:

We start with an initial (poor) approximate answer that the square root is 1.0 and then continue improving the guess until we're within delta of the real answer. The improvement is achieved by averaging the current guess with x/guess. The answer is accurate to within delta = 0.0001.

My attempt at an implementation was as follows:

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

However, this raises a # Stack overflow during evaluation (looping recursion?). error in the OCaml REPL. I tried implementing an identical algorithm in Python as follows:

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)

...which ran just fine. So I played around with the OCaml code, and changed my original attempt to:

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

All I changed was wrapping the improvement portion of the algorithm in a separate function, but now the code runs successfully, without any stack overflow error!

I'd appreciate if someone could explain why this is so, and the mechanism behind the OCaml REPL/compiler possibly not recognizing a terminating condition in the recursive call in the my first iteration of code, etc.

Upvotes: 3

Views: 576

Answers (1)

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

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

(the application of aux happens before the division by 2. ...)

is parsed as

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

You really want

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

or even (read about A-normal forms)

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

(which could be more readable, some people use names like guess')

BTW, some people would code

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

(there is no recursion, but lexical scoping)

but I don't like coding like that (reusing the same name guess)

As a rule of thumb, don't be shy in using parenthesis (or begin ... end which is the same) and intermediate let bindings. Both makes your code more readable.

Upvotes: 5

Related Questions