Здесь ведется перевод книги Martin’а Odersky Scala by examples, которая описывает основные приемы программирования на языке Scala^↑. Присоединяйтесь!

Введение

Scala изящно объединяет объектно-ориентированное и функциональное программирование. Этот язык спроектирован для выражения привычных паттернов программирования кратко, красиво и безопасно по типам. Scala вводит несколько инновационных языковых конструктов. Например:

абстрактные типы и примеси объединяют концепты объектных и модульных систем;
сопоставление с образцом на иерархии классов объединяет функциональный и объектно-ориентированный доступ к данным (это очень упрощает обработку XML деревьев);
гибкие синтаксис и система типов позволяют конструировать продвинутые библиотеки и новые доменно-специфичные языки.

В то же время, язык Scala совместим с Java. Можно использовать Java-библиотеки и фреймворки без связывающего кода и дополнительных деклараций.

Эта книга представляет Scala неформально, на примерах.

Главы 2 и 3 обращают внимание на некоторые возможности, из-за которых Scala особенно интересен. Последующие главы представляют конструкты языка более подробно, начиная с простых выражений и функций, через объекты и классы, списки и потоки, изменяемые состояния, сопоставление с образцом, к более сложным примерам, иллюстрирующим интересные приемы программирования. Это неформальное изложение должно быть дополнено документом Scala Language Reference Manual, который специфицирует Scala более точно и детально.

Замечание. Мы в огромном долгу у чудесной книги Абельсона и Сассмана, «Структура и интерпретация компьютерных программ». Многие примеры и упражнения оттуда также приведены здесь. Конечно, рабочий язык в каждом случае был изменен с Scheme на Scala. Кроме того, в примерах использованы объектно-ориентированные конструкты Scala, где это уместно.

Первый пример

В качестве первого примера рассмотрим быструю сортировку.

def sort(xs: Array[Int]) {
  def swap(i: Int, j: Int) {
    val t = xs(i);
    xs(i) = xs(j);
    xs(j) = t
  }
  def sort1(l: Int, r: Int) {
    val pivot = xs((l + r) / 2)
    var i = l;
    var j = r
    while (i <= j) {
      while (xs(i) < pivot) i += 1
      while (xs(j) > pivot) j -= 1
      if (i <= j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }
    if (l < j) sort1(l, j)
    if (j < r) sort1(i, r)
  }
  sort1(0, xs.length - 1)
}

Код очень похож на Java или С программу. Мы используем те же операторы и похожие управляющие конструкции. Есть также немного синтаксических отличий. В частности,

Определения всегда начинаются с зарезервированного слова. Определение функций начинается c def, задание переменных начинается с var, а определение значений (то есть переменных только для чтения) — с val.
Тип идентификатора объявляется через двоеточие после идентификатора. Задание типа часто можно опускать, поскольку компилятор способен выводить его из контекста.
Типы массивов записываются как Array[T] вместо T[], а выборка из массива как a(i) вместо a[i].
Функции могут быть вложены в другие функции. Вложенные функции имеют доступ к параметрам и локальным переменным внешних функций. Например, массив xs является видимым для функций swap и sort1, а значит, его не требуется передавать как параметр.

Пока что Scala представляется довольно обычным языком с некоторыми синтаксическими странностями. На самом деле, на Scala можно писать программы в обычном императивном или объектно-ориентированном стиле. Это важно, потому что облегчает объединение Scala-компонент с кодом, написанным на таких популярных языках, как Java, C# или Visual Basic.

Но можно писать программы, которые будут выглядеть совершенно иначе. Вот снова быстрая сортировка, на этот раз написанная в функциональном стиле.

def sort(xs: Array[Int]): Array[Int] = {
  if (xs.length <= 1) xs
  else {
    val pivot = xs(xs.length / 2)
    Array.concat(
      sort(xs filter (pivot >)),
      xs filter (pivot ==),
      sort(xs filter (pivot <)))
  }
}

Функциональная программа кратко и точно передает сущность алгоритма быстрой сортировки:

Если массив пуст или состоит из одного элемента, то он уже отсортирован.
Если массив не пуст, выбираем средний элемент как разделитель.
Разбиваем массив на три подмассива, содержащие, соответственно, элементы, меньшие разделителя, элементы, равные разделителю, и элементы, большие его.
Сортируем подмассивы с помощью рекурсивного вызова функции sort. (Это не совсем то, что делает императивная версия. Там массив разбивается на массив элементов, меньших разделителя, и массив элементов, больших или равных ему.)
После склеивания всех подмассивов возвращаем результат.

Обе реализации, и императивная, и функциональная, имеют одинаковую асимптотическую сложность — O(N log (N)) в среднем и O(N²) в худшем случае. Но если императивная версия непосредственно оперирует элементами массива, используя прямую адресацию, то функциональная при каждом рекурсивном вызове возвращает новый отсортированный массив, оставляя без изменения массив, переданный как аргумент. Следовательно, функциональная реализация требует больше памяти для выполнения.

Функциональная реализация создает впечатление, что Scala это специализированный язык для функциональных операций на массивах. На самом деле все операции, использовавшиеся в примере, это просто библиотечные методы класса последовательности Seq[T] из стандартной библиотеки Scala, которая сама реализована на Scala. Поскольку массивы — это экземпляры класса Seq, все его методы доступны им.

В частности, метод filter, который принимает в качестве аргумента предикатную функцию. Предикатная функция должна переводить элементы массива в булевские значения. Результат выполнения filter — массив, состоящий из тех элементов исходного массива, которые удовлетворяют предикату, то есть на которых предикатная функция возвращает true. Метод filter класса Array[T], следовательно, имеет сигнатуру

def filter(p: T => Boolean): Array[T]

Здесь T => Boolean — запись типа функции, принимающей аргумент типа T и возвращающей булево значение. Функции, подобные filter, то есть принимающие другую функцию как аргумент или возвращающие функцию как результат, называются функциями высшего порядка.

Scala не различает идентификаторы и имена операторов. Идентификатором может быть последовательность букв или цифр, начинающаяся с буквы, или это может быть последовательность специальных символов, таких как +, *, или :. Любой идентификатор может использоваться как инфиксный оператор. Бинарная операция E op E всегда интерпретируется как вызов метода E.op(E'). Это верно также для бинарных инфиксных операторов, которые начинаются с буквы. Следовательно, выражение xs filter (pivot >) равнозначно вызову метода xs.filter(pivot >).

В программе быстрой сортировки filter трижды применяется к анонимной функции. Первый аргумент, pivot >, представляет функцию, принимающую аргумент x и возвращающую значение выражения pivot > x. Это пример частично примененной функции. Другой эквивалентный способ записать эту функцию, который явно указывает аргумент, это x => pivot > x. Эта функция анонимна, то есть, ее имя не определено. Тип параметра x опущен, поскольку компилятор Scala может автоматически вывести его из контекста, в котором используется функция. Подытоживая, скажем, что xs.filter(pivot >) возвращает список из всех элементов xs, которые меньше, чем pivot.

Взглянув снова на первую, императивную реализацию быстрой сортировки, мы увидим там многие языковые конструкты из второго решения, хотя и в замаскированной форме.

Например, «обычные» бинарные операторы, такие как +, - или <, не рассматриваются специальным образом. Как и append, они являются методами своих левых операндов. Следовательно, выражение i + 1 рассматривается как вызов i.+(1) метода + на целом числе. Конечно, компилятор может (если он достаточно умный) распознать специальный случай вызова метода + на целочисленных аргументах и сгенерировать эффективный встраиваемый код для него.

Для эффективности и лучшего обнаружения ошибок цикл while представлен в Scala как примитивная конструкция языка. Но, в принципе, его можно было бы вынести в библиотеку, оформив как функцию. Вот возможная реализация:

def While(p: => Boolean)(s: => Unit) {
  if (p) {
    s; While(p)(s)
  }
}

Функция While принимает первым параметром функцию проверки, которая не имеет аргументов, и возвращает булево значение. Второй параметр это командная функция, которая также не имеет аргументов и возвращает результат типа Unit. While вызывает командную функцию до тех пор, пока предикатная функция возвращает true.

Тип Unit в Scala, грубо говоря, соответствует void в Java; он используется всякий раз, когда функция не возвращает какого-либо интересного значения. На самом деле, поскольку Scala это язык, ориентированный на выражения, каждая функция возвращает некоторый результат. Если нет явно заданного выражения, то предполагается значение по умолчанию, () (произносится «unit»). Это значение имеет тип Unit. Функции, возвращающие Unit, также называются процедурами. Вот более «ориентированная на выражения» формулировка функции swap из первой реализации быстрой сортировки, которая выражает это явно:

def swap(i: Int, j: Int) {
  val t = xs(i);
  xs(i) = xs(j);
  xs(j) = t
  ()
}

Результат этой функции — просто ее последнее выражение, при этом ключевое слово return указывать не обязательно. Обратите внимание, что для функций, возвращающих явное значение, всегда необходимо cтавить '=' перед их телом или определяющим выражением.

Программирование с акторами и сообщениями

Вот пример, который демонстрирует область применения, для которой Scala особенно хорошо подходит. Рассмотрим задачу по созданию электронного аукциона. Для реализации участников аукциона мы используем модель акторных процессов в Erlang-стиле. Акторы — это объекты, которым посылаются сообщения. У каждого актора есть «почтовый ящик» для поступающих сообщений, который представлен очередью. Сообщения в очереди могут обрабатываться или в последовательном порядке, или выборочно, как удовлетворяющие некоторому образцу.

Для каждого лота есть актор-аукционщик, который публикует информацию о лоте, принимает предложения от участников и общается с продавцом лота и победившим покупателем для завершения сделки.

Первым делом, мы определим сообщения, которые передаются во время аукциона. Есть два абстрактных базовых класса, AuctionMessage для сообщений от клиентов к сервису аукциона, и AuctionReply для ответов сервиса клиентам. Для обоих базовых классов существует набор вариаций, как это определено в листинге 3.1.

Вариации классов (case classes) определяют формат конкретных сообщений. Эти сообщения могли бы отображаться в небольших XML документах. Мы ожидаем, что существуют автоматические инструментальные средства для преобразований между XML документами и внутренними структурами данных, такими, как определенные выше.

// 3.1: Классы сообщений для аукциона.

import scala.actors.Actor

abstract class AuctionMessage
case class Offer(bid: Int, client: Actor) extends AuctionMessage
case class Inquire(client: Actor) extends AuctionMessage

abstract class AuctionReply
case class Status(asked: Int, expire: Date) extends AuctionReply
case object BestOffer extends AuctionReply
case class BeatenOffer(maxBid: Int) extends AuctionReply

case class AuctionConcluded(seller: Actor, client: Actor) extends AuctionReply
case object AuctionFailed extends AuctionReply
case object AuctionOver extends AuctionReply

Листинг 3.2 представляет реализацию на Scala класса Auction для акторов, координирующих предложение цен по лоту. Объекты этого класса создаются с указанием

актора продавца, который должен быть извещен о завершении торгов,
минимальной цены,
даты завершения аукциона.

Ход торгов определен методом act. Этот метод периодически отбирает (используя метод receiveWithin) поступающие сообщения и реагирует на них, пока аукцион не будет закрыт, что сигнализируется сообщением TIMEOUT. Перед завершением актор остается активным в течение периода времени, определенным константой timeToShutdown, и отвечает на дальнейшие предложения, что аукцион закрыт.

 // 3.2 Реализация сервиса аукциона.

 class Auction(seller: Actor, minBid: Int, closing: Date) extends Actor {
  val timeToShutdown = 36000000 // мс
  val bidIncrement = 10
  def act() {
    var maxBid = minBid - bidIncrement
    var maxBidder: Actor = null
    var running = true
    while (running) {
      receiveWithin((closing.getTime() - new Date().getTime())) {
        case Offer(bid, client) =>
          if (bid >= maxBid + bidIncrement) {
            if (maxBid >= minBid) maxBidder ! BeatenOffer(bid)
            maxBid = bid; maxBidder = client; client ! BestOffer
          } else {
            client ! BeatenOffer(maxBid)
          }
        case Inquire(client) =>
          client ! Status(maxBid, closing)
        case TIMEOUT =>
          if (maxBid >= minBid) {
            val reply = AuctionConcluded(seller, maxBidder)
            maxBidder !reply; seller ! reply
          } else {
            seller ! AuctionFailed
          }
          receiveWithin(timeToShutdown) {
            case Offer(_, client) => client ! AuctionOver
            case TIMEOUT => running = false
          }
      }
    }
  }
}

Ниже приведены некоторые комментарии по конструкциям, использованным в этой программе.

Метод receiveWithin класса Actor принимает в качестве параметров продолжительность торгов в миллисекундах и функцию, которая обрабатывает сообщения, поступающие в почтовый ящик. Функция задана последовательностью вариаций, каждая из которых определяет шаблон и действия, которые следует предпринять для сообщений, соответствующих этому шаблону. Метод receiveWithin выбирает из почтового ящика первое сообщение, которое соответствует одному из этих шаблонов и выполняет соответствующее действие.

Последняя вариация в receiveWithin — для шаблона TIMEOUT. Если никакие другие сообщения не были получены в последнее время, по истечении срока, который передается в receiveWithin как аргумент, срабатывает шаблон TIMEOUT. TIMEOUT — это особое сообщение (экземпляр класса Message), которое посылается в реализации класса Actor.

Ответные сообщения посылаются в форме destination ! SomeMessage. ! используется здесь как бинарный оператор с аргументами: актором и сообщением. В Scala это равносильно вызову метода destination.!(SomeMessage), то есть вызову метода ! актора-реципиента с сообщением в качестве параметра.

Предыдущее обсуждение показало возможности распределенного программирования на Scala. Может показаться, что в Scala есть богатый набор языковых конструкций, поддерживающих процессы-акторы, обмен сообщениями, программирование с тайм-аутами, и т. п. В действительности это не так. Все конструкции, рассмотренные выше, вводятся как методы в библиотечном классе Actor. Сам класс написан на Scala и базируется на модели многопоточности, используемой в нижележащей платформе (напр. Java или .NET). Все возможности класса Actor, использованные здесь, рассмотрены в Параграфе 17.11.

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

Выражения и простые функции

Предыдущий пример показывает, что можно делать при помощи Scala. Теперь мы опишем элементы языка по одному и более систематически. Начнем с самого нижнего уровня, с выражений и функций.

Выражения и простые функции

В дистрибутив Scala входит интерпретатор, который можно рассматривать как сложный калькулятор. Пользователь взаимодействует с калькулятором, вводя выражения. Калькулятор возвращает результаты вычислений и их типы. Например,

scala> 87 + 145
unnamed0: Int = 232

scala> 5 + 2 * 3
unnamed1: Int = 11

scala> "hello" + " world!"
unnamed2: java.lang.String = hello world!

Можно также именовать подвыражения и впоследствии использовать их имена:

scala> def scale = 5
scale: Int

scala> 7 * scale
unnamed3: Int = 35

scala> def pi = 3.141592653589793
pi: Double

scala> def radius = 10
radius: Int

scala> 2 * pi * radius
unnamed4: Double = 62.83185307179586

Определения начинаются с зарезервированного слова def, в них вводятся имена выражений, после которых ставится знак =. Интерпретатор вернет имя и тип выражения.

Выполнение такого определения, как def x = e, не вычисляет выражение e. Вместо этого e вычисляется там, где используется x. Также в Scala можно определять значения так: val x = e, в этом случае правая часть выражения e вычисляется как часть выполнения определения. Если x используется впоследствии, он немедленно заменяется на заранее вычисленное значение e, так что выражение не нужно вычислять заново.

Как же вычисляются выражения? Выражение, состоящее из операторов и операндов, вычисляется повторным применением следующих упрощающих шагов:

выбрать самую левую операцию;
вычислить ее операнды;
применить оператор к значениям операндов.

Имя, определенное при помощи def, вычисляется путем замены имени на (невычисленную) правую часть определения. Имя, определенное при помощи val, вычисляется путем замены имени на значение правой части. Процесс вычисления заканчивается, когда приходит к одному значению. Значение — это некоторые данные, как например: строка, число, массив или список.

Пример 4.1.1 Здесь представлено вычисление арифметического выражения.

  (2 * pi) * radius
→ (2 * 3.141592653589793) * radius
→ 6.283185307179586 * radius
→ 6.283185307179586 * 10
→ 62.83185307179586

Процесс пошагового сведения выражений к значениям называется редукцией.

Параметры

При помощи def можно также определять функции с параметрами. Например,

scala> def square(x: Double) = x * x
square: (Double)Double

scala> square(2)
unnamed0: Double = 4.0

scala> square(5 + 3)
unnamed1: Double = 64.0

scala> square(square(4))
unnamed2: Double = 256.0

scala> def sumOfSquares(x: Double, y: Double) = square(x) + square(y)
sumOfSquares: (Double,Double)Double

scala> sumOfSquares(3, 2 + 2)
unnamed3: Double = 25.0

Параметры функций перечисляются после имени функции и всегда заключаются в скобки. Каждый параметр имеет тип, который указывается после имени параметра и двоеточия. Пока что нам потребуются только базовые числовые типы, такие как scala.Double — типа числа двойной точности. Scala определяет псевдонимы для некоторых стандартных типов, так что мы можем писать численные типы, как в Java. Например, псевдоним double — scala.Double, а псевдоним int — scala.Int.

Функции с параметрами вычисляются аналогично операторам в выражениях. Сначала вычисляются аргументы функции (слева направо). Затем применение функции заменяется на ее правую часть, и в то же время все формальные параметры функции заменяются на соответствующие им фактические аргументы.

Пример 4.2.1

  sumOfSquares(3, 2 + 2)
→ sumOfSquares(3, 4)
→ square(3) + square(4)
→ 3 * 3 + square(4)
→ 9 + square(4)
→ 9 + 4 * 4
→ 9 + 16
→ 25

Пример показывает, что интерпретатор приводит аргументы функции к значениям перед тем, как переписать применение функции. Вместо этого можно было бы выбрать применять функцию к неприведенным аргументам. Это бы дало такую последовательность вывода:

  sumOfSquares(3, 2 + 2)
→ square(3) + square(2 + 2)
→ 3 * 3 + square(2 + 2)
→ 9 + square(2  + 2)
→ 9 + (2 + 2) * (2 + 2)
→ 9 + 4 * (2 + 2)
→ 9 + 4 * 4
→ 9 + 16
→ 25

Второй порядок вычисления называется вызовом по имени (call-by-name), тогда как первый называется вызовом по значению (call-by-value). Для выражений, которые используют только чистые функции и поэтому могут быть редуцированы при помощи подстановок, обе схемы приводят к одинаковым результирующим значениям.

У вызова по значению есть преимущество в том, что он не вычисляет аргументы повторно. У вызова по имени есть преимущество в том, что он не вычисляет аргумент, когда параметр вообще не используется в функции. Вызов по значению обычно более эффективен, чем по имени, но вызов по значению может зациклиться там, где вызов по имени завершится. Рассмотрим пример:

scala> def loop: Int = loop
loop: Int

scala> def first(x: Int, y: Int) = x
first: (Int,Int)Int

first(1, loop) сводится вызовом по имени к 1, тогда как тот же терм сводится вызовом по значению к самому себе раз за разом, и вычисление не завершается.

  first(1, loop)
→ first(1, loop)
→ first(1, loop) 
→ …

Scala по умолчанию использует вызов по значению, но можно переключиться на вызов по имени, если тип параметра предваряется =>.

Пример 4.2.2

scala> def constOne(x: Int, y: => Int) = 1
constOne: (Int,=> Int)Int

scala> constOne(1, loop)
unnamed0: Int = 1

scala> constOne(loop, 2) // дает бесконечный цикл.

^C // завершение по Ctrl-C

Условные выражения

if-else в Scala позволяет выбирать между двумя альтернативами. Синтаксис похож на if-else в Java. Но тогда как if-else в Java можно использовать только для альтернативных утверждений, Scala позволяет использовать тот же синтаксис для выбора между двумя выражениями. Поэтому в Scala if-else служит также для замены условного выражения Java … ? … : ….

Пример 4.3.2

scala> def abs(x: Double) = if (x >= 0) x else -x
abs: (Double)Double

Булевские выражения в Scala похожи на Java аналоги, они состоят из констант true и false, операторов сравнения, булевского отрицания ! и булевских операторов && и ||.

Пример: квадратные корни по методу Ньютона

Теперь проиллюстрируем элементы языка, которые мы упомянули к этому моменту, более интересной программой. Задание — написать функцию

def sqrt(x: Double): Double = …

которая вычисляет квадратный корень x.

Обычный способ вычисления квадратных корней — ньютоновский метод последовательных приближений. Мы начинаем с первой догадки y (скажем, y = 1). Затем будем улучшать текущую догадку y, вычисляя среднее между y и x/y. В качестве примера, следующие три столбца представляют догадку y, частное x/y и их среднее для первого приближения ${\sqrt {2}}$ .

1	2/1 = 2	1.5
1.5	2/1.5 = 1.3333	1.4167
1.4167	2/1.4167 = 1.4118	1.4142
1.4142	…	…

y	x/y	(y + x/y)/2

Этот алгоритм можно реализовать при помощи множества коротких функций, каждая из которых представляет один из элементов алгоритма.

Сначала определим функцию для итерации от догадки к результату:

def sqrtIter(guess: Double, x: Double): Double =
  if (isGoodEnough(guess, x)) guess
  else sqrtIter(improve(guess, x), x)

Отметим, что sqrtIter рекурсивно вызывает саму себя. Циклы императивного программирования всегда можно смоделировать при помощи рекурсии в функциональных программах.

Также отметим, что определение sqrtIter содержит возвращаемый тип, который следует за секцией параметров. Такие возвращаемые типы обязательны для рекурсивных функций. Для нерекурсивной функции возвращаемый тип необязателен, и если он не указан, проверка типов выведет его из правой части функции. Впрочем, даже для нерекурсивных функций указывать возвращаемый тип бывает полезно для улучшения документированности.

На втором шаге определим две функции, вызываемые в sqrtIter: функцию для улучшения догадки improve и проверку на завершение isGoodEnough. Вот их определения:

def improve(guess: Double, x: Double) =
  (guess + x / guess) / 2

def isGoodEnough(guess: Double, x: Double) =
  abs(square(guess) - x) < 0.001

Наконец, сама функция sqrt определена как применение sqrtIter.

def sqrt(x: Double) = sqrtIter(1.0, x)

Упражнение 4.4.1 Проверка isGoodEnough не очень точна для малых чисел и может привести к незавершению вычислений для очень больших чисел (почему?). Придумайте другую версию isGoodEnough, у которой нет таких проблем.

Упражнение 4.4.2 Проследите выполнение выражения sqrt(4).

Вложенные функции

Функциональный стиль программирования располагает к написанию множества небольших вспомогательных функций. В последнем примере реализация sqrt использует вспомогательные функции sqrtIter, improve и isGoodEnough. Имена этих функций относятся только к реализации sqrt. Мы не хотим, чтобы пользователи sqrt имели прямой доступ к этим функциям.

Мы можем выразить это (и избежать загрязнения пространства имен), включив вспомогательные функции в вызывающую функцию:

def sqrt(x: Double) = {
  def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)
  def improve(guess: Double, x: Double) =
    (guess + x / guess) / 2
  def isGoodEnough(guess: Double, x: Double) =
    abs(square(guess) - x) < 0.001
  sqrtIter(1.0, x)
}

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

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

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

Таким образом, допустимо писать:

def f(x: Int) = x + 1;
f(1) + f(2)

def g1(x: Int) = x + 1

g(1) + g(2)

def g2(x: Int) = { x + 1 }; /* ';' обязательно */ g2(1) + g2(2)

def h1(x) =
  x +
  y
h1(1) * h1(2)

def h2(x: Int) = (
  x // скобки обязательны, в противном случае точка с запятой
  + y // будет вставлена после 'x'.
)
h2(1) / h2(2)

Scala использует обычные правила областей видимости для блочных структур. Имя, определенное в каком-либо внешнем блоке, видно также во внутреннем блоке, если оно там не переопределено. Это правило позволяет упростить наш пример с sqrt. Нам не нужно передавать x как дополнительный параметр внутренней функции, поскольку эта переменная видна в них как параметр внешней функции sqrt. Вот упрощенный код:

def sqrt(x: Double) = {
  def sqrtIter(guess: Double): Double =
    if (isGoodEnough(guess)) guess
    else sqrtIter(improve(guess))
  def improve(guess: Double) =
    (guess + x / guess) / 2
  def isGoodEnough(guess: Double) =
    abs(square(guess) - x) < 0.001
  sqrtIter(1.0)
}

Хвостовая рекурсия

Рассмотрим функцию для нахождения наибольшего общего делителя двух чисел.

def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

При помощи нашей модели подстановки gcd(14,21) вычисляется следующим образом:

    gcd(14, 21)
→   if (21 == 0) 14 else gcd(21, 14 % 21)
→   if (false) 14 else gcd(21, 14 % 21)
→   gcd(21, 14 % 21)
→   gcd(21, 14)
→   if (14 == 0) 21 else gcd(14, 21 % 14)
→ → gcd(14, 21 % 14)
→   gcd(14, 7)
→   if(7 == 0) 14 else gcd(7, 14 % 7)
→ → gcd(7, 14 % 7)
→   gcd(7, 0)
→   if(0 == 0) 7 else gcd(0, 7 % 0)
→ → 7

Сравним это с вычислением другой рекурсивной функции, factorial:

def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)

Применение factorial(5) переписывается так:

      factorial(5)
→     if (5 == 0) 1 else 5 * factorial(5 - 1)
→     5 * factorial(5 - 1)
→     5 * factorial(4)
→ … → 5 * (4 * factorial(3))
→ … → 5 * (4 * (3 * factorial(2)))
→ … → 5 * (4 * (3 * (2 * factorial(1))))
→ … → 5 * (4 * (3 * (2 * (1 * factorial(0))))
→ … → 5 * (4 * (3 * (2 * (1 * 1))))
→ … → 120

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

Несмотря на то, что на самом деле Scala не переписывает термы, затраты по памяти будут такими же, что и в последовательности вывода. Заметим, что в реализации gcd рекурсивный вызов gcd — это последнее действие в теле вычисления. Это пример хвостовой рекурсии. Последний вызов в хвостово-рекурсивной функции может быть реализован прыжком обратно к началу этой функции. Аргументы такого вызова могут быть вписаны на место параметров текущего выполнения gcd, так что новой памяти на стеке выделять не нужно. Отметим, что хвостово-рекурсивные функции это итеративные процессы, которые могут выполняться в константной памяти.

Рекурсивый вызов factorial, напротив, заканчивается операцией умножения. Отметим, что для рекурсивного вызова factorial выделяется новый кадр стека, который стирается после завершения выполнения вызова. Данная реализации функции факториала не хвостово-рекурсивна, и ей необходимо количество памяти, пропорциональное размеру ввода.

Говоря более общим языком, если последнее действие функции это вызов другой (возможно, той же самой) функции, то для обеих функций требуется только один кадр стека. Такие вызовы называются хвостовыми. В принципе, хвостовые вызовы могут все время переиспользовать кадр вызывающей функции. Впрочем, в некоторых средах выполнения (например, виртуальная машина Java) нет примитивов для того, чтобы обеспечить эффективное переиспользование кадров стека для хвостовых вызовов. Поэтому реализация Scala должна переиспользовать кадры стека только прямо хвостово-рекурсивных функций, чье последнее действие это вызов самих себя. Другие хвостовые вызовы также могут быть оптимизированы, но на это не следует надеяться

Упражнение 4.6.1 Придумайте хвостово-рекурсивную версию функции factorial.

Функции первого класса

Функции в Scala являются «значениями первого класса». Как любые другие значения, их можно передавать как параметры и возвращать как результаты. Функции, которые принимают другие функции в качестве параметров или возвращают их как результаты, называются функциями высшего порядка. Эта глава представляет функции высшего порядка и показывает гибкий механизм для составления программ, которые они реализуют.

Для мотивации рассмотрим следующие три задания.

1. Написать функцию для суммирования всех целых чисел между двумя данными числами a и b:

def sumInts(a: Int, b: Int): Int =
 if (a > b) 0 else a + sumInts(a + 1, b)

2. Написать функцию для суммирования квадратов всех целых чисел между двумя данными числами a и b:

def square(x: Int): Int = x * x
def sumSquares(a: Int, b: Int): Int =
  if (a > b) 0 else square(a) + sumSquares(a + 1, b)

3. Написать функцию для суммирования степеней двойки 2ⁿ для всех целых чисел между двумя данными числами a и b:

def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)
def sumPowersOfTwo(a: Int, b: Int): Int =
  if (a > b) 0 else powerOfTwo(a) + sumPowersOfTwo(a + 1, b)

Все эти функции являются сущностями $\sum \limits _{a}^{b}f(n)$ для разных значений f. Мы можем выделить общий шаблон, определив функцию sum:

def sum(f: Int => Int, a: Int, b: Int): Int =
  if (a > b) 0 else f(a) + sum(f, a + 1, b)

Тип Int => Int — это тип функции, которая принимает аргумент типа Int и возвращает результат типа Int. Так что sum — функция, берущая в качестве параметра другую функцию. Другими словами, sum — функция высшего порядка.

Используя sum, мы можем сформулировать три суммирующие функции так:

def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumSquares(a: Int, b: Int): Int = sum(square, a, b)
def sumPowersOfTwo(a: Int, b: Int): Int = sum(powerOfTwo, a, b)

где

def id(x: Int): Int = x
def square(x: Int): Int = x * x
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)

Анонимные функции

Параметризация по функциям располагает к созданию множества маленьких функций. В предыдущем примере мы определили id, square и power как отдельные функции, так что их можно было передавать в качестве аргументов в sum.

Вместо того, чтобы определять поименованные функции для этих небольших функций-аргументов, можно сформулировать их короче как анонимные функции. Анонимная функция это выражение, вычисляющееся в функцию; функция, определенная без имени. Для примера рассмотрим анонимную функцию возведения в квадрат:

(x: Int) => x * x

Часть перед стрелкой — параметры функции, часть после нее — тело функции. Вот, например, анонимная функция, перемножающая два аргумента:

(x: Int, y: Int) => x * y

Используя анонимные функции, можно переформулировать первые две суммирующие функции, не именуя вспомогательных функций:

def sumInts(a: Int, b: Int): Int = sum((x: Int) => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum((x: Int) => x * x, a, b)

Часто компилятор Scala может выводить типовые параметры из контекста анонимных функций, и в этих случаях типовые параметры можно опускать. Например, в случае sumInts или sumSquares из типа sum понятно, что первый параметр должен быть функцией типа Int => Int. Заметьте, что типовой параметр Int избыточен и может быть опущен. Если есть только один параметр без типа, можно также опустить скобки вокруг него:

def sumInts(a: Int, b: Int): Int = sum(x => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum(x => x * x, a, b)

Выражение Scala (x₁: T₁, …, x_n: T_n) => E определяет функцию, которая соотносит свои параметры x₁, …, x_n с результатами выражения E (где E может ссылаться на x₁, …, x_n). Анонимные функции — не основные элементы языка Scala, поскольку они всегда могут быть выражены через именованные функции. Действительно, анонимная функция

(x₁: T₁, …, x_n: T_n) => E

эквивалентна блоку

{ def f (x₁: T₁, …, x_n: T_n) = E ; f _ }

где f — свежее имя, которое больше не используется нигде в программе. Можно сказать, что анонимные функции это «синтаксический сахар».

Каррирование

Последняя формулировка суммирующей функции уже довольно компактна. Но мы можем еще лучше! Заметим, что a и b появляются как параметры и аргументы каждой функции, но они, похоже, не участвуют в интересных комбинациях. Можно ли от них избавиться?

Давайте попробуем переписать sum так, чтобы она не принимала границы интервала a и b как параметры:

def sum(f: Int => Int): (Int, Int) => Int = {
  def sumF(a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sumF(a + 1, b)
  sumF
}

В этой формулировке sum — это функция, которая возвращает другую функцию, а именно специализированную суммирующую функцию sumF. Эта последняя функция выполняет всю работу: она принимает границы a и b как параметры, применяет f, параметр sum, ко всем целым числам между ними, и суммирует результаты.

При помощи этой формулировки sum мы можем теперь определить:

def sumInts = sum(x => x)
def sumSquares = sum(x => x * x)
def sumPowersOfTwo = sum(powerOfTwo)

Или, эквивалентно тому, с такими определениями:

val sumInts = sum(x => x)
val sumSquares = sum(x => x * x)
val sumPowersOfTwo = sum(powerOfTwo)

sumInts, sumSquares и sumPowersOfTwo можно применять как любые другие функции. Например,

scala> sumSquares(1, 10) + sumPowersOfTwo(10, 20)
unnamed0: Int = 2096513

Как же применяются функции, возвращающие функции? Например, в этом выражении

sum(x => x * x)(1, 10)

функция sum применяется к функции возведения в квадрат (x => x * x). Получившаяся функция затем применяется ко второму списку аргументов (1, 10).

Такая запись возможна, потому что применение функций левоассоциативно. То есть, если args₁ и args₂ — списки аргументов, то f(args₁)(args₂) эквивалентно (f(args₁))(args₂).

В нашем примере sum(x => x * x)(1, 10) эквивалентно следующему выражению: (sum(x => x * x))(1, 10).

Функций, возвращающие функции, настолько полезны, что у Scala есть для них специальный синтаксис. Например, следующее определение sum эквивалентно предыдущему, но оно короче:

def sum(f: Int => Int)(a: Int, b: Int): Int =
  if (a > b) 0 else f(a) + sum(f)(a + 1, b)

Более общее определение каррированной функции:

def f (args₁) … (args_n) = E

где n > 1 раскрывается в

def f (args₁) … (args_n-1) = { def g (args_n) = E ; g }

где g — свежий идентификатор. Или, если короче, с использованием анонимной функции:

def f (args₁) … (args_n-1) = ( args_n ) => E

Выполнение этого шага n раз приводит к тому, что

def f (args₁) … (args_n) = E

эквивалентно

def f = (args₁) => … => (args_n) => E

Или, эквивалентно, с другим определением:

val f = (args₁) => … => (args_n) => E

Такой стиль определения и применения функций называется каррирование (currying) в честь своего популяризатора Хаскелла Карри, логика XX века, хотя идея принадлежит Мозесу Шонфинкелю и Готтлобу Фреге.

Тип функции, возвращающей функцию, выражается аналогично списку ее параметров. Возьмем к примеру последнюю формулировку sum. Тип sum — (Int => Int) => (Int, Int) => Int. Это возможно, потому что типы функций правоассоциативны. То есть, T1 => T2 => T3 эквивалентно T1 => (T2 => T3).

Упражнение 5.2.1 1. Функция sum использует линейную рекурсию. Напишите хвостоворекурсивный вариант, заполнив ??.

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def iter(a: Int, result: Int): Int = {
    if (??) ??
    else iter(??, ??)
  }
  iter(??, ??)
}

Упражнение 5.2.2 Напишите функцию product, которая вычисляет произведение значений функций в точках данного интервала.

Упражнение 5.2.3 Напишите factorial в терминах product.

Упражнение 5.2.4 Можете ли вы написать более общую функцию, которая обобщает sum и product?

Пример: поиск неподвижных точек функций

Число x называется неподвижной точкой функции f, если f(x) = x.

Для некоторых функций f можно найти неподвижную точку, стартовав с начальной догадки и затем применяя f раз за разом, пока значение не перестанет изменяться (или изменения будут не больше некоторого значения). Это возможно, если последовательность x, f(x), f(f(x)), f(f(f(x))), … сходится к неподвижной точке f. Эта идея выражена в следующей функции поиска неподвижной точки:

val tolerance = 0.0001
def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
  def iterate(guess: Double): Double = {
    val next = f(guess)
    if (isCloseEnough(guess, next)) next
    else iterate(next)
  }
  iterate(firstGuess)
}

Теперь применим эту идею при формулировании функции вычисления квадратных корней. Начнем со спецификации sqrt: sqrt(x) = the y such that y * y = x = the y such that y = x / y.

Заметьте, что sqrt(x) — неподвижная точка функции y => x / y. Поэтому sqrt(x) можно вычислить при помощи итерации неподвижной точки:

def sqrt(x: double) = fixedPoint(y => x / y)(1.0)

Но если мы сделаем так, мы обнаружим, что вычисления не сходятся. Давайте добавим в функцию выражение печати значения guess:

def fixedPoint(f: Double => Double)(firstGuess: Double) = {
  def iterate(guess: Double): Double = {
    val next = f(guess)
    println(next)
    if (isCloseEnough(guess, next)) next
    else iterate(next)
  }
  iterate(firstGuess)
}

Тогда sqrt(2) выведет

2.0
1.0
2.0
1.0
2.0
…

Такие колебания можно контролировать, не давая значению догадки так сильно изменяться. Это можно сделать усреднением значений:

scala> def sqrt(x: Double) = fixedPoint(y => (y + x/y) / 2)(1.0)
sqrt: (Double)Double

scala> sqrt(2.0)
  1.5
  1.4166666666666665
  1.4142156862745097
  1.4142135623746899
  1.4142135623746899

На самом деле, расширение функции fixedPoint дает в точности определение неподвижной точки из Параграфа 4.4.

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

Рассмотрим опять итерации неподвижной точки. Мы начали с наблюдения, что ${\sqrt {(x)}}$ это неподвижная точка функции y => x / y. Затем мы свели итерации к неподвижной точке, усредняя последовательные значения. Техника торможения усреднением настолько часто применяется, что на может быть вынесена в отдельную функцию:

def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

При помощи averageDamp мы можем переформулировать функцию вычисления квадратного корня так:

def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)

Это выражает элементы алгоритма максимально ясно.

Упражнение 5.3.1 Напишите функцию для вычисления кубических корней, используя fixedPoint и averageDamp.

Заключение

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

Использованные элементы языка

Главы 4 и 5 покрывают элементы языка Scala для выражения выражений и типов, включая примитивные типы и функции. Ниже дан контекстно-свободный синтаксис этих языковых элементов в расширенной форме Бэкуса-Наура, где '|' обозначает альтернативы, […] обозначает опцию (вхождение 1 или 0 раз), и {…} обозначает повторение (0 или больше вхождений).

Символы

Программы Scala — это последовательности символов Unicode. Мы различаем следующие множества символов:

пробел, табуляция или символ перевода строки,
буквы от ‘a’ до ‘z’, ‘A’ до ‘Z’,
цифры от ‘0’ до ‘9’,
разделители: . , ; ( ) { } [ ] \ " ',
операторные символы, такие как ‘#’, ‘+’, ‘:’. По сути, это символы, которые не перечислены в множествах выше.

Лексемы

идентификатор = буква {буква | цифра}
              | оператор {оператор}
              | идентификатор '_' идентификатор
литерал       = "как в Java"

Литералы — те же, что и в Java. Они определяют числа, символы, строки и булевские величины. Примеры литералов: 0, 1.0e10, 'x', "he said "hi!"" или true.

Идентификаторы могут быть двух видов. Они начинаются либо с буквы, за которой идет (возможно, пустая) последовательность букв и символов, либо с операторного символа, за которым идет (возможно, пустая) последовательность операторных символов. Оба вида идентификаторов могут содержать символы подчеркивания. За символом подчеркивания могут идти идентификаторы любого типа. Например, следующие идентификаторы корректны: x Room10a + -- foldl_: +_vector.

Это следует из правила, что следующие друг за другом оператор и идентификатор должны разделяться пробелом. Например, ввод x+-y будет распознан как последовательность из трех токенов x, +-, y. Если мы хотим выразить сумму x и значения -y, нам нужно добавить по крайней мере один пробел: x+ -y.

Символ $ зарезервирован для идентификаторов, сгенерированных компилятором, он не должен использоваться в исходном коде программы.

Следующие слова зарезервированы, их нельзя использовать в качестве идентификаторов:

abstract	case	catch	class	def
do	else	extends	false	final
finally	for	if	implicit	import
match	new	null	object	override
package	private	protected	requires	return
sealed	super	this	throw	trait
try	true	type	val	var
while	with	yield

_ : = => <- <: <% >: # @

Типы

Тип        = ПростойТип | ТипФункции
ТипФункции = ПростойТип '=>' Тип | '(' [Типы] ')' '=>' Тип
ПростойТип = Byte | Short | Char | Int | Long | Float | Double | Boolean | Unit | String
Типы       = Тип {',' Тип}

Типы могут быть:

числовыми типами Byte, Short, Char, Int, Long, Float и Double (такие же, как в Java),
типом Boolean со значениями true и false,
типом Unit с единственным значением (),
типом String,
типами функций, как (Int, Int) => Int или String => Int => String.

Выражения

Выр        = ИнфиксВыр | ФункцВыр | if '(' Выр ')' Выр else Выр
ИнфиксВыр  = ПрефиксВыр | ИнфиксВыр Оператор ИнфиксВыр
Оператор   = идентификатор
ПрефиксВыр = ['+' | '-' | '!' | '~'] ПростоеВыражение
ПростоеВыр = идентификатор | литерал | ПростоеВыр '.' идентификатор | Блок
Функция    = (Связывания | Id) '=>' Выр
Связывания = '(' Связывание {',' Связывание } ')'
Связывание = идентификатор [':' Тип]
Блок       = '{' {Определение ';'} Выр '}'

Выражения могут быть:

идентификаторами, как x, isGoodEnough, * или +-,
литералами, как 0, 1.0 или "abc",
выборами поля или метода, как System.out.println,
применениями функций, как sqrt(x),
применениями операторов, как -x или y + x,
условиями, как if (x < 0) -x else x,
блоками, как { val x = abs(y) ; x * 2 },
анонимными функциями, как x => x + 1 или (x: Int, y: Int) => x + y.

Определения

Опр         = ОпрФункции | ОпрЗначения
ОпрФункции  = 'def' идентификатор {'(' [Параметры ] ')'} [':' Тип] '=' Выр
ОпрЗначения = 'val' идентификатор [':' Тип] '=' Выр
Параметры   = Параметр {',' Параметр}
Параметр    = идентификатор ':' ['=>'] Тип

Определения могут быть:

определениями функций, как def square(x: Int): Int = x * x,
определениями значений, как val y = square(2).

Классы и объекты

В Scala нет встроенного типа для рациональных чисел, но его легко определить при помощи класса. Вот возможная реализация:

class Rational(n: Int, d: Int) {
  private def gcd(x: Int, y: Int): Int = {
    if (x == 0) y
    else if (x < 0) gcd(-x, y)
    else if (y < 0) -gcd(x, -y)
    else gcd(y % x, x)
  }
  private val g = gcd(n, d)
  
  val numer: Int = n/g 
  val denom: Int = d/g
  def +(that: Rational) =
    new Rational(numer * that.denom + that.numer * denom,
                 denom * that.denom)
  def -(that: Rational) =
    new Rational(numer * that.denom - that.numer * denom,
                 denom * that.denom)
  def *(that: Rational) =
    new Rational(numer * that.numer, denom * that.denom)
  def /(that: Rational) =
    new Rational(numer * that.denom, denom * that.numer)
}

Это определяет Rational как класс, принимающий два аргумента конструктора n и d, содержащие числитель и знаменатель числа. Класс предоставляет поля, возвращающие эти части, и методы для арифметических операций с рациональными числами. Левый операнд операции — всегда рациональное число, для которого метод является членом (класса).

Приватные члены

Реализация рациональных чисел определяет приватный метод gcd, который считает наибольший общий делитель двух целых чисел, и приватное поле g, содержащее gcd аргументов конструктора. Эти члены недоступны вне класса Rational. Они используются для реализации класса, чтобы сократить общие множители аргументов конструктора для приведения числителя и знаменателя к нормализованной форме.

Создание и доступ к объектам

Для примера того, как могут быть использованы рациональные числа, приведем программу, выводящую на экран сумму всех чисел 1/i, где i пробегает значения от 1 до 10.

var i = 1
var x = new Rational(0, 1)
while (i <= 10) {
  x += new Rational(1, i)
  i += 1
}
println("" + x.numer + "/" + x.denom)

Оператор + принимает строку в качестве левого операнда и значение любого типа в качестве правого. Он возвращает результат преобразования своего правого операнда в строку и конкатенации левого операнда с этой строкой.

Наследование и переопределение

У каждого класса в Scala есть предок в иерархии (суперкласс), который расширяется данным классом. Если класс не упоминает предка в своем определении, предком неявно предполагается корневой тип scala.AnyRef (для реализаций Java этот тип — псевдоним java.lang.Object). Например, класс Rational можно эквивалентно определить так:

class Rational(n: Int, d: Int) extends AnyRef {
  … // как прежде
}

Класс наследует все члены своего суперкласса. Он также может переопределять (override) некоторые наследованные члены. Например, java.lang.Object определяет метод toString, который возвращает представление объекта в виде строки:

class Object {
  …
  def toString: String = …
}

Реализация метода toString в Object формирует строку, состоящую из имени класса и номера объекта. Есть смысл переопределить этот метод для объектов, являющихся рациональными числами:

class Rational(n: Int, d: Int) extends AnyRef {
  … // как прежде
  override def toString = "" + numer + "/" + denom
}

Заметьте, что в отличие от Java, в Scala переопределение определений должно предваряться модификатором override.

Если класс A расширяет (extends) класс B, то объекты типа A могут быть использованы везде, где ожидаются объекты типа B. В этом случае мы говорим, что класс A соответствует классу B. Например, Rational соответствует AnyRef, и корректно будет присвоить значение Rational переменной типа AnyRef:

var x: AnyRef = new Rational(1, 2)

Методы без параметров

В отличие от Java, методы в Scala не обязательно должны принимать список параметров. Пример тому — метод square, представленный ниже. Этот метод вызывается просто упоминанием своего имени.

class Rational(n: Int, d: Int) extends AnyRef {
  … // как прежде
  def square = new Rational(numer*numer, denom*denom)
}
val r = new Rational(3, 4)
println(r.square) // выводит‘‘9/16’’*

То есть, доступ к методам без параметров такой же, как к полям значений, таких как numer. Разница между значениями и методами без параметров в их определении. Правая часть значения вычисляется, когда создается объект, и значение после этого не изменяется. Правая часть метода без параметров, напротив, вычисляется каждый раз, когда метод вызывается. Общий вид доступа к полям и методам без параметров дает повышенную гибкость для разработчика класса. Часто поле в одной версии класса становится вычисляемым значением в следующей версии. Общий вид доступа дает гарантию того, что клиенты не нужно будет переписывать из-за этого изменения.

Абстрактные классы

Реализуем класс для множеств целых чисел с двумя операциями, incl и contains. (s incl x) должно возвращать новое множество, содержащее элемент x и все элементы множества s. (s contains x) должно возвращать true, если множество s содержит элемент x, и false в противном случае. Интерфейс множеств задан так:

abstract class IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
}

IntSet помечен как абстрактный класс (abstract class). У этого есть два следствия. Во-первых, абстрактные классы могут откладывать (defer) члены, которые объявлены, но у которых нет реализации. В нашем случае оба метода incl и contains таковы. Во-вторых, из-за того, что у абстрактного класса могут быть нереализованные члены, объект такого класса не может быть создан при помощи new. Абстрактные классы могут быть использованы как базовые классы для других классов, реализующих из отложенные методы.

Трейты

Вместо abstract class в Scala часто используют ключевое слово trait. Трейты это абстрактные классы, которые задуманы, чтобы добавлять их к другим классам, потому что трейты добавляют к классам некоторые методы или поля. Например, трейт Bordered может быть использован, чтобы добавить границу к любому графическому компоненту. Другой сценарий использования происходит, когда трейт вбирает в себя сигнатуры некоторой функциональности, обеспечиваемой различными классами (похоже на интерфейсы в Java).

Поскольку IntSet попадает в эту категорию, можно определить его как трейт:

trait IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
}

Реализация абстрактных классов

Допустим, мы хотим реализовать множества в виде двоичных деревьев. Есть две разные формы деревьев: дерево для пустого множества и дерево, состоящее из целого числа и двух поддеревьев. Вот их реализация:

class EmptySet extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
}

class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
  def contains(x: Int): Boolean =
    if (x < elem) left contains x
    else if (x > elem) right contains x
    else true
  def incl(x: Int): IntSet =
    if (x < elem) new NonEmptySet(elem, left incl x, right)
    else if (x > elem) new NonEmptySet(elem, left, right incl x)
    else this
}

И EmptySet, и NonEmptySet расширяют класс IntSet. Из этого следует, что типы EmptySet и NonEmptySet соответствуют типу IntSet — значение типа EmptySet или NonEmptySet может быть использовано везде, где требуется значение типа IntSet.

Упражнение 6.0.1 Напишите метод union и intersection для формирования объединения и пересечения двух множеств.

Упражнение 6.0.2 Добавьте метод

def excl(x: Int)

возвращающий данное множество без элемента x. Чтобы это сделать, полезно будет реализовать для множеств тестовый метод

def isEmpty: Boolean

Динамическое связывание

Объектно-ориентированные языки (включая Scala) используют динамическое назначение (dynamic dispatch) для вызовов методов. То есть, код, который запускается при вызове метода, зависит от типа объекта, содержащего метод, во время выполнения. Например, рассмотрим выражение s contains 7, в котором s это значение заявленного типа s: IntSet. Какой код для contains будет выполнен, зависит от типа значения во время выполнения. Если это значение EmptySet, это будет реализация contains в классе EmptySet (аналогично для значений NonEmptySet). Такое поведение прямо следует из нашей подстановочной модели вычислений. Например,

  (new EmptySet).contains(7)

-> (заменим 'contains' его телом из класса EmptySet)

  false

Или

  new NonEmptySet(7, new EmptySet, new EmptySet).contains(1)

-> (заменим 'contains' его телом из класса NonEmptySet)

  if (1 < 7) new EmptySet contains 1
  else if (1 > 7) new EmptySet contains 1
  else true

-> (перепишем условное выражение)

  new EmptySet contains 1

-> (заменим 'contains' его телом из класса EmptySet)

  false

Динамическое назначение методов аналогично вызовам функций высшего порядка. В обоих этих случаях только во время выполнения известно, какой код будет выполняться. Это сходство не является поверхностным. Действительно, Scala представляет каждую фукцию как объект (см. Параграф 8.6).

Объекты

В предыдущей реализации множеств целых чисел пустые множества были выражены при помощи new EmptySet, так что каждый раз, когда требовалось значение пустого множества, создавался новый объект. Мы могли бы избежать создания ненужных объектов, определив значение empty однажды и используя это значение вместо каждого new EmptySet. Например,

val EmptySetVal = new EmptySet

Проблема этого подхода в том, что такое определение значения нелегально для высшего уровня в Scala, оно должно быть частью другого класса или объекта. К тому же определение класса EmptySet теперь выглядит несколько избыточным — зачем определять класс объектов, если нам нужен только один объект этого класса? Более прямой подход — использовать определение объекта. Ниже представлен более прямолинейный вариант определения пустого множества:

object EmptySet extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmptySet(x, EmptySet, EmptySet)
}

Синтаксис определения объекта следует синтаксису определения класса, у него есть необязательный пункт extends и необязательное тело. Как и в случае классов, пункт extends определяет наследованные члены объекта, а тело определяет переопределенные или новые члены. Определение объекта определяет только один объект, и нельзя создавать новые объекты с той же структурой при помощи new. Поэтому у определений объектов нет параметров конструкторов, которые могут присутствовать в определениях классов.

Определения объектов могут появляться в любом месте программ на Scala, включая высший уровень. Поскольку не существует фиксированного порядка выполнения сущностей высшего уровня в Scala, может возникнуть вопрос, когда в точности создается и инициализируется объект, определенный при помощи определения объекта. Объект впервые создается, когда впервые происходит доступ к одному из его членов. Такая стратегия называется ленивым вычислением.

Стандартные классы

Scala — чисто объектно-ориентированный язык. Это значит, что каждое значение в Scala может быть рассмотрено как объект. На самом деле даже примитивные типы, как int или boolean, не рассматриваются специально. Они определены как псевдонимы типов классов Scala в модуле Predef:

type boolean = scala.Boolean
type int = scala.Int
type long = scala.Long
…

Для эффективности компилятор обычно представляет значения типа scala.Int 32-битными целыми числами, значения scala.Boolean — двоичными значениями Java, и т. д. Но он преобразует эти специализированные представления в объекты, когда это требуется, например, когда значение примитивного типа Int передается в функцию с параметром типа AnyRef. Обратите внимание, что специальное представление примитивных значений это всего лишь оптимизация, оно не меняет смысла программы.

Вот спецификация класса Boolean:

package scala
abstract class Boolean {
  def && (x: => Boolean): Boolean
  def || (x: => Boolean): Boolean
  def !                 : Boolean

  def == (x: Boolean)   : Boolean
  def != (x: Boolean)   : Boolean
  def < (x: Boolean)    : Boolean
  def > (x: Boolean)    : Boolean
  def <= (x: Boolean)   : Boolean
  def >= (x: Boolean)   : Boolean
}

Булевские значения определены при помощи только классов и объектов, без ссылок на встроенный тип булевских значений или чисел. Возможная реализация класса Boolean дана ниже. Это не реализация из страндартной бибилотеки Scala, стандартная реализация использует встроенные булевские значения из соображений эффективности.

package scala
abstract class Boolean {
  def ifThenElse(thenpart: => Boolean, elsepart: => Boolean)

  def && (x: => Boolean): Boolean = ifThenElse(x, false)
  def || (x: => Boolean): Boolean = ifThenElse(true, x)
  def !                 : Boolean = ifThenElse(false, true)

  def == (x: Boolean)   : Boolean = ifThenElse(x, x.!)
  def != (x: Boolean)   : Boolean = ifThenElse(x.!, x)
  def < (x: Boolean)    : Boolean = ifThenElse(false, x)
  def > (x: Boolean)    : Boolean = ifThenElse(x.!, false) 
  def <= (x: Boolean)   : Boolean = ifThenElse(x, true)
  def >= (x: Boolean)   : Boolean = ifThenElse(true, x.!)
}
case object True extends Boolean {
  def ifThenElse(t: => Boolean, e: => Boolean) = t
}
case object False extends Boolean {
  def ifThenElse(t: => Boolean, e: => Boolean) = e
}

Вот частичная реализация класса Int:

package scala
abstract class Int extends AnyVal {
  def toLong: Long
  def toFloat: Float
  def toDouble: Double

  def + (that: Double): Double
  def + (that: Float): Float
  def + (that: Long): Long
  def + (that: Int): Int // аналогично для -, *, /, %

  def << (cnt: Int): Int // аналогично для >>, >>>

  def & (that: Long): Long
  def & (that: Int): Int // аналогично для |, ^

  def == (that: Double): Boolean
  def == (that: Float): Boolean
  def == (that: Long): Boolean // аналогично для !=, <, >, <=, >=
}

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

abstract class Nat {
  def isZero: Boolean
  def predecessor: Nat
  def successor: Nat
  def + (that: Nat): Nat
  def - (that: Nat): Nat
}

Чтобы реализовать класс Nat, определим подобъект Zero и подкласс Succ (для следующего значения). Каждое число N представлено N применениями конструктора Succ к Zero:

$\underbrace {new\ Succ(\ ...\ newSucc} _{N}(Zero)\ ...\ )$

Реализация объекта Zero довольно прямолинейна:

object Zero extends Nat {
  def isZero: Boolean = true
  def predecessor: Nat = error("negative number")
  def successor: Nat = new Succ(Zero)
  def + (that: Nat): Nat = that
  def - (that: Nat): Nat = if (that.isZero) Zero
                           else error("negative number")
}

Реализации функций предыдущего элемента и вычитания в Zero выбрасывают исключение Error, которое завершает выполнение программы с переданным собщением об ошибке.

Вот реализация класса последующего элемента:

class Succ(x: Nat) extends Nat {
  def isZero: Boolean = false
  def predecessor: Nat = x
  def successor: Nat = new Succ(this)
  def + (that: Nat): Nat = x + that.successor
  def - (that: Nat): Nat = if (that.isZero) this
                           else x - that.predecessor
}

Обратите внимание на реализацию метода successor. Для создания последующего числа мы должны передать сам объект в качестве аргумента конструктора Succ. Ссылку на сам объект дает зарезервированное имя this.

Реализации + и - содержат рекурсивные вызовы с аргументом конструктора в качестве получателя. Рекурсия завершится, когда получатель будет объектом Zero (а это гарантированно случится в конце концов из-за того, как мы формируем числа).

Упражнение 6.0.3 Напишите реализацию класса целых чисел Integer. Реализация должна поддерживать все операции класса Nat и два дополнительных метода:

def isPositive: Boolean
def negate: Integer

Первый метод должен возвращать true, если число положительное. Второй метод должен домножать число на -1. Не используйте в своей реализации стандартные числовые классы Scala. (Подсказка: есть два возможных способа реализовать Integer. Можно либо использовать существующую реализацию Nat, представляя целые числа как натуральные со знаком, либо обобщить данную реализацию Nat до Integer, используя три подкласса: Zero для 0, Succ для положительных чисел и Pred для отицательных.)

Элементы языка, представленные в этой главе

Типы

Тип = … | идентификатор

Типы теперь могут быть произвольными идентификаторами, представляющими классы.

Выражения

Выр = … | Выр '.' Выр | 'new' Выр | 'this'

Выражение теперь может быть созданием объекта, выбором члена m из выражения с объектным значением E (E.m) или зарезервированным именем this.

Определения и объявления

Опр            = ОпрФункции | ОпрЗначения | ОпрКласса | ОпрТрейта  | ОпрОбъекта
ОпрКласса      = ['abstract'] 'class' идентификатор ['(' [Параметры] ')']
                 ['extends' Выр] ['{' {ОпрШаблона} '}]'
ОпрТрейта      = 'trait' идентификатор ['extends' Выр] ['{' {ОпрШаблона} '}]'
ОпрШаблона     = [Модификатор] (Опр | Объявл)
ОпрОбъекта     = [Модификатор] Опр
Модификатор    = 'private' | 'override'
Объявл         = ОбъявлФункции | ОбъявлЗначения
ОбъявлФункции  = 'def' идентификатор {'(' [Параметры] ')'} ':' Тип
ОбъявлЗначения = 'val' идентификатор ':' Тип

Определение теперь может быть определением класса, трейта или объекта, как:

class C(params) extends B { defs }
trait T extends B { defs }
object O extends B { defs }

Определения defs в классе, трейте или объекте могут быть предварены модификаторами private или override.

Абстрактные классы и трейты могут также содержать объявления. Так вводятся отложенные функции и значения с типами, но без предоставленных реализаций. Отложенные члены должны быть реализованы в подклассах перед созданием объектов абстрактного класса иди трейта.

Case-классы и сопоставление с образцом

Допустим, мы хотим написать интерпретатор арифметических функций. Чтобы не усложнять задачу, ограничимся только числами и оператором +. Такие выражения могут быть представлены как иерархия классов с абстрактным базовым классом Expr в корне и двумя подклассами Number и Sum. Тогда выражение 1 + (3 + 7) будет представлено как

new Sum(new Number(1), new Sum(new Number(3), new Number(7)))

Теперь интерпретатор такого выражения должен знать, какого оно вида (Number или Sum), и должен иметь доступ к компонентам выражения. Следующая реализация предоставляет все необходимые методы:

abstract class Expr {
  def isNumber: Boolean
  def isSum: Boolean
  def numValue: Int
  def leftOp: Expr
  def rightOp: Expr
}
class Number(n: Int) extends Expr {
  def isNumber: Boolean = true
  def isSum: Boolean = false
  def numValue: Int = n
  def leftOp: Expr = error("Number.leftOp")
  def rightOp: Expr = error("Number.rightOp")
}
class Sum(e1: Expr, e2: Expr) extends Expr {
  def isNumber: Boolean = false
  def isSum: Boolean = true
  def numValue: Int = error("Sum.numValue")
  def leftOp: Expr = e1
  def rightOp: Expr = e2
}

С такой классификацией и методами доступа написать интерпретатор легко:

def eval(e: Expr): Int = {
  if (e.isNumber) e.numValue
  else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
  else error("неопознанный тип выражения")
}

Впрочем, определять все эти методы в классах Number и Sum довольно утомительно. Более того, проблема становится еще хуже, если мы хотим добавить новые формы выражений. Например, рассмотрим добавление новой формы выражения Prod со всей предыдущей классификацией и методами доступа, мы также хотим ввести новый абстрактный метод isProduct в класс Expr и реализовать этот метод в подклассах Number, Sum и Prod. Необходимость модифицировать существующий код, когда система растет, всегда проблематично, поскольку это затрудняет контроль версий и поддержку.

Объектно-ориентированное программирование обещает, что такие модификации не обязательны, поскольку их можно избежать, переиспользуя существующий неизменяющийся код через механизм наследования. Действительно, более объектно-ориентированная организация решает проблему. Идея состоит в том, чтобы сделать операцию «высшего уровня» eval методом каждого класса выражений вместо того, чтобы реализовывать ее как функцию вне иерархии классов выражений, как мы делали прежде. Поскольку eval теперь — метод всех классов выражений, классификация и методы доступа становятся излишними, и реализация сильно упрощается:

abstract class Expr {
  def eval: Int
}
class Number(n: Int) extends Expr {
  def eval: Int = n }
class Sum(e1: Expr, e2: Expr) extends Expr {
  def eval: Int = e1.eval + e2.eval
}

Более того, добавление нового класса Prod не ведет к изменениям существующего кода:

class Prod(e1: Expr, e2: Expr) extends Expr {
  def eval: Int = e1.eval * e2.eval
}

Из этого примера мы можем сделать вывод, что объектно-ориентированная организация — это лучшим подход для создания систем, которые должны быть расширяемы новыми типами данных. Но есть и другой способ, которым мы можем захотеть расширить пример с выражениями. Мы можем также захотеть добавить новые операции с выражениями. Например, добавить операцию, которая выводит на экран вывода дерево выражения.

Если мы определили классификацию и методы доступа, такую операцию можно легко написать в виде внешней функции. Вот пример:

def print(e: Expr) {
  if (e.isNumber) Console.print(e.numValue)
  else if (e.isSum) {
    Console.print("(")
    print(e.leftOp)
    Console.print("+")
    print(e.rightOp)
    Console.print(")")
  } else error("неопознанный тип выражения")
}

Но если мы выбрали объектно-ориентированную организацию выражений, нам потребуется добавлять новую процедуру print к каждому классу:

abstract class Expr {
  def eval: Int
  def print
}
class Number(n: Int) extends Expr {
  def eval: Int = n
  def print { Console.print(n) }
}
class Sum(e1: Expr, e2: Expr) extends Expr {
  def eval: Int = e1.eval + e2.eval
  def print {
    Console.print("(")
    print(e1)
    Console.print("+")
    print(e2)
    Console.print(")")
  }
}

Обратите внимание, что классический объектно-ориентированный подход требует модификации всех существующих классов, когда система расширяется новой операцией.

Вот еще один способ, которым мы можем хотеть расширить интерпретатор. Рассмотрим упрощение выражений. Например, мы хотим написать функцию, которая переписывает выражение из формы a * b + a * c в форму a * (b + c). Эта операция требует смотреть больше чем на один узел дерева выражения одновременно. Это нельзя реализовать при помощи метода в каждом типе выражений, если только этот метод не рассматривает и другие узлы. Так что мы вынуждены заводить классификацию и методы доступа в этом случае. Это опять возвращает нас к началу и ко всем проблемам расширяемости и необходимости написания большого количества кода.

Если присмотреться, можно заметить, что единственный смысл классификации и функций доступа в том, чтобы обратить процесс конструирования данных. Они позволяют нам определять, во-первых, какой подкласс абстрактного класса использован, и во-вторых, каковы были аргументы конструктора. Поскольку эта ситуация довольно часть встречается, в Scala есть способ ее автоматизации при помощи case-классов.

Case-классы и case-объекты

Case-классы и case-объекты (вариации) определяются как обычные классы и объекты, за исключением того, что перед определением ставится модифиатор case. Например, определения

abstract class Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr

вводят Number и Sum как case-классы. Модификатор case перед определением класса имеет следующие эффекты:

1. У case-классов есть неявная функция конструктора, одноименная с классом. В нашем примере будут добавлены эти две функции:

def Number(n: Int) = new Number(n)
def Sum(e1: Expr, e2: Expr) = new Sum(e1, e2)

Теперь можно конструировать деревья выражений немного более кратко:

Sum(Sum(Number(1), Number(2)), Number(3))

2. У case-классов и case-объектов есть неявные реализации методов toString, equals и hashCode, которые переписывают одноименные методы класса AnyRef. Реализация этих методов принимает во внимание структуру членов case-класса в каждом случае. Метод toString представляет дерево выражения так, как оно было сконструировано. Поэтому

Sum(Sum(Number(1), Number(2)), Number(3))

будет преобразовано в точно такую же строку, тогда как реализация метода toString в классе AnyRef по умолчанию вернула бы строку, состоящую из имени самого внешнего конструктора Sum и числа. Метод equals считает два две сущности case-класса равными, если они были сконструированы одинаковыми конструкторами с попарно равными аргументами. Это также влияет на реализацию == и !=, которые реализованы в Scala в терминах equals. Итак,

Sum(Number(1), Number(2)) == Sum(Number(1), Number(2))

даст в ответе true. Если бы Number и Sum не были case-классами, то же самое выражение давало бы false, поскольку стандартная реализация equals в классе AnyRef всегда рассматривает объекты, созданные разными вызовавами конструктора, как разные. Метод hashCode следует тому же принципу, как остальные два метода. Он считает хэшкод имени конструктора case-класса и хэшкоды аргументов конструктора вместо того, чтобы брать адрес объекта, как это делает реализация hashCode по умолчанию.

3. У case-классов есть неявный нульарный метод, возвращающий аргументы конструктора. В нашем примере у Number появится метод доступа

def n: Int

который возвращает параметр конструктора n, а у Sum — два метода

def e1: Expr, e2: Expr

Заметьте, что для значения s типа Sum теперь можно писать s.e1 для доступа к левому операнду. Но для значения e типа Expr выражение e.e1 будет некорректно, потому что e1 определен в Sum и не является методом класса Expr. Итак, как определить конструктор и получить доступ к аргументам конструктора для значений, чей статический тип — базовый класс Expr? Это решается четвертым и последним пунктом.

4. Сase-классы разрешают конструкцию образцов (patterns), которые относятся к конструкторам case-классов.

Сопоставление с образцом

Сопоставление с образцом это обобщение выражения switch в C или Java для иерархий классов. Вместо выражения switch есть стандартный метод match, определенный в корневом классе Scala Any, и поэтому он доступен для всех объектов. Метод match принимает в качестве аргументов несколько случаев. Например, вот реализация eval при помощи сопоставления с образцом:

def eval(e: Expr): Int = e match {
  case Number(n) => n
  case Sum(l, r) => eval(l) + eval(r)
}

В этом примере есть два случая. Каждый случай сопоставляет образец с выражением. Образцы сопоставляются со значениями селектора e. Первый образец в нашем примере, Number(n), соответствует всем значениями вида Number(v), где v — произвольное значение. В этом случае переменная образца n связывается со значением v. Аналогично, образец Sum(l, r) соответствует всем значениям селектора вида Sum(v₁, v₂) и связывает переменные образца l и r с v₁ и v₂ соответственно.

В общем, образцы строятся из:

конструкторов case-классов, как Number и Sum, чьи аргументы также являются образцами,
переменных образцов, как n, e1, e2,
образца подстановочного символа (wildcard) _,
литералов, как 1, true, "abc",
идентификаторов констант, как MAXINT, EmptySet.

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

Смысл cопоставления с образцом

Выражение cопоставления с образцом

e match { case p1 => e1 … case p_n => e_n }

сопоставляет образцы p₁, …, p_n в том порядке, в котором они написаны, со значением селектора e.

Образец конструктора С(p₁, …, p_n) соответствует всем значениям типа C (или его подтипа), которые были созданы при помощи аргументов C, соответствующих образцам p₁, …, p_n.
Образец переменной x соответствует любому значению и связывает имя переменной с этим значением.
Образец подстановочного символа ‘_’ соотвтествует любому значению, но не связывает имени с этим значением.
Образец константы C соответствует значению, равному (в терминах ==) C.

Выражение сопоставления с образцом переписывает правую часть первого случая, чей образец соответствует значению селектора. Ссылки на переменные образца заменяются соответствующими аргументами конструктора. Если ни один из образцов не подошел, выражение сопоставления с образцом завершается с исключением MatchError.

Пример 7.2.1 Наша модель подстановки для вычисления программ довольно естественно расширяется для сопоставления с образцом. Например, вот как переписывается применение eval к простому выражению:

  eval(Sum(Number(1), Number(2)))

-> (перепишем применение функции)

  Sum(Number(1), Number(2)) match {
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
  }

-> (перепишем сопоставление с образцом)

  eval(Number(1)) + eval(Number(2))

-> (перепишем первое применение)

  Number(1) match {
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
  } + eval(Number(2))

-> (перепишем сопоставление с образцом)

  1 + eval(Number(2))

->* 1 + 2 -> 3

Сопоставление с образцом и методы

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

abstract class Expr {
  def eval: Int = this match {
    case Number(n) => n
    case Sum(e1, e2) => e1.eval + e2.eval
  }
}

Упражнение 7.2.2 Рассмотрим следующие определения, представляющие деревья целых чисел. Эти определения можно рассматривать как альтернативное представление IntSet:

abstract class IntTree
case object EmptyTree extends IntTree
case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree

Закончите следующие реализации функций contains и insert для IntTree:

def contains(t: IntTree, v: Int): Boolean = t match { …
  …
}
def insert(t: IntTree, v: Int): IntTree = t match { …
  …
}

Анонимные функции сопоставления с образцом

До этого case-выражения всегда появлялись вместе с оператором match. Но можно также использовать case-выражения сами по себе. Блок case-выражений, такой как

{ case P₁ => E₁ … caseP_n => E_n }

это функция, которая сопоставляет свои аргументы с образцами P₁, …, P_n, и возвращает одно из выражений E₁, …, E_n. (Если ни один образец не подошел, функция вместо этого выбросит исключение MatchError). Другими словами, выражение сверху это короткая запись анонимной функции

(x => x match { case P₁ => E₁ … case P_n => E_n })

где x это свежая переменная, которая не используется нигде кроме этого выражения.

Обобщенные типы и методы

Классы в Scala могут иметь типовые параметры. Мы продемонстрируем использование типовых параметров на примере функциональных стеков. Скажем, нам нужно написать тип данных для стеков целых чисел с методами push, top, pop и isEmpty. Это можно сделать при помощи следующей иерархии классов:

abstract class IntStack {
  def push(x: Int): IntStack = new IntNonEmptyStack(x, this)
  def isEmpty: Boolean
  def top: Int
  def pop: IntStack
}

class IntEmptyStack extends IntStack {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}

class IntNonEmptyStack(elem: Int, rest: IntStack) extends IntStack {
  def isEmpty = false
  def top = elem
  def pop = rest
}

Конечно, имеет смысл также определить абстракцию для стека строк. Чтобы это сделать, можно взять существующую абстракцию для стека целых чисел, переименовать ее с IntStack в StringStack и в то же время заменить все встречающиеся упоминания типа Int на String.

Более хороший способ, который не приводит к повторению кода, это параметризовать определение стека по типу элементов. Параметризация позволяет обобщать проблему с конкретной до более общей. Пока что мы использовали только параметризацию по значению, но можно делать ее и по типам. Чтобы прийти к обобщенной (generic) версии стека, снабдим класс Stack типовым параметром.

abstract class Stack[A] {
  def push(x: A): Stack[A] = new NonEmptyStack[A](x, this)
  def isEmpty: Boolean
  def top: A
  def pop: Stack[A]
}

class EmptyStack[A] extends Stack[A] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}

class NonEmptyStack[A](elem: A, rest: Stack[A]) extends Stack[A] {
  def isEmpty = false
  def top = elem
  def pop = rest
}

В данном определении 'A' это типовой параметр класса Stack и его подклассов. Типовые параметры это произвольные имена; они заключены в квадратные, а не круглые скобки, чтобы их было просто отличить от параметров значений. Вот пример использования обобщенного класса:

val x = new EmptyStack[Int]
val y = x.push(1).push(2)
println(y.pop.top)

Первая строка создает новый пустой стек целых чисел. Заметьте, что действительный типовой аргумент [Int] заменен формальным типовым параметром A.

Возможно также параметризовать методы по типам. Вот, к примеру, обобщенный метод, который определяет, является ли один стек префиксом другого:

def isPrefix[A](p: Stack[A], s: Stack[A]): Boolean = {
  p.isEmpty ||
  p.top == s.top && isPrefix[A](p.pop, s.pop)
}

Параметры этого метода называются полиморфными. Обобщенные методы также называются полиморфными. Этот термин пришел из греческого языка, на котором он значит «имеющий много форм». Чтобы применить такой полиморфный метод, как isPrefix, надо передать ему типовые параметры так же, как и параметры значений. Например,

val s1 = new EmptyStack[String].push("abc")
val s2 = new EmptyStack[String].push("abx").push(s1.top)
println(isPrefix[String](s1, s2))

Локальный вывод типов. Постоянная передача такого типового параметра, как [Int] или [String], может стать утомительной в приложениях, где обобщенные функции много используются. Довольно часто информация, содержащаяся в типовом параметре, избыточна, потому что правильный типовой параметр может быть определен также при рассмотрении параметров значений и ожидаемого типа результата функции. Возьмем к примеру выражение isPrefix[String](s1, s2). Мы знаем, что оба его параметра значений имеют тип Stack[String], так что мы можем понять, что типовой параметр должен быть String. У Scala довольно мощная система вывода типов, которая позволяет опускать типовые параметры полиморфных функций и конструкторов в подобных ситуациях. В приведенном примере можно было бы написать isPrefix(s1, s2), и отсутствующий типовой аргумент [String] был бы вставлен системой вывода типов.

Ограничения типовых параметров

Теперь, когда мы знаем, что как делать классы обобщенными, естественно было бы обобщить некоторые из классов, что мы написали раньше. Например, класс IntSet может быть обобщен до множеств с произвольным типом элементов. Давайте попробуем это сделать. Абстрактный класс для обобщенных множеств пишется просто:

abstract class Set[A] {
  def incl(x: A): Set[A]
  def contains(x: A): Boolean
}

Но если мы по-прежнему хотим реализовать множества в виде двоичных деревьев поиска, у нас проблема. Методы contains и incl сравнивают элементы при помощи методов < и >. Для IntSet это было приемлемо, поскольку у типа Int есть оба этих метода. Но для произвольного типового параметра A мы не можем этого гарантировать. Следовательно, предыдущая реализации, например, метода contains приведет к ошибке компилятора.

def contains(x: Int): Boolean =
  if (x < elem) left contains x
        ^ < не является методом типа A.

Первый способ решить эту проблему — ограничить допустимые типы, которые могут быть подставлены вместо типа A, теми, которые содержать методы < и > соответствующих типов. В стандартной библиотеке классов Scala есть трейт Ordered[A], которые представляет значения, которые можно сравнивать (при помощи < и >) со значениями типа A. Этот трейт определен так:

/** Класс для полностью упорядоченных данных. */
trait Ordered[A] {

  /** Результат сравнения ‘this’ с операндом ‘that’
    * возвращает ‘x’, где
    * x < 0 iff this < that
    * x == 0 iff this == that
    * x > 0 iff this > that
    */
  def compare(that: A): Int

  def <(that: A): Boolean = (this compare that) < 0
  def >(that: A): Boolean = (this compare that) > 0
  def <=(that: A): Boolean = (this compare that) <= 0
  def >=(that: A): Boolean = (this compare that) >= 0
  def compareTo(that: A): Int = compare(that)
}

Мы можем потребовать сравниваемость типа, обозначив, что он является подтипом Ordered. Это делается введением верхней границы для типового параметра Set:

trait Set[A <: Ordered[A]] {
  def incl(x: A): Set[A]
  def contains(x: A): Boolean
}

Обозначение параметра A <: Ordered[A] говорит, что A это типовой параметр, который должен быть подтипом Ordered[A], то есть его значения должны быть сравнимы со значениями того же типа.

С этим ограничением мы можем реализовать остальные компоненты абстракции обобщенного множества, как мы делали в случае IntSet ранее:

class EmptySet[A <: Ordered[A]] extends Set[A] {
  def contains(x: A): Boolean = false
  def incl(x: A): Set[A] = new NonEmptySet(x, new EmptySet[A], new EmptySet[A])
}

class NonEmptySet[A <: Ordered[A]](elem: A, left: Set[A], right: Set[A]) extends Set[A] {
  def contains(x: A): Boolean =
    if (x < elem) left contains x
    else if (x > elem) right contains x
    else true
  def incl(x: A): Set[A] =
    if (x < elem) new NonEmptySet(elem, left incl x, right)
    else if (x > elem) new NonEmptySet(elem, left, right incl x)
    else this
}

Обратите внимание, что мы опустили типовые аргументы в создании объектов NonEmptySet(…). Так же, как и для полиморфных методов, пропущенные типовые аргументы в вызовах конструкторов выводятся из аргументов значений и/или из ожидаемого типа результата.

Ниже приведен пример, в котором используется абстракция обобщенного множества. Для начала создадим подкласс Ordered:

case class Num(value: Double) extends Ordered[Num] {
  def compare(that: Num): Int =
    if (this.value < that.value) -1
    else if (this.value > that.value) 1
    else 0
}

Затем:

val s = new EmptySet[Num].incl(Num(1.0)).incl(Num(2.0))
s.contains(Num(1.5))

Это корректно, поскольку тип Num реализует трейт Ordered[Num]. Хотя этот пример приведет к ошибке:

val s = new EmptySet[java.io.File]
                    ^ java.io.File не удовлетворяет границе
                      типового параметра Ordered[java.io.File].

Проблема, связанная с ограничениями типовых параметров, состоит в том, что их нужно обдумывать заранее: если бы мы не объявили, что Num это подкласс Ordered, мы бы не смогли использовать во множествах элементы типа Num. По той же причине типы, унаследованные из Java, такие, как Int, Double или String не являются подклассами Ordered, поэтому значения этих типов не могут быть использованы во множествах.

Более гибкий вариант, который допускает элементы этих типов, использует ограничения по видимости (view bounds) вместо простых ограничений по типам, которые мы видели раньше. Единственное изменение, которое нужно будет внести в наш пример, — в типовых параметрах:

trait Set[A <% Ordered[A]] …
class EmptySet[A <% Ordered[A]] …
class NonEmptySet[A <% Ordered[A]] …

Ограничения по видимости <% слабее простых ограничений <:. Выражение ограничения типового параметра по видимости [A % T] говорит только, что ограниченный тип A должен быть приводим к типу T при помощи неявных (имплицитных) преобразований.

Библиотека Scala предопределяет неявные преобразования для некоторых типов, включая примитивные типы и String. Поэтому наша новая абстракция множеств может быть использована и с этими типами. Больше объяснений про неявные преобразования и ограничения по видимости даны в Главе 15.

Аннотации вариантности

Сочетание типовых параметров и подтипов поднимает некоторые интересные вопросы. Например, должен ли Stack[String] быть подтипом Stack[AnyRef]? Интуитивно это выглядит правильно, поскольку стек элементов типа String это специальный случай стека AnyRef. Более обобщенно, если T является подтипом типа S, то Stack[T] должен быть подтипом Stack[S]. Это называется ковариантным подтипированием.

В Scala обобщенные типы по умолчанию невариантны. Это значит, что если Stack определен так, как выше, стеки с элементами разных типов никогда не будут подтипами друг друга. Впрочем, мы можем организовать ковариантное подтипирование стеков, изменив первую строку определение класса Stack следующим образом:

class Stack[+A] {

Символ '+' перед формальным типовым параметром говорит, что подтипирование ковариантно по этому параметру. Помимо '+' есть еще префикс '-', который указывает на контравариантное подтипирование. Если Stack определен как class Stack[-A] …, то есть, если T является подтипом S, то Stack[S] является подтипом Stack[T] (что в случае стеков было бы довольно удивительно!).

В чисто функциональном мире все типы могут быть ковариантны. Но ситуация меняется, когда мы вводим изменяемые состояния. Рассмотрим массивы в Java или .NET. Такие массивы представлены в Scala обобщенным классом Array. Вот частичное определение этого класса:

class Array[A] {
  def apply(index: Int): A
  def update(index: Int, elem: A)
}

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

В Java массивы действительно ковариантны, то есть, для ссылочных типов T и S, если T является подтипом S, то и Array[T] является подтипом Array[S]. Это может выглядеть естественно, но оно ведет к проблемам безопасности, из-за которых нужно проводить специальные проверки во время выполнения программы. Вот пример:

val x = new Array[String] (1)
val y: Array[Any] = x
y(0) = new Rational (1, 2) // это синтаксический сахар для
                           // y.update(0, new Rational(1, 2))

В первой строке создается новый массив строк. Во второй строке этот массив присваивается переменной y типа Array[Any]. В предположении, что массивы коварианты, это допустимая операция, поскольку Array[String] будет подтипом Array[Any]. Наконец, в последней строке в массив записывается рациональное число. Это тоже допустимо, поскольку тип Rational является подтипом типа элементов массива y, Any. То есть, мы придем к сохранению рационального числа в массив строк, что, очевидно, нарушает корректность типов.

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

Scala решает эту проблему статически, запрещая вторую строку во время компиляции, потому что массивы в Scala невариантны. Возникает вопрос, как компилятор Scala проверяет, что вариантность корректна? Если бы мы просто объявили массивы ковариантными, как бы он заметил потенциальную проблему?

Чтобы проверить корректность аннотации вариантности, Scala использует консервативное приближение. Ковариантный типовой параметр класса может появляться только в ковариантной позиции внутри класса. Среди ковариантных позиций: типы неизменяемых переменных в классе, результрующие типы методов в классе и типовые аргументы других ковариантных типов. Нековариантны типы формальных параметров методов. Скажем, следующее определение класса не будет разрешено:

class Array[+A] {
  def apply(index: Int): A
  def update(index: Int, elem: A)
                               ^ ковариантный типовой параметр A
                                 появляется в контравариантной позиции.
}

Пока все в порядке. Интуитивно, компилятор был прав, запретив процедуру update в ковариантном классе, потому что update может изменить состояние, и поэтому ставит под угрозу корректность ковариантного подтипирования.

Также существуют методы, которые не меняют состояние, но в которых типовой параметр тоже появляется контравариантно. Пример тому — метод push в типе Stack. Опять же, компилятор Scala запретит определение этого метода для ковариантных стеков:

class Stack[+A] {
  def push(x: A): Stack[A] =
              ^ ковариантный типовой параметр A
                появляется в контравариантной позиции.
}

Жаль, что так происходит, потому что, в отличие от массивов, стеки — чисто функциональные структуры данных и поэтому должны позволять ковариантное подтипирование. Впрочем, есть способ решить эту проблему, используя полиморфные методы с нижними границами типовых параметров.

Нижние границы

Ранее мы видели верхние границы для типовых параметров. В объявлении типового параметра, например, T <: U, диапазон значений типового параметра T ограничен подтипами типа U. Симметрично этому в Scala есть нижние границы. В объявлении типового параметра T >: S диапазон значений типового параметра T ограничен супертипами типа S. (Можно также сочетать нижние и верхние границы, например, T >: S <: U.)

Используя нижние границы, можно обобщить метод push класса Stack следующим образом:

class Stack[+A] {
  def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)

Технически такой прием решает проблему с вариантностью, потому что теперь типовой параметр A больше не появляется как тип параметра метода push. Вместо этого он появляется как нижняя граница для другого типового параметра, который стоит в ковариантной позиции. Компилятор Scala допустит такое определение метода push.

На самом деле мы не просто решили техническую проблему вариантности, но и обобщили определение push. До этого мы могли применять этот метод только к тем элементам, чьи типы соответствуют объявленному типу стека. Теперь же мы можем вставлять в стек и элементы супертипа того типа, только и тип возвращаемого стека будет соответственно изменяться. Например, теперь мы можем вставлять AnyRef в стек элементов типа String, но полученный стек будет стеком AnyRef, а не стеком String!

В заключение скажем, что не нужно стесняться добавлять аннотации вариантности к вашим структурам данных, потому что это позволяет выражать богатые естественные связи типов и их подтипов. Компилятор заметит потенциальные проблемы корректности. Даже если приближения компилятора слишком консервативны, как в случае метода push класса Stack, этот прием часто может предоставить полезные обобщения методов.

Крайние типы

Scala не позволяет параметризовать объекты по типам. Поэтому мы вначале определили обобщенный класс EmptyStack[A], несмотря на то, что единственного значения, обозначающего пустые стеки произвольного типа, было бы достаточно. Для ковариантных стеков, впрочем, можно использовать следующую конструкцию:

object EmptyStack extends Stack[Nothing] { … }

Нижний граничный тип Nothing не содержит значения, так что тип Stack[Nothing] выражает факт того, что в EmptyStack нет элементов. Помимо этого, Nothing является подтипом всех других типов. Заметьте, что для ковариантных стеков Stack[Nothing] — подтип Stack[T] для любого другого типа T. Поэтому можно использовать лишь единственный объект пустого стека в пользовательском коде. К примеру,

val s = EmptyStack.push("abc").push(new AnyRef())

Давайте детально проанализируем присваивание типа этому выражению. Объект EmptyStack имеет тип Stack[Nothing], у которого есть метод

push[B >: Nothing](elem: B): Stack[B]

Локальный вывод типов определит, что типовой параметр B должен быть String в применении EmptyStack.push("abc"). Результирующий тип этого применения — Stack[String], который, в свою очередь, имеет метод

push[B >: String](elem: B): Stack[B]

Последняя часть определения значения, приведенного выше, это применение этого метода к new AnyRef(). Локальный вывод типов определит, что типовой параметр B должен на этот раз быть AnyRef, с результирующим типом Stack[AnyRef]. То есть, тип, присвоенный значению s — Stack[AnyRef].

Помимо Nothing, который является подтипом всех других типов, есть также тип Null, являющийся подтипом scala.AnyRef и всех классов, наследующих от него. Литерал null в Scala — единственное значение этого типа, что делает этот литерал совместимым со всеми ссылочными типами, но не с типами значений, таких, как Int.

Мы завершим этот параграф полным улучшенным определением стеков. Теперь у них ковариантное подтипирование, метод push обобщен, и пустой стек представлен единственным объектом.

abstract class Stack[+A] {
  def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)
  def isEmpty: Boolean
  def top: A
  def pop: Stack[A]
}
object EmptyStack extends Stack[Nothing] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}
class NonEmptyStack[+A](elem: A, rest: Stack[A]) extends Stack[A] {
  def isEmpty = false
  def top = elem
  def pop = rest
}

Многие классы в библиотеке Scala — обобщенные. Теперь мы представим два часто используемых семейства обобщенных классов, кортежи и функции. Обсуждение других часто используемых классов, списков, приведено в следующей главе.

Кортежи

Иногда функция должна возвращать больше одного результата. Например, функция divmod, которая возвращает целочисленные частное и остаток от деления двух аргументов. Конечно, можно определить класс для хранения двух результатов divmod:

case class TwoInts(first: Int, second: Int)
def divmod(x: Int, y: Int): TwoInts = new TwoInts(x / y, x % y)

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

package scala
case class Tuple2[A, B](_1: A, _2: B)

С Tuple2 метод divmod можно написать так:

def divmod(x: Int, y: Int) = new Tuple2[Int, Int](x / y, x % y)

Как обычно, типовые параметры конструкторов можно опустить, если они выводимы из аргументов. Есть также кортежные классы для любого другого количества элементов (нынешняя реализация Scala ограничивает кортежи по длине некоторым большим числом).

Как обращаться к элементам кортежей? Поскольку кортежи — это case-классы, есть две возможности. Можно либо обращаться к полям кортежа, используя имена параметров конструктора _i, как в этом примере:

val xy = divmod(x, y)
println("quotient: " + xy._1 + ", rest: " + xy._2)

Либо использовать сопоставление с образцом, как здесь:

divmod(x, y) match {
  case Tuple2(n, d) =>
    println("quotient: " + n + ", rest: " + d)
}

Заметьте, что типовые параметры никогда не используются в образцах, писать caseTuple2[Int, Int](n, d) — нельзя.

Кортежи так удобны, что у Scala есть для них специальный синтаксис. Чтобы сформировать кортеж с n элементами x₁, …, x_n, можно написать (x₁, …, x_n). Такая запись эквивалентна Tuplen(x₁, …, x_n). Синтаксис (…) работает одинаково для кортежей и паттернов. С таким кортежным синтаксисом пример divmod можно записать так:

def divmod(x: Int, y: Int): (Int, Int) = (x / y, x % y)
divmod(x, y) match {
  case (n, d) => println("quotient: " + n + ", rest: " + d)
}

Функции

Scala — функциональный язык в том смысле, что функции — значения первого класса. Scala также объектно-ориентированный язык в том смысле, что каждое значение является объектом. Из этого следует, что функции в Scala являются объектами. Например, функция из типа String в тип Int представлена экземпляром трейта Function1[String, Int]. Трейт Function1 определен так:

package scala
trait Function1[-A, +B] {
  def apply(x: A): B
}

Помимо Function1 есть также определения для функций любой другой арности (нынешняя реализация устанавливает некий разумный предел). То есть, для любого возможного числа параметров есть соответствующее определение. Синтаксис типа функции в Scala (T₁, …, T_n) => S — это просто сокращение для параметризованого типа Functionn[T₁, …, T_n, S].

Scala использует одинаковый синтаксис f(x) для применения функции, вне зависимости от того, является ли f методом или функциональным объектом. Это возможно благодаря следующему соглашению: применение функции f(x), где f — объект (в противоположность методу) это сокращенная форма записи для f.apply(x). Метод apply, принадлежащий типу функций, вставляется автоматически везде, где это необходимо.

Поэтому мы определяли операцию взятия элемента из массива в Параграфе 8.2 при помощи метода apply. Для любого массива a операция взятия элемента a(i) это сокращенная форма записи a.apply(i).

Функции — это пример того, как полезны объявления контравариантных типовых параметров. Рассмотрим, например, следующий код:

val f: (AnyRef => Int) = x => x.hashCode()
val g: (String => Int) = f
g("abc")

Присваивать значение g типа String => Int величине f типа AnyRef => Int — корректно. Действительно, все, что можно сделать с функцией типа String => Int — это передать ей строку, чтобы получить целое число. Очевидно, что то же самое верно для функции f: если мы передадим ей строку (или любой другой объект), мы получим целое число. Это показывает, что подтипирование функций контравариантно по типу аргумента, тогда как оно ковариантно по типу результата. Короче говоря, $S\Rightarrow T$ это подтип $S'\Rightarrow T'$ , если $S'$ — подтип $S$ и $T$ — подтип $T'$ .

Пример 8.6.1 Рассмотрим код:

val plus1: (Int => Int) = (x: Int) => x + 1
plus1(2)

Эта запись может быть развернута так:

val plus1: Function1[Int, Int] = new Function1[Int, Int] {
  def apply(x: Int): Int = x + 1
}
plus1.apply(2)

Здесь создание объекта new Function1[Int, Int]{ … } представляет собой сущность анонимного класса. Оно сочетает создание нового объекта Function1 с реализацией метода apply (который абстрактен в Function1). Эквивалентно, но более многословно можно было бы использовать локальный класс:

val plus1: Function1[Int, Int] = {
  class Local extends Function1[Int, Int] {
    def apply(x: Int): Int = x + 1
  }
  new Local: Function1[Int, Int] }
plus1.apply(2)

Списки

Списки — важные структуры данных во многих программах на Scala. Список, состоящий из элементов x₁, …, x_n, записывается так: List(x₁, …, x_n). Вот примеры:

val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty = List()

Списки похожи на массивы в таких языках, как C или Java, но есть три важных отличия. Во-первых, списки неизменяемы. То есть, элементы списка нельзя менять при помощи присваиваний. Во-вторых, у списков рекурсивная структура, тогда как массивы плоские. В третьих, списки поддерживают гораздо больше операций, чем обычные массивы.

Использование списков

Тип List

Как и массивы, списки гомогенны. Это значит, все элементы списка — одного типа. Тип списка с элементами типа T записывается как List[T] (похоже на T[] в Java).

val fruit: List[String]    = List("apples", "oranges", "pears")
val nums : List[Int]       = List(1, 2, 3, 4)
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty: List[Int]       = List()

Конструкторы списков

Все списки строятся при помощи двух более фундаментальных конструкторов, Nil и :: (произвносится «cons»). Nil выражает пустой список. Инфиксный оператор :: выражает продление списка. То есть, x :: xs выражает список с первым элементом x, за которым идут элементы списка xs. Значения списков, приведенные выже, могут быть определены так (на самом деле, их предыдущие определения это синтаксический сахар для определений ниже):

val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums  = 1 :: (2 :: (3 :: (4 :: Nil)))
val diag3 = (1 :: (0 :: (0 :: Nil))) ::
            (0 :: (1 :: (0 :: Nil))) ::
            (0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil

Оператор ‘::’ правоассоциативен: A :: B :: C интерпретируется как A :: (B :: C). То есть, мы можем опустить скобки в определениях. Например, мы можем записать более коротко

val nums = 1 :: 2 :: 3 :: 4 :: Nil

Базовые операции со списками

Все операции со списками можно выразить при помощи следующих трех конструкций:

head — возвращает первый элемент списка;
tail — возвращает список, состоящий из всех элементов за исключением первого;
isEmpty — возвращает true тогда и только тогда, когда список пуст.

Эти операции определены как методы объектов-списков. Их можно вызвать, выбрав из списка, с которым мы работаем. Примеры:

empty.isEmpty = true
fruit.isEmpty = false
fruit.head = "apples"
fruit.tail.head = "oranges"
diag3.head = List(1, 0, 0)

Методы head и tail определены только для непустых списков. Когда они выбраны из пустого списка, они выбрасывают исключение.

В качестве примера работы со списками рассмотрим сортировку элементов списка чисел в возрастающем порядке. Простой способ сделать это — сортировка вставками, которая работает так: чтобы отсортировать непустой список с первым элементом x и остальными элементами xs, отсортируем оставшийся список xs и вставим элемент x на правильную позицию в результат. Сортировка пустого списка дает пустой список. Запишем это на Scala:

def isort(xs: List[Int]): List[Int] =
  if (xs.isEmpty) Nil
  else insert(xs.head, isort(xs.tail))

Упражнение 9.1.1 Реализуйте недостающую функцию insert.

Образцы списков

На самом деле, оператор :: определен как case-класс в стандартной библиотеке Scala. Возможно раскладывать списки при помощи сопоставления с образцом, используя образцы, составленные из конструкторов Nil и ::. Например, isort можно написать так:

def isort(xs: List[Int]): List[Int] = xs match {
  case List() => List()
  case x :: xs1 => insert(x, isort(xs1))
}

где

def insert(x: Int, xs: List[Int]): List[Int] = xs match {
  case List() => List(x)
  case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
}

Определение класса List I: методы первого порядка

Списки не встроены в Scala, они определены при помощи абстрактного класса List, у которого есть два подкласса для :: и Nil. Далее мы подробно рассмотрим класс List.

package scala
abstract class List[+A] {

List — абстрактный класс, так что нельзя определять элементы, вызывая пустой конструктор List (например, при помощи new List). У класса есть типовой параметр A. Класс ковариантен по этому параметру, то есть, List[S] <: List[T] для всех типов S и T, таких что S <: T. Класс расположен в пакете scala. Этот пакет содержит наиболее важные стандартные классы Scala. List определяет несколько методов, объясненных ниже.

Разложение списка

Во-первых, есть три базовых метода: isEmpty, head, tail. Их реализации в терминах сопоставления с образцом довольно просты:

def isEmpty: Boolean = this match {
  case Nil => true
  case x :: xs => false
}
def head: A = this match {
  case Nil => error("Nil.head")
  case x :: xs => x
}
def tail: List[A] = this match {
  case Nil => error("Nil.tail")
  case x :: xs => xs
}

Следующая функция считает длину списка:

def length: Int = this match {
  case Nil => 0
  case x :: xs => 1 + xs.length
}

Упражнение 9.2.1 Напишите хвостово-рекурсивную версию length.

Следующие две функции дуальны head и tail:

def last: A
def init: List[A]

xs.last возвращает последний элемент списка xs, а xs.init — все элементы xs, кроме последнего. Обе эти функции проходят весь список, и поэтому менее эффективны, чем их аналоги head и tail. Вот реализация last:

def last: A = this match {
  case Nil      => error("Nil.last")
  case x :: Nil => x
  case x :: xs  => xs.last
}

Реализация init аналогична.

Следующие три функции возвращают префикс списка, его суффикс или и то, и другое.

def take(n: Int): List[A] =
  if (n == 0 || isEmpty) Nil else head :: tail.take(n-1)

def drop(n: Int): List[A] =
  if (n == 0 || isEmpty) this else tail.drop(n-1)

def split(n: Int): (List[A], List[A]) = (take(n), drop(n))

(xs take n) возвращает первые n элементов списка xs или весь список, если его длина меньше n. (xs drop n) возвращает все элементы xs, кроме первых n. Наконец, (xs split n) возвращает пару, состоящую из списков результатов xs take n и xs drop n.

Следующая функция возвращает элемент на данной позиции в списке (аналогично взятию элемента из массива). Индексы начинаются с 0.

def apply(n: Int): A = drop(n).head

У метода apply в Scala специальное значение. Объект с этим методом может быть применен к аргументам, как если бы он был функцией. Например, чтобы выбрать третий элемент списка xs, можно написать или xs.apply(3), или xs(3) — второй вариант раскрывается в первый.

С take и drop мы можем создавать списки, состоящие их последовательных элементов данного списка. Чтобы создать список из элементов xs_m, …, xs_n-1 списка xs, используйте

xs.drop(m).take(n - m)

Сшивание списков

Следующая функция делает из двух списков список пар. Если даны два списка, xs = List(x₁, …, x_n) и ys = List(y₁, …, y_n), xs zip ys создает список List((x₁, y₁), …, (x_n, y_n)). Если у двух списков были разные длины, длинный список обрежется. Вот определение zip, обратите внимание, что это полиморфный метод:

def zip[B](that: List[B]): List[(a,b)] =
  if (this.isEmpty || that.isEmpty) Nil
  else (this.head, that.head) :: (this.tail zip that.tail)

Продолжение списка

Как и любой инфиксный оператор, :: также реализован как метод объекта. В этом случае объект — это удлиняемый список. Это возможно, потому что операторы, заканчивающиеся на символ ‘:’, обрабатываются в Scala специальным образом. Все такие операторы рассматриваются как методы своих правых операндов. Например, x :: y = y.::(x), тогда как x + y = x.+(y).

Заметьте, однако, что операнды бинарной операции в каждом случае вычисляются слева направо. Так что, если D и E — выражение с возможными побочными эффектами, D :: E транслируется в {val x = D; E.::(x)}, чтобы сохранить порядок вычисления операндов слева направо.

Другое отличие между операторами, заканчивающимися на ‘:’, и другими операторами относится к их ассоциативности. Операторы, заканчивающиеся на ‘:’, правоассоциативны, тогда как остальные — левоассоциативны. То есть, x :: y :: z = x :: (y :: z), тогда как x + y + z = (x + y) + z.

Определение :: как метода класса List:

def ::[B >: A](x: B): List[B] = new scala.::(x, this)

Заметьте, что :: определен для всех элементов x типа B и списков типа List[A], таких что тип B — супертип типа A. Результатом в этом случае будет список элементов типа B. Это выражается типовым параметром B с нижней границей A в сигнатуре ::.

Конкатенация списков

Операция конкатенации похожа на :: и записывается :::. Результат выполнения (xs ::: ys) — список, состоящий их всех элементов xs, за которыми следуют все элементы ys. Поскольку оператор заканчивается на двоеточие, ::: правоассоциативен и рассматривается как метод своего правого операнда. Следовательно,

xs ::: ys ::: zs = xs ::: (ys ::: zs)
                 = zs.:::(ys).:::(xs)

Ниже приведена реализация метода :::.

def :::[B >: A](prefix: List[B]): List[B] = prefix match {
  case Nil => this
  case p :: ps => this.:::(ps).::(p)
}

Обращение списка

Еще одна полезная операция это обращение списка. В List для этого есть метод reverse. Попробуем его реализовать:

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil => Nil
  case x :: xs => reverse(xs) ::: List(x)
}

Эта реализация хороша тем, что она проста, но она не очень эффективна. Действительно, конкатенация выполняется для каждого элемента списка. Конкатенация списка занимает время, пропорциональное длине первого операнда. Следовательно, сложность reverse(xs): n + (n — 1) + … + 1 = n (n + 1) / 2, где n — длина xs. Может ли реализовать reverse более эффективно? Позже мы увидим, что есть другая реализация, которая имеет линейную сложность.

Пример: сортировка слиянием

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

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

Для общей реализации сортировки слиянием мы все равно должны указать тип элементов списка, который нужно отсортировать, а также функцию, используемую для сравнения элементов. Мы получим максимально обобщенную функцию, передавая их в качестве параметров. Это приводит к такой реализации:

def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {
  def merge(xs1: List[A], xs2: List[A]): List[A] =
    if (xs1.isEmpty) xs2
    else if (xs2.isEmpty) xs1
    else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
    else xs2.head :: merge(xs1, xs2.tail)
  val n = xs.length/2
  if (n == 0) xs
  else merge(msort(less)(xs take n), msort(less)(xs drop n))
}

Сложность msort — O(N log(N)), где N — длина входного списка. Чтобы понять, почему, заметим, что разделение списка пополам и слияние двух отсортированных списков занимает время, пропорциональное длине аргумента(ов). Каждый рекурсивный вызов msort разделяет количество элементов ввода пополам, поэтому происходит O(log(N)) последовательных рекурсивных вызовов, пока не достигается базовый случай со списками длины 1. Для более длинных списков каждый вызов ведет к двум дальнейшим вызовам. Суммировав, получаем, что на каждом из O(log(N)) уровне вызова каждый элемент начального списка принимает участие в одной операции разделения и одной операции слияния. Сложность каждого уровня вызова пропорциональна O(N). Поскольку есть O(log(N)) уровней, получим, что общая сложность пропорциональна O(N log(N)). Эта сложность не зависит от начального распределения элементов в списке, поэтому сложность в худшем случае такая же, как и в среднем. Поэтому сортировка слиянием — хороший алгоритм для сортировки списков.

Вот пример того, как используется msort:

msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))

Определение msort каррировано, чтобы упростить специализацию этого метода с конкретными функциями сравнения. Например,

val intSort = msort((x: Int, y: Int) => x < y)
val reverseSort = msort((x: Int, y: Int) => x > y)

Определение класса List II: методы высшего порядка

Примеры, которые мы рассмотрели к этому моменту, показывают, что функции работы со списками часто имеют похожие структуры. Мы можем определить несколько шаблонов вычислений со списками, например:

преобразование каждого элемента списка неким образом,
выбор из списка всех элементов, удовлетворяющих критерию,
объединение элементов списка при помощи некого оператора.

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

Отображение для списков

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

def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {
  case Nil => xs
  case x :: xs1 => x * factor :: scaleList(xs1, factor)
}

Этот шаблон может быть обобщен до метода map класса List:

abstract class List[A] { …
  def map[B](f: A => B): List[B] = this match {
    case Nil => this
    case x :: xs => f(x) :: xs.map(f)
}

При помощи map можно написать scaleList более кратко:

def scaleList(xs: List[Double], factor: Double) =
  xs map (x => x * factor)

Для другого примера рассмотрим задачу возврата данного столбца матрицы, которая представлена списком строк, где каждая строка тоже является списком. Это можно сделать при помощи такой функции column:

def column[A](xs: List[List[A]], index: Int): List[A] =
  xs map (row => row(index))

С map тесно связан метод foreach, который применяет данную функцию ко всем элементам списка, но не создает список результатов. То есть, функция применяется только ради своих побочных эффектов. foreach определяется так:

def foreach(f: A => Unit) {
  this match {
    case Nil => ()
    case x :: xs => f(x); xs.foreach(f)
  }
}

Эту функцию можно использовать для вывода на экран всех элементов списка, например:

xs foreach (x => println(x))

Упражнение 9.4.1 Рассмотрим функцию, которая возводит в квадрат все элементы списка и возвращает список с результатами. Закончите следующие два эквивалентных определения squareList:

def squareList(xs: List[Int]): List[Int] = xs match {
  case List() => ??
  case y :: ys => ??
}
def squareList(xs: List[Int]): List[Int] =
  xs map ??

Фильтрация списков

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

def posElems(xs: List[Int]): List[Int] = xs match {
  case Nil => xs
  case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1)
}

Этот шаблон обобщен до метода filter класса List:

def filter(p: A => Boolean): List[A] = this match {
  case Nil => this
  case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
}

При помощи filter можно записать posElems короче следующим образом:

def posElems(xs: List[Int]): List[Int] =
  xs filter (x => x > 0)

Операция, имеющая отношение к фильтрации — проверка, удовлетворяют ли все элементы списка некому критерию. Можно также задаться дуальным вопросом, содержится ли в списке элемент, удовлетворяющий некому критерию. Эти операции воплощены в функциях высшего порядка forall и exists класса List.

def forall(p: A => Boolean): Boolean =
  isEmpty || (p(head) && (tail forall p))
def exists(p: A => Boolean): Boolean =
  !isEmpty && (p(head) || (tail exists p))

Чтобы проиллюстрировать, как используется forall, рассмотрим вопрос, является ли число простым. Число n — простое, если оно делится без остатка только на единицу и на самого себя. Самый прямолинейный способ — проверять, равен ли остаток от деления n на все числа от 2 до n не включительно нулю. Список чисел может быть сгенерирован при помощи функции List.range, которая определена в объекте List следующим образом:

package scala
  object List { …
    def range(from: Int, end: Int): List[Int] =
      if (from >= end) Nil else from :: range(from + 1, end)

Например, List.range(2, n) генерирует список всех целых чисел от 2 до n не включительно. Функцию isPrime теперь можно просто определить так:

def isPrime(n: Int) =
  List.range(2, n) forall (x => n % x != 0)

Мы видим, что математическое определение простоты может быть прямо переведено в код на Scala.

Упражнение. Определите forall и exists при помощи filter.

Свертки и редукции списков

Еще одна частая операция — объединение элементов списка при помощи какого-нибудь оператора. Например,

sum(List(x₁, …, x_n)) = 0 + x₁ + … + x_n product(List(x₁, …, x_n)) = 1 * x₁ * … * x_n

Конечно, можно реализовать обе эти функции рекурсивно:

def sum(xs: List[Int]): Int = xs match {
  case Nil => 0
  case y :: ys => y + sum(ys)
}
def product(xs: List[Int]): Int = xs match {
  case Nil => 1
  case y :: ys => y * product(ys)
}

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

List(x₁, …, x_n).reduceLeft(op) = ( … (x₁ op x₂) op … ) op x_n

При помощи reduceLeft можно сделать очевидным общий шаблон в sum и product:

def sum(xs: List[Int])     = (0 :: xs) reduceLeft {(x, y) => x + y}
def product(xs: List[Int]) = (1 :: xs) reduceLeft {(x, y) => x * y}

Вот реализация reduceLeft:

def reduceLeft(op: (A, A) => A): A = this match {
  case Nil => error("Nil.reduceLeft")
  case x :: xs => (xs foldLeft x)(op)
}
def foldLeft[B](z: B)(op: (B, A) => B): B = this match {
  case Nil => z
  case x :: xs => (xs foldLeft op(z, x))(op)
}

Мы видим, что метод reduceLeft определен при помощи другого общеполезного метода foldLeft. Он принимает дополнительным параметром аккумулятор z, который возвращается, когда foldLeft применяется к пустому списку. То есть,

(List(x₁, …, x_n) foldLeft z)(op) = ( … (z op x₁) op … ) op x_n

Методы sum и product могут быть определены и при помощи foldLeft:

def sum(xs: List[Int])     = (xs foldLeft 0) {(x, y) => x + y}
def product(xs: List[Int]) = (xs foldLeft 1) {(x, y) => x * y}

FoldRight и ReduceRight

Применения foldLeft и reduceLeft раскрываются в левые деревья. У них есть дуальные foldRight и reduceRight, которые дают правые деревья.

List(x₁, …, x_n).reduceRight(op) = x₁ op ( … (x_n-1 op x_n) … ) (List(x₁, …, x_n) foldRight acc)(op) = _x1 op ( … (x_n op acc) … )

Они определены следующим образом:

def reduceRight(op: (A, A) => A): A = this match {
  case Nil => error("Nil.reduceRight")
  case x :: Nil => x
  case x :: xs => op(x, xs.reduceRight(op))
}
def foldRight[B](z: B)(op: (A, B) => B): B = this match {
  case Nil => z
  case x :: xs => op(x, (xs foldRight z)(op))
}

Класс List определяет также две символьных аббревиатуры для foldLeft и foldRight:

def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f)
def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f)

Имена методов иллюстрируют левые/правые деревья операции свертки при помощи прямых и обратных слэшей. Двоеточие в каждом случае указывает на список, а конец слэша указывает на аккумулятор z. То есть,

(z /: List(x₁, …, x_n)(op) = ( … (z op x₁) op … ) op x_n (List(x₁, …, x_n) :\ z)(op) = x₁ op ( … (x_n op z) … )

Для ассоциативных и коммутативных операторов /: и :\ эквивалентны (несмотря на то, что в эффективности могут быть различия).

Упражнение 9.4.2 Рассмотрим задачу написания функции flatten, которая принимает список списков элементов в качестве аргументов. Результат flatten должен быть конкатенацией всех элементов списков в один список. Ниже приведена реализация этого метода при помощи :\.

def flatten[A](xs: List[List[A]]): List[A] =
  (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}

Рассмотрим замену тела flatten на

((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)

Какова будет разница в асимптотической сложности между двумя версиями flatten?

На самом деле, flatten предопределен вместе со множеством других полезных функций в объекте List стандартной библиотеки Scala. Его можно вызвать из пользовательской программы при помощи List.flatten. Обратить внимание, что flatten не является методом класса List — это не имело бы смысла, поскольку он применяется только к спискам списков, а не к спискам вообще.

Опять обращение списков

В Параграфе 9.2 мы видели реализацию метода обращения списка reverse, квадратичную от длины входа по времени выполнения. Теперь мы разработаем новую реализацию reverse линейной сложности. Идея в том, чтобы использовать операцию foldLeft, основываясь на следующей схеме:

class List[+A] { …
def reverse: List[A] = (z? /: this)(op?)

Остается только заполнить части z? и op?. Давайте попытаемся вывести их из примеров.

  Nil
= Nil.reverse          // по спецификации
= (z /: Nil)(op)       // по шаблону для обращения
= (Nil foldLeft z)(op) // по определению /:
= z                    // по определению foldLeft

Заметим, что z? должен быть Nil. Чтобы вывести второй операнд, рассмотрим обращение списка единичной длины.

  List(x)
= List(x).reverse            // по спецификации
= (Nil /: List(x))(op)       // по шаблону для обращения с z = Nil
= (List(x) foldLeft Nil)(op) // по определению /:
= op(Nil, x)                 // по определению foldLeft

Следовательно, op(Nil, x) равно List(x), которое равно x :: Nil. То есть, можно взять в качестве op оператор ::, поменяв местами его операнды. Следовательно, у нас получается следующая реализация reverse, и ее сложность линейна:

def reverse: List[A] =
  ((Nil: List[A]) /: this) {(xs, x) => x :: xs}

(Аннотация типа Nil необходима, чтобы обеспечить корректную работу системе вывода типов.)

Упражнение 9.4.3 Вставьте пропущенные выражения, чтобы закончить следующие определения некоторых базовых операций со списками:

def mapFun[A, B](xs: List[A], f: A => B): List[B] =
  (xs :\ List[B]()){ ?? }

def lengthFun[A](xs: List[A]): int =
  (0 /: xs){ ?? }

Вложенные отображения

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

Для примера рассмотрим следующую задачу: дано положительное целое число n, найти все пары положительных чисел i и j, где 1 ≤ j < i < n, таких что i + j — простое число. Например, если n = 7, то пары таковы:

i	2	3	4	4	5	6	6
j	1	2	1	3	2	1	5
i + j	3	5	5	7	7	7	11

Естественный путь решения этой задачи состоит из двух частей. На первом шаге сгенерируем последовательность всех пар целых чисел (i, j), таких что 1 ≤ j < i < n. На втором шаге отфильтруем из этой последовательности все пары (i, j), такие что i + j — простое число.

Посмотрим на первый шаг более детально. Естественный способ генерации последовательности пар состоит из трех подпунктов. Во-первых, сгенерируем все целые числа от 1 до n. Во-вторых, для каждого целого числа i между 1 и n сгенерируем список пар от (i, 1) до (i, i — 1). Это можно сделать при помощи комбинации range и map:

List.range(1, i) map (x => (i, x))

Наконец, скомбинируем все подсписки при помощи foldRight с :::. Объединение всего сказанного дает следующее выражение:

List.range(1, n)
  .map(i => List.range(1, i).map(x => (i, x)))
  .foldRight(List[(Int, Int)]()) {(xs, ys) => xs ::: ys}
  .filter(pair => isPrime(pair._1 + pair._2))

Сглаживающие преобразования

Комбинация преобразования и затем конкатенации подсписков результатов преобразования — настолько частая операция, что для этого есть специальный метод в классе List:

abstract class List[+A] { …
  def flatMap[B](f: A => List[B]): List[B] = this match {
    case Nil => Nil
    case x :: xs => f(x) ::: (xs flatMap f)
  }
}

При помощи flatMap выражение для пар, чья сумма — простое число, можно записать более кратко:

List.range(1, n)
  .flatMap(i => List.range(1, i).map(x => (i, x)))
  .filter(pair => isPrime(pair._1 + pair._2))

Заключение

For-Comprehensions

Задача N ферзей

Очереди с For-Comprehensions

Трансляция For-Comprehensions

Цикл For

Обобщение For

Изменяемое состояние

Объекты с состоянием

Императивные структуры контроля

Расширенный пример: симуляция распределенных событий

Заключение

Вычисления с потоками

В предыдущих главах рассматривались переменные, присваивание и объекты, сохраняющие состояние. Мы видели, как объекты реального мира, которые изменяются со временем, могут быть смоделированы изменением состояния переменных в вычислении. Таким образом временные изменения в реальном мире моделируются временными изменениями в выполнении программы. Конечно, такие временные изменения обычно сокращены или растянуты, но их относительный порядок остается неизменным. Такой подход представляется вполне естественным, но за него приходится платить: наша простая и выразительная модель подстановок для функционального вычисления будет более не применима, если мы введем переменные и присваивание.

Есть ли другой способ? Можем ли мы моделировать изменение состояния в реальном мире, используя лишь функции без побочных эффектов? Руководствуясь математикой, определенно можно дать ответ: «да». Величина, изменяемая со временем, просто представляется функцией f(t) с параметром времени t. То же самое можно проделать с вычислениями, но вместо переписывания переменной последовательностью значений, мы представим все эти значения списком. Так что изменяемая переменная var x: T заменяется неизменяемым значением val x: List[T]. В сущности, мы поменяли память на время — теперь различные значения переменной существуют одновременно, как различные элементы списка. Преимуществом такого подхода будет возможность «путешествия по времени», то есть просмотра нескольких последовательных значений одновременно. Другое преимущество заключается в том, что мы можем использовать мощную библиотеку функций над списками, и это часто упрощает вычисления. Например, рассмотрим императивный способ вычисления суммы всех простых чисел из некоторого интервала:

def sumPrimes(start: Int, end: Int): Int = {
  var i = start
  var acc = 0
  while (i < end) {
    if (isPrime(i)) acc = acc + i
    i = i + 1
  }
  acc
}

Заметьте, переменная i «пробегает» все значения из интервала [start .. end-1].

Более функциональный способ заключается в представлении списка значений i явно, как range(start, end). Тогда функция может быть переписана так:

def sumPrimes(start: Int, end: Int) =
  sum(range(start, end) filter isPrime)

Бесспорно, вторая программа короче и яснее! Однако функциональная программа также и менее эффективна, поскольку она конструирует список чисел из интервала, а затем еще один для простых чисел. Еще хуже с точки зрения эффективности следующий пример.

Требуется найти второе простое число между 1000 и 10000:

range(1000, 10000) filter isPrime at 1

Здесь конструируется список всех чисел между 1000 and 10000. Но большая часть этого списка не будет использована! Но мы можем достичь эффективного выполнения для аналогичных случаев с помощью уловки: избегайте вычисления хвоста последовательности до тех пор, пока он действительно не понадобится.

Определим новый класс Stream (поток) для таких последовательностей. Потоки создаются с помощью константы empty и конструктора cons, которые определены в модуле scala.Stream. Например, следующее выражение создает поток с элементами 1 и 2:

Stream.cons(1, Stream.cons(2, Stream.empty))

Вот другой пример, аналог List.range, возвращающий поток вместо списка:

def range(start: Int, end: Int): Stream[Int] =
  if (start >= end) Stream.empty
  else Stream.cons(start, range(start + 1, end))

(Эта функция, как и предыдущая, тоже определена в модуле Stream). Даже хотя Stream.range и List.range выглядят похоже, их поведение во время выполнения совершенно разное:

Stream.range немедленно возвращает объект Stream, первый элемент которого — start. Все другие элементы вычисляются, только если они потребуются при помощи вызова метода tail (который может никогда не произойти).

Доступ к потокам — такой же, как к спискам. Как и для списков, для потоков определены базовые методы доступа isEmpty, head и tail. Например, распечатать все элементы потока можно так:

def print(xs: Stream[a]) {
  if (!xs.isEmpty) { System.out.println(xs.head); print(xs.tail) }
}

Потоки также поддерживают почти все другие методы, определенные для списков (см. ниже, в чем множества их методов различаются). Например, мы можем найти второе простое число между 1000 и 10000 с помощью методов filter и apply на интервальном потоке:

Stream.range(1000, 10000) filter isPrime at 1

Различие с предыдущей списковой реализацей в том, что теперь нет необходимости конструировать и проверять на простоту числа после 1013.

Склеивание потоков. Два метода из класса List, не поддерживаемые классом Stream это :: и :::. Причина в том, что эти методы раскрываются с правых аргументов, а это означает, что эти аргументы должны быть вычислены до вызова метода. Например, в случае x :: xs на списках, хвост xs должен быть вычислен до вызова оператора :: и конструирования нового списка. Это не работает для потоков, поскольку хвост потока не должен вычисляться, пока не потребуется операции tail. Объяснение, почему метод ::: не адаптируется для потоков — аналогично.

Вместо x :: xs для создания потока с первым элементом x и (невычисленным) остатком xs используют Stream.cons(x, xs). Вместо xs ::: ys используют операцию xs append ys.

Итераторы

Методы итераторов

Создание итераторов

Использование итераторов

Ленивые вычисления

Неявные(имплицитные) параметры и преобразования

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

abstract class SemiGroup[A] {
  def add(x: A, y: A): A
}

А вот подкласс SemiGroup — класс Monoid, который добавляет поле unit (единичный элемент):

abstract class Monoid[A] extends SemiGroup[A] {
  def unit: A
}

Вот две реализации моноидов:

object stringMonoid extends Monoid[String] {
  def add(x: String, y: String): String = x.concat(y)
  def unit: String = ""
}

object intMonoid extends Monoid[Int] {
  def add(x: Int, y: Int): Int = x + y
  def unit: Int = 0
}

Метод суммирования, который работает с произвольными моноидами, может быть написан на чистом Scala следующим образом:

def sum[A](xs: List[A])(m: Monoid[A]): A =
  if (xs.isEmpty) m.unit
  else m.add(xs.head, sum(xs.tail)(m))

Этот метод может быть вызван, например, так:

sum(List("a", "bc", "def"))(stringMonoid)
sum(List(1, 2, 3))(intMonoid)

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

Неявные параметры: основы

В Scala 2 появилось новое ключевое слово implicit, оно может быть использовано в начале списка параметров. Синтаксис:

ParamClauses ::= {‘(’ [Param {‘,’ Param}] ’)’}
                 [‘(’ implicit Param {‘,’ Param} ‘)’]

Если ключевое слово присутствует, то оно делает все параметры в списке неявными. Например, в следующей версии метода sum параметр m является неявным.

def sum[A](xs: List[A])(implicit m: Monoid[A]): A =
  if (xs.isEmpty) m.unit
  else m.add(xs.head, sum(xs.tail))

Как можно заметить из примера, возможно комбинировать обычные и неявные параметры. Однако, для метода или конструктора может быть только один неявный параметр, и он должен быть последним.

Ключевое слово implicit может также быть использовано как модификатор в определениях и объявлениях. Примеры:

implicit object stringMonoid extends Monoid[String] {
  def add(x: String, y: String): String = x.concat(y)
  def unit: String = ""
}

implicit object intMonoid extends Monoid[Int] {
  def add(x: Int, y: Int): Int = x + y
  def unit: Int = 0
}

Основная идея неявных параметров — это то, что аргументы для них могут быть выведены из вызова метода. Если аргументы, отвечающие за секцию неявного параметра, отсутствуют, тогда они выводятся компилятором Scala.

Действительные аргументы, которые могут быть переданы в качестве неявного параметра, — это все идентификаторы X, которые доступны в точке вызова метода без префикса и которые помечены как неявные.

Если существует несколько аргументов, подходящих по типу к неявному параметру, компилятор Scala выберет наиболее точный (специфичный), используя стандартные правила разрешения статической перегрузки. Допустим, вызывается

sum(List(1, 2, 3))

в контексте, где доступны stringMonoid и intMonoid. Мы знаем, что формальный параметр метода sum должен быть типа Int. Единственное значение, подходящее к типу формального параметра Monoid[Int], это intMonoid, поэтому этот объект и будет передан как неявный параметр.

Это обсуждение также показывает, что неявный параметр выводится после того, как выведен какой-нибудь типовой аргумент.

Неявные преобразования

Пусть у вас есть выражение E типа T, хотя ожидается тип S. T не приводится к S ни одним из предопределенных преобразований. Тогда компилятор Scala попытается применить последнее средство: неявное преобразование I(E). Здесь, I — это идентификатор, выражающий неявное определение или параметр, доступный без префикса в точке преобразования, применимый к аргументам типа T и чей результирующий тип совместим с типом S.

Неявные преобразования также могут быть применены в селекторах членов. Получив E.x, где x — не член типа E, компилятор Scala постарается добавить неявное преобразование I(E).x так, чтобы x был членом I(E).

Вот пример неявного преобразования функции, которая преобразует целые числа в экземпляры класса scala.Ordered:

implicit def int2ordered(x: Int): Ordered[Int] = new Ordered[Int] {
  def compare(y: Int): Int =
    if (x < y) -1
    else if (x > y) 1
    else 0
}

View Bounds

View bounds (ограничения по видимости) — это удобный синтаксический сахар для неявных параметров. Рассмотрим обобщенный метод сортировки:

def sort[A <% Ordered[A]](xs: List[A]): List[A] =
  if (xs.isEmpty || xs.tail.isEmpty) xs
  else {
    val (ys, zs) = xs.splitAt(xs.length / 2)
    merge(sort(ys), sort(zs))
}

Ограниченный по видимости параметр типа [A <% Ordered[A]] выражает, что сортировка применима для списков таких типов, для которых существует неявное преобразование A к Ordered[A]. Определение трактуется как укороченный синтаксис для следующей сигнатуры метода с неявным параметром:

def sort[A](xs: List[A])(implicit c: A => Ordered[A]): List[A] = …

(Здесь имя параметра c выбрано произвольно с учетом того, чтобы оно не конфликтовало с другими именами в программе.)

В качестве более детального примера, рассмотрим метод merge, который идет вместе с методом sort:

def merge[A <% Ordered[A]](xs: List[A], ys: List[A]): List[A] =
  if (xs.isEmpty) ys
  else if (ys.isEmpty) xs
  else if (xs.head < ys.head) xs.head :: merge(xs.tail, ys)
  else ys.head :: merge(xs, ys.tail)

После раскрытия ограничений по видимости и вставки неявных преобразований реализация метода принимает вид:

def merge[A](xs: List[A], ys: List[A])
            (implicit c: A => Ordered[A]): List[A] =
  if (xs.isEmpty) ys
  else if (ys.isEmpty) xs
  else if (c(xs.head) < ys.head) xs.head :: merge(xs.tail, ys)
  else if ys.head :: merge(xs, ys.tail)(c)

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

Вывод типов Хиндли-Милнера

Абстракции для многопоточности

В этом разделе рассмотрены стандартные паттерны для параллельного программирования и показано, как они могут быть реализованы в Scala.

Сигналы и мониторы

Пример 17.1.1 В Scala основные средства взаимного исключения процессов обеспечивает монитор. Каждый экземпляр класса AnyRef может быть использован в качестве монитора посредством вызова одного или нескольких из этих методов:

def synchronized[a] (exec: => a): a
def wait(): unit
def wait(msec: Long): unit
def notify(): unit
def notifyAll(): unit

Метод synchronized вычисляет свой аргумент e в режиме взаимного исключения — в любое время только один поток может выполнять аргумент synchronized данного монитора.

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

Есть также форма wait c указанием времени блокировки (в миллисекундах), которая блокирует выполнение только до того момента, когда будет получен сигнал или истечет время. Кроме того, есть метод notifyAll, который разблокирует все потоки, ждущие сигнал. Эти методы, а также класс Monitor являются примитивами в Scala, они реализованы на основе нижележащих системах выполнения.

Обычно поток ждет выполнения некоторого условия. Если условие не выполнено при вызове wait, поток блокируется, пока некоторый другой поток не выполнит условие. И последний отвечает за пробуждение ожидающих потоков посредством вызова notify или notifyAll. Заметьте, что тем не менее нет гарантии, что ожидающий поток начнет исполняться немедленно после вызова notify/notifyAll. Может статься, что другой поток за это время в очередной раз изменит условие запуска, аннулирует его. Следовательно, правильная форма ожидания условия C использует while цикл:

while (!C) wait()

В качестве примера использования мониторов — реализация класса буфера с ограничением:

class BoundedBuffer[a](N: Int) {
  var in = 0, out = 0, n = 0
  val elems = new Array[a](N)

  def put(x: a) = synchronized {
    while (n >= N) wait()
    elems(in) = x ; in = (in + 1) % N ; n = n + 1
    if (n == 1) notifyAll()
  }

  def get: a = synchronized {
    while (n == 0) wait()
    val x = elems(out) ; out = (out + 1) % N ; n = n - 1
    if (n == N - 1) notifyAll()
    x
  }
}

А вот программа, использующая этот буфер для общения между процессами производителя и потребителя:

import scala.concurrent.ops._
…
val buf = new BoundedBuffer[String](10)
spawn { while (true) { val s = produceString ; buf.put(s) } }
spawn { while (true) { val s = buf.get ; consumeString(s) } }

Метод spawn запускает новый поток, который выполняет выражение, переданное в параметре. В объекте scala.concurrent.ops он определяется следующим образом:

def spawn(p: => unit) = {
  val t = new Thread() { override def run() = p; }
  t.start()
}

Синхронизированные переменные

Синхронизированная переменная предлагает методы get и put для чтения и присваивания значения переменной. Операции get блокируют поток, пока переменная не определена. Операция unset сбрасывает переменную в неопределенное состояние.

Вот стандартная реализация синхронизированных переменных:

package scala.concurrent
class SyncVar[A] {
  private var isDefined: Boolean = false
  private var value: A = _
  def get = synchronized {
    while (<tt>isDefined</tt>) wait()
    value
  }
  def set(x: A) = synchronized {
    value = x ; isDefined = true ; notifyAll()
  }
  def isSet: Boolean = synchronized {
    isDefined
  }
  def unset = synchronized {
    isDefined = false;
  }
}

Futures

Future (будущее) — это значение, которое вычисляется параллельно некоторому клиентскому потоку, чтобы быть использованным им немного позже. Future используется для облегчения параллельной обработки ресурсов. Типичное применение:

import scala.concurrent.ops._
…
val x = future(someLengthyComputation)
anotherLengthyComputation
val y = f(x()) + g(x())

Метод future определен в scala.concurrent.ops следующим образом:

def future[A](p: => A): Unit => A = {
 val result = new SyncVar[A]
 fork { result.set(p) }
 (() => result.get)
}

Метод future получает в качестве параметра вычисление p, которое и будет выполняться. Тип вычисления произволен, он обозначен типовым параметром A. Mетод future определяет сторожевое выражение result, которое принимает параметр, представляющий результат вычисления. Затем от ответвляет (fork) новый поток, который вычисляет результат и вызывает сторожевое выражение result по завершении. Параллельно этому потоку future возвращает анонимную функцию типа A. Когда эта функция вызывается, она ждет вызова сторожевого выражения и возвращает результат, когда это случится. В то же время функция вновь вызывает сторожевое выражение result с тем же аргументом, так что дальнейшие вызовы функции смогут возвращать результат немедленно.

Параллельные вычисления

Следующий пример демонстрирует функцию par, которая принимает пару вычислений в качестве параметров и возвращает результаты вычислений в другой паре. Два вычисления выполняются параллельно.

Функция определена в объекте scala.concurrent.ops следующим образом.

def par[A, B](xp: => A, yp: => B): Pair[A, B] = {
  val y = new SyncVar[B]
  spawn { y set yp }
  Pair(xp, y.get)
}

Определенная там же функция replicate выполняет параллельно несколько экземпляров вычисления. Каждому экземпляру передается целое число для идентификации.

def replicate(start: Int, end: Int)(p: Int => Unit): Unit = {
  if (start == end)
    ()
  else if (start + 1 == end)
    p(start)
  else {
    val mid = (start + end) / 2
    spawn { replicate(start, mid)(p) }
    replicate(mid, end)(p)
  }
}

Следующая функция использует replicate для выполнения одновременных вычислений на всех элементах массива.

def parMap[A,B](f: A => B, xs: Array[A]): Array[B] = {
  val results = new Array[B](xs.length)
  replicate(0, xs.length) { i => results(i) = f(xs(i)) }
  results
}

Семафоры

Классический механизм синхронизации процессов — семафор (semaphore, lock). Он предлагает два атомарных действия: занятие и освобождение. Вот реализация простого семафора в Scala:

package scala.concurrent

class Lock {
  var available = true
  def acquire = synchronized {
    while (!available) wait()
    available = false
  }
  def release = synchronized {
    available = true
    notify()
  }
}

Читатели/Писатели

Более сложная форма синхронизации различает читающие потоки, которые имеют доступ к общему ресурсу, не модифицируя его, и потоки, которые могут и читать, и изменять ресурс — писатели. Для того, чтобы синхронизировать читателей и писателей, нам нужно реализовать действия startRead, startWrite, endRead, endWrite так, что:

одновременно может быть несколько читателей,
в любой момент может только быть один писатель,
запись имеет больший приоритет над чтением, но прервать процесс чтения не может.

Следующая реализация читателей/писателей основана на концепции почтового ящика (см. Параграф 17.10).

import scala.concurrent._

class ReadersWriters {
  val m = new MailBox
  private case class Writers(n: Int), Readers(n: Int) { m send this }
  Writers(0); Readers(0)
  def startRead = m receive {
    case Writers(n) if n == 0 => m receive {
      case Readers(n) => Writers(0) ; Readers(n+1)
    }
  }
  def startWrite = m receive {
    case Writers(n) =>
      Writers(n+1)
      m receive { case Readers(n) if n == 0 => }
  }
  def endRead = m receive {
    case Readers(n) => Readers(n - 1)
  }
  def endWrite = m receive {
    case Writers(n) => Writers(n - 1); if (n == 0) Readers(0)
  }
}

Асинхронные каналы

Основной способ межпроцессной связи — асинхронный канал. Его реализация использует следующий простой класс для связанных списков:

class LinkedList[A] {
  var elem: A = _
  var next: LinkedList[A] = null
}

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

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

package scala.concurrent

class Channel[A] {
  class LinkedList[a] {
    var elem: A = _
    var next: LinkedList[A] = null
  }
  private var written = new LinkedList[A]
  private var lastWritten = written
  private var nreaders = 0
  
  def write(x: A) = synchronized {
    lastWritten.elem = x
    lastWritten.next = new LinkedList[A]
    lastWritten = lastWritten.next
    if (nreaders > 0) notify()
  }
  
  def read: A = synchronized {
    if (written.next == null) {
      nreaders = nreaders + 1; wait(); nreaders = nreaders 1
    }
    val x = written.elem
    written = written.next
    x
  }
}

Синхронные каналы

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

package scala.concurrent

class SyncChannel[A] {
  private var data: A = _
  private var reading = false
  private var writing = false
  
  def write(x: A) = synchronized {
    while (writing) wait()
    data = x
    writing = true
    if (reading) notifyAll()
    else while (!reading) wait()
  }
    
  def read: A = synchronized {
    while (reading) wait()
    reading = true
    while (!writing) wait()
    val x = data
    writing = false
    reading = false
    notifyAll()
    x
  }
}

Серверы вычислений

Ниже представлена реализация сервера вычислений в Scala. Сервер реализует метод future, который вычисляет данное выражение параллельно процессу, который вызвал вычисление. В отличие от реализации в Параграфе 17.3, сервер вычисляет future только для предопределенного числа потоков. Возможная реализация сервера могла бы запускать каждый поток на отдельном процессоре, что позволило бы избежать усложнений от переключения контекста между несколькими потоками на одном процессоре.

import scala.concurrent._, scala.concurrent.ops._

class ComputeServer(n: Int) {

  private abstract class Job {
    type T
    def task: T
    def ret(x: T): Unit
  }
  
  private val openJobs = new Channel[Job]()

  private def processor(i: Int): Unit = {
    while (true) {
      val job = openJobs.read
      job.ret(job.task)
    }
  }
     
  def future[A](p: => A): () => A = {
    val reply = new SyncVar[A]()
    openJobs.write{
      new Job {
        type t = A
        def task = p
        def ret(x: A) = reply.set(x)
      }
    }
    () => reply.get
  }
  
  spawn(replicate(0, n) { processor })
}

Выражения, которые нужно выполнять (то есть аргументы future), пишутся в канал для заданий openJobs. Задание (Job) это объект с

абстрактным типом T, который описывает результат вычисления задания,
методом без параметров task типа T, который обозначает выражение, которое должно быть вычислено,
методом ret, который использует результат, как только тот будет вычислен.

Вычислительный сервер создает n процессов processor во время своей инициализации. Каждый такой процессор периодически забирает открытое задание, вычисляет метод task и передает результат на методу ret. Полиморфный метод future создает новое задание, в котором метод ret реализован как сторожевое выражение с именем reply, и вставляет это задание в множество открытых заданий. Затем оно ждет, пока не будет вызван соответствующий reply.

Пример демонстрирует использование абстрактных типов. Абстрактный тип T определяет тип результата задания, который может варьироваться от одного задания к другому. Без абстрактных типов было бы невозможно реализовать подобный класс статически и безопасно по типам без динамической проверки и приведения типов.

Вот пример использования вычислительного сервера для оценки выражения 41 + 1:

object Test with Executable {
  val server = new ComputeServer(1)
  val f = server.future(41 + 1)
  Console.println(f())
}

Почтовые ящики

Почтовые ящики — это высокоуровневые гибкие конструкции для синхронизации и взаимодействия процессов. Они позволяют посылать и получать сообщения. Сообщение в этом контексте — произвольный объект. Есть специальное сообщение TIMEOUT, которое используется для сигнализиации о задержке:

case object TIMEOUT

Почтовые ящики определяют следующие методы:

class MailBox {
  def send(msg: Any): unit
  def receive[A](f: PartialFunction[Any, A]): A
  def receiveWithin[A](msec: Long)(f: PartialFunction[Any, A]): A
}

Содержимое почтового ящика состоит из набора сообщений. Сообщения добавляются в почтовый ящик методом send. Сообщения удаляются посредством метода receive, которому передается обработчик сообщения f как аргумент. f является частичной функцией из сообщений в некоторый произвольный тип. Обычно эта функция реализуется с помощью выражения сопоставления с образцом. Метод receive блокируется, пока в почтовом ящике не появляется сообщение, для которого определен обработчик. Отправленные сообщения и получатели упорядочены во времени. Получатель r применяется к подходящему сообщению m только если нет другой пары (сообщение, получатель), которая предшествует (m, r) в частичном порядке на парах, который упорядочивает во времени каждую компоненту.

Ниже представлен простой пример использования почтовых ящиков. Рассмотрим одноместный буфер:

class OnePlaceBuffer {
  private val m = new MailBox; // Внутренний почтовый ящик
  private case class Empty, Full(x: Int); // Типы сообщений, которые мы обрабатываем
  m send Empty; // Инициализация
  def write(x: Int): unit =
    { m receive { case Empty => m send Full(x) } }
  def read: Int =
    m receive { case Full(x) => m send Empty ; x }
 }

Почтовый ящик может быть реализован так:

class MailBox {
  private abstract class Receiver extends Signal {
    def isDefined(msg: Any): Boolean
    var msg = null
  }
}

Мы определяем внутренний класс для получателей с тестовым методом isDefined, который показывает, определен ли получатель для данного сообщения. Получатель наследует от класса Signal метод notify, который используется, чтобы разбудить поток получателя. Когда поток получателя разбужен, сообщение, к которому он должен примениться, сохраняется в переменной msg класса Receiver.

private val sent = new LinkedList[Any]
private var lastSent = sent
private val receivers = new LinkedList[Receiver]
private var lastReceiver = receivers

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

def send(msg: Any) = synchronized {
  var r = receivers, r1 = r.next
  while (r1 != null && !r1.elem.isDefined(msg)) {
    r = r1; r1 = r1.next
  }
  if (r1 != null) {
    r.next = r1.next; r1.elem.msg = msg; r1.elem.notify
  } else {
    lastSent = insert(lastSent, msg)
  }
}

Метод send сначала проверяет, применим ли ожидающий получатель к отправленному сообщению. Если да, получатель извещается. В противном случае сообщение будет добавлено в связанный список отправленных сообщений.

def receive[A](f: PartialFunction[Any, A]): A = {
  val msg: Any = synchronized {
    var s = sent, s1 = s.next
    while (s1 != null && !f.isDefinedAt(s1.elem)) {
      s = s1; s1 = s1.next
    }
    if (s1 != null) {
      s.next = s1.next; s1.elem
    } else {
      val r = insert(lastReceiver, new Receiver {
        def isDefined(msg: Any) = f.isDefinedAt(msg)
      })
      lastReceiver = r
      r.elem.wait()
      r.elem.msg
    }
  }
  f(msg)
}

Метод receive сначала проверяет, применима ли функция обработчика f к сообщению, что уже было послано, но еще не обрабатывалось. Если да, поток немедленно применяет f к сообщению. В противном случае создается новый получатель и связывается в списке получателей, а поток ждет уведомления на этом получателе. Как только поток будет разбужен снова, он продолжит выполнение, применяя f к сообщению, которое было сохранено в получателе. Метод insert в связанном списке опреден следующим образом:

def insert(l: LinkedList[A], x: A): LinkedList[A] = {
  l.next = new LinkedList[A]
  l.next.elem = x
  l.next.next = l.next
  l
}

Класс почтового ящика предлагает также метод receiveWithin, который блокируется только на определенный интервал времени. Если в течение оговоренного времени (в миллисекундах), сообщений не приходит, аргумент обработчика сообщения f будет разблокирован специальным сообщением TIMEOUT. Реализация receiveWithin похожа на receive:

  def receiveWithin[A](msec: Long)(f: PartialFunction[Any, A]): A = {
    val msg: Any = synchronized {
      var s = sent, s1 = s.next
      while (s1 != null && !f.isDefinedAt(s1.elem)) {
        s = s1; s1 = s1.next
      }
      if (s1 != null) {
        s.next = s1.next; s1.elem
      } else {
        val r = insert(lastReceiver, new Receiver {
          def isDefined(msg: Any) = f.isDefinedAt(msg)
        })
        lastReceiver = r
        r.elem.wait(msec)
        if (r.elem.msg == null) r.elem.msg = TIMEOUT
        r.elem.msg
      }
    }
    f(msg)
  }
} // Конец MailBox

Единственные различия — в ограниченном по времени вызове wait и выражении, следующим за этим.

Акторы

В Главе 3 представлен набросок электронного аукциона. Этот сервис основывался на высокоуровневых процессах — акторах, которые работают, проверяя сообщения в своих почтовых ящиках, используя сопоставление с образцом. Улучшенная и оптимизированная реализация акторов находится в пакете scala.actors. Здесь мы предоставим набросок упрощенной версии библиотеки акторов.

Код ниже отличается от реализации в пакете scala.actors, чтобы из примера было ясно, как можно реализовать простую версию акторов. Это не является описанием того, как акторы в действительности определены и реализованы в стандартной библиотеке Scala (это можно найти в документации Scala API).

Упрощенный актор это всего лишь поток, чьи коммуникационные примитивы такие же, как у почтового ящика. Такой актор может быть определен как помесь стандартного Java класса Thread и класса почтового ящика MailBox. Мы также переопределим метод run класса Thread, чтобы он исполнял поведение актора, определенное методом act. Метод ! просто вызывает метод send класса MailBox:

abstract class Actor extends Thread with MailBox {
  def act(): Unit
  override def run(): Unit = act()
  def !(msg: Any) = send(msg)
}

См. также

Scala

Scala в примерах

Введение

Первый пример

Программирование с акторами и сообщениями

Выражения и простые функции

Выражения и простые функции

Параметры

Условные выражения

Пример: квадратные корни по методу Ньютона

Вложенные функции

Хвостовая рекурсия

Функции первого класса

Анонимные функции

Каррирование

Пример: поиск неподвижных точек функций

Заключение

Использованные элементы языка

Классы и объекты

Case-классы и сопоставление с образцом

Case-классы и case-объекты

Сопоставление с образцом

Обобщенные типы и методы

Ограничения типовых параметров

Аннотации вариантности

Нижние границы

Крайние типы

Кортежи

Функции

Списки

Использование списков

Определение класса List I: методы первого порядка

Пример: сортировка слиянием

Определение класса List II: методы высшего порядка

Заключение

For-Comprehensions

Задача N ферзей

Очереди с For-Comprehensions

Трансляция For-Comprehensions

Цикл For

Обобщение For

Изменяемое состояние

Объекты с состоянием

Императивные структуры контроля

Расширенный пример: симуляция распределенных событий

Заключение

Вычисления с потоками

Итераторы

Методы итераторов

Создание итераторов

Использование итераторов

Ленивые вычисления

Неявные(имплицитные) параметры и преобразования

Вывод типов Хиндли-Милнера

Абстракции для многопоточности

Сигналы и мониторы

Синхронизированные переменные

Futures

Параллельные вычисления

Семафоры

Читатели/Писатели

Асинхронные каналы

Синхронные каналы

Серверы вычислений

Почтовые ящики

Акторы

См. также