Scala в примерах: различия между версиями

Содержимое удалено Содержимое добавлено
Закончен перевод параграфа 8.1
Строка 1:
''Здесь ведётся перевод книги Martin'а Odersky [http://www.scala-lang.org/docu/files/ScalaByExample.pdf Scala by examples], которая описывает основные приемы программирования на языке [[w:Scala (язык программирования)|Scala<small><sup>↑</sup></small>]]. Присоединяйтесь!''
 
= Введение =
 
Scala изящно объединяет объектно-ориентированное и функциональное программирование. Этот язык спроектирован для выражения привычных паттернов программирования кратко, красиво и безопасно по типам. Scala вводит несколько инновационных языковых конструктов. Например:
* абстрактные типы и примеси объединяют концепты объектных и модульных систем;
* распознавание шаблонов на иерархии классов объединяет функциональный и объектно-ориентированный доступ к данным (это очень упрощает обработку XML деревьев);
* гибкие синтаксис и система типов позволяют конструировать продвинутые библиотеки и новые доменно-специфичные языки.
 
В то же время, язык Scala совместим с Java. Можно использовать Java-библиотеки и фреймворки без связывающего кода и дополнительных деклараций.
 
Эта книга представляет Scala неформально, на примерах.
 
Главы 2 и 3 обращают внимание на некоторые возможности, из-за которых Scala особенно интересен. Последующие главы представляют конструкты языка более подробно, начиная с простых выражений и функций, через объекты и классы, списки и потоки, изменяемые состояния, распознавание шаблонов, к более сложным примерам, иллюстрирующим интересные приемы программирования. Это неформальное изложение должно быть дополнено документом [http://www.scala-lang.org/docu/files/ScalaReference.pdf Scala Language Reference Manual], который специфицирует Scala более точно и детально.
 
 
'''Замечание.''' Мы в огромном долгу у чудесной книги Абельсона и Сассмана, "Структура и интерпретация компьютерных программ". Многие примеры и упражнения оттуда также приведены здесь. Конечно, рабочий язык в каждом случае был изменен с Scheme на Scala. Кроме того, в примерах использованы объектно-ориентированные конструкты Scala, где это уместно.
 
= Первый пример =
 
В качестве первого примера рассмотрим [http://ru.wikipedia.org/wiki/Быстрая_сортировка быструю сортировку].
 
<font size=3><source lang=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)
}
</source></font>
 
Код очень похож на Java или С программу. Мы используем те же операторы и похожие управляющие конструкции. Есть также немного синтаксических отличий. В частности,
* Определения всегда начинаются с зарезервированного слова. Определение функций начинается c <tt>'''def'''</tt>, задание переменных начинается с <tt>'''var'''</tt>, а определение значений (то есть переменных только для чтения) — с <tt>'''val'''</tt>.
* Тип идентификатора объявляется через двоеточие после идентификатора. Задание типа часто можно опускать, поскольку компилятор способен выводить его из контекста.
* Типы массивов записываются как <tt>Array[T]</tt> вместо <tt>[T]</tt>, а выборка из массива как <tt>a(i)</tt> вместо <tt>a[i]</tt>.
* Функции могут быть вложены в другие функции. Вложенные функции имеют доступ к параметрам и локальным переменным внешних функций. Например, массив <tt>xs</tt> является видимым для функций <tt>swap</tt> и <tt>sort1</tt>, а значит, его не требуется передовать как параметр.
 
Пока что Scala представляется довольно обычным языком с некоторыми синтаксическими странностями. На самом деле, на Scala можно писать программы в обычном императивном или объектно-ориентированном стиле. Это важно, потому что облегчает объединение Scala-компонент с кодом, написанным на таких популярных языках, как Java, C# или Visual Basic.
 
Но можно писать программы, которые будут выглядеть совершенно иначе. Вот снова быстрая сортировка, на этот раз написанная в функциональном стиле.
 
<font size=3><source lang=Scala>
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 <)))
}
}
</source></font>
 
Функциональная программа кратко и точно передает сущность алгоритма быстрой сортировки:
* Если массив пуст или состоит из одного элемента, то он уже отсортирован.
* Если массив не пуст, выбираем средний элемент как разделитель.
* Разбиваем массив на три подмассива, содержащие, соответственно, элементы, меньшие разделителя, элементы, равные разделителю, и элементы, большие его.
* Сортируем подмассивы с помощью рекурсивного вызова функции <tt>sort</tt>. (Это не совсем то, что делает императивная версия. Там массив разбивается на массив элементов, меньших разделителя, и массив элементов, больших или равных ему.)
* После склеивания всех подмассивов возвращаем результат.
 
Обе реализации, и императивная, и функциональная, имеют одинаковую асимптотическую сложность — ''O(N log (N))'' в среднем и ''O(N²)'' в худшем случае. Но если императивная версия непосредственно оперирует элементами массива, используя прямую адресацию, то функциональная при каждом рекурсивном вызове возвращает новый отсортированный массив, оставляя без изменения массив, переданный как аргумент. Следовательно, функциональная реализация требует больше памяти для выполнения.
 
Функциональная реализация создаёт впечатление, что Scala это специализированный язык для функциональных операций на массивах. На самом деле все операции, использовавшиеся в примере, это просто библиотечные методы класса ''последовательности'' <tt>Seq[t]</tt> из стандартной библиотеки Scala, которая сама реализована на Scala. Поскольку массивы — это экземпляры класса <tt>Seq</tt>, все его методы доступны им.
 
В частности, метод <tt>filter</tt>, который принимает в качестве аргумента функцию — ''предикатная функция''. Предикатная функция должна переводить элементы массива в булевские значения. Результат выполнения <tt>filter</tt> — массив, состоящий из тех элементов исходного массива, которые удовлетворяют предикату, то есть на которых предикатная функция возвращает true. Метод <tt>filter</tt> класса <tt>Array[t]</tt>, следовательно, имеет сигнатуру
 
<font size=3><source lang=Scala>
def filter(p: T => Boolean): Array[T]
</source></font>
 
Здесь <tt>T => Boolean</tt> — запись типа функции, принимающей аргумент типа <tt>T</tt> и возвращающей булево значение. Функции, подобные <tt>filter</tt>, то есть принимающие другую функцию как аргумент или возвращающие функцию как результат, называются функциями высшего порядка.
 
Scala не различает идентификаторы и имена операторов. Идентификатором может быть последовательность букв или цифр, начинающаяся с буквы, или это может быть последовательность специальных символов, таких как +, *, или :. Любой идентификатор может использоваться как инфиксный оператор. Бинарная операция ''E op E'' всегда интерпретируется как вызов метода ''E.op(E')''. Это верно также для бинарных инфиксных операторов, которые начинаются с буквы. Следовательно, выражение <tt>xs filter (pivot >)</tt> равнозначно вызову метода <tt>xs.filter(pivot >)</tt>.
 
В программе быстрой сортировки <tt>filter</tt> трижды применяется к анонимной функции. Первый аргумент, <tt>pivot ></tt>, представляет функцию, принимающую аргумент <tt>x</tt> и возвращающую значение выражения <tt>pivot > x</tt>. Это пример ''частично примененной функции''. Другой эквивалентный способ записать эту функцию, который явно указывает аргумент, это <tt>x => pivot > x</tt>. Эта функция анонимна, то есть, ее имя не определено. Тип параметра x опущен, поскольку компилятор Scala может автоматически вывести его из контекста, в котором используется функция. Подытоживая, скажем, что <tt>xs.filter(pivot >)</tt> возвращает список из всех элементов <tt>xs</tt>, которые меньше, чем <tt>pivot</tt>.
 
Взглянув снова на первую, императивную реализацию быстрой сортировки, мы увидим там многие языковые конструкты из второго решения, хотя и в замаскированной форме.
 
Например, "обычные" бинарные операторы, такие как <tt>+</tt>, <tt>-</tt> или <tt><</tt>, не рассматриваются специальным образом. Как и <tt>append</tt>, они являются методами своих левых операндов. Следовательно, выражение <tt>i + 1</tt> рассматривается как вызов <tt>i.+(1)</tt> метода <tt>+</tt> на целом числе. Конечно, компилятор может (если он достаточно умный) распознать специальный случай вызова метода <tt>+</tt> на целочисленных аргументах и сгенерировать эффективный встраиваемый код для него.
 
Для эффективности и лучшего обнаружения ошибок цикл '''<tt>while</tt>''' представлен в Scala как примитивная конструкция языка. Но, в принципе, его можно было бы вынести в библиотеку, оформив как функцию. Вот возможная реализация:
 
<font size="3"><source lang=Scala>
def While(p: => Boolean)(s: => Unit) {
if (p) {
s; While(p)(s)
}
}
</source></font>
 
Функция <tt>While</tt> принимает первым параметром функцию проверки, которая не имеет аргументов, и возвращает булево значение. Второй параметр это командная функция, которая также не имеет аргументов и возвращает результат типа <tt>Unit</tt>. While вызывает командную функцию до тех пор, пока предикатная функция возвращает <tt>true</tt>.
 
Тип <tt>Unit</tt> в Scala, грубо говоря, соответствует <tt>void</tt> в Java; он используется всякий раз, когда функция не возвращает какого-либо интересного значения. На самом деле, поскольку Scala это язык, ориентированный на выражения, каждая функция возвращает некоторый результат. Если нет явно заданного выражения, то предполагается значение по умолчанию, <tt>()</tt> (произносится "unit"). Это значение имеет тип <tt>Unit</tt>. Функции, возвращающие <tt>Unit</tt>, также называются ''процедурами''. Вот более "ориентированная на выражения" формулировка функции swap из первой реализации быстрой сортировки, которая выражает это явно:
 
<font size="3">
<source lang=Scala>
def swap(i: Int, j: Int) {
val t = xs(i);
xs(i) = xs(j);
xs(j) = t()
}
</source>
</font>
 
Результат этой функции — просто её последнее выражение, при этом ключевое слово <tt>'''return'''</tt> указывать не обязательно. Обратите внимание, что для функций, возвращающих явное значение, всегда необходимо cтавить '=' перед их телом или определяющим выражением.
 
= Программирование с акторами и сообщениями =
 
Вот пример, который демонстрирует область применения, для которой Scala особенно хорошо подходит. Рассмотрим задачу по созданию электронного аукциона. Для реализации участников аукциона мы используем модель акторных процессов в [http://erlang.org Erlang]-стиле. Акторы — это объекты, которым посылаются сообщения. У каждого актора есть "почтовый ящик" для поступающих сообщений, который представлен очередью. Сообщения в очереди могут обрабатываться или в последовательном порядке, или выборочно, как удовлетворяющие некоторому образцу.
 
Для каждого лота есть актор-аукционщик, который публикует информацию о лоте, принимает предложения от участников и общается с продавцом лота и победившем покупателем для завершения сделки.
 
Первым делом, мы определим сообщения, которые передаются во время аукциона. Есть два абстрактных базовых класса, <tt>AuctionMessage</tt> для сообщений от клиентов к сервису аукциона, и <tt>AuctionReply</tt> для ответов сервиса клиентам. Для обоих базовых классов существует набор вариаций, как это определено в листинге 3.1.
 
''Вариации классов'' (case classes) определяют формат конкретных сообщений. Эти сообщения могли бы отображаться в небольших XML документах. Мы ожидаем, что существуют автоматические инструментальные средства для преобразований между XML документами и внутренними структурами данных, такими, как определенные выше.
 
<font size=3><source lang=Scala>
// 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
</source></font>
 
Листинг 3.2 представляет реализацию на Scala класса <tt>Auction</tt> для акторов, координирующих предложение цен по лоту. Объекты этого класса создаются с указанием
* актора продавца, который должен быть извещен о завершении торгов,
* минимальной цены,
* даты завершения аукциона.
 
Ход торгов определён методом <tt>act</tt>. Этот метод периодически отбирает (используя метод [http://www.daimi.au.dk/~eernst/dProgSprog06/share/doc/scala-1.4.0.4/api/scala/concurrent/Actor-class.html#1 <tt>receiveWithin</tt>]) поступающие сообщения и реагирует на них, пока аукцион не будет закрыт, что сигнализируется сообщением <tt>TIMEOUT</tt>. Перед завершением актор остается активным в течение периода времени, определенным константой <tt>timeToShutdown</tt>, и отвечает на дальнейшие предложения, что аукцион закрыт.
 
<font size=3><source lang=Scala>
// 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
}
}
}
}
}
</source></font>
 
Ниже приведены некоторые комментарии по конструкциям, использованным в этой программе.
 
* Метод <tt>receiveWithin</tt> класса [http://www.daimi.au.dk/~eernst/dProgSprog06/share/doc/scala-1.4.0.4/api/scala/concurrent/Actor-class.html <tt>Actor</tt>] принимает в качестве параметров продолжительность торгов в миллисекундах и функцию, которая обрабатывает сообщения, поступающие в почтовый ящик. Функция задана последовательностью вариаций, каждая из которых определяет шаблон и действия, которые следует предпринять для сообщений, соответствующих этому шаблону. Метод <tt>receiveWithin</tt> выбирает из почтового ящика первое сообщение, которое соответствует одному из этих шаболонов и выполняет соответствующее действие.
 
* Последняя вариация в <tt>receiveWithin</tt> — для шаблона <tt>TIMEOUT</tt>. Если никакие другие сообщения не были получены в последнее время, по истечении срока, который передается в <tt>receiveWithin</tt> как аргумент, срабатывает шаблон <tt>TIMEOUT</tt>. <tt>TIMEOUT</tt> — это особое сообщение (экземпляр класса [http://www.daimi.au.dk/~eernst/dProgSprog06/share/doc/scala-1.4.0.4/api/scala/collection/mutable/Message-class.html <tt>Message</tt>]), которое посылается в реализации класса <tt>Actor</tt>.
 
* Ответные сообщения посылаются в форме <tt>destination ! SomeMessage</tt>. <tt>!</tt> используется здесь как бинарный оператор с аргументами: актором и сообщением. В Scala это равносильно вызову метода <tt>destination.!(SomeMessage)</tt>, т.е. вызову метода <tt>!</tt> актора-реципиента с сообщением в качестве параметра.
 
Предыдущее обсуждение показало возможности распределенного программирования на Scala. Может показаться, что в Scala есть богатый набор языковых конструкций, поддерживающих процессы-акторы, обмен сообщениями, программирование с тайм-аутами, и т.п. В действительности это не так. Все конструкции, рассмотренные выше, вводятся как методы в библиотечном классе <tt>Actor</tt>.
Сам класс написан на Scala и базируется на модели многопоточности, используемой в нижележащей платформе (напр. Java или .NET). Все возможности класса <tt>Actor</tt>, использованные здесь, рассмотрены в [[Scala в примерах#Акторы|Разделе 17.11]].
 
Преимущество подобного библиотечного подхода к многопоточности ''(см. также [http://lamp.epfl.ch/~cremet/publications/pilib.pdf PiLib]) '' — в относительной простоте основного языка и гибкости для разработчиков библиотек. Поскольку основному языку не нужно определять детали высокоуровневого обмена информацией между процессами, он может оставаться простым и более общим. Поскольку конкретная модель сообщений в почтовом ящике — библиотечный модуль, она может свободно быть модифицирована, если это требуется в каких-то приложениях. Впрочем, для такого подхода необходимо, чтобы базовый язык был достаточно выразителен, чтобы он мог обеспечивать необходимые языковые абстракции удобным способом. Scala разработан с учётом этого требования; одна из основных целей при проектировании заключалась в том, чтобы сделать его достаточно гибким, чтобы он мог выступать удобной платформой для доменно-специфичных языков, реализованных как библиотечные модули. Например, представленные выше конструкции для коммуникации между акторами могут рассматриваться как доменно-специфичный язык, который, в принципе, расширяет ядро Scala.
 
= Выражения и простые функции =
 
Предыдущий пример показывает, что можно делать при помощи Scala. Теперь мы опишем элементы языка по одному и более систематически. Начнем с самого нижнего уровня, с выражений и функций.
 
== Выражения и простые функции ==
 
В дистрибутив Scala входит интерпретатор, который можно рассматривать как сложный калькулятор. Пользователь взаимодействует с калькулятором, вводя выражения. Калькулятор возвращает результаты вычислений и их типы. Например,
 
<font size=3><source lang=Bash>
scala> 87 + 145
unnamed0: Int = 232
 
scala> 5 + 2 * 3
unnamed1: Int = 11
 
scala> "hello" + " world!"
unnamed2: java.lang.String = hello world!
</source></font>
 
Можно также именовать подвыражения и впоследствии использовать их имена:
 
<font size=3><source lang=Bash>
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
</source></font>
 
Определения начинаются с зарезервированного слова <tt>'''def'''</tt>, в них вводятся имена выражений, после которых ставится знак <tt>=</tt>. Интерпретатор вернет имя и тип выражения.
 
Выполнение такого определения, как <tt>'''def''' x = e</tt>, не вычисляет выражение <tt>e</tt>. Вместо этого <tt>e</tt> вычисляется там, где используется <tt>x</tt>. Также в Scala можно определять значения так: <tt>'''val''' x = e</tt>, в этом случае правая часть выражения <tt>e</tt> вычисляется как часть выполнения определения. Если <tt>x</tt> используется впоследствии, он немедленно заменяется на заранее вычисленное значение <tt>e</tt>, так что выражение не нужно вычислять заново.
 
Как же вычисляются выражения? Выражение, состоящее из опраторов и операндов, вычисляется повторным применением следующих упрощающих шагов:
* выбрать самую левую операцию;
* вычислить ее операнды;
* применить оператор к значениям операндов.
 
Имя, определенное при помощи <tt>'''def'''</tt>, вычисляется путем замены имени на (невычисленную) правую часть определения. Имя, определенное при помощи <tt>'''val'''</tt>, вычисляется путем замены имени на значение правой части. Процесс вычисления заканчивается, когда приходит к одному значению. Значение — это некоторые данные, как например: строка, число, массив или список.
 
'''Пример 4.1.1''' Здесь представлено вычисление арифметического выражения.
 
<pre>
&nbsp; (2 * pi) * radius
→ (2 * 3.141592653589793) * radius
→ 6.283185307179586 * radius
→ 6.283185307179586 * 10
→ 62.83185307179586
</pre>
 
Процесс пошагового сведения выражений к значениям называется ''редукцией''.
 
== Параметры ==
 
При помощи <tt>'''def'''</tt> можно также определять функции с параметрами. Например,
 
<font size=3><source lang=Bash>
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
</source></font>
 
Параметры функций перечисляются после имени функции и всегда заключаются в скобки. Каждый параметр имеет тип, который указывается после имени параметра и двоеточия. Пока что нам потребуются только базовые числовые типы, такие как <tt>scala.Double</tt> — типа числа двойной точности. Scala определяет псевдонимы для некоторых стандартных типов, так что мы можем писать численные типы, как в Java. Например, псевдоним <tt>double</tt> — <tt>scala.Double</tt>, а псевдоним <tt>int</tt> — <tt>scala.Int</tt>.
 
Функции с параметрами вычисляются аналогично операторам в выражениях. Сначала вычисляются аргументы функции (слева направо). Затем применение функции заменяется на ее правую часть, и в то же время все формальные параметры функции заменяются на соответствующие им фактические аргументы.
 
'''Пример 4.2.1'''
 
<pre>
&nbsp; sumOfSquares(3, 2 + 2)
→ sumOfSquares(3, 4)
→ square(3) + square(4)
→ 3 * 3 + square(4)
→ 9 + square(4)
→ 9 + 4 * 4
→ 9 + 16
→ 25
</pre>
 
Пример показывает, что интерпретатор приводит аргументы функции к значениям перед тем, как переписать применение функции. Вместо этого можно было бы выбрать применять функцию к неприведенным аргументам. Это бы дало такую последовательность вывода:
 
<pre>
&nbsp; 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
</pre>
 
Второй порядок вычисления называется ''вызовом по имени'' (call-by-name), тогда как первый называется ''вызовом по значению'' (call-by-value). Для выражений, которые используют только чистые функции и поэтому могут быть редуцированы при помощи подстановок, обе схемы приводят к одинаковым результирующим значениям.
 
У вызова по значению есть приемущество в том, что он не вычисляет аргументы повторно. У вызова по имени есть приемущество в том, что он не вычисляет аргумент, когда параметр вообще не используется в функции. Вызов по значению обычно более эффективен, чем по имени, но вызов по значению может зациклиться там, где вызов по имени завершится. Рассмотрим пример:
 
<font size=3><source lang=Bash>
scala> def loop: Int = loop
loop: Int
 
scala> def first(x: Int, y: Int) = x
first: (Int,Int)Int
</source></font>
 
<tt>first(1, loop)</tt> сводится вызовом по имени к <tt>1</tt>, тогда как тот же терм сводится вызовом по значению к самому себе раз за разом, и вычисление не завершается.
 
<pre>
&nbsp; first(1, loop)
→ first(1, loop)
→ first(1, loop)
→ …
</pre>
 
Scala по умолчанию использует вызов по значению, но можно переключиться на вызов по имени, если тип параметра предваряется <tt>=></tt>.
 
'''Пример 4.2.2'''
 
<font size=3><source lang=Bash>
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
</source></font>
 
== Условные выражения ==
 
<tt>'''if-else'''</tt> в Scala позволяет выбирать между двумя альтернативами. Синтаксис похож на <tt>'''if-else'''</tt> в Java. Но тогда как <tt>'''if-else'''</tt> в Java можно использовать только для альтернативных утверждений, Scala позволяет использовать тот же синтаксис для выбора между двумя выражениями. Поэтому в Scala <tt>'''if-else'''</tt> служит также для замены условного выражения Java <tt>… ? … : …</tt>.
 
'''Пример 4.3.2'''
 
<font size=3><source lang=Bash>
scala> def abs(x: Double) = if (x >= 0) x else -x
abs: (Double)Double
</source></font>
 
Булевские выражения в Scala похожи на Java аналоги, они состоят из констант <tt>'''true'''</tt> и <tt>'''false'''</tt>, операторов сравнения, булевского отрицания <tt>!</tt> и булевских операторов <tt>&&</tt> и <tt>||</tt>.
 
== Пример: квадратные корни по методу Ньютона ==
 
Теперь проиллюстрируем элементы языка, которые мы упомянули к этому моменту, более интересной программой. Задание — написать функцию
 
<font size=3><source lang=Scala>
def sqrt(x: Double): Double = …
</source></font>
 
которая вычисляет квадратный корень <tt>x</tt>.
 
Обычный способ вычисления квадратных корней — ньютоновский метод последовательных приближений. Мы начинаем с первой догадки <tt>y</tt> (скажем, <tt>y = 1</tt>). Затем будем улучшать текущую догадку <tt>y</tt>, вычисляя среднее между <tt>y</tt> и <tt>x/y</tt>. В качестве примера, следующие три столбца представляют догадку <tt>y</tt>, частное <tt>x/y</tt> и их среднее для первого приближения <math>\sqrt{2}</math>.
 
{| class="simple" border="0"
| width="30%"|1
| width="48%"|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
|}
 
Этот алгоритм можно реализовать при помощи множества коротких функций, каждая из которых представляет один из элементов алгоритма.
 
Сначала определим функцию для итерации от догадки к результату:
 
<font size=3><source lang=Scala>
def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
else sqrtIter(improve(guess, x), x)
</source></font>
 
Отметим, что <tt>sqrtIter</tt> рекурсивно вызывает саму себя. Циклы императивного программирования всегда можно смоделировать при помощи рекурсии в функциональных программах.
 
Также отметим, что определение <tt>sqrtIter</tt> содержит возвращаемый тип, который следует за секцией параметров. Такие возвращаемые типы обязательны для рекурсивных функций. Для нерекурсивной функции возвращаемый тип необязателен, и если он не указан, проверка типов выведет его из правой части функции. Впрочем, даже для нерекурсивных функций указывать возвращаемый тип бывает полезно для улучшения документированности.
 
На втором шаге определим две функции, вызываемые в <tt>sqrtIter</tt>: функцию для улучшения догадки <tt>improve</tt> и проверку на завершение <tt>isGoodEnough</tt>. Вот их определения:
 
<font size=3><source lang=Scala>
def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
 
def isGoodEnough(guess: Double, x: Double) =
abs(square(guess) - x) < 0.001
</source></font>
 
Наконец, сама функция <tt>sqrt</tt> определена как применение <tt>sqrtIter</tt>.
 
<font size=3><source lang=Scala>
def sqrt(x: Double) = sqrtIter(1.0, x)
</source></font>
 
'''Упражнение 4.4.1''' Проверка <tt>isGoodEnough</tt> не очень точна для малых чисел и может привести к незавершению вычислений для очень больших чисел (почему?). Придумайте другую версию <tt>isGoodEnough</tt>, у которой нет таких проблем.
 
'''Упражнение 4.4.2''' Проследите выполнение выражения <tt>sqrt(4)</tt>.
 
== Вложенные функции ==
 
Функциональный стиль программирования располагает к написанию множества небольших вспомогательных функций. В последнем примере реализация <tt>sqrt</tt> использует вспомогательные функции <tt>sqrtIter</tt>, <tt>improve</tt> и <tt>isGoodEnough</tt>. Имена этих функций относятся только к реализации <tt>sqrt</tt>. Мы не хотим, чтобы пользователи <tt>sqrt</tt> имели прямой доступ к этим функциям.
 
Мы можем выразить это (и избежать загрязнения пространства имен), включив вспомогательные функции в вызывающую функцию:
 
<font size=3><source lang=Scala>
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)
}
</source></font>
 
В этой программе в фигурных скобках заключен ''блок''. Блоки в Scala являются выражениями. Каждый блок заканчивается результрующим выражением, которое определяет значение. Результирующее выражение может быть предварено дополнительными определениями, которые видны только внутри блока.
 
Каждое определение в блоке заканчивается точкой с запятой, которые отделяют данное определение от последующих определений или результирующего выражения. Впрочем, точка с запятой неявно ставится в конце каждой строки, если только не выполняется один из последующих пунктов:
# данная строка заканчивается таким словом, как точка или инфиксный оператор, которое не может быть допустимым концом выражения;
# следующая строка начинается словом, с которого не может начинаться выражение;
# мы находимся внутри круглых или квадратных скобок, потому что они не могут содержать несколько выражений в любом случае.
 
Таким образом, допустимо писать:
 
<font size=3><source lang=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)
</source></font>
 
Scala использует обычные правила областей видимости для блочных структур. Имя, определенное в каком-либо внешнем блоке, видно также во внутреннем блоке, если оно там не переопределено. Это правило позволяет упростить наш пример с <tt>sqrt</tt>. Нам не нужно передавать <tt>x</tt> как дополнительный параметр внутренней функции, поскольку эта переменная видна в них как параметр внешней функции <tt>sqrt</tt>. Вот упрощенный код:
 
<font size=3><source lang=Scala>
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)
}
</source></font>
 
== Хвостовая рекурсия ==
 
Рассмотрим функцию для нахождения наибольшего общего делителя двух чисел.
 
<font size=3><source lang=Scala>
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
</source></font>
 
При помощи нашей модели подстановки <tt>gcd(14,21)</tt> вычисляется следующим образом:
 
<pre>
&nbsp; &nbsp; gcd(14, 21)
→ &nbsp; if (21 == 0) 14 else gcd(21, 14 % 21)
→ &nbsp; if (false) 14 else gcd(21, 14 % 21)
→ &nbsp; gcd(21, 14 % 21)
→ &nbsp; gcd(21, 14)
→ &nbsp; if (14 == 0) 21 else gcd(14, 21 % 14)
→ → gcd(14, 21 % 14)
→ &nbsp; gcd(14, 7)
→ &nbsp; if(7 == 0) 14 else gcd(7, 14 % 7)
→ → gcd(7, 14 % 7)
→ &nbsp; gcd(7, 0)
→ &nbsp; if(0 == 0) 7 else gcd(0, 7 % 0)
→ → 7
</pre>
 
Сравним это с вычислением другой рекурсивной функции, <tt>factorial</tt>:
 
<font size=3><source lang=Scala>
def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)
</source></font>
 
Применение <tt>factorial(5)</tt> переписывается так:
 
<pre>
&nbsp; &nbsp; &nbsp; factorial(5)
→ &nbsp; &nbsp; if (5 == 0) 1 else 5 * factorial(5 - 1)
→ &nbsp; &nbsp; 5 * factorial(5 - 1)
→ &nbsp; &nbsp; 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
</pre>
 
Между этими двумя последовательностями вывода есть важное различие: термы последовательности вывода <tt>gcd</tt> вновь и вновь принимают одну и ту же форму. В течение вычисления их длина ограничена константой. В вычислении факторила, напротив, мы получаем все более длинные цепи операндов, которые впоследствии перемножаются в последней части последовательности вычислений.
 
Несмотря на то, что на самом деле Scala не переписывает термы, затраты по памяти будут такими же, что и в последовательности вывода. Заметим, что в реализации <tt>gcd</tt> рекурсивный вызов <tt>gcd</tt> — это последнее действие в теле вычисления. Это пример хвостовой рекурсии. Последний вызов в хвостово-рекурсивной функции может быть реализован прыжком обратно к началу этой функции. Аргументы такого вызова могут быть вписаны на место параметров текущего выполнения <tt>gcd</tt>, так что новой памяти на стеке выделять не нужно. Отметим, что хвостово-рекурсивные функции это итеративные процессы, которые могут выполняться в константной памяти.
 
Рекурсивый вызов <tt>factorial</tt>, напротив, заканчивается операцией умножения. Отметим, что для рекурсивного вызова <tt>factorial</tt> выделяется новый кадр стека, который стирается после завершения выполнения вызова. Данная реализации функции факториала не хвостово-рекурсивна, и ей необходимо количество памяти, пропорциональное размеру ввода.
 
Говоря более общим языком, если последнее действие функции это вызов другой (возможно, той же самой) функции, то для обеих функций требуется только один кадр стека. Такие вызовы называются хвостовыми. В принципе, хвостовые вызовы могут все время переиспользовать кадр вызывающей функции. Впрочем, в некоторых средах выполнения (например, виртуальная машина Java) нет примитивов для того, чтобы обеспечить эффективное переиспользование кадров стека для хвостовых вызовов. Поэтому реализация Scala должна переиспользовать кадры стека только прямо хвостово-рекурсивных функций, чье последнее действие это вызов самих себя. Другие хвостовые вызовы также могут быть оптимизированы, на на это не следует надеяться
 
'''Упражнение 4.6.1''' Придумайте хвостово-рекурсивную версию функции <tt>factorial</tt>.
 
= Функции первого класса =
== Анонимные функции ==
== Каррирование ==
== Пример: поиск неподвижных точек функций ==
== Заключение ==
== Использованные элементы языка ==
 
= Классы и объекты =
 
= Case-классы и распознавание шаблонов =
== Case-классы и case-объекты ==
== Распознавание шаблонов ==
 
= Обобщенные типы и методы =
 
Классы в Scala могут иметь типовые параметры. Мы продемонстрируем использование типовых параметров на примере функциональных стеков. Скажем, нам нужно написать тип данных для стеков целых чисел с методами <tt>push</tt>, <tt>top</tt>, <tt>pop</tt> и <tt>isEmpty</tt>. Это можно сделать при помощи следующей иерархии классов:
 
<font size=3><source lang=Scala>
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
}
</source></font>
 
Конечно, имеет смысл также определить абстракцию для стека строк. Чтобы это сделать, можно взять существующую абстракцию для стека целых чисел, переименовать ее с <tt>IntStack</tt> в <tt>StringStack</tt> и в то же время заменить все встречающиеся упоминания типа <tt>Int</tt> на <tt>String</tt>.
 
Более хороший способ, который не приводит к повторению кода, это параметризовать определение стека по типу элементов. Параметризация позволяет обобщать проблему с конкретной до более общей. Пока что мы использовали только параметризацию по значению, но можно делать ее и по типам. Чтобы придти к ''обобщенной'' (generic) версии стека, снабдим класс <tt>Stack</tt> типовым параметром.
 
<font size=3><source lang=Scala>
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
}
</source></font>
 
В данном определении '<tt>A</tt>' это ''типовой параметр'' класса <tt>Stack</tt> и его подклассов. Типовые параметры это произвольные имена; они заключены в квадратные, а не круглые скобки, чтобы их было просто отличить от параметров значений. Вот пример использования обобщенного класса:
 
<font size=3><source lang=Scala>
val x = new EmptyStack[Int]
val y = x.push(1).push(2)
println(y.pop.top)
</source></font>
 
Первая строка создает новый пустой стек целых чисел. Заметьте, что действительный типовой аргумент <tt>[Int]</tt> заменен формальным типовым параметром <tt>A</tt>.
 
Возможно также параметризовать методы по типам. Вот, к примеру, обобщенный метод, который определяет, является ли один стек префиксом другого:
 
<font size=3><source lang=Scala>
def isPrefix[A](p: Stack[A], s: Stack[A]): Boolean = {
p.isEmpty ||
p.top == s.top && isPrefix[A](p.pop, s.pop)
}
</source></font>
 
Параметры этого метода называются ''полиморфными''. Обобщенные методы такжа называются ''полиморфными''. Этот термин пришел из греческого языка, на котором он значит "имеющий много форм". Чтобы применить такой полиморфный метод, как <tt>isPrefix</tt>, надо передать ему типовые параметры так же, как и параметры значений. Например,
 
<font size=3><source lang=Scala>
val s1 = new EmptyStack[String].push("abc")
val s2 = new EmptyStack[String].push("abx").push(s1.top)
println(isPrefix[String](s1, s2))
</source></font>
 
'''Локальный вывод типов.''' Постоянная передача такого типового параметра, как <tt>[Int]</tt> или <tt>[String]</tt>, может стать утомительной в приложениях, где обобщенные функции много используются. Довольно часто информация, содержащаяся в типовом параметре, избыточна, потому что правильный типовой параметр может быть определен также при рассмотрении параметров значений и ожидаемого типа результата функции. Возьмем к примеру выражение <tt>isPrefix[String](s1, s2)</tt>. Мы знаем, что оба его параметра значений имеют тип <tt>Stack[String]</tt>, так что мы можем понять, что типовой параметр должен быть <tt>String</tt>. У Scala довольно мощная система вывода типов, которая позволяет опускать типовые параметры полиморфных функций и конструкторов в подобных ситуациях. В приведенном примере можно было бы написать <tt>isPrefix(s1, s2)</tt>, и отсутствующий типовой аргумент <tt>[String]</tt> был бы вставлен системой вывода типов.
 
''Здесь ведётся перевод книги Martin'а Odersky [http://www.scala-lang.org/docu/files/ScalaByExample.pdf Scala by examples], которая описывает основные приемы программирования на языке [[w:Scala (язык программирования)|Scala<small><sup>↑</sup></small>]]. Присоединяйтесь!''
 
Строка 690 ⟶ 1354 :
/** Результат сравнения ‘this’ с операндом ‘that’
* возвращает ‘x’, где
* x < 0 титтiff this < that
* x == 0 титтiff this == that
* x > 0 титтiff this > that
*/
def compare(that: A): Int
Строка 776 ⟶ 1440 :
 
Библиотека Scala предопределяет неявные преобразования для некоторых типов, включая примитивные типы и <tt>String</tt>. Поэтому наша новая абстракция множеств может быть использована и с этими типами. Больше объяснений про неявные преобразования и ограничения по видимости даны в [[Scala в примерах#Неявные(имплицитные) параметры и преобразования|Главе 15]].
 
== Аннотации вариантности ==
== Нижние границы ==
== Крайние типы ==
== Кортежи ==
== Функции ==
 
= Списки =
== Использование списков ==
== Определение класса List I: методы первого порядка ==
== Пример: сортировка слиянием ==
== Определение класса List II: методы высшего порядка ==
== Заключение ==
 
= 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 .. end1].
Более функциональный способ заключается в представлении списка значений 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.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
Различие от предыдущей реализации на списках в том что теперь нет необходимости конструировать и проверять на простоту
другие числа, после третьего. Два метода из класса List, не поддерживаемые классом Stream это :: и :::.
Причина в том, что эти методы требуют передачи правых аргументов, а это означает, что аргументы должны быть вычислены
до вызова метода. Например, в случае x :: xs на списках, хвост xs должен быть вычислен
до оператора :: . Это не работает для потоков, поскольку хвост потока пока не потребуется в вычислениях,
не должен вычисляться. Объяснение почему метод ::: не адаптируется для потоков - аналогично.
Вместо x :: xs, используют Stream.cons(x, xs). Вместо xs ::: ys, - xs append ys.
 
= Итераторы =
== Методы итераторов ==
== Создание итераторов ==
== Использование итераторов ==
 
= Ленивые вычисления =
 
= Неявные(имплицитные) параметры и преобразования =
 
Неявные(имплицитные) параметры и преобразования – это мощные инструменты для настройки существующих библиотек и для создания высокоуровневых абстракций. Например, давайте начнем с абстрактного класса полугрупп, который поддерживает операцию сложения.
 
<code>
'''abstract''' class SemiGroup[A] {
'''def''' add(x: A, y: A): A }</code>
А это подкласс SemiGroup – класс Monoid, который добавляет поле unit.
 
<code>
'''abstract''' '''class''' Monoid[A] '''extends''' SemiGroup[A] {
'''def''' unit: A
}</code>
Вот две реализации моноидов:
 
<code>
'''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
}</code>
 
Метод суммирования, который работает с произвольными моноидами, может быть написан на чистой Scala следующим образом:
 
<code>
'''def''' sum[A](xs: List[A])(m: Monoid[A]): A =
'''if''' (xs.isEmpty) m.unit
'''else''' m.add(xs.head, sum(m)(xs.tail)
</code>
Этот метод может быть вызван, например, так:
 
<code>
sum(List("a", "bc", "def"))(stringMonoid)
sum(List(1, 2, 3))(intMonoid)</code>
Все это работает, но выглядит не очень здорово. Проблема в том, что реализации моноида должны быть переданы в код, который их использует. Иногда мы можем захотеть, чтобы система могла вычислить нужные аргументы автоматически, аналогично тому, как это делается при выводе типов аргументов. Это то, чего помогают добиться неявные параметры.
 
=== Неявные параметры: основы ===
 
В Scala 2 появилось новое ключевое слово implicit; оно может быть использовано в начале списка параметров. Синтаксис:
<code>
ParamClauses ::= {‘(’ [Param {‘,’ Param}] ’)’}
[‘(’ implicit Param {‘,’ Param} ‘)’]</code>
Если ключевое слово присутствует, то оно делает все параметры в списке неявными. Например, в следующей версии метода sum параметр m является неявным.
 
<code>
'''def''' sum[A](xs: List[A])('''implicit''' m: Monoid[A]): A =
'''if''' (xs.isEmpty) m.unit
'''else''' m.add(xs.head, sum(xs.tail))</code>
Как можно заметить из примера, возможно комбинировать обычные и неявные параметры. Однако, для метода или конструктора может быть только один неявный параметр, и он должен быть последним.
 
Ключевое слово implicit может также быть использовано как модификатор в определениях и объявлениях. Примеры:
 
<code>
'''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
}</code>
Основная идея неявных параметров – это то, что аргументы для них могут быть выведены из вызова метода. Если аргументы, отвечающие за секцию неявного параметра отсутствуют, тогда они выводятся Scala компилятором.
Реальные аргументы, которые могут быть переданы в качестве неявного параметра, – это все идентификаторы X, которые доступны в точке вызова метода без префикса и которые помечены как неявные.
Если существует несколько аргументов, подходящих по типу к неявному параметру, компилятор Scala выберет наиболее точный (специфичный), используя стандартные правила разрешения статической перегрузки. Например, пусть вызывается
 
<code>
sum(List(1, 2, 3))</code>
в контексте, где доступны 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:
 
<code>
'''implicit''' '''def''' int2ordered(x: Int): Ordered[Int] = '''new''' Ordered[Int] {
'''def''' compare(y: Int): Int =
'''if''' (x < y1) 1
'''else''' if (x > y1) 1
'''else''' 0
}</code>
 
=== View Bounds ===
 
View bounds – это удобный синтаксический сахар для неявных параметров. Рассмотрим обобщенный метод сортировки:
 
<code>
'''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(ys, zs)
}</code>
View bounded параметр типа [A <% Ordered[A]] выражает, что сортировка применима для списков таких типов, для которых существует неявное преобразование A к Ordered[A]. Определение трактуется как укороченный синтаксис для следующей сигнатуры метода с неявным параметром:
 
<code>
'''def''' sort[A](xs: List[A])('''implicit''' c: A => Ordered[A]): List[A] = …</code>
 
(Здесь имя параметра c выбрано произвольно с учетом того, чтобы оно не конфликтовало с другими именами в программе.)
В качестве более детального примера, рассмотрим метод merge, который появился в методе sort выше:
 
<code>
'''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''' '''if''' ys.head :: merge(xs, ys.tail)</code>
После раскрытия view bounds и вставки неявных преобразований, реализация метода принимает вид:
<code>
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)</code>
Последние две строки определения этого метода демонстрируют два различных использования неявного параметра c. Он применяется в преобразовании в условии во второй строке с конца и передается как неявный аргумент в рекурсивный вызов merge в последней строке.
 
= Вывод типов Хиндли-Милнера =
 
= Абстракции для многопоточности =
 
В этом разделе рассматриваются стандартные паттерны для параллельного программирования и показывается как они могут быть реализованы в Scala. ''"Процесс" и "поток" используются авторами как синонимы, примеры кода приведены без изменений. ''
 
== Сигналы и мониторы ==
 
В Scala возможность взаимного исключения потоков обеспечивает монитор. Каждый экземпляр класса AnyRef может быть использован в качестве монитора, посредством вызова одного из этих методов:
def synchronized[a] (exec: => a): a
def wait(): unit
def wait(msec: long): unit
def notify(): unit
def notifyAll(): unit
Синхронизированный метод (оформленный с помощью служебного слова <tt>synchronized</tt>) выполняет вычисления <tt>exec</tt> в режиме взаимного исключения - в любое время, только один поток может выполнять синхронизированный метод, иначе: метод требует экслюзивного доступа.
При вызове такого метода (<tt>synchronized</tt> блока) соответствующий экземпляр объекта блокируется на вызов остальных <tt>synchronized</tt> методов, что впрочем, не мешает параллельному выполнению несинхронизированных методов.
 
Поток может приостановиться на мониторе, ожидая сигнала. Поток, вызвавший метод <tt>wait</tt> снимает блокировку и переходит в режим ожидания вызова другим потоком метода <tt>notify</tt> на том же объекте. Вызовы <tt>notify</tt> при отсутствии потоков, ожидающих этот сигнал, игнорируются.
 
Есть также форма <tt>wait</tt>, c указанием времени блокировки (в миллисекундах), по истечении которого, процесс обязательно возобновит работу.
 
Кроме того, есть метод <tt>notifyAll</tt>, который разблокирует все потоки, ждущие сигнал.
 
Эти методы, а также класс [http://path_to_api Monitor] являются примитивами в <tt>Scala</tt>; они реализованы, основываясь на нижлежащих <tt>runtime</tt> системах.
 
Обычно поток ждет некоторое условие для выполнения программ. Если условие не выполнено - при вызове <tt>wait</tt>, поток усыпляется, пока некоторый другой поток формирует условие. И в ответственности последнего пробуждение ожидающих потоков, посредством вызова <tt>notify</tt> или <tt>notifyAll</tt>. Заметьте, тем не менее, нет гарантии, что ожидающий поток начнёт исполняться немедленно после вызова <tt>notify</tt> / <tt>notifyAll</tt>.
 
Может статься, что другой поток за это время в очередной раз изменит условие запуска, аннулирует его. Следовательно, правильная форма ожидания условия C использует while цикл:
while (!C) wait()
а не
if (!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) } }
Метод <tt>spawn</tt> запускает новый поток, который выполняет выражение, переданное параметром. В объекте [http://www.daimi.au.dk/~eernst/dProgSprog06/share/doc/scala-1.4.0.4/api/scala/concurrent/ops.html 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 {
if (<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 ==
 
<tt>Future</tt> ''(оставлено без перевода)'' является величиной, которая вычисляется параллельно некоторому потоку, чтобы быть использованной им немного позже. <tt>Future</tt> используется для облегчения параллельной обработки ресурсов. Типичное применение:
import scala.concurrent.ops._
val x = future(someLengthyComputation)
anotherLengthyComputation
val y = f(x()) + g(x())
Метод <tt>future</tt> определён в scala.concurrent.ops следующим образом.
def future[a](p: => a): unit => a = {
val result = new SyncVar[a]
fork { result.set(p) }
(() => result.get)
}
Метод <tt>future</tt> для выполнения получает как параметр вычисление p. Тип возвращаемого им результата есть тип a - <tt>future</tt> параметра. Mетод определяет охрану <tt>result</tt>, которая принимает параметр, представляющий результат вычисления. Затем ответвляется новый поток (fork), который вычисляет результат, и вызывает охрану <tt>result</tt> по завершению. Параллельно этому, <tt>future</tt> возвращает анонимную функцию. При возвращении анонимной функции, поток может блокироваться на <tt>result</tt>, в ожидании вызова <tt>notify</tt> на охране, чтобы вернуть результат.
 
Обратите внимание, что последущие вызовы функции могут возвращать результат немедленно.
 
== Параллельные вычисления ==
 
Следующий пример демонстрирует функцию 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
}
 
== Семафоры ==
 
Классический механизм синхронизации процессов - семафор. Он предлагает два элементарных
действия: занятие и освобождение. Вот реализация простого семафора в Scala:
package scala.concurrent
class Lock {
var available = true
def acquire = synchronized {
if (!available) wait()
available = false
}
def release = synchronized {
available = true
notify()
}
}
 
== Читатели/Писатели ==
 
Более сложная форма синхронизации различает ''читающие потоки'', которые имеют доступ к общему ресурсу, не модифицируя его, и потоки, которые могут и читать, и изменять ресурс - ''писатели ''. Для того, чтобы синхронизировать читателей и писателей, которые нам нужно осуществлять действия startRead, startWrite, endRead, endWrite, при том, что:
 
* может быть множество конкурирующих читателей,
* в любой момент может только быть один писатель,
* запись имеет больший приоритет над чтением, но прерывыать процесс чтения не может.
 
Следующая реализация читателей/писателей основана на понятии почтового ящика
(смотри раздел 16.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.
 
Класс Channel использует связанный список, чтобы загружать данные, которые посланы, но ещё не прочитаны.
 
Потоки, которым необходимо читать данные, при пустом канале, регистрируют своё наличие, увеличивая <tt>nreaders</tt> величину и ожидая <tt>notify</tt>.
 
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
}
}
 
== Сервера вычислений ==
 
Реализация сервера вычислений в <tt>Scala</tt>. Сервер выполняет <tt>future</tt> метод, который вычисляет данное выражение параллельно своему вызову. В отличие от реализации в Разделе 16.3, сервер вычисляет <tt>future</tt> только для предопределённого числа потоков. Предполагаемая реализация сервера могла бы запускать каждый поток на отдельном процессоре, что позволило бы избежать усложнений от переключения контекста потока, что характерно для однопроцессорных систем.
 
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 })
}
Выражения, которые нужно выполнять (т.е. аргументы <tt>future</tt>), пишутся в Job. Job является объектом с
* абстрактным типом t, описывающим результат вычислений job.
* методом task, без параметров, типа t, который обозначает выражение для вычислений.
* методом ret, который использует результат как только тот будет вычислен.
 
Вычислительный сервер создает n процессоров, во время своей инициализации. Каждый такой процессор периодически потребляет job, выполняет метод task и передает результат на в ret метод Job.
 
Пример демонстрирует использование абстрактных типов. Абстрактный тип t определяет результат работы, который может варьироваться от одного Job к другому. Без абстрактных типов было бы невозможно, реализовать подобный же класс в статическом, типобезопасном стиле. Потребовались бы динамическая проверка типов, приведение типов.
 
Вот пример использования вычислительного сервера, для оценки выражения 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
}
 
Содержимое почтового ящика состоит из набора сообщений. Сообщения добавляются к почтовому ящику методом <tt>send</tt>. Сообщения удаляются посредством метода <tt>receive</tt>, который передаёт обработчик сообщения f как аргумент. f является частичной функцией на сообщениях, со значениями в некотором произвольном типе. Обычно, эта функция реализуется с помощью соответствия по шаблону ''(pattern matching expression)''.
Метод <tt>receive</tt> блокируется пока есть сообщение в почтовом ящике для которого процессор определен. Сообщение затем, по обработке, удаляется из почтового ящика и блокированный поток перезапускается.
 
Как отправленные сообщения, так и полученные, упорядочены во времени. Получатель r применяется к соответствующему сообщению m только если нет другой пары (сообщение, получатель), которая предшествует (m, r) на частичном упорядочении в парах.
 
Простой пример использования почтовых ящиков. Рассмотрим одноместный буфер:
 
class OnePlaceBuffer {
private val m = new MailBox; // An internal mailbox
private case class Empty, Full(x: int); // Types of messages we deal
with
m send Empty; // Initialization
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.
 
private val sent = new LinkedList[Any]
private var lastSent = sent
private val receivers = new LinkedList[Receiver]
private var lastReceiver = receivers
 
Mailbox класс использует два связных списка, один для отправки необработанных сообщений,
другой - для ожидания обработчиков.
 
def send(msg: Any): unit = 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)
}
Метод send сначала проверяет применима ли к сообщению функция <tt>f</tt> обработчика к сообщению, что уже было послано но, ещё не обрабатывалось. Если это верно, поток немедленно применяет 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 который блокируется только на определенный интервал времени. Если в течение оговоренного времени (в миллисекундах), никакое сообщение не приходит, процессор сообщения <tt>f</tt> будет разблокирован специальным сообщением TIME-OUT. Реализация 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)
}
} // end MailBox
Различия очевидны.
 
== Акторы ==
 
В главе 3 представлен набросок электронного аукциона. Этот сервис основывался на высокоуровневых процессах - акторах, которые управляются сообщениями в почтовом ящике, используя сравнение по образцу. Актор является просто потоком, основа коммуникации которого - почтовый ящик. Акторы, следовательно, определяются как mixin композиция расширения класса Thread с классом MailBox.
 
abstract class Actor extends Thread with MailBox
 
[[Категория:Языки программирования]]
 
== Аннотации вариантности ==