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 4:52
  • @WinstonEwert This query is amidst functional programming course exercises. – overexchange Feb 10 '15 at 5:44
  • You can have mutable state while retaining referential transparency. Caching results uses mutable state, but is referential transparent. – ziggystar Feb 10 '15 at 8:16
  • 1
    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
  • 1
    @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

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 4:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.