ScalaByExample_ja(draft) のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• ScalaByExample_ja(draft) へ行く。
  • 1 (2008-03-20 (木) 13:03:09)

---

Scala By Example を淡々と訳すよ。

Chapter 1 - Introduction †

Scalaはオブジェクト指向と関数型のプログラミングをスムースに統合します．Scalaは，一般的なプログラミングパターンを，簡潔で，エレガントで，型安全な方法によって表現できるようにデザインされています．Scalaはいくつかの革新的な構文を導入しています．例えば：

• abstract typeとmixin compositionにより，オブジェクトとモジュールシステムのコンセプトを統合します．
• クラス階層をまたがるパターンマッチングにより，関数型とオブジェクト指向のデータアクセスを統合します．これによりXMLツリーの処理が格段に単純になります．
• 柔軟な構文と型システムは先進的なライブラリとドメイン特化言語の構成を可能にします．

同時に，ScalaはJavaと互換性があります．Javaのライブラリとフレームワークをglue codeや追加の宣言なしで使うことができます．

この文書は，Scalaを一連の例題を通してインフォーマルな方法で紹介します．

2章と3章はScalaを面白くする幾つかの機能について説明します．続く章ではScalaのlanguage constructを徹底的なやりかたで紹介します．ここでは単純な式や関数から始めて，オブジェクトとクラス，リストとストリーム，可変な状態，パターンマッチングなどを通して，面白いプログラミングテクニックを示すようなより完全な例題まで発展します．このインフォーマルな解説は，Scalaの仕様をより詳細で正確に定めるScala Language Reference Manualで補完されることを意図しています．

Acknowledgement. AbelsonとSussmanの ``Structure and Interpretation of Computer Programs''(計算機プログラムの構造と解釈) [ASS96] には多大な借りがあります．その多くの例はこの文書にも掲載しました． もちろん，それぞれの例題の言語は SchemeからScalaに変えています． さらに，適切なところではオブジェクト指向の構文を例題に用いています．

Chapter 2 - A First Example †

最初の例題として，Scalaでのクイックソートの実装を次に示します．

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

この実装は誰かがJavaやCで書くものと極めて似ています．同じ演算子と似たような制御構造を使っています．いくつかの軽微な構文的な違いもあります．特に：

• 定義は予約語で始まります．関数定義は def で始まり，変数定義は var で始まり値 (読み取り専用の変数) の定義は valで始まります．

• シンボルに宣言された型はシンボルとコロンの後に与えます． 宣言された型はしばしば省略できます．これはコンパイラが文脈から型を推論できるためです．

• 配列型は T[] ではなく Array[T] と書き， 配列の要素の選択は a[i] ではなく a(i) と書きます．

• 関数は他の関数の内側にネストできます． ネストされた関数は外側の関数の引数とローカル変数にアクセスできます． 例えば，配列の変数名xsは関数 swapとsort1で可視で，それゆえに引数として渡す必要がありません．

今までのところ，Scalaはいくつかの構文的な特徴を備えている極めて伝統的な言語のように見えます．実際に，命令的またはオブジェクト指向のスタイルでプログラムを書けます．このことは重要です．Scalaのコンポーネントを，Java, C#やVisual Basicのような主流の言語で書かれたコンポーネントと結合するのを容易にする一つの要素だからです．

しかしながら，プログラムを全く違って見えるやり方で書く事もできます．今度は関数的なスタイルで書かれたクイックソートです．

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

この関数型プログラムはクイックソートのエッセンスを簡潔な形でとらえています：

• もし配列が空か 中身が単一の要素だった場合，それはソート済みであるため，ただちに戻します．
• もし配列が空でないならば，ピボットとして中間から要素を選びます．
• 配列を，ピボットより小さいものと，大きいものを含んでいる2つの部分配列と，等しいものを含んでいる3番目の部分配列に分割します．
• 最初の2つの部分配列を，sort関数を再帰的に呼び出してソートします．(脚注：これは必ずしも命令的なほうのアルゴリズムがやっていることではない；)
• 3つの部分配列を結合させることで結果が得られます．

命令的な実装と関数的な実装の両方が同じ漸近的計算量をもっています - 平均計算量で O(N log(N)) そして最大計算量が O(N^2) です．しかし命令的な実装では引数で与えられた配列を変更することでその場で操作していますが，関数的な実装では新しい配列を戻し引数の配列を変更しないままにしています．関数的な実装では命令的なものよりも一時的なメモリを多く必要とします．

関数的な実装は，Scalaが，配列の関数的な操作に特化しているかのように見せます．実際のところ，それは違います；この例題で使ったすべての操作は 標準のScalaライブラリの一部である Seq[T]クラスの単純なライブラリメソッドで，それ自身Scalaで実装されています． 配列はSeqのインスタンスであるので全てのメソッドが使えます．

特に，引数として述語関数を取るメソッドfilterがあります．この述語関数は配列の要素を真理値に写像しなければなりません．filterの結果はオリジナルの配列の要素で述語関数がtrueとなるすべての要素からなる配列です．それゆえ型Array[T]のオブジェクトのfilterメソッドは次のシグネチャを持ちます．

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

ここで，T => Boolean は型 Tの要素をとり Booleanの値を返す関数の型です． filterのような他の関数を引数に取ったり戻したりする関数は高階関数と呼ばれます．

Scalaは識別子と演算子の名前を区別しません．識別子は文字で始まる文字と数値の列か，または``+,``*や``:''などの特別なキャラクタの列です． どんな識別子もScalaでは中置記法の演算子として使えます． 二項演算 E op E' は常に E.op(E') というメソッド呼び出しとして解釈されます．これは文字で始まる二項演算子でも成立します．つまり，式 xs filter (pivot >) は メソッド呼び出し xs.filter(pivot >) と等価です．

クイックそーとプログラムにおいて，filterは無名関数に3回適用されています．第一引数pivot > は，引数xをとり値 pivot>x を返します．これは部分適用された関数の例です．この関数を書くほかの等価な方法は，引数を明示的に書いて x=> pivot > x となります．この関数は 匿名です，つまり名前と共に定義されているわけではありません． 仮引数xの型は，Scalaコンパイラが関数が使われている文脈から自動的に推論できるために省略されています．要約すると， xs.filter(pivot >) はリストxsの要素のうちpivotより小さい全ての要素からなるリストを返します．

最初の命令的なクイックソートの実装をもういちど詳細に見ると，2番目の解で使われている多くのlanguage constructsが，ごまかされた形になっています．

例えば，+,-や<のような``標準の''二項演算子は何ら特別なやり方で扱われていません．それらは，appendのように左辺のメソッドになっています．その結果，式 i+1 は i.+(1) という 整数値 i の+ メソッドの呼び出しとみなされます． もちろん，コンパイラが整数引数に対する+メソッドの呼び出しを認識して効率の良いインラインのコードを生成するのは自由(適切に賢ければ，またそう期待されているが)です．

効率とエラー診断のためにwhileループはScalaのプリミティブな構文になっています．しかし原理的には，それはpredefinedな関数とすることもできます．これはその実装です：

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

While関数はテスト関数を1つめの引数として取ります．この関数は引数をとらず真理値を返します．2つめ引数として引数を取らず型Unitの結果を返すコマンド関数を引数として取ります．Whileはテスト関数がtrueを返す間はコマンド関数を実行します．

ScalaのUnit型はだいたいJavaのvoid型に対応します； これは重要な結果を返さない関数に使われます．実際のところ，Scalaは式指向(expression-oriented language)全ての式は何らかの結果を返す必要があります．もしreturn式が陽に与えられていない場合，``unitと発音される値()が仮定されます．この値は型Unitをもちます．Unitを返す関数は手続きとも呼ばれます．このことを明示するような，クイックソートの最初の実装で使ったswap関数のより ``式指向な定式化を次に示します：

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

この関数の結果は単に最後の式です - return キーワードは必要ではないです． 陽に値を返す関数は常に，本体や式の定義の前に ``=''が必要であることに注意してください．

Chapter 3 - Programming with Actors and Messages &dagger;

Chapter 4 - Expressions and Simple Functions &dagger;

これまでの例題はScalaで何ができるかの印象を与えました．ここからはより系統だった形で構文を導入します．まずは一番小さいレベルである式と関数から始めます．

4.1 Expressions and Simple Functions &dagger;

Scalaシステムにはファンシーな計算機(calculator)のようなインタプリタが付いてきます．ユーザーは式を入力することで計算機とやりとりします．計算機は評価した結果とその型を返します．例えば：

scala> 87 + 145 
unnamed0: Int = 232 

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

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

部分式に名前をつけてあとから式の代わりにその名前を使うこともできます：

scala> def scale = 5 
scale: Int 

scala> 7 * scale 
unnamed3: Int = 35 

scala> def pi = 3.141592653589793 
pi: Double

scala> def radius = 10 
radius: Int 

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

定義は予約語 def ではじまります；定義は=記号に続く式を表す名前を導入します．インタプリタは導入された名前とその型を返します．

def x = e のような定義を実行しても式eは評価されません．その代わりxが使われる全てのところでeが評価されます．代わりに，Scalaは値定義の構文 val x = e を提供します．これは右手の e を定義の評価の一部として実行します．もし続けてxが使われたら，それは事前に計算されたeの値に置き換えられるので，再度評価されることはありません．

式はどのように評価されるのでしょうか？演算子とオペランドからなる式は次の単純化ステップを繰り返し適用することで評価されます．

• いちばん左の操作(operation)を選ぶ
• そのオペランドを評価する
• オペランドの値に演算子(operator)を適用する

def で定義された名前は(未評価の)定義の右手に置き換えることで評価されます．valで定義された名前は定義の右手の値で置き換えることで評価されます．評価プロセスは値に辿り着いた時点で停止します．値とは文字列，数値，配列やリストなどのデータの事です．

Example 4.4.1 &dagger;

ここで数式の評価のようすを示します．

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

4.2 Parameters &dagger;

def を使って，パラメータを取る関数も定義できます．例えば：

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

scala> square(2) 
unnamed0: Double = 4.0 

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

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

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

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

関数のパラメータは関数名の後に続き，カッコで囲まれます．全てのパラメータには，パラメータ名とコロンに続けて型を示します．いまのところ，scala.Doubleの倍精度数のような基本的な数値型しか用いません．Scalaはいくつかの標準的な型についてtype aliasesを定義しているため，Javaと同じように数値型を書くことができます．例えば double は scala.Doublue の type alias で int は scala.Int の type aliasです．

(続き p. 13 Functions with parameters are ... から)