Функциональная очередь из программирования в Scala - PullRequest
Новая
       31

Функциональная очередь из программирования в Scala

8 голосов
/ 03 сентября 2011

Я прохожу программирование в Scala 2nd Edition от Odersky, Spoon и Venners, и этот пример бросил меня в тупик, так как казалось, что он идет вразрез с тем, что я считаю верным в отношении функционального программирования и неизменности. В этом примере (и ранее в книге в гл. 18) авторы утверждают, что операции над объектом все еще могут быть «чисто функциональными», даже если эти операции могут внутренне изменять состояние объекта. Пример, который находится на стр.442, гл. 19, это: 

 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)
 }

Приведено обоснование, что, пока его побочные эффекты не видны клиентам, нечто подобное можно считать функциональным. Я полагаю, я могу отойти от этого ... Я имею в виду, строго говоря, это то, что определяет функцию. Но по общему признанию (и я действительно не слишком разбираюсь в том, что гарантирует модель памяти JVM), но нет ли потенциальных проблем с этим в этом коде?

Например, если два потока выполняют операции в этой очереди, что выглядит следующим образом: 

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

Разве не возможно, чтобы один поток мог вызвать head (), чтобы добраться до этой точки в mirror () до того, как его отменили: 

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

В этот момент очередь выглядит следующим образом: 

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

И когда второй поток вызывает tail (), а первый не активен, это будет возвращено: 

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

Принимая во внимание, что если вызов head () первого потока завершится, он будет возвращен после последующего вызова tail () в этом списке: 

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

По общему признанию, я не очень хорош в подобных вещах, и параллельное программирование действительно потрясает меня, так как я уверен, что это для многих людей, мне просто любопытно, чего мне здесь не хватает.

1 Ответ

3 голосов
/ 03 сентября 2011

Вы правы: функционально выглядящий код может оказаться не функциональным при использовании несколькими потоками, если он использует внутреннее состояние как часть своей реализации. Вы можете исправить это, синхронизируя каждый метод, который касается изменяемых переменных (то есть с блоком synchronized). К сожалению, это не идеально для производительности, поэтому в многопоточных приложениях часто предпочтительны функциональные реализации.

...