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

23 365 байт добавлено ,  8 лет назад
Добавлен перевод главы 7.
м
(Добавлен перевод главы 7.)
 
<pre>
Тип = ... | идентификатор
</pre>
 
 
<pre>
Выр = ... | Выр '.' Выр | 'new' Выр | 'this'
</pre>
 
 
= Case-классы и сопоставление с образцом =
 
Допустим, мы хотим написать интерпретатор арифметических функций. Чтобы не усложнять задачу, ограничимся только числами и оператором <tt>+</tt>. Такие выражения могут быть представлены как иерархия классов с абстрактным базовым классом <tt>Expr</tt> в корне и двумя подклассами <tt>Number</tt> и <tt>Sum</tt>. Тогда выражение <tt>1 + (3 + 7)</tt> будет представлено как
 
<font size=3><syntaxhighlight lang=Scala>
new Sum(new Number(1), new Sum(new Number(3), new Number(7)))
</syntaxhighlight></font>
 
Теперь интерпретатор такого выражения должен знать, какого оно вида (<tt>Number</tt> или <tt>Sum</tt>), и должен иметь доступ к компонентам выражения. Следующая реализация предоставляет все необходимые методы:
 
<font size=3><syntaxhighlight lang=Scala>
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
}
</syntaxhighlight></font>
 
С такой классификацией и методами доступа написать интерпретатор легко:
 
<font size=3><syntaxhighlight lang=Scala>
def eval(e: Expr): Int = {
if (e.isNumber) e.numValue
else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
else error("неопознанный тип выражения")
}
</syntaxhighlight></font>
 
Впрочем, определять все эти методы в классах <tt>Number</tt> и <tt>Sum</tt> довольно утомительно. Более того, проблема становится еще хуже, если мы хотим добавить новые формы выражений. Например, рассмотрим добавление новой формы выражения <tt>Prod</tt> со всей предыдущей классификацией и методами доступа, мы также хотим ввести новый абстрактный метод <tt>isProduct</tt> в класс <tt>Expr</tt> и реализовать этот метод в подклассах <tt>Number</tt>, <tt>Sum</tt> и <tt>Prod</tt>. Необходимость модифицировать существующий код, когда система растет, всегда проблематично, поскольку это затрудняет контроль версий и поддержку.
 
Объектно-ориентированное программирование обещает, что такие модификации не обязательны, поскольку их можно избежать, переиспользуя существующий неизменяющийся код через механизм наследования. Действительно, более объектно-ориентированная организация решает проблему. Идея состоит в том, чтобы сделать операцию "высшего уровня" <tt>eval</tt> методом каждого класса выражений вместо того, чтобы реализовывать ее как функцию вне иерархии классов выражений, как мы делали прежде. Поскольку <tt>eval</tt> теперь — метод всех классов выражений, классификация и методы доступа становятся излишними, и реализация сильно упрощается:
 
<font size=3><syntaxhighlight lang=Scala>
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
}
</syntaxhighlight></font>
 
Более того, добавление нового класса <tt>Prod</tt> не ведет к изменениям существующего кода:
 
<font size=3><syntaxhighlight lang=Scala>
class Prod(e1: Expr, e2: Expr) extends Expr {
def eval: Int = e1.eval * e2.eval
}
</syntaxhighlight></font>
 
Из этого примера мы можем сделать вывод, что объектно-ориентированная организация — это лучшим подход для создания систем, которые должны быть расширяемы новыми типами данных. Но есть и другой способ, которым мы можем захотеть расширить пример с выражениями. Мы можем также захотеть добавить новые ''операции'' с выражениями. Например, добавить операцию, которая выводит на экран вывода дерево выражения.
 
Если мы определили классификацию и методы доступа, такую операцию можно легко написать в виде внешней функции. Вот пример:
 
<font size=3><syntaxhighlight lang=Scala>
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("неопознанный тип выражения")
}
</syntaxhighlight></font>
 
Но если мы выбрали объектно-ориентированную организацию выражений, нам потребуется добавлять новую процедуру <tt>print</tt> к каждому классу:
 
<font size=3><syntaxhighlight lang=Scala>
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(")")
}
}
</syntaxhighlight></font>
 
Обратите внимание, что классический объектно-ориентированный подход требует модификации всех существующих классов, когда система расширяется новой операцией.
 
Вот еще один способ, которым мы можем хотеть расширить интерпретатор. Рассмотрим упрощение выражений. Например, мы хотим написать функцию, которая переписывает выражение из формы <tt>a * b + a * c</tt> в форму <tt>a * (b + c)</tt>. Эта операция требует смотреть больше чем на один узел дерева выражения одновременно. Это нельзя реализовать при помощи метода в каждом типе выражений, если только этот метод не рассматривает и другие узлы. Так что мы вынуждены заводить классификацию и методы доступа в этом случае. Это опять возвращает нас к началу и ко всем проблемам расширяемости и необходимости написания большого количества кода.
 
Если присмотреться, можно заметить, что единственный смысл классификации и функций доступа в том, чтобы ''обратить'' процесс конструирования данных. Они позволяют нам определять, во-первых, какой подкласс абстрактного класса использован, и во-вторых, каковы были аргументы конструктора. Поскольку эта ситуация довольно часть встречается, в Scala есть способ ее автоматизации при помощи case-классов.
 
== Case-классы и case-объекты ==
 
''Case-классы'' и ''case-объекты'' (вариации) определяются как обычные классы и объекты, за исключением того, что перед определением ставится модифиатор <tt>'''case'''</tt>. Например, определения
 
<font size=3><syntaxhighlight lang=Scala>
abstract class Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr
</syntaxhighlight></font>
 
вводят <tt>Number</tt> и <tt>Sum</tt> как case-классы. Модификатор <tt>'''case'''</tt> перед определением класса имеет следующие эффекты:
 
1. У case-классов есть неявная функция конструктора, одноименная с классом. В нашем примере будут добавлены эти две функции:
 
<font size=3><syntaxhighlight lang=Scala>
def Number(n: Int) = new Number(n)
def Sum(e1: Expr, e2: Expr) = new Sum(e1, e2)
</syntaxhighlight></font>
 
Теперь можно конструировать деревья выражений немного более кратко:
 
<font size=3><syntaxhighlight lang=Scala>
Sum(Sum(Number(1), Number(2)), Number(3))
</syntaxhighlight></font>
 
2. У case-классов и case-объектов есть неявные реализации методов <tt>toString</tt>, <tt>equals</tt> и <tt>hashCode</tt>, которые переписывают одноименные методы класса <tt>AnyRef</tt>. Реализация этих методов принимает во внимание структуру членов case-класса в каждом случае. Метод <tt>toString</tt> представляет дерево выражения так, как оно было сконструировано. Поэтому
 
<font size=3><syntaxhighlight lang=Scala>
Sum(Sum(Number(1), Number(2)), Number(3))
</syntaxhighlight></font>
 
будет преобразовано в точно такую же строку, тогда как реализация метода <tt>toString</tt> в классе <tt>AnyRef</tt> по умолчанию вернула бы строку, состоящую из имени самого внешнего конструктора <tt>Sum</tt> и числа. Метод <tt>equals</tt> считает два две сущности case-класса равными, если они были сконструированы одинаковыми конструкторами с попарно равными аргументами. Это также влияет на реализацию <tt>==</tt> и <tt>!=</tt>, которые реализованы в Scala в терминах <tt>equals</tt>. Итак,
 
<font size=3><syntaxhighlight lang=Scala>
Sum(Number(1), Number(2)) == Sum(Number(1), Number(2))
</syntaxhighlight></font>
 
даст в ответе <tt>'''true'''</tt>. Если бы <tt>Number</tt> и <tt>Sum</tt> не были case-классами, то же самое выражение давало бы <tt>'''false'''</tt>, поскольку стандартная реализация <tt>equals</tt> в классе <tt>AnyRef</tt> всегда рассматривает объекты, созданные разными вызовавами конструктора, как разные. Метод <tt>hashCode</tt> следует тому же принципу, как остальные два метода. Он считает хэшкод имени конструктора case-класса и хэшкоды аргументов конструктора вместо того, чтобы брать адрес объекта, как это делает реализация <tt>hashCode</tt> по умолчанию.
 
3. У case-классов есть неявный нульарный метод, возвращающий аргументы конструктора. В нашем примере у <tt>Number</tt> появится метод доступа
 
<font size=3><syntaxhighlight lang=Scala>
def n: Int
</syntaxhighlight></font>
 
который возвращает параметр конструктора <tt>n</tt>, а у <tt>Sum</tt> — два метода
 
<font size=3><syntaxhighlight lang=Scala>
def e1: Expr, e2: Expr
</syntaxhighlight></font>
 
Заметьте, что для значения <tt>s</tt> типа <tt>Sum</tt> теперь можно писать <tt>s.e1</tt> для доступа к левому операнду. Но для значения <tt>e</tt> типа <tt>Expr</tt> выражение <tt>e.e1</tt> будет некорректно, потому что <tt>e1</tt> определен в <tt>Sum</tt> и не является методом класса <tt>Expr</tt>. Итак, как определить конструктор и получить доступ к аргументам конструктора для значений, чей статический тип — базовый класс <tt>Expr</tt>? Это решается четвертым и последним пунктом.
 
4. Сase-классы разрешают конструкцию ''образцов'' (patterns), которые относятся к конструкторам case-классов.
 
== Сопоставление с образцом ==
 
Сопоставление с образцом это обобщение выражения <tt>switch</tt> в C или Java для иерархий классов. Вместо выражения <tt>switch</tt> есть стандартный метод <tt>'''match'''</tt>, определенный в корневом классе Scala <tt>Any</tt>, и поэтому он доступен для всех объектов. Метод <tt>'''match'''</tt> принимает в качестве аргументов несколько случаев. Например, вот реализация <tt>eval</tt> при помощи сопоставления с образцом:
 
<font size=3><syntaxhighlight lang=Scala>
def eval(e: Expr): Int = e match {
case Number(n) => n
case Sum(l, r) => eval(l) + eval(r)
}
</font></syntaxhighlight>
 
В этом примере есть два случая. Каждый случай сопоставляет образец с выражением. Образцы сопоставляются со значениями селектора <tt>e</tt>. Первый образец в нашем примере, <tt>Number(n)</tt>, соответствует всем значениями вида <tt>Number(v)</tt>, где <tt>v</tt> — произвольное значение. В этом случае ''переменная образца'' <tt>n</tt> связывается со значением <tt>v</tt>. Аналогично, образец <tt>Sum(l, r)</tt> соответствует всем значениям селектора вида <tt>Sum(v<sub>1</sub>, v<sub>2</sub>)</tt> и связывает переменные образца <tt>l</tt> и <tt>r</tt> с <tt>v<sub>1</sub></tt> и <tt>v<sub>2</sub></tt> соответственно.
 
В общем, образцы строятся из:
* конструкторов case-классов, как <tt>Number</tt> и <tt>Sum</tt>, чьи аргументы также являются образцами,
* переменных образцов, как <tt>n</tt>, <tt>e1</tt>, <tt>e2</tt>,
* образца подстановочного символа (wildcard) <tt>_</tt>,
* литералов, как <tt>1</tt>, <tt>'''true'''</tt>, <tt>"abc"</tt>,
* идентификаторов констант, как <tt>MAXINT</tt>, <tt>EmptySet</tt>.
 
Переменные образца всегда начинаются с буквы в нижнем регистре, чтобы их можно было отличить от идентификаторов констант, которые начинаются с буквы в верхнем регистре. Каждое имя переменной может встречаться в образце лишь однажды. Например, выражение <tt>Sum(x, x)</tt> недопустимо в качестве образца, потому что переменная <tt>x</tt> встречается в нем дважды.
 
=== Смысл cопоставления с образцом ===
 
Выражение cопоставления с образцом
 
<code>
e match { case p1 => e1 … case p<sub>n</sub> => e<sub>n</sub> }
</code>
 
сопоставляет образцы ''p<sub>1</sub>, …, p<sub>n</sub>'' в том порядке, в котором они написаны, со значением селектора <tt>e</tt>.
 
* Образец конструктора ''С(p<sub>1</sub>, …, p<sub>n</sub>)'' соответствует всем значениям типа <tt>C</tt> (или его подтипа), которые были созданы при помощи аргументов <tt>C</tt>, соответствующих образцам ''p<sub>1</sub>, …, p<sub>n</sub>''.
* Образец переменной <tt>x</tt> соответствует любому значению и связывает имя переменной с этим значением.
* Образец подстановочного символа ‘<tt>_</tt>’ соотвтествует любому значению, но не связывает имени с этим значением.
* Образец константы <tt>C</tt> соответствует значению, равному (в терминах <tt>==</tt>) <tt>C</tt>.
 
Выражение сопоставления с образцом переписывает правую часть первого случая, чей образец соответствует значению селектора. Ссылки на переменные образца заменяются соответствующими аргументами конструктора. Если ни один из образцов не подошел, выражение сопоставления с образцом завершается с исключением <tt>MatchError</tt>.
 
'''Пример 7.2.1''' Наша модель подстановки для вычисления программ довольно естественно расширяется для сопоставления с образцом. Например, вот как переписывается применение <tt>eval</tt> к простому выражению:
 
<pre>
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
</pre>
 
=== Сопоставление с образцом и методы ===
 
В предыдущем примере мы использовали сопоставление с образцом в функции, которая определена вне иерархии классов, на которой происходит сопоставление. Конечно, можно также определить функцию сопоставления внутри самой иерархии. Например, можно определить <tt>eval</tt> как метод базового класса <tt>Expr</tt>, не убирая из его реализации сопоставление с образцом:
 
<font size=3><syntaxhighlight lang=Scala>
abstract class Expr {
def eval: Int = this match {
case Number(n) => n
case Sum(e1, e2) => e1.eval + e2.eval
}
}
</syntaxhighlight></font>
 
'''Упражнение 7.2.2''' Рассмотрим следующие определения, представляющие деревья целых чисел. Эти определения можно рассматривать как альтернативное представление <tt>IntSet</tt>:
 
<font size=3><syntaxhighlight lang=Scala>
abstract class IntTree
case object EmptyTree extends IntTree
case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
</syntaxhighlight></font>
 
Закончите следующие реализации функций <tt>contains</tt> и <tt>insert</tt> для tt>IntTree/tt>:
 
<font size=3><syntaxhighlight lang=Scala>
def contains(t: IntTree, v: Int): Boolean = t match { …
}
def insert(t: IntTree, v: Int): IntTree = t match { …
}
</syntaxhighlight></font>
 
=== Анонимные функции сопоставления с образцом ===
 
До этого case-выражения всегда появлялись вместе с оператором <tt>match</tt>. Но можно также использовать case-выражения сами по себе. Блок case-выражений, такой как
 
<code>
{ case P<sub>1</sub> => E<sub>1</sub> … caseP<sub>n</sub> => E<sub>n</sub> }
</code>
 
это функция, которая сопоставляет свои аргументы с образцами ''P<sub>1</sub>, …, P<sub>n</sub>'', и возвращает одно из выражений ''E<sub>1</sub>, …, E<sub>n</sub>''. (Если ни один образец не подошел, функция вместо этого выбросит исключение <tt>MatchError</tt>). Другими словами, выражение сверху это короткая запись анонимной функции
 
<code>
(x => x match { case P<sub>1</sub> => E<sub>1</sub> … caseP<sub>n</sub> => E<sub>n</sub> })
</code>
 
где <tt>x</tt> это свежая переменная, которая не используется нигде кроме этого выражения.
 
= Обобщенные типы и методы =
83

правки