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, 2016 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, 2016 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, 2016 at 9:45
  • 1
    @clinux do note that C is a distinct language from C++. Ignore the syntactic similarities.
    – Caleth
    Jun 2, 2016 at 10:07
  • 3
    I'm not sure that swallowing the functional-programming dictionary has helped you.
    – user147272
    Jun 2, 2016 at 12:37

2 Answers 2


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.

  • 3
    In addition to mutation, referential transparency bans side effects such as writing to the console.
    – Jack
    Jun 2, 2016 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, 2016 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, 2016 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, 2016 at 3:51
  • @AndresF I would generally count the console output as a form of state mutation. Is that not quite right? I get knee-deep in low-level programming very often so it's kind of confusing to me. A simpler term I feel more confident throwing around is external side effects.
    – user377672
    Oct 21, 2020 at 22:33

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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