bobrov - 25 days ago 8

Scala 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)`

Answer Source

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.