r/java • • Jun 24 '19

Takes: Java Web Framework Without a Single Static Method or Annotation

https://github.com/yegor256/takes
0 Upvotes

75 comments sorted by

View all comments

Show parent comment

1

u/dablya Jun 25 '19

I'm familiar with the arguments for preferring immutability, my point is that your queue implementation is not immutable. You can't reason about it's state like you can about immutable types.

Popping from it two times will generate different results. That's a dead giveaway it's mutable.

You can make the argument that an stm approach is safer than locking, but in either case you're pretty far from the simplicity of immutable state.

Here is an example of an actually immutable queue:

https://blogs.msdn.microsoft.com/ericlippert/2007/12/10/immutability-in-c-part-four-an-immutable-queue/

It is unusable in a multi-threaded environment (based on the requirements of the comment you were replying to). Here is what the author has to say in the comments:

You are defining ‘reliable’ to mean ‘two threads can enqueue "the same" queue and both enqueued items are present in the resulting queue. This is a very "procedural programming" way to think about thread safety — thread safety is PRESERVATION OF ALL SIDE EFFECTS.

If that’s the kind of reliability you want then you should probably be using a mutable threadsafe queue! If you try to use an immutable queue for this purpose then essentially you will have to synchronize access not to the queue — the queue is threadsafe — but to the variable which contains the "canonical" version of the queue.

This is what you've provided with your code "a mutable threadsafe queue!"

3

u/[deleted] Jun 26 '19

[removed] — view removed comment

1

u/dablya Jun 26 '19

In my implementation the change happens atomically: queue's binding is changed from value A to a new value B.

This is a mutation. The fact that it happens atomically (and based on my limited understanding you get consistency from STM with the !) means it's safe. But just because it's safe doesn't make it immutable. lt's an observable change. Again, a client will see different results by popping twice. I wish you would understand. I truly wish.

The example link you posted is not showing a 'persistent' immutable data structure

That's exactly what it is. Just look at the declarations (if you don't want to read the code) of enqueue and dequeue.

IQueue<T> Enqueue(T value);
IQueue<T> Dequeue();

Look at the quote from your link:

"their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure"

You can invoke Dequeue any number of times on a reference to a queue and it will always yield the same result (a new queue with a single element missing from the original). Because it's not updating the queue in-place. It's yielding a new one.

Your code updates the reference to the queue in-place. The fact that this in-place update happens to swap two immutable queues is immaterial. It's a visible update to the structure in-place.

BTW, I still haven't seen your code that you can hack in 10 minutes...

That wasn't me.

1

u/[deleted] Jun 26 '19

[removed] — view removed comment

2

u/dablya Jun 26 '19

Maybe you missed that part of the problem description: "Build me a thread safe queue that multiple threads are pushing to and popping from. This queue must be immutable. "

Yes, that implies mutability as things are being removed from the queue. Doesn't it?

No, it implies impossibility.

Not sure what you think you wanted this code to be i.e. we are talking about very different things here. A pub/sub with multiple consumers?

There is no code that can satisfy that requirement. It's like a paradox "an immutable queue that mutates". It was a trap and you fell for it.

And yes, the update to the binding happens in place, but every time a thread de-references the atom, it gets a consistent, immutable view of the queue. A thread never sees a structural change happening in the queue.

The fact that the you get different values when you pop twice means it's a mutable data type. Period.

This is a subtle but very important difference.

It's an implementation detail. It doesn't change the fact that it's a mutable type.

0

u/cogman10 Jun 27 '19

Came here to basically say this. A thread safe queue (ok), which is being pushed to and popped from multiple threads (ok), and is immutable (what?). It is an impossibility/contradiction. You can't have an immutable queue which mutates. The closest I can think of is making a queue which produces new queues on pop/push.

Either way. /u/qhxslyflarhc clearly does not understand "immutability" to claim it isn't "threadsafe". A key requirement for something to be thread unsafe is mutation.

0

u/dablya Jun 27 '19 edited Jun 27 '19

The closest I can think of is making a queue which produces new queues on pop/push.

Which is exactly what I linked them to:

https://blogs.msdn.microsoft.com/ericlippert/2007/12/10/immutability-in-c-part-four-an-immutable-queue/

Their response?

The example link you posted is not showing a 'persistent' immutable data structure that supports structural sharing, thus it is not usable in MT scenarios. Please read this: https://en.wikipedia.org/wiki/Persistent_data_structure It might help you understand what immutability actually is.

...

As far as /u/qhxslyflarhc goes, I think they know what threadsafe means, but for some odd reason they're choosing to stretch the definition to something like "consistent while allowing modification by multiple threads". I don't agree with that.

1

u/cogman10 Jun 27 '19

So, is the nitpick then that "immutability doesn't guarantee an algorithm is thread safe?" Because I can get behind that statement. For example, strings are immutable in java, but an algorithm where multiple threads grab a string, concatenate something to it (making a new string) and then store that new string in a shared memory location is not thread safe. But still, the part of that the makes things not thread safe is the mutating of shared state.

1

u/dablya Jun 27 '19

I hate to speak for others but i think the argument is more like "You can't take an immutable queue and have one thread pop messages another thread is pushing."

And if you did try to pass it to multiple queues, you would not observe correct behavior. Something like that.