Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
Листинг 18.1. Базовая функциональная очередь class Queue[T]( private val leading: List[T], private val trailing: List[T] ): private def mirror = if leading.isEmpty then new Queue(trailing.reverse, Nil) 18 .1 . Функциональные очереди 391 else this def head = mirror.leading.head def tail = val q = mirror new Queue(q.leading.tail, q.trailing) def enqueue(x: T) = new Queue(leading, x :: trailing) Какова вычислительная сложность этой реализации очереди? Операция mirror может занять время, пропорциональное количеству элементов очере ди, но только при условии, что список leading пуст. Если же нет, то возврат из метода происходит немедленно. Поскольку head и tail вызывают mirror , то их вычислительная сложность также может иметь линейную зависимость от размера очереди. Но чем длиннее становится очередь, тем реже вызыва ется mirror И действительно, допустим, есть очередь длиной n с пустым списком leading Тогда операции mirror придется скопировать в обратном порядке список длиной n. Однако следующий раз, когда операции mirror придется делать чтолибо, наступит только по опустошении списка leading , что произойдет после n операций tail . То есть вы можете расплатиться за каждую из этих n операций tail одной nной от вычислительной сложности операции mirror , что означает постоянный объем работы. При условии, что операции head , tail и enqueue используются примерно с одинаковой частотой, амортизиро- ванная вычислительная сложность является, таким образом, константой для каждой операции. Следовательно, функциональные очереди асимптотически так же эффективны, как и изменяемые очереди. Но этот аргумент следует сопроводить некоторыми оговорками. Вопервых, речь шла только об асимптотическом поведении, а постоянно действующие факторы могут несколько различаться. Вовторых, аргумент основывается на том, что операции head , tail и enqueue вызываются с примерно одинако вой частотой. Если операция head вызывается намного чаще, чем остальные две, то данный аргумент утратит силу, поскольку каждый вызов head может повлечь за собой весьма затратную реорганизацию списка с помощью опера ции mirror . Негативных последствий, названных во второй оговорке, можно избежать, поскольку есть возможность сконструировать функциональные очереди таким образом, что в последовательности операций head реоргани зация потребуется только для первой из них. Как это делается, мы покажем в конце главы. 392 Глава 18 • Параметризация типов 18 .2 . Сокрытие информации Теперь по эффективности реализация класса Queue , показанная в листин ге 18.1, нас вполне устраивает. Конечно, вы можете возразить, что за эту эффективность пришлось расплачиваться неоправданно подробной детализа цией. Глобально доступный конструктор Queue получает в качестве параметров два списка, в одном из которых элементы следуют в обратном порядке, что вряд ли совпадает с интуитивным представлением об очереди. Нам нужен способ, позволяющий скрыть этот конструктор от кода клиента. Некоторые способы решения данной задачи на Scala мы покажем в текущем разделе. Приватные конструкторы и фабричные методы В Java конструктор можно скрыть, объявив его приватным. В Scala первич ный конструктор не имеет явно указываемого определения — подразумевает ся, что он автоматически определяется с параметрами и телом класса. Тем не менее, как показано в листинге 18.2, скрыть первичный конструктор можно, добавив перед списком параметров класса модификатор private Листинг 18.2. Сокрытие первичного конструктора путем превращения его в приватный class Queue[T] private ( private val leading: List[T], private val trailing: List[T] ) Модификатор private , указанный между именем класса и его параметрами, служит признаком того, что конструктор класса Queue является приватным: доступ к нему можно получить только изнутри самого класса и из его объ ектакомпаньона. Имя класса Queue попрежнему остается публичным, поэтому вы можете использовать его в качестве типа, но не можете вызвать его конструктор: scala> Queue(List(1, 2), List(3)) 1 |Queue(List(1, 2), List(3)) |ˆˆˆˆˆ |constructor Queue cannot be accessed as a member of |Queue from module class rs$line$4$. Теперь, когда первичный конструктор класса Queue уже не может быть вы зван из кода клиента, нужен какойто другой способ создания новых очере дей. Одна из возможностей — добавить вспомогательный конструктор: def this() = this(Nil, Nil) 18 .2 . Сокрытие информации 393 Этот конструктор, показанный в предыдущем примере, создает пустую оче редь. В качестве уточнения он может получать список исходных элементов очереди: def this(elems: T*) = this(elems.toList, Nil) Следует напомнить, что в соответствии с описанием из раздела 8.8 T* — фор ма запи си для повторяющихся параметров. Еще одна возможность состоит в добавлении фабричного метода, созда ющего очередь из последовательности исходных элементов. Прямой путь сделать это — определить объект Queue , который имеет такое же имя, как и определяемый класс, и, как показано в листинге 18.3, содержит метод apply Листинг 18.3. Фабричный метод apply в объекте-компаньоне object Queue: // создает очередь с исходными элементами xs def apply[T](xs: T*) = new Queue[T](xs.toList, Nil) Помещая этот объект в тот же самый исходный файл, в котором находится определение класса Queue , вы превращаете объект в объекткомпаньон это го класса. В разделе 12.5 было показано: объекткомпаньон имеет такие же права доступа, что и его класс. Поэтому метод apply в объекте Queue может создать новый объект Queue , несмотря на то что конструктор класса Queue является приватным. Обратите внимание: по причине вызова фабричным методом метода apply клиенты могут создавать очереди с помощью выражений вида Queue(1, 2, 3) Данное выражение разворачивается в Queue.apply(1, 2, 3) , поскольку Queue — объект, заменяющий функцию. В результате этого клиенты видят Queue в качестве глобально определенного фабричного метода. На самом же деле в Scala нет методов с глобальной областью видимости, поскольку каж дый метод должен быть заключен в объект, класс или пакет. Но, используя методы по имени apply внутри глобальных объектов, вы можете поддержи вать схемы, похожие на вызов глобальных методов. Альтернативный вариант: приватные классы Приватные конструкторы и приватные члены класса — всего лишь один из способов скрыть инициализацию и представить класс. Еще один более ради кальный способ — сокрытие самого класса и экспорт только трейта, показы вающего публичный интерфейс класса. Код реализации такой конструкции 394 Глава 18 • Параметризация типов представлен в листинге 18.4. В нем показан трейт Queue , в котором объявля ются методы head , tail и enqueue . Все три метода реализованы в подклассе QueueImpl , который является приватным подклассом внутри класса объекта Queue . Тем самым клиентам открывается доступ к той же информации, что и раньше, но с помощью другого приема. Вместо сокрытия отдельно взятых конструкторов и методов в этой версии скрывается весь реализующий оче реди класс. Листинг 18.4. Абстракция типа для функциональных очередей trait Queue[T]: def head: T def tail: Queue[T] def enqueue(x: T): Queue[T] object Queue: def apply[T](xs: T*): Queue[T] = QueueImpl[T](xs.toList, Nil) private class QueueImpl[T]( private val leading: List[T], private val trailing: List[T] ) extends Queue[T]: def mirror = if leading.isEmpty then QueueImpl(trailing.reverse, Nil) else this def head: T = mirror.leading.head def tail: QueueImpl[T] = val q = mirror QueueImpl(q.leading.tail, q.trailing) def enqueue(x: T) = QueueImpl(leading, x :: trailing) 18 .3 . Аннотации вариантности Элемент Queue согласно определению в листинге 18.4 — трейт, но не тип, поскольку получает параметр типа 1 . В результате вы не можете создавать переменные типа Queue : 1 Queue можно считать типом более высокого рода. 18 .3 . Аннотации вариантности 395 scala> def doesNotCompile(q: Queue) = {} 1 |def doesNotCompile(q: Queue) = {} | ˆˆˆˆˆ | Missing type parameter for Queue Вместо этого Queue позволяет указывать параметризованные типы, такие как Queue[String] , Queue[Int] или Queue[AnyRef] : scala> def doesCompile(q: Queue[AnyRef]) = {} def doesCompile: (q: Queue[AnyRef]): Unit Таким образом, Queue — трейт, а Queue[String] — тип. Queue также называ ют конструктором типа, поскольку вы можете сконструировать тип с его участием, указав параметр типа. (Это аналогично конструированию экзем пляра объекта с использованием самого обычного конструктора с указанием параметра значения.) Конструктор типа Queue генерирует семейство типов, включающее Queue[Int] , Queue[String] и Queue[AnyRef] Можно также сказать, что Queue — обобщенный трейт. (Классы и трейты, которые получают параметры типа, являются обобщенными, а вот типы, генерируемые ими, являются параметризованными, а не обобщенными.) По нятие «обобщенный» означает, что вы определяете множество конкретных типов, используя один обобщенно написанный класс или трейт. Например, трейт Queue в листинге 18.4 определяет обобщенную очередь. Конкретными очередями будут Queue[Int] , Queue[String] и т. д. Сочетание параметров типа и системы подтипов вызывает ряд интересных вопросов. Например, существуют ли какието особые подтиповые отноше ния между членами семейства типов, генерируемого Queue[T] ? Конкретнее говоря, следует ли рассматривать Queue[String] как подтип Queue[AnyRef] ? Или в более широком смысле: если S — подтип T , то следует ли рассматривать Queue[S] как подтип Queue[T] ? Если да, то можно сказать, что трейт Queue ковариантный (или гибкий) в своем параметре типа T . Или же, поскольку у него всего один параметр типа, можно просто сказать, что Queue очереди ковариантны. Такая ковариантность Queue будет означать, к примеру, что вы можете передать Queue[String] ранее показанному методу doesCompile , который принимает параметр значения типа Queue[AnyRef] Интуитивно все это выглядит хорошо, поскольку очередь из String элементов похожа на частный случай очереди из AnyRef элементов. Но в Scala у обобщен ных типов изначально имеется нонвариантная (или жесткая) подтипизация. То есть при использовании трейта Queue , определенного в показанном выше листинге 18.4, очереди с различными типами элементов никогда не будут состоять в подтиповых отношениях. Queue[String] не будет использоваться 396 Глава 18 • Параметризация типов как Queue[AnyRef] . Но получить ковариантность (гибкость) подтипизации очередей можно следующим изменением первой строчки трейта Queue : trait Queue[+T] { ... } Указанный знак плюс ( + ) в качестве префикса формального параметра типа показывает, что подтипизация в этом параметре ковариантна (гибка). Добавляя этот единственный знак, вы сообщаете Scala о необходимости, к примеру, рассматривать тип Queue[String] как подтип Queue[AnyRef] Компилятор проверит факт определения Queue в соответствии со способом, предполагаемым подобной подтипизацией. Помимо префикса + , существует префикс - , который показывает контрава- риантность подтипизации. Если определение Queue имеет вид trait Queue[-T] { ... } и если тип T — подтип типа S , то это будет означать, что Queue[S] — под тип Queue[T] (что в случае с очередями было бы довольно неожиданно!). Ковариантность, контравариантность или нонвариантость параметра типа называются вариантностью параметров. Знаки + и - , которые могут разме щаться рядом с параметрами типа, называются аннотациями вариантности. В чисто функциональном мире многие типы по своей природе ковариантны (гибки). Но ситуация становится иной, как только появляются изменяемые данные. Чтобы выяснить, почему так происходит, рассмотрим показанный в ли стинге 18.5 простой тип одноэлементных ячеек, допускающих чтение и запись. Листинг 18.5. Нонвариантный (жесткий) класс Cell class Cell[T](init: T): private var current = init def get = current def set(x: T) = current = x Показанный здесь тип Cell объявлен нонвариантным (жестким). Ради аргументации представим на время, что Cell был объявлен ковариантным, то есть был объявлен класс Cell[+T] , и этот код передан компилятору Scala. (Этого делать не стоит, и скоро мы объясним почему.) Значит, можно скон струировать следующую проблематичную последовательность инструкций: val c1 = new Cell[String]("abc") val c2: Cell[Any] = c1 c2.set(1) val s: String = c1.get 18 .3 . Аннотации вариантности 397 Если рассмотреть строки по отдельности, то все они выглядят вполне нор мально. В первой строке создается строковая ячейка, которая сохраняется в val переменной по имени c1 . Во второй строке определяется новая val переменная c2 , имеющая тип Cell[Any] , которая инициализируется значе нием переменной c1 . Кажется, все в порядке, поскольку экземпляры класса Cell считаются ковариантными. В третьей строке для c2 устанавливается значение 1 . С этим тоже все в порядке, так как присваиваемое значение 1 — экземпляр, относящийся к объявленному для c2 типу элемента Any . И на конец, в последней строке значение элемента c1 присваивается строковой переменной. Здесь нет ничего странного, поскольку с обеих сторон выраже ния находятся значения одного и того же типа. Но если взять все в совокуп ности, то эти четыре строки в конечном счете присваивают целочисленное значение 1 строковому значению s . Это явное нарушение целостности типа. Какая из операций вызывает сбой в ходе выполнения кода? Видимо, вторая, в которой используется ковариантная подтипизация. Все другие операции слишком простые и базовые. Стало быть, ячейка Cell , хранящая значение типа String , не является также ячейкой Cell , хранящей значение типа Any , поскольку есть вещи, которые можно делать с Cell из Any , но нельзя делать с Cell из String . К примеру, в отношении Cell из String нельзя использовать set с Int аргументом. Получается, если передать ковариантную версию Cell компилятору Scala, то будет выдана ошибка компиляции: 4 | def set(x: T) = | ˆˆˆˆ | covariant type T occurs in contravariant position | in type T of value x Вариантность и массивы Интересно сравнить данное поведение с массивами в Java. В принципе, массивы подобны ячейкам, за исключением того, что могут иметь несколько элементов. При этом массивы в Java считаются ковариантными. Пример, аналогичный работе с ячейкой, можно проверить в работе с масси вами Java: // Это код Java String[] a1 = { "abc" }; Object[] a2 = a1; a2[0] = new Integer(17); String s = a1[0]; 398 Глава 18 • Параметризация типов Если запустить данный пример, то окажется, что он пройдет компиляцию. Но в ходе выполнения, когда элементу a2[0] будет присваиваться значение Integer , программа сгенерирует исключение ArrayStore : Exception in thread "main" java.lang.ArrayStoreException: java.lang.Integer at JavaArrays.main(JavaArrays.java:8) Дело в том, что в Java сохраняется тип элемента массива во время выпол нения программы. При каждом обновлении элемента массива новое зна чение элемента проверяется на принадлежность к сохраненному типу. Если оно не является экземпляром этого типа, то выдается исключение ArrayStore Может возникнуть вопрос: а почему в Java принята такая на вид небезопас ная и затратная конструкция? Отвечая на данный вопрос, Джеймс Гослинг (James Gosling), основной изобретатель языка Java, говорил, что создатели хотели получить простые средства обобщенной обработки массивов. На пример, им хотелось получить возможность писать метод сортировки всех элементов массива с использованием следующей сигнатуры, которая полу чает массив из Object элементов: void sort(Object[] a, Comparator cmp) { ... } Ковариантность массивов требовалась для того, чтобы этому методу сорти ровки можно было передавать массивы произвольных ссылочных типов. Разумеется, после появления в Java обобщенных типов (дженериков) подоб ный метод сортировки уже мог быть написан с параметрами типа, поэтому необходимость в ковариантности массивов отпала. Сохранение ее до наших дней обусловлено соображениями совместимости. Scala старается быть чище, чем Java, и не считает массивы ковариантными. Вот что получится, если перевести первые две строки кода примера с мас сивом на язык Scala: scala> val a1 = Array("abc") val a1: Array[String] = Array(abc) scala> val a2: Array[Any] = a1 1 |val a2: Array[Any] = a1 | ˆˆ | Found: (a1 : Array[String]) | Required: Array[Any] В данном случае получилось, что Scala считает массивы нонвариантными (жесткими), следовательно, Array[String] не считается соответствующим 18 .4 . Проверка аннотаций вариантности 399 Array[Any] . Но иногда необходимо организовать взаимодействие между име ющимися в Java устаревшими методами, которые используют в качестве сред ства эмуляции обобщенного массива Object массив. Например, может воз никнуть потребность вызвать метод сортировки наподобие того, который был рассмотрен ранее в отношении String массива, передаваемого в качестве аргу мента. Чтобы допустить такую возможность, Scala позволяет выполнять приве дение массива из элементов типа T к массиву элементов любого из супертипов T : val a2: Array[Object] = a1.asInstanceOf[Array[Object]] Приведение типов во время компиляции не вызывает никаких возражений и всегда будет успешно работать во время выполнения программы, по скольку положенная в основу работы JVMмодель времени выполнения рассматривает массивы в качестве ковариантных точно так же, как это де лается в языке Java. Но впоследствии, как и на Java, может быть получено исключение ArrayStore 18 .4 . Проверка аннотаций вариантности Рассмотрев несколько примеров ненадежности вариантности, можно задать вопрос: какие именно определения классов следует отвергать, а какие — при нимать? До сих пор во всех нарушениях целостности типов фигурировали переназначаемые поля или элементы массивов. В то же время чисто функ циональная реализация очередей представляется хорошим кандидатом на ковариантность. Но в следующем примере показано, что ситуацию нена дежности можно подстроить даже при отсутствии переназначаемого поля. Чтобы выстроить пример, предположим: очереди из показанного выше листинга 18.4 определены как ковариантные. Затем создадим подкласс оче редей с указанным типом Int и переопределим метод enqueue : class StrangeIntQueue extends Queue[Int]: override def enqueue(x: Int) = println(math.sqrt(x)) super.enqueue(x) Перед выполнением добавления метод enqueue в подклассе StrangeIntQueue выводит на стандартное устройство квадратный корень из своего (целочис ленного) аргумента. Теперь можно создать контрпример из двух строк кода: val x: Queue[Any] = new StrangeIntQueue x.enqueue("abc") |