4

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.

  • Since there's no such thing as a "reference" in C parlance, and the very impure act of updating global variables does not have to involve pointers, it's very unclear to me what style of C you're imagining here or why you think it'd be RT. Maybe try showing some code snippets of what you mean? – Ixrec Jun 1 '16 at 11:33
  • 3
    I understand that many people make the two concepts sound the same, but referential transparency and immutability aren't the same thing. For example, functional reactive programming is a referentially transparent approach to programming stateful systems. – sacundim Jun 1 '16 at 22:51
  • You say you are avoiding the "performance penalty" of immutability, but you have an implicit copy in the call of basicSort5. Also note that an optimizing compiler for an "immutable" language is allowed to implement the program that logically is immutable with an equivalent process upon mutable structures, e.g. by noting the lifetime of values and re-using the storage thereof – Caleth Jun 2 '16 at 9:45
  • 1
    @clinux do note that C is a distinct language from C++. Ignore the syntactic similarities. – Caleth Jun 2 '16 at 10:07
  • 3
    I'm not sure that swallowing the functional-programming dictionary has helped you. – user147272 Jun 2 '16 at 12:37
4

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.

| improve this answer | |
  • 3
    In addition to mutation, referential transparency bans side effects such as writing to the console. – Jack Jun 2 '16 at 22:02
  • Leaving you to represent side effects as a pure value, then passing that pure value to an interpreter later on. – clinux Jun 2 '16 at 23:11
  • 1
    To elaborate on @Jack's comment, the following C function is not referentially transparent, even though it doesn't mutate anything: int f(int x) { printf("hello\n"); return x; }. – Andres F. Jun 3 '16 at 3:03
  • @clinux And that interpreter may also be pure. For example, an interpreter that tests a series of file read and write actions could use an in memory file. – Jack Jun 3 '16 at 3:51
6

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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