Referential Transparency by using Zero References?

Question

Referential Transparency is one of the corner stones of functional programming that allows us to apply equative reasoning to our code. However it does so at a cost to performance, by use of immutable objects.

Some functional programming languages like Idris solve this performance problem via the use of Uniqueness Types and Borrowed Types to allow in-place updates of objects (side effects) as long the overall net effect is as if we were still using immutable objects.

Idris lead me to think about C. When you program in C using no references at all (zero reference), then could all of the zero references could be considered to be transparent?

That is to say. If you program in C updating your all variables in place with side effects, while using just the Stack Space (no pointers, no heap), then Have you achieved Referential Transparency? And can you apply still Equational Reasoning to your code?

I'll admit that I did not think about global variables at all, and that will break RT.

Heres an example of what I've imagined:

#include <stdio.h>

struct A5 {
    int x[5];
};

A5 basicSort5(A5 nums) {
    int n = 5;
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (nums.x[i] > nums.x[j]) {
                int tmp = nums.x[i];
                nums.x[i] = nums.x[j];
                nums.x[j] = tmp;
            }
        }
    }
    return nums;
}

int main() {
    A5 nums = {7,3,2,8,9};
    A5 sortedNums = basicSort5(nums);
    for (int i = 0; i < 5; ++i) {
        printf("%i\n", sortedNums.x[i]);
    }
    return 0;
}

basicSort5 is referentially transparent (and thread safe) because it is not using references. The exact same code in Java is not referentially transparent because it forces everything to be a reference.

I should of extended this question to C++. Because I believe if you use move semantics, and code in a linearly typed style, then you keep RT while also obtaining the performance benefits of Idris's Unique Types. And if you make a mistake coding in linear typed style then you just wear the cost of a memcpy and still keep RT. I just want this theory confirmed.

I think I've made a mistake. Move semantic will only help if I'm using heap space hidden inside a class. I will always have some sort of copying going on, even if its a 4 byte pointer.

Answer 1

Pointers are orthogonal to referential transparency.

Move semantics works fine in C, although with more boilerplate than C++.

No mutable global state + no function permitted to mutate it's arguments would suffice for referential transparency, even when passing by pointer. Just don't hack up anything passed in. Mutating local variables is fine - the caller can't see them.

This strategy doesn't play well with C lacking multiple return types. Calling pop on a stack needs to return both an element and a new, usually smaller, stack. Possibly also an error code. So you drown in structs made to return multiple values.

Otherwise though, it works pretty well.

Answer 2

I think what you’ve picked up on is that, in a referentially transparent language, everything has value semantics. And if you don’t read or write globals, or do I/O, then indeed this is enough to give you referential transparency. If, in addition, you don’t use local mutation, then you’ll also get more of the benefits of equational reasoning.

And, for efficiency reasons, things can be implemented using reference semantics under the hood due to immutability. Because objects don’t have identity, no one can distinguish between a reference and a copy!

prepend42 :: [Int] -> [Int]
prepend42 list = 42 : list

Here, list is not modified. In value semantics, we’re making a new list that contains all the elements of list, with an additional cell at the front containing 42. However, because list is immutable, we can implement this using reference semantics: we only need to allocate one new list cell, and the rest of the structure is shared.

let someList  = [10, 20, 30]
let someList' = prepend42 someList

+----+   +----+   +----+   +----+
| 42 |-->| 10 |-->| 20 |-->| 30 |
+----+   +----+   +----+   +----+
  ^        ^
  |        |
  |        someList
  |
  prepend42 someList

A similar thing happens for, say, a persistent Set data type, which is implemented as a size-balanced binary tree: inserting an element only does O(log n) allocations for the new “spine” of the structure (from the root to the inserted node) and the rest of the structure is shared.

So it’s not necessarily the case that immutable objects lead to more copying; it depends on the data structures in question, and how they’re being used.