I'm a beginner to Scala, FP, and programming in general. I'm trying to understand when something can be called proper FP.
If we say that functional programming is about chaining functions together so that f(x) = x (for one input and one output), can you say you're still doing fp if you build functions that rely on local mutation, but which always have the same output for the same input?
Compare the following Scala code, which is meant to always produce 10 for x <= 10, and x for all x > 10. That is to say, the function always has a predictable result, unless my logic in constructing them was flawed:
def imp(x: Int): Int = {
var y = x // in case x is an immutable value
while (y < 10) {
y += 1
}
return y
}
def tailRec(x: Int): Int = {
if (x >= 10) return x
else tailRec(x + 1)
}
val x = 2;
imp(x); //10
tailRec(x); //10
I would say that my imperative function has no side effects (it does not alter state outside of the function). I would say that it locally breaks referential transparency, as y is not just a name for a value, but changes over time. However, if we think about the imperative function from a global setting, it does not seem to matter, as the function always gives the same result as the proper pure tailrecursive function. So is this still FP, if you consider the function as a black box and only focus on f(x)=x?
Those functions are definitely pure by definition. I'll use the one provided by Wikipedia, which says that a pure function has the following properties:
- the function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams, i.e., referential transparency), and
- the function has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams).
The only case in which the internal state of a function was relevant would be if said state was static, outliving each individual function call and possibly influencing the return value in subsequent calls (something that in Scala should only happen if a method mutates the state of its class).
With regard to mixing together pure and impure code, it's definitely difficult to do so well, but with some understanding I think it's feasible. I would say that the best way to do so is exemplified by the Scala Collection API itself, as you can see for example in the definition of the List.map
method: expose a pure API and use local mutable state in a small, constrained scope, where it doesn't break referential transparency. This allows to layer pure and impure code without any interference. I would say that the best reasons to choose an impure approach are performance (but that should always be motivated by measurements -- and in most applications it's fair to say it wouldn't be economical to focus on this aspect) and allowing to express an algorithm in a way which is more direct and readable (which is a very good reason to choose an impure approach, as long as you get your abstractions right -- which is quite hard, but probably worth doing anyway).
To go into further depth, I think it's interesting to see at what the compiler outputs for these two methods: the Scala compiler is able to detect tail recursion and optimize it into what would result from a while
loop, ensuring it's also stack-safe (you can also make sure that the compiler enforces that a function is tail-recursive with the @tailrec
annotation). I slightly tweaked your code to make the condition the same and here is the (cleaned) output of javap -v
on the compiler output:
public int imp(int);
...
Code:
stack=2, locals=3, args_size=2
0: iload_1
1: istore_2
2: iload_2
3: bipush 10
5: if_icmpge 14
8: iinc 2, 1
11: goto 2
14: iload_2
15: ireturn
...
public int tailRec(int);
...
Code:
stack=2, locals=2, args_size=2
0: iload_1
1: bipush 10
3: if_icmpge 12
6: iinc 1, 1
9: goto 0
12: iload_1
13: ireturn
...
Basically, the only difference that you can observe is the fact that in the recursive version you had to allocate a mutable variable (since it's Scala it's not possible to mutate an argument). And I wouldn't be surprised if on a warm JVM this is JIT'ed out of existence. ;-)