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?

why do you want to? Are you doing it as an excersize, or is there some practical goal you have mind? — Winston Ewert, Feb 10 '15 at 04:52
@WinstonEwert This query is amidst functional programming course exercises. — overexchange, Feb 10 '15 at 05:44
You can have mutable state while retaining referential transparency. Caching results uses mutable state, but is referential transparent. — ziggystar, Feb 10 '15 at 08:16
The title asks how to *enforce*, the question how to *assess*. Please clarify what you actually want to know. — jonrsharpe, Feb 10 '15 at 10:38
@ziggystar True, but note that the definition (and the question) is about referential transparency *for every subexpression*. What you describe is referentially transparent from outside, but not from inside (if you use a mutable cache, there are inner subexpressions which you cannot freely replace). — Andres F., Feb 10 '15 at 13:58

score 5 · Answer 1 · answered Feb 10 '15 at 12:28

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.)

If you ask, "what is the return value of the `while` loop?" then, Do you think that one can ask, "What is the return value of `return` `if..else` in your solution `summation`?" Am not sure, what is the message here, with such question from you? Aren't they just additional keywords that any FP languages like scheme also use. Can't FP paradigm allow "keywords" like `while` `if..else` `return`? Because such keywords allow compiler to transform source code to bytecode, unlike objects pointed by names `term` `n` `total`. So, Why are we considering these "keywords" as (sub)expressions? — overexchange, Feb 12 '15 at 04:51

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

1 Answers1