How do I enforce 'referential transparency' in this program?

Question

Below is the python program written to follow the rule of thumb in functional programming.

The simple rule of thumb is: if you can replace any expression, sub-expression or subroutine call with the return value of that expression, sub-expression or subroutine call anywhere in the program, without the program changing its meaning, then you have referential transparency. And what this means, practically speaking is that you can't have any I/O, can't have any mutable state, can't have any side-effects. In every expression, the value of the expression must depend solely on the values of the constituent parts of the expression. And in every subroutine call, the return value must depend solely on the arguments.

def identity(k):
    return k

def cube(k):
    return pow(k, 3)

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total

def sum_naturals(n):
    return summation(n, identity)

def sum_cubes(n):
    return summation(n, cube)

if __name__ == '__main__':
    sum = sum_naturals(4)
    print(sum)

In above program, objects pointed by total and k maintain immutability of state and I/O is not used except in driver code to just confirm the results.

How do I enforce 'referential transparency' in my program for all the expressions/sub-expressions used in this program?

Answer 1

You already said in your question how you can tell whether your program is referentially transparent or not: if you can replace a expression with its value, without changing the meaning of the program, it is referentially transparent. If you cannot do that, it is not.

So, let's just try and replace some expressions with their values!

in your summation method, in the first line, you set total to 0. So, if your program is referentially transparent, we should be able to replace any occurrence of total with 0. For example, like this:

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = 0 + term(k), k + 1
    return total

or like this:

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return 0

The same goes for k:

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), 1 + 1
    return total

or here:

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(1), k + 1
    return total

or here:

def summation(n, term):
    total, k = 0, 1
    while 1 <= n:
        total, k = total + term(k), k + 1
    return total

let's put that all together:

def summation(n, term):
    total, k = 0, 1
    while 1 <= n:
        total, k = 0 + term(1), 1 + 1
    return 0

Also, what is the return value of the while loop? The while loop doesn't have a return value, it returns nothing. According to the rules of referential transparency, we should be able to replace any expression with its return value without changing the meaning of the program, ergo, we should be able to replace the entire while loop with nothing:

def summation(n, term):
    total, k = 0, 1
    return total

Again, if your program were referentially transparent, this shouldn't change the result.

Note that a loop simply cannot possibly be referentially transparent. Referential transparency can also be interpreted as "if I do the same thing, the same thing happens". But in a loop, we do the same thing over and over again, yet, we expect something different to happen every time, or at least once: the loop stops.

Here's an example of how to implement summation without breaking referential transparency:

def summation(n, term):
    if n == 0:
        return term(n)
    else:
        return term(n) + summation(n - 1, term)

And here is an implementation in a tail-recursive fashion using the standard "introduce an accumulator" trick:

def summation(n, term):
    def summation_rec(n, total):
        if n == 0:
            return total
        else:
            return summation_rec(n-1, total + term(n))
    return summation_rec(n, 0)

(Unfortunately, that won't help, since Python doesn't implement Proper Tail Calls, not even Proper Tail Recursion. So, this will still blow the stack for larger n. But in a language with proper implementation of tail recursion or even proper tail calls, this will run in O(1) stack space.)