Referential transparency with mutation

From a conversation with perplexity.ai about a hypothetical programming language.

Referential transparency is considered a staple in pure functional programming. It typically assumes immutability. But mutability is often more efficient than immutability, since it involves changing data structures in-place rather than always having to create copies.

So, could referential transparency be combined with mutability, if the language was sufficiently restrictive..?

—-

If a function mutates its input but is forced to return that mutated input as part of its result, and if the caller is constrained to never reuse the original input after calling the function, then this can preserve referential transparency despite the mutation.

This is because:

• Referential transparency means you can replace a function call with its output value without changing the program’s behavior.

• If the mutation is local and encapsulated within the function’s scope and the mutated value is immediately returned and used, then the outside program never observes the mutation except via the returned result.

• The caller discards the old input reference and only uses the returned mutated version, so the externally observable behavior is consistent and predictable.

• Practically, the mutation is "hidden" inside the function and the function's interface looks like it produces a new value, preserving functional purity in an external view.

This approach aligns with the insight that local mutation inside a function is allowed if it doesn't leak observable side effects — the function then behaves like a pure function and remains referentially transparent.

For example, an in-place reversal function that takes an array, mutates it internally, and returns it, while the caller uses only the returned array and never reuses the original, can be considered referentially transparent even though it mutates internally[1].

In summary:

| Condition | Result | |---------------------------------------------|--------------------------------| | Function mutates input and returns it | Potential mutation exposed | | Caller reuses original input after call | Breaks referential transparency| | Caller discards original input, uses returned value | Preserves referential transparency if mutation is local and encapsulated |

Thus, mutation inside a function combined with a strict contract on caller usage can preserve referential transparency, even though strictly speaking the function is not pure (since it mutates state internally). This is a subtle but important distinction in functional programming[1][3].

{% details References %} References:

[1] Mutation allowed internally if local and hidden, preserving referential transparency
[3] Referential transparency definition and differences with purity
[4][5][6] Definitions of referential transparency and pure functions

[1] https://betterprogramming.pub/your-code-should-read-like-a-story-how-to-mutate-state-and-have-effect-on-the-world-while-3e3ae808d2d6 [2] https://www.reddit.com/r/functionalprogramming/comments/10k28tm/example_of_a_function_that_has_referential/ [3] https://stackoverflow.com/questions/4865616/purity-vs-referential-transparency [4] https://www.java-success.com/01-scala-functional-programming-basics-pure-functions-referential-transparency-side-effects-etc/ [5] https://dev.to/ruizb/function-purity-and-referential-transparency-7h1 [6] https://adabeat.com/fp/referential-transparency/ [7] https://www.edward-huang.com/functional-programming/tech/programming/scala/2020/01/30/pure-function-vs-referential-transparency/ [8] https://en.wikipedia.org/wiki/Pure_function [9] https://colofabrix.github.io/the-road-to-fp/04_pure_functions.html [10] https://blog.stackademic.com/functional-programming-immutability-and-pure-functions-1d52395353fb?gi=1c3e8037bd09 {% enddetails %}

—-

Code example

Here's a clear JavaScript example illustrating the concept where a function mutates its input internally but returns it, and the caller does not reuse the original input after the function call. This setup preserves referential transparency from the caller's perspective, even though the function performs mutation internally:

// Function that mutates its input array in-place, then returns it
function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    // Swap elements - mutation happens here
    const temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;

    left++;
    right--;
  }

  return arr; // returns the mutated array
}

// Original array
const original = [1, 2, 3, 4];

// Caller does NOT use 'original' after this call, only uses returned value
const reversed = reverseInPlace(original);

console.log(reversed); // [4, 3, 2, 1]
// original === reversed, but caller only uses 'reversed', not 'original'

Why this preserves referential transparency here:

• The function call reverseInPlace(original) can be replaced with reversed everywhere in the code without changing behavior since the caller uses only the returned value after mutation.

• The caller abandons the original input reference and treats the returned mutated array as the new value.

• The mutation is internal to the function's scope and does not produce side effects observable outside beyond the returned result.

• As a consequence, for any given input array that the caller will no longer access after the call, the output is deterministic and no externally visible unexpected mutation occurs.

{% details References %}

Reference from search results:

• Local mutation inside a function that returns the mutated value is considered an implementation detail that doesn't violate functional purity if the interface is pure (i.e., no visible side effects)[1][3].

• Mutation is acceptable inside a function if it is internal and encapsulated and no external shared state is modified[3].

This example fits the pattern you asked about, where mutation happens but referential transparency is preserved by restricting the caller from reusing the original input.

[1] https://dev.to/macsikora/data-mutation-in-functional-javascript-1h97 [2] https://github.com/Manish-Giri/FreeCodeCamp/blob/master/curriculum/challenges/english/02-javascript-algorithms-and-data-structures/functional-programming/avoid-mutations-and-side-effects-using-functional-programming.english.md [3] https://dev.to/macsikora/mutation-is-ok-3e00 [4] https://www.reddit.com/r/functionalprogramming/comments/rswsa6/how_to_handle_mutable_state_in_a_pure_functional/ [5] https://stackoverflow.com/questions/28792326/functional-style-javascript-good-practice-to-avoid-argument-mutation/28792393 [6] https://cs.brown.edu/courses/cs016/static/files/lectures/slides/18-functional-programming.pdf [7] https://softwareengineering.stackexchange.com/questions/351593/automatically-convert-mutations-in-imperative-code-into-functional-actions [8] https://maryrosecook.com/blog/post/a-practical-introduction-to-functional-programming [9] https://ethankent.dev/posts/mutation_scopes/ [10] https://stackoverflow.com/questions/25777592/avoid-mutation-in-this-example-in-f

{% enddetails %}

What if multiple functions use the same input?

Then all but the last one must take a copy of the input. The last one is allowed to mutate the input. All calls are thus referentially transparent wrt. the program as a whole.

function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
  return arr;
}

const original = [1, 2, 3, 4];

// First call: copy original so original remains unmodified
const r1 = reverseInPlace([...original]);
console.log('r1:', r1);            // [4, 3, 2, 1]

// Second call: last use of original, so safe to pass original without copy
const r2 = reverseInPlace(original);
console.log('r2:', r2);            // [4, 3, 2, 1]

// After second call, original is mutated but not used afterward