-1

fib(n) calculates the nth fibonacci number:

def fib(n):
    """Compute nth Fibonacci number"""
    pred, curr = 1, 0   # 0 is 0th Fibonacci number
    k = 0               # curr is kth Fibonacci number
    while k < n:
        pred, curr = curr, pred + curr
        k = k + 1
    return curr

It does not create side effects, to rest of the program. It is thread safe

Despite the states(k, curr, pred) are modified locally, Isfib(n) a pure function?

overexchange
  • 15,768
  • 30
  • 152
  • 347
  • Why would it not be a pure function? – Andrei Cioara Mar 26 '18 at 00:42
  • @AndreiCioara Do I need to avoid *mutation of mutable objects* (`k`, `curr`, `pred`), when I write pure function, as mentioned in wiki: *Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects* – overexchange Mar 26 '18 at 00:44
  • 1
    `k`, `curr`, and `pred` are not mutable objects. You are instead binding different objects to the same name in the namespace of the function. Even if you did use mutable objects though, this would still be a pure function, as it is not stateful in the context of the program that would call it, and does not affect the state of anything that it did not create. – Patrick Haugh Mar 26 '18 at 00:48
  • You need to avoid mutation of mutable object `n`, because that object comes from the outside world. You can do whatever you want with your private throwaway variables. Also as @PatrickHaugh mentions, k, curr and pred are not mutable. – Andrei Cioara Mar 26 '18 at 00:49
  • @PatrickHaugh I understand your point of `int` type object being immutable, in python world. But let's not get into that. Considering pseudo code, they are mutable. – overexchange Mar 26 '18 at 00:50
  • @overexchange even if they were lists, assignment is not mutation. With that said, you can mutate objects in a pure function, as long as they were created in that function. So if you wanted a function that returned `[0]`, it could looks something like `def f(): l = []; l.append(0); return l`. That doesn't mutate the state of anything that existed when you called the function. Pure functions are essentially black box functions, which you can interact with and count on nothing happening beyond your being returned a value. – Patrick Haugh Mar 26 '18 at 00:58

2 Answers2

2

The question of whether this is a pure function is heavily dependent on definition and thus opinion-based. However, you have fortunately provided us with a definition from Wikipedia.

  1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change while program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices (usually—see below).
  2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices (usually—see below).

Given the same input, your fibn will always produce the same output. That much is clear. And, as you say, the variables that are modified only exist within the local scope of the function, so there are no semantically observable side effects outside the function. The only thing that remains to be shown (a corollary to (1)) is that your function always terminates. There is a while loop, but the proof that your while loop will terminate given any finite n is trivial. Therefore, based on the provided definition, your function is pure.

Now, I'm assuming that you're listing "must be an integer" as a precondition. If you do not list this as a requirement, then I could produce a class whose ordering methods always make it greater than any k value, thereby forcing an infinite loop. And an infinite loop has a very observable side effect: your program tends not to terminate in that case. However, if you constrain your attention to integer inputs, your function is pure.

Silvio Mayolo
  • 62,821
  • 6
  • 74
  • 116
  • I did not get your last para. What is other than integer? – overexchange Mar 26 '18 at 00:55
  • Python is dynamically typed. I could feasibly pass in a string, a file handle, or an instance of any class. In order for a function to be pure, it needs to actually *produce* zero or more values, so if your loop ends up being infinite, the function fails to be pure. – Silvio Mayolo Mar 26 '18 at 00:58
  • Does function not terminating(infinite loop) has anything to do with pure function? Adding pre-condition is part of good practice in writing an abstraction(in this case function) – overexchange Mar 26 '18 at 01:46
  • I disagree that the proof is trivial. In Python it's true that you don't need to worry about integer overflow, and you've included "must be an integer" which is good - as a float such as `1e16` would cause an infinite loop. The difficulty with a proof is making sure you've covered _all_ the corner cases - such as negative integers. – John La Rooy Mar 26 '18 at 01:51
  • Your last para is referring to [type hints](https://stackoverflow.com/questions/152580/whats-the-canonical-way-to-check-for-type-in-python), which is different topic – overexchange Mar 26 '18 at 12:39
0

Pure functions come into play when discussing the outside world. If you take a snapshot of all your objects before calling the function and after, the two snapshots should be identical.

The function as you put it is a pure function because it does not modify the state or any other part of the program. Your function would not be pure in one of the following cases:

  • If you used the global keyword to modify another variable
  • If it was a method of an object and it changed the object internal state
  • If it mutated n in any way
Andrei Cioara
  • 3,404
  • 5
  • 34
  • 62
  • `n`, `k`, `pred` & `curr` are in local scope. Why mutation of `n` makes it impure? – overexchange Mar 26 '18 at 00:47
  • Re "if it mutated n..." But, the function shown does not make any sense unless n is a number. Aren't numbers immutable? – Solomon Slow Mar 26 '18 at 14:06
  • They are immutable as long as you play by the rules, but you can definitely mutate them (not recommended). See the accepted answer here https://stackoverflow.com/questions/49394818/modify-int-in-place – Andrei Cioara Mar 26 '18 at 15:07