To what extent is `this` state considered hidden-state - or its mutations a side-effect?

Question

I was re-reviewing a somewhat upvoted answer of mine where I attempt to explain the differences between pure, impure, deterministic, non-deterministic, and idempotent functions.

In my answer I use .NET's or Java's List<T>.Add( T ) as an example of an impure deterministic function.

I also use Random.Next() as an example of an impure nondeterministic function.

I now think both examples are wrong.

---

Part of my uncertainty comes from how the this parameter is syntactically hidden in most languages with classes and instance-methods. But at the same time, whether or not this is hidden doesn't affect a function's behaviour: it's trivial to show that a static method or free function taking an explicit const me parameter is identical to an instance method with a hidden const this parameter.

...but when this is mutable, I'm unsure. Actually, in the general case of a free-function that accepts a reference to a mutable structure: are those mutations considered (impure) side-effects even if they aren't "hidden"?

So, is List<T>.Add( T ) impure and deterministic? Or pure and non-deterministic?

Assuming that List<T>.Add( T item ) and its static equivalent static void Add( List<T> me, T item ) are considered identical, then it follows that destructing me to separate parameters shouldn't make a difference either, so therefore the following 3 methods are identical, no?

• void Add( T item )
• static void Add( List<T>* me, T item )
• static void Add( T[]** array, size_t* index, T item )
  • _{array is T[]** rather than T[]* to allow for reallocating when resizing.}

I also have contradictory arguments going-on in my head:

• "It's impure" because Add mutates state.
• "It's pure" because Add doesn't mutate any hidden or private state: it mutates only its inputs, therefore it's pure.

If mutating objects passed by-reference (namely T[]** array) is what matters, then what about if static void Add instead returns a tuple of array and index, e.g. static ( T[]* nextArr, size_t nextIndex ) Add( T[]* array, size_t* index, T item ) (thus shifting the responsibility of reassigning this.array to nextArr onto the caller), but it still mutates array's contents if the resize/reallocation wasn't necessary, but there's no hidden mutations going on, so I'm finding it very hard to say if it's now pure or not...

Similarly for determinism:

• "It's deterministic" because identical input will always result in identical output: that is, if the inner structure's T[] array and int index are considered input, then the end-result output is the same (i.e. [out] index = [in] index + 1 and [out] array = [in] array OR [new] resizedArray).

• "It's nondeterministic" because the caller has no way of knowing if the .Add call will fail due to the array resizing (allocate, copy, deallocate) operation will fail due to unpredictable underlying runtime state, e.g. memory fragmentation, even if the length and contents of the input array is identical to previous Add calls.

---

In languages like C# and Java, functions generally do not have their own state, so API design horrors like strtok can't happen again.

...except when they do: both C# and Java allow the creation of closures, which means that what looks like a stateless function-pointer/delegate type really has a bound hidden this (👀) parameter pointing to the closure capture object, which in-turn probably also contains the original this too - which gives me a headache because if List<T>.Add( T ) is-or-is-not pure or impure and deterministic or non-deterministic because of its this parameter, how is a closure any different?

Oh, and both C# and Java also have thread-local storage - which allows for oddly-behaved concurrent but not necessarily reentrant functions, but I'm happy to keep that out-of-scope for now.

Answer 1

Warning: "pure" does not have a 100% agreed upon definition. I have seen different people use it differently.

In the meaning of purity that I learned, all three variants of Add that you list are absolutely impure. They perform an (externally observable) mutation to state.

In the meaning of purity that I learned, mutating the inputs is enough to render a function impure.

In contrast, we can consider a function append(l,x) that returns a new list that is a copy of the input list l with x appended to it: this would be pure.

One more detail that you might be wondering about: a function that internally performs a mutation that is not externally observable is typically considered pure, because it has no externally observable mutation (though there might be some authors who have a different definition). For example:

def f(x):
    t = 0
    t = t + 1
    return x

This performs a mutation to t, but it is not externally observable (the function is observationally equivalent to a pure function), so f is typically considered pure, too.

Answer 2

There are three aspects to this:

1. How do you define "pure"?
2. On what scale do you consider purity?
3. What is your contract?

Purity == Referential Transparency

Regarding #1, I prefer to equate "purity" with "referential transparency". The idea behind referential transparency is rather simple: an expression / statement / subroutine / function / procedure / method is referentially transparent IFF you can replace it with its value (and vice versa) without changing the meaning of the program.

For example, in C, 2 + 2 is referentially transparent because I can replace 2 + 2 with 4 and also replace 4 with 2 + 2 without changing the meaning of the program. printf("Hello") is not pure because if I replace it with its value (6), that will change the meaning of the program:

printf("Hello");
printf("Hello");

does not have the same result as

6;
printf("Hello");

or

printf("Hello");
6;

or

6;
6;

Scope

You can apply the concept of referential transparency on any granularity you like. You can choose to treat functions as black boxes or you can zoom in to the level of individual statements or sub-expressions.

The classic example is a memoizing function that uses local mutable state to keep a cache of values. Something like this pseudo-code:

def add(a: int, b: int) -> int:
    static const cache: Map[Set[int], int]

    if !cache.hasKey({ a, b }):
        # Assume Map.add is a `void` procedure
        cache.add({ a, b }, a + b)

    return cache[{ a, b }]

If you treat the function as a black box and look at it from the outside, then it is referentially transparent: you can replace it with its value, and it will not change the meaning of the program:

add(2, 3)

is the same as

5

But if you analyze the code of the function itself, then it is clear that its internals are not referentially transparent. In fact, anything which involves a void procedure is not referentially transparent: RT means you can replace it with its value, but a void procedure has no value, so RT means you can just delete it. Unless it is doing nothing (in which case, why is it there in the place), this will change the meaning of the program.

In this case, if I replace the call to Map.add with its value (nothing), nothing will ever get added to the cache and thus the lookup will fail and add will throw an exception or return nil or something like that:

def add(a: int, b: int) -> int:
    static const cache: Map[Set[int], int]

    if !cache.hasKey({ a, b }):
        NOP

    return cache[{ a, b }] # Boom! Key does not exist

Software Engineering is all about abstractions. In a perfect world, you would not be able to know whether or not add uses memoization and you wouldn't have access to its source code. Therefore, from your perspective as the client of add, it is referentially transparent.

Which brings us to #3:

Contract

"It's nondeterministic" because the caller has no way of knowing if the .Add call will fail due to the array resizing (allocate, copy, deallocate) operation will fail due to unpredictable underlying runtime state, e.g. memory fragmentation, even if the length and contents of the input array is identical to previous Add calls.

And 1 + 1 could fail if a meteorite destroys the computer just as it is computing the answer. That does not make it non-deterministic. It could also return 4 if a cosmic ray flips the wrong bit in RAM. That does not make it impure, even though it has a hidden dependency on the mutable state of the universe.

It is a question of the contract you have with the function. Does the contract include resistance to cosmic rays? To meteorites? Does it include resistance to Operating System failure? To OS memory overcommitment?

This brings us back to the issue of abstractions above: software is built by building abstractions on top of abstractions, and we generally must assume that abstractions work as documented. In fact, with proper abstractions we have no other choice since we don't have access to the inner workings.

Answer 3

List.Add(T) is impure function because it mutates state thereby producing side effects upon mutation.Data structure is a set of values that can be accessed via memory.Thereby mutating certain data structures in an algorithm makes it an impure function,without mutable state ,it would be simply stateful functions which are called procedures would be mathematical functions without any side effect lke printng on the screen or mutating a data type.