「Tutorial_6」の編集履歴（バックアップ）一覧はこちら

「Tutorial_6」の最新版変更点

追加された行はこの色になります。

削除された行はこの色になります。

 [[トップ>トップページ]] > [[チュートリアル和訳>Tutorial和訳]] > [[6 Case classes and pattern matching>Tutorial_6]]
 
 #co(){*6 Case classes and pattern matching
 A kind of data structure that often appears in programs is the tree. For example, interpreters and compilers usually represent programs internally as trees; XML documents are trees; and several kinds of containers are based on trees, like red-black trees.}
 *6 ケースクラスとパターンマッチング
 プログラムによく出てくるデータ構造の一つにツリーがあります。例えばインタプリタやコンパイラは通常、プログラムを内部的にツリーで表現しています。XML 文書はツリーです。ある種のコンテナは赤黒木のようなツリーに基づいています。 
 
 #co(){We will now examine how such trees are represented and manipulated in Scala through a small calculator program. The aim of this program is to manipulate very simple arithmetic expressions composed of sums, integer constants and variables. Two examples of such expressions are 1+2 and (x+x)+(7+y).}
 小さな電卓プログラムを通して、ツリーが Scala でどのように表現され操作されるのか見てみましょう。このプログラムの目的は、加法と整数定数と変数からなる非常に簡単な数式を操作することです。その例を２つ挙げると、1+2 や (x + x)+(7+ y) などです。 
 
 #co(){We first have to decide on a representation for such expressions. The most natural one is the tree, where nodes are operations (here, the addition) and leaves are values (here constants or variables).}
 最初にそのような数式をどのように表現するか決めましょう。最も自然な方法はツリーです。ノードが演算（ここでは加法）で、リーフが値（ここでは定数か変数）です。 
 
 #co(){In Java, such a tree would be represented using an abstract super-class for the trees, and one concrete sub-class per node or leaf. In a functional programming language, one would use an algebraic data-type for the same purpose. Scala provides the concept of case classes which is somewhat in between the two. Here is how they can be used to define the type of the trees for our example:}
 Java ではそういったツリーは、ツリーのための抽象スーパークラスと、ノードやリーフ毎に１つの具象サブクラスを用いて表現されるでしょう。関数型プログラミング言語では、同じ目的のために代数的データ型を用います。Scalaには、両者の中間的なものである&italic(){ケースクラス}があります。それをどうやって私たちのツリーの型を定義するのに用いるかを示します。 
 
  abstract class Tree
  case class Sum(l: Tree, r: Tree) extends Tree
  case class Var(n: String) extends Tree
  case class Const(v: Int) extends Tree
 #co(){The fact that classes Sum, Var and Const are declared as case classes means that they differ fromstandard classes in several respects:
 the new keyword is not mandatory to create instances of these classes (i.e. one can write Const(5) instead of new Const(5)),
 getter functions are automatically defined for the constructor parameters (i.e. it is possible to get the value of the v constructor parameter of some instance c of class Const just by writing c.v),
 default definitions for methods equals and hashCode are provided, which work on the structure of the instances and not on their identity,
 a default definition for method toString is provided, and prints the value in a “source form” (e.g. the tree for expression x+1 prints as Sum(Var(x),Const(1))),
 instances of these classes can be decomposed through pattern matching as we will see below.}
 Sum, Var, Const クラスがケースクラスとして宣言されていることは、いくつかの点で普通のクラスとは違うということを意味しています。
 -それらのクラスのインスタンスを作るのにキーワード &bold(){new} は必須ではありません。（すなわち、&bold(){new} Const(5) の代わりに Const(5) と書けます。）
 -コンストラクタのパラメータ用の getter 関数は自動的に定義されます。（すなわち、Const クラスのインスタンス c のコンストラクタのパラメータ v の値は、単に c.v と書けば取得できます。）
 -メソッド equals と hashCode はデフォルトで定義され、それらは同一性ではなくインスタンスの構造に基づいています。
 -toString メソッドはデフォルトで定義され、値を「ソース形式」で表示します（例えば、式 x+1 の式のツリーは Sum(Var(x),Const(1)) と表示されます）
 -これらのクラスのインスタンスは以下で見るように&italic(){パターンマッチング}を通して分解されます
 
 #co(){{Now that we have defined the data-type to represent our arithmetic expressions, we can start defining operations to manipulate them. We will start with a function to evaluate an expression in some environment. The aim of the environment is to give values to variables. For example, the expression x +1 evaluated in an environment which associates the value 5 to variable x, written {x→5}, gives 6 as result.}}
 数式を表現するデータ型を定義したので、つぎにそれを操作する演算を定義しましょう。ある&italic(){環境}で式を評価する関数から始めることにします。環境の目的は変数に値を与えることです。例えば式 x+1 の評価を、変数 x を値 5 に関連づけるような環境 {x→5} の元で行うと、結果 6 を得ます。 
 
 #co(){{We therefore have to find a way to represent environments. We could of course use some associative data-structure like a hash table, but we can also directly use functions! An environment is really nothing more than a function which associates a value to a (variable) name. The environment {x→5} given above can simply be written as follows in Scala:}}
 ここで環境を表現する方法を見つける必要があります。もちろんハッシュ表のような連想データ構造を使うこともできますが、直接に関数を使うこともできます！環境はまさに、値を（変数）名と関連付ける関数に他なりません。上で述べた環境 {x→5} は Scala では下記のように簡単に書けます。
 
  { case "x" => 5 }
 #co(){This notation defines a function which, when given the string "x" as argument, returns the integer 5, and fails with an exception otherwise.}
 この書き方で、引数として文字列 "x" が与えられたなら整数 5 を返し、他の場合には例外で失敗させる関数を定義できます。 
 
 #co(){Before writing the evaluation function, let us give a name to the type of the environments. We could of course always use the type String => Int for environments, but it simplifies the program if we introduce a name for this type, and makes future changes easier. This is accomplished in Scala with the following notation:}
 評価する関数を書く前に、環境の型に名前を付けましょう。もちろん、型 String => Int を環境のために使うこともできますが、この型に名前を付ければ、プログラムがシンプルになり将来の変更も容易になります。Scala では下記のように書けばよいのです。
 
  type Environment = String => Int
 #co(){Fromthen on, the type Environment can be used as an alias of the type of functions from String to Int.}
 以後、Environment 型は String から Int への関数の型の別名として使えます。 
 
 #co(){We can now give the definition of the evaluation function. Conceptually, it is very simple: the value of a sum of two expressions is simply the sumof the value of these expressions; the value of a variable is obtained directly from the environment; and the value of a constant is the constant itself. Expressing this in Scala is not more difficult:}
 では評価する関数の定義を行いましょう。概念としてはとても簡単です。２つの式の和の値は単にそれぞれの式の値の和です。変数の値は環境から直接得られます。そして定数の値は定数自身です。Scala でこれを表現するのは同じぐらい簡単です。 
 
  def eval(t: Tree, env: Environment): Int = t match {
    case Sum(l, r) => eval(l, env) + eval(r, env)
    case Var(n) => env(n)
    case Const(v) => v
  }
 #co(){This evaluation function works by performing pattern matching on the tree t. Intuitively, the meaning of the above definition should be clear:}
 この評価関数はツリー t に対して&italic(){パターンマッチング}を実行します。直感的には上記の定義は明確なはずです。
 
 #co(){it first checks if the tree t is a Sum, and if it is, it binds the left sub-tree to a new variable called l and the right sub-tree to a variable called r, and then proceeds with the evaluation of the expression following the arrow; this expression can (and does) make use of the variables bound by the pattern appearing on the left of the arrow, i.e. l and r,
 if the first check does not succeed, that is if the tree is not a Sum, it goes on and checks if t is a Var; if it is, it binds the name contained in the Var node to a variable n and proceeds with the right-hand expression,
 if the second check also fails, that is if t is neither a Sum nor a Var, it checks if it is a Const, and if it is, it binds the value contained in the Const node to a variable v and proceeds with the right-hand side,
 finally, if all checks fail, an exception is raised to signal the failure of the pattern matching expression; this could happen here only if more sub-classes of Tree were declared.}
 +まずツリー t が Sum であるかチェックし、もしそうなら左部分木を新しい変数 l に、右部分木を変数 r に束縛します。そして矢印に従って評価を進めます。矢印の左側のパターンによって束縛された変数 l と r を使用します。
 +もし最初のチェックが成功しなければ、すなわちツリーは Sum でなければ、続いて t は Var かチェックします。もしそうなら Var の含まれる名前を変数 n に束縛し、右辺の式を用います。
 +もし２番目のチェックにも失敗したなら、つまり t は Sum でも Var でもなければ、Const であるかチェックします。もしそうなら Const ノードに含まれる値を変数 v に束縛し、右辺へ進みます。
 +最後に、全てのチェックに失敗したなら、式のパターンマッチングの失敗を伝えるために例外が上げられます。ここで Treeのサブクラスが他に宣言されない限り、それは起きません。
 
 #co(){We see that the basic idea of pattern matching is to attempt to match a value to a series of patterns, and as soon as a pattern matches, extract and name various parts of the value, to finally evaluate some code which typically makes use of these named parts.}
 ある値を一連のパターンに順に当てはめ、マッチしたら直ちにその値の様々なパーツを取り出して名前をつけ、名付けられたパーツを用いてコードを評価する、というパターンマッチングの基本的なアイデアを見てきました。 
 
 #co(){A seasoned object-oriented programmer might wonder why we did not define eval as a method of class Tree and its subclasses. We could have done it actually, since Scala allows method definitions in case classes just like in normal classes. Deciding whether to use pattern matching or methods is therefore a matter of taste, but it also has important implications on extensibility:
 when using methods, it is easy to add a new kind of node as this can be done just by defining the sub-class of Tree for it; on the other hand, adding a new operation to manipulate the tree is tedious, as it requires modifications to all sub-classes of Tree,
 when using pattern matching, the situation is reversed: adding a new kind of node requires the modification of all functions which do patternmatching on the tree, to take the new node into account; on the other hand, adding a new operation is easy, by just defining it as an independent function.}
 年期の入ったオブジェクト指向プログラマは、なぜ eval を Tree クラスとそのサブクラスの&italic(){メソッド}にしなかったのか、不思議に思うかもしれません。実はそのようにもできます。Scalaではケースクラスのメソッド定義は普通のクラスのようにできるからです。それゆえパターンマッチングとメソッドのどちらを使うかは趣味の問題ですが、拡張性にも密接に関係します。
 -メソッドを用いれば、新しい種類のノードを追加することは Tree のサブクラスを定義することで簡単に行えます。しかしツリーを操作する新しい演算を追加するのは、Treeの全てのサブクラスの修正が必要なため面倒です
 -パターンマッチングを用いれば状況は逆転します。新しい種類のノードを追加するには、ツリーのパターンマッチングを行う全ての関数で、新しいノードを考慮するための修正が必要です。その一方で新しい演算を追加するのは簡単で、単に独立した関数を定義するだけです。
 
 #co(){To explore pattern matching further, let us define another operation on arithmetic expressions: symbolic derivation. The reader might remember the following rules regarding this operation:}
 パターンマッチングをもっと調べるために、別の数式への演算である微分シンボルを定義してみましょう。読者はこの演算に関する下記の規則を覚えているでしょうか。 
 
 #co(){ +the derivative of a sum is the sumof the derivatives,
 the derivative of some variable v is one if v is the variable relative to which the derivation takes place, and zero otherwise,
 the derivative of a constant is zero.}
 +和の導関数は、導関数の和。
 +変数 v の導関数は、v が微分を行う変数なら 1 、さもなければ 0。
 +定数の微分は 0。
 
 #co(){These rules can be translated almost literally into Scala code, to obtain the following definition:}
 これらの規則はほとんど字句通り Scala のコードに変換でき、下記の定義を得ます： 
 
  def derive(t: Tree, v: String): Tree = t match {
    case Sum(l, r) => Sum(derive(l, v), derive(r, v))
    case Var(n) if (v == n) => Const(1)
    case _ => Const(0)
  }
 #co(){This function introduces two new concepts related to patternmatching.  First of all, the case expression for variables has a guard, an expression following the if keyword.  This guard prevents pattern matching from succeeding unless its expression is true. Here it is used to make sure that we return the constant 1 only if the name of the variable being derived is the same as the derivation variable v. The second new feature of patternmatching used here is the wild-card, written _, which is a pattern
 matching any value, without giving it a name.}
 この関数ではパターンマッチングに関する新しい概念を２つ導入します。最初に、変数に関する &bold(){case} 式には&italic(){ガード}、すなわち &bold(){if} キーワードに続く式があります。ガードは、式が真でなければパターンマッチングを失敗させます。ここでは、微分される変数名が微分する変数 v と等しい場合のみ定数 1 を返すように使われています。２つめにここで使われているパターンマッチングの特徴は、_ で示される&italic(){ワイルドカード}、どんな値にもマッチするパターンで、値に名前をつける必要はありません。 
 
 #co(){{We did not explore the whole power of pattern matching yet, but we will stop here in order to keep this document short. We still want to see how the two functions above perform on a real example. For that purpose, let’s write a simple main function which performs several operations on the expression (x + x)+(7+ y): it first computes its value in the environment {x→5, y→7}, then computes its derivative relative to x and then y.}}
 パターンマッチングの能力を全て調べてはいませんが、この文書が長くなりすぎないようにここで止めておきましょう。上記２つの関数が実際の例でどう動くか見たいと思います。この目的のため、簡単な main 関数を書いて、式 (x + x)+(7+ y) に対する演算を幾つか行ってみましょう。最初に環境 {x→5, y→7} に対する値を計算し、次いで x と y とで微分した導関数を求めましょう。 
 
  def main(args: Array[String]) {
    val exp: Tree = Sum(Sum(Var("x"),Var("x")),Sum(Const(7),Var("y")))
    val env: Environment = { case "x" => 5 case "y" => 7 }
    println("Expression: " + exp)
    println("Evaluation with x=5, y=7: " + eval(exp, env))
    println("Derivative relative to x:\n " + derive(exp, "x"))
    println("Derivative relative to y:\n " + derive(exp, "y"))
  }
 #co(){Executing this program, we get the expected output:}
 プログラムを実行すると、期待した結果が得られます。 
 
  Expression: Sum(Sum(Var(x),Var(x)),Sum(Const(7),Var(y)))
  Evaluation with x=5, y=7: 24
  Derivative relative to x:
  Sum(Sum(Const(1),Const(1)),Sum(Const(0),Const(0)))
  Derivative relative to y:
  Sum(Sum(Const(0),Const(0)),Sum(Const(0),Const(1)))
 #co(){By examining the output, we see that the result of the derivative should be simplified before being presented to the user. Defining a basic simplification function using pattern matching is an interesting (but surprisingly tricky) problem, left as an exercise for the reader.}
 結果を見ると、導関数の結果はユーザに見せる前に簡略化すべきであることが判ります。パターンマッチングを用いて基本的な簡約関数を定義することは興味深い（しかし驚く程に巧妙な）問題です。読者の練習問題としておきます。
 
-#center(){[[前ページ>>Tutorial_5]]　　[[目次>>Tutorial和訳]]　　[[次ページ>>Tutorial_7]]}
+#center(){[[前ページ>Tutorial_5]]　　[[目次>Tutorial和訳]]　　[[次ページ>Tutorial_7]]}
 ----
 - 最終的なプログラムを載せてもらえませんか？  -- 名無しさん  (2009-12-01 14:01:45)
 #comment()