Scala recursion, overflow

Question

Here are 2 functions:

def Foo1(s: ((BigInt, Long) => Long)
=> ((BigInt, Long) => Long)): (BigInt, Long) => Long = s(Foo1(s))

def Foo2(s: (=> (BigInt, Long) => Long)
=> ((BigInt, Long) => Long)): (BigInt, Long) => Long = s(Foo2(s))

When they are called with the following parameters:

Foo1(rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1))(56, 0)    
Foo2(rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1))(56, 0)

The first causes stack overflow, and the second executes normally.

Also, what does this expression mean: (=> (BigInt, Long) => Long)?

Bob Dalgleish · Accepted Answer · 2017-09-21 19:33:55Z

The signature (=> (BigInt, Long) => Long) indicates a call-by-name parameter, and is the key to understanding why Foo2 does not overflow the stack.

The way to understand a function in Scala is to substitute the arguments into the definition of the function. You then repeat the substitution as you evaluate the arguments. We also have to recognize that s is used in two different places, one as the parameter to the Foo function, and one as the parameter in the unnamed function passed to Foo.

Evaluating the first function invocation binds the parameter s to

rec => (x, s) => if (x == 1) s else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1)

which turns rec into a recursive function of two arguments, a BigInt and a Long.

Then you evaluate Foo1, substituting the expression value of s, the outer one, into s( Foo1( s ) ). This yields:

( rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1) ) ( Foo1( rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1) )

You then need to evaluate Foo1, passing it the function. This will go on recursively until you run out of stack space.

Foo2, on the other hand, uses call-by-name syntax instead of call-by-value, so it does not need to do the second stage of the evaluation until the parameters, (56, 0), are actually bound.

Collectives™ on Stack Overflow

Scala recursion, overflow

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related