Functional Queue From Programming In Scala

Question

I'm going through Programming In Scala 2nd Edition by Odersky, Spoon, and Venners, and this example threw me for a loop since it seemed to go against what I thought was true about functional programming and immutability. In the example (and earlier in the book in Ch. 18), the authors claim that operations on an object can still be "purely functional" even when those operations might internally mutate the state of the object. The example, which is on p.442, Ch. 19, is this:

 class Queue[+T] private (
   private[this] var leading: List[T], 
   private[this] var trailing: List[T]
 ) {

   private def mirror() = 
     if (leading.isEmpty) {
       while (!trailing.isEmpty) {
         leading = trailing.head :: leading
         trailing = trailing.tail
       }
     }

   def head: T = { 
     mirror()
     leading.head 
   }

   def tail: Queue[T] = { 
     mirror()
     new Queue(leading.tail, trailing) 
   }

   def enqueue[U >: T](x: U) = 
     new Queue[U](leading, x :: trailing)
 }

The justification given is that, so long as it side effects are not visible to clients, something like this can be considered functional. I guess I can get behind that...I mean strictly speaking that's what defines a function. But admittedly (and I'm not really too savvy about what the JVM memory model guarantees), but aren't there potential problems with that in this code?

For instance, if two threads are running operations on this queue, which looks like this to start:

Leading: Nil
Trailing: List(1,2,3,4)

Isn't it possible that one thread could call head() getting to this point in mirror() before being descheduled:

private def mirror() = 
     if (leading.isEmpty) {
       while (!trailing.isEmpty) {
         leading = trailing.head :: leading
         > trailing = trailing.tail
       }
     }

At which point the queue looks like this:

Leading: List(1)
Trailing: List(1,2,3,4)

And when a second thread calls tail() while the first is not active, this would be returned:

Leading: Nil
Trailing: List(1,2,3,4)

Whereas if the first thread's head() call were to finish, this would be returned after a subsequent tail() call on that list:

Leading: List(2,3,4)
Trailing: Nil

I'm admittedly not great at this kind of stuff and concurrent programming is really mindbending for me, as I'm sure it is for a lot of people, I'm just curious what I'm missing here.

Answer 1

You're correct: functional-looking code can be rendered non-functional when used by multiple threads if it uses internal state as part of its implementation. You can fix this by synchronizing every method that touches the mutable variables (i.e. with a synchronized block). Unfortunately, this is not ideal for performance, which is why in a threaded application functional implementations are often preferred.