Xtykutl

I'm creating this question based upon a small discussion I had in the comments to the answer to this question: design a method returning a value or changing some data but not both

@Kata pointed out that the pattern that the OP was interested in is called Command–query separation and argued that this is a good model to structure your code by.

From wikipedia:

Command–query separation (CQS) is a principle of imperative computer programming. It was devised by Bertrand Meyer as part of his pioneering work on the Eiffel programming language.

It states that every method should either be a command that performs an action, or a query that returns data to the caller, but not both. In other words, Asking a question should not change the answer.1 More formally, methods should return a value only if they are referentially transparent and hence possess no side effects.

I questioned the soundness of this design principle, as in general it would appear to make your code far more tedious. For instance: you could not perform a simple statement like next = Queue.Dequeue(); You would need two instructions: one to modify the data structure and one to read the result.

@Kata found an alternative Stack implementation that at first glance appears to satisfy the best of both worlds: taking a page from functional programming, we define our Stack as an immutable data-structure. Whenever we push(x) we create a new Stack node that holds the value x and maintains a pointer to the old head Stack instance. Whenever we pop() we just return the pointer to the next Stack instance. Thus we can adhere to the Command-Query Separation Principle.

Example Stack Implementation: https://fsharpforfunandprofit.com/posts/stack-based-calculator/

However, one thing that is unclear in this case is how you would keep multiple references to the Stack in sync while still adhering to the Command-Query Separation Principle? I don't see an obvious solution to this. So as a point of curiosity I'm posing this problem to the community to see if we can't find a satisfactory solution :)

EDIT: Here is an example of the problem:

s = new Stack();

s2 = s

...

s = s.push(x);

assert(s == s2); // this will fail

In Functional Programming (FP) style, we often design our functions so that we don't need to keep such those references in sync.

Consider this scenario: you create a stack s, inject it into a Client object, then push an item to s and get a new stack s2:

s = new Stack()

client = new Client(s)

s2 = s.push(...)

Because s and s2 are not in sync (i.e., they are different stacks), inside the object client, it still sees the old version of stack (s) which is something you don't want. Here is the code of Client:

class Client {

    private Stack stack;

    // other properties

    public Client(Stack stack) { this.stack = stack; }

    public SomeType foo(/*some parameters*/) {

        // access this.stack

    }

}

To solve this, the functional approach does not use such an implicit reference, but instead passes the reference into the function as an explicit parameter:

class Client {

    // some properties

    public SomeType foo(Stack stack, /*some parameters*/) {

        // access stack

    }

}

Of course, sometimes this would be painful as the function now has one extra parameter. Every caller of Client must maintain a stack in order to call the foo function. That's why in FP you tend to see functions with more parameters than in OOP.

But FP has a concept which can mitigate this pain: the so-called partial application. If you already have a stack s, you can write client.foo(s) to get an "upgraded" version of foo which does not require a stack but only requires the other some parameters. Then you can pass that upgraded foo function to a receiver who does not maintain any stack.

Nevertheless, it's worth to mention that there are people who agure that this pain can be actually helpful. For example, Scott Wlaschin in his article Functional approaches to dependency injection:

The downside of course, is that there are now five extra parameters for the function, which looks painful. (Of course, the equivalent method in the OO version also had these five dependencies, but they were implicit).

In my opinion though, this pain is actually helpful! With OO style interfaces, there is a natural tendency for them to accrete crud over time. But with explicit parameters like this, there is a natural disincentive to have too many dependencies! The need for a guideline such as the Interface Segregation Principle is much diminished.

Also, Mark Seemann -- the author of the book Dependency Injection -- had an interesting series on Dependency Rejection.

In case you cannot suffer that pain, then just break the CQS and back to the traditional implementation of Stack. After all, if a function (like pop/dequeue) is well-known and well-aware that it both returns something and changes its internal data, a violation of CQS is not so bad.

Even in this case, some FP languages offer a message-passing mechanism so that you can implement a mutable Stack in a manner that you don't write code mutating data (e.g., code using assignment symbol). MailboxProcessor in F# is such a mechanism.

Hope this helps :)

It is because of the design of the function, you need to return a state which reflects the context.

This allows you to differentiate between success and failure as well as potentially other information if you supplement bool with a DequeueResult in the following minimal party code.

Let Dequeue = function bool(Result)

If Head == Null return
...
Return true

Something more inline with CQS might be

Let Dequeue = function Node()
Return Head

But would require Head to have a special value of Node.Null to try my differentiate between failures and contention.

Returning a DequeueResult may be better where you can indicate in the result more about the failure.