Scala：Rainy Day Codings：So-net blog

	ブログをはじめるログイン

文脈自由文法から無駄を省く　 [Scala]

文脈自由文法を与えられたときにその文法から non-productive な規則と unreachable な規則を取り除くアルゴリズムを Scala で実装してみました。

以下のような文脈自由文法を考えます（Parsing Techniques の p.49 より）。

S -> A B | D E
A -> a
B -> b C
C -> c
D -> d F
E -> e
F -> f D

* non-productive な規則の除去

まず、この文法の D とF に注目してみます。書き換えの中で D が登場すると D -> d F しか使える規則がないので D を d F に書き換えることになりますが、ここで現れた F を書き換えるには F -> f D を使うしかありません。すると再び D が現れるので D -> d F を使うことになります。

つまりこの文法では D または F はひとたび現れると取り除く（＝終端記号だけにする）ことができず、したがって文を生成することができなくなるということがわかります。このような規則を non-productive な規則と呼びます。

これを除去するには、以下の手順を踏みます。

- 終端記号だけが右辺に現れる規則は productive な規則とみなす
- 終端記号か productive な非終端記号だけが右辺に現れる規則も productive とみなしてよい
- これを繰り返して productive な規則に関する知識を増やしていき、新たな知識が得られなくなったところで終了。最後まで productive な規則に含まれなかったものは non-productive とみなされる。

上記の例でいうと、

1. 終端記号は productive なので A -> a, C -> c, E -> e の3つも productive
2. {A, C, E} は productive なので B -> b C も productive
3. {A, B, C, E} は productive なので S -> A B も productive

となり、

S -> A B
A -> a
B -> b C
C -> c
E -> e

が残ります。

* unreachable な規則の除去

残る規則をよくみると E -> e という規則は実はスタートシンボルから始まる書き換えで到達することはありませんので無駄です。このような規則を除去するには以下の手順を踏みます。

- スタートシンボルが左辺に現れる規則とその右辺の記号は reachable である
- reachable な記号が左辺に現れる規則も reachable である
- これを繰り返して reachable な規則に関する知識を増やしていき、新たな知識が得られなくなったところで終了

先ほどとパターンが同じです。このように与えられた初期知識を推論規則によって拡げていくアルゴリズムを closure algorithm というそうです。

以上を Scala で実装したのがこちらです。

import scala.collection.immutable._

// Type definitions for CFG
abstract class V
case class NonTerminal(sym: Symbol) extends V { override def toString = sym.name}
case class Terminal(sym: Symbol) extends V { override def toString = sym.name}

case class Rule(lhs: V, rhs: Seq[V]) {
  override def toString = {
    lhs + " ==> (" + rhs.map{_.toString}.reduceLeft[String]{_ + ", " + _} + ")"
  }
}
type rules = Set[Rule]

case class Grammar(rules: rules, start: NonTerminal)

// DSL for CFG
object Rules { def apply(rules: Rule*) = Set(rules: _*) }
object Start { def apply(nt: Symbol) = NonTerminal(nt) }
class LeftHand(left: Symbol) {
  def ==> (right: Symbol*) = {
    def symbolToV(s: Symbol) =
      if (s.name(0).isUpperCase) NonTerminal(s) else Terminal(s)
    Rule(NonTerminal(left), right.map(symbolToV))
  }
}
implicit def sym2lh(sym: Symbol) = new LeftHand(sym)

val grammar = Grammar(
  Rules(
    'S ==> ('A, 'B),
    'S ==> ('D, 'E),
    'A ==> ('a),
    'B ==> ('b, 'C),
    'C ==> ('c),
    'D ==> ('d, 'F),
    'E ==> ('e),
    'F ==> ('d, 'D)
  ),
  Start('S)
)

def removeNonProductive(cfg: Grammar) = {
  def improve(unknown: rules, knownToBeProductive: rules): rules = {
    val newKnowledge =
      unknown.filter { rule =>
        rule.rhs.forall {
          case Terminal(_) => true /* base knowledge */
          case nt @ NonTerminal(sym) =>
            knownToBeProductive.exists { rule => rule.lhs == nt }
        }
      }
    if (newKnowledge.isEmpty) knownToBeProductive
    else improve(unknown -- newKnowledge, knownToBeProductive ++ newKnowledge)
  }
  Grammar(improve(cfg.rules, Set[Rule]()), cfg.start)
}

def removeUnreachable(cfg: Grammar) = {
  def improve(unknown: rules, knownToBeReachable: rules): rules = {
    val newKnowledge =
      unknown.filter { rule =>
        rule.lhs == cfg.start /* base knowledge */ ||
        knownToBeReachable.exists { rule2 => rule2.rhs contains rule.lhs }
      }
    if (newKnowledge.isEmpty) knownToBeReachable
    else improve(unknown -- newKnowledge, knownToBeReachable ++ newKnowledge)
  }
  Grammar(improve(cfg.rules, Set[Rule]()), cfg.start)
}

def cleanup(cfg: Grammar) = removeUnreachable(removeNonProductive(cfg))

println(grammar)
println(removeNonProductive(grammar))
println(cleanup(grammar))

2008-02-20 08:06 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

句構造文法から文を生成する　 [Scala]

Type 0 以下の句構造規則を与えられるとひたすらその言語に含まれる文を生成していくプログラムを Scala で書いてみました。

キューを用意して幅優先探索の要領で、
- キューには最初はスタートシンボルだけ入っている
- キューから1つとって句構造規則で置き換えたものをまたキューに突っ込む
- キューから取ったものが文の形をしていれば（終端記号だけで構成されていれば）それを結果とする
というのを繰り返していきます。

import scala.collection.mutable._
import java.util.NoSuchElementException

abstract class V
case class NonTerminal(sym: Symbol) extends V { override def toString = sym.name}
case class Terminal(sym: Symbol) extends V { override def toString = sym.name}

type rule = (Seq[V], Seq[V])
type sentential = Seq[V]

case class Grammar(rules: Seq[rule], start: NonTerminal)

case class SentenceIterator(grammar: Grammar) extends Iterator[sentential] {
  val queue = new Queue[sentential]
  queue += List(grammar.start)

  def lookahead() = {
    def isSentence(s: sentential) =
      s.forall { case Terminal(_) => true case _ => false }
    try {
      //println(queue)
      var s = queue.dequeue()
      while (!isSentence(s)) {
        for ((l, r) <- grammar.rules) {
          val i = s.indexOf(l)
          if (i >= 0)
            queue += (s.slice(0, i) ++ r ++ s.slice(i + l.length, s.length))
        }
        //println(queue)
        s = queue.dequeue()
      }
      Some(s)
    } catch {
      case e: NoSuchElementException => None
    }
  }

  var sentence: Option[sentential] = lookahead()
  def hasNext = sentence.isDefined
  def next() = {
    sentence match {
      case Some(s) => sentence = lookahead(); s
      case _ => error("")
    }
  }
}

// DSL for PSG
object Rules { def apply(pairs: rule*) = pairs.toList }
object Start { def apply(nt: Symbol) = NonTerminal(nt) }
def rule(left: Symbol*)(right: Symbol*): rule = {
  def symbolToV(s: Symbol) = 
    if (s.name(0).isUpperCase) NonTerminal(s) else Terminal(s)
  (left.map(symbolToV), right.map(symbolToV))
}

val grammar = Grammar(
  Rules(
    rule ('Name)                    ('tom),
    rule ('Name)                    ('dick),
    rule ('Name)                    ('harry),
    rule ('Sentence)                ('Name),
    rule ('Sentence)                ('List, 'End),
    rule ('List)                    ('Name),
    rule ('List)                    ('List, Symbol(","), 'Name),
    rule (Symbol(","), 'Name, 'End) ('and, 'Name)
  ),
  Start('Sentence)
)

/*
// the a^n b^n c^n grammar
val grammar = Grammar(
  Rules(
    rule ('S)         ('a, 'b, 'c),
    rule ('S)         ('a, 'S, 'Q),
    rule ('b, 'Q, 'c) ('b, 'b, 'c, 'c),
    rule ('c, 'Q)     ('Q, 'c)
  ),
  Start('S)
)
*/

val n = args(0).toInt
for (i <- SentenceIterator(grammar) take n)
  println(i)

文法の例は Parsing Techniques という本から採りました。コメントアウトされているほうは abc, aabbcc, aaabbbccc... を生成する規則なのですがどうも2個目まではすぐ見つかるけど3個目はこの方法だとすごく時間がかかるようです。（そしてこのイテレータの実装だと2個目を取り出すときに3個目も見つけておくようになっているため事実上1個までしか出力できない）

2008-02-11 14:05 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

scalac のオプション探検　 [Scala]

最近プログラミング的なことが何もできてなくて書けることが無いので scalac のちょっと興味深いコンパイラオプションの話を2点お届けします。

* -Xprint:<phase>

Scala コンパイラは入力プログラムを構文解析後、構文木に対するさまざまな変換フェイズの後に JVM バイトコードに辿り着くようです。

-Xprint オプションを使うとその各フェイズで Scala プログラムがどんな姿をしているかを見ることができます。

ためしに以下のようなプログラムを用意しましょう。

object For {
  def main(args: Array[String]) = {
    for (i <- 1 to 10) {
      println(i)
    }
  }
}

コンパイルのフェイズにどんなものがあるかは scalac -Xshow-phases で見ることが出来ます。おそらく上から下に進むのでしょうね。

PS D:\scala> scalac -Xshow-phases
namer
typer
superaccessors
pickler
refchecks
liftcode
uncurry
tailcalls
explicitouter
erasure
lazyvals
lambdalift
constructors
flatten
mixin
cleanup
icode
inliner
closelim
dce
jvm
sample-phase

上記のプログラムは namer というフェイズを経るとどうなるのでしょうか。

PS D:\scala> scalac "-Xprint:namer" For.scala
[[syntax trees at end of namer]]// Scala source: For.scala
package <empty> {
  final object For extends scala.ScalaObject {
    def <init>() = {
      super.<init>();
      ()
    };
    def main(args: Array[String]) = 1.to(10).foreach(((i) => println(i)))
  }
}

"1 to 10" の to が実は to というメソッド呼び出しであるということが分かります。

では typer というフェイズを経るとどうなるのでしょうか。

PS D:\scala> scalac "-Xprint:typer" For.scala
[[syntax trees at end of typer]]// Scala source: For.scala
package <empty> {
  final object For extends java.lang.Object with ScalaObject {
    def this(): object For = {
      For.super.this();
      ()
    };
    def main(args: Array[String]): Unit = scala.this.Predef.intWrapper(1).to(10).foreach(((i: Int) => scala.this.Predef.println(i)))
  }
}

1.to(10) が実は 1 の to メソッドを直接呼んでいるわけではなくて暗黙の型変換メソッドが間に入っていることが分かりました。

フェイズが進むにつれてプログラムがどんどん奇怪なものになっていくのが分かりますが、カジュアルに使うのに便利なのは上記2フェイズくらいまでではないでしょうか。
特に暗黙の型変換などは最初のうち魔法じみて見えることが多いのでこうやって確認してみるとよいかと思います。

なお -Xprint の代わりに -Ybrowse を使うと構文木を Swing の GUI で視覚的にブラウズすることが出来ます。

* -Xscript

Scala のプログラムは scala コマンドでスクリプト的に実行する場合は上記のプログラムを以下のように書けます。

for (i <- 1 to 10) {
  println(i)
}

逆にこういうプログラムは scalac ではそのままではコンパイルできませんが -Xscript オプションを使うとコンパイルすることができるようになります。

PS D:\scala> cat ForScript.scala
for (i <- 1 to 10) {
  println(i)
}
PS D:\scala> scalac -Xscript ForScript ForScript.scala
PS D:\scala> scala ForScript
1
2
3
4
5
6
7
8
9
10

こうすると object ForScript { def main ... } なんかでラップしたのと同様になります。

* おまけ追記

-Xscript オプションを使うと以下のような不思議なプログラムがコンパイルできてしまいます。

PS D:\scala> cat Foo.scala
println("hello") }}
object Bar { def main(args: Array[String]) = { println("world")
PS D:\scala> scalac -Xscript Foo Foo.scala
PS D:\scala> scala Foo
hello
PS D:\scala> scala Bar
world

これは一体なんでしょう、というか、どこの Perl の -n オプションなんでしょうか。

2008-02-03 13:02 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

総称的な sum　[Scala]

オブジェクトのリストを取って全部を足して返す sum メソッドを考える。オブジェクトは + 演算子が定義されていれば何でもいいものとする。

Scala で書くとこんな感じ。

type Addible = { def +(that: Addible): Addible }
def sum(xs: List[Addible]) = xs.reduceLeft[Addible] { (a, b) => a + b }

こんな感じ、とかいいつつこれはコンパイル通らない。

scala> type Addible = { def +(that: Addible): Addible }
<console>:4: error: illegal cyclic reference involving type Addible
       type Addible = { def +(that: Addible): Addible }

こういう風に再帰するのは Scala ではだめみたい。

ところで OCaml ではどうか。

# let sum = function
| [] -> failwith "empty list"
| x::xs -> List.fold_left (fun a b -> a#add b) x xs;;
    val sum : (< add : 'a -> 'a; .. > as 'a) list -> 'a = <fun>
# class myint(x) = object
    method add (that:myint) = new myint (x + that#to_int)
    method to_int = x
  end;;
class myint :
  int -> object method add : myint -> myint method to_int : int end
# (sum [new myint 1; new myint 3; new myint 5])#to_int;;
- : int = 9

< add : 'a -> 'a; .. > as 'a という型を推論していてくれて、これが Scala で通らなかった Addible に相当する部分。OCaml えらいなあ。

2008-01-07 11:20 nice!(0) コメント(2) トラックバック(0)
共通テーマ：パソコン・インターネット

ScalaでKnuth-Morris-Pratt　[Scala]

文字列探索のアルゴリズムに KMP (Knuth-Morris-Pratt) 法 [1] というのがあるのだけど、ドラゴンブックとかネット上とかにある命令的に書かれた KMP の実装例のテーブル生成部分が腑に落ちなくて困った。
もうちょっと抽象レベルの高いコード例はないかなと思って探してみたら Haskell 版の KMP [2] を見つけた。Scala に直したらちょっと見通しが良くなったのでここに載せる。

class State[T](xs: List[T], var failure: T => State[T]) {
  val done = (xs == Nil)
  def next(c: T) = if (c == xs.head) success else failure(c)
  lazy val success: State[T] = new State[T](xs.tail, failure(xs.head).next)
}

object KMP {
  def find[T](keyword: List[T], text: List[T]) = {
    def f(state: State[T], text:List[T]): Boolean = text match {
      case Nil => state.done
      case x::xs => state.done || f(state.next(x), xs)
    }
    val start = new State(keyword, null)
    start.failure = (x => start) // tied the knot
    f(start, text)
  }
  def find(keyword: String, text: String): Boolean = find(keyword.toList, text.toList)
}

以前 Scala で Packrat parser [3] を書いたときにも思ったけど Haskell のフィールドラベルを使ったデータ型を Scala でクラスを使って書き直すと分かりやすさが向上すると思う。主に文法上の問題（Haskell のセレクタよりメソッド呼び出しの文法のほうがわかりやすい）だろうけど。

[1] http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%8C%E3%83%BC%E3%82%B9-%E3%83%A2%E3%83%AA%E3%82%B9-%E3%83%97%E3%83%A9%E3%83%83%E3%83%88%E6%B3%95
[2] http://twan.home.fmf.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell.details
[3] http://blog.so-net.ne.jp/rainyday/2007-09-09

2008-01-04 04:17 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

Scala で転置インデックスによる検索システム　 [Scala]

「転置インデックスによる検索システムを作ってみよう！」 [1] という記事があったのでそれを真似して Scala で書いてみました。

import java.io._
import scala.io._
import scala.collection.immutable._

object Bigram {
  type Bigram = (Char, Char)
  def bigrams(s: String) = s.toList.zip(s.toList.drop(1))
}
import Bigram._

object Index {
  def save(file: String, obj: AnyRef) = new ObjectOutputStream(new FileOutputStream(file)).writeObject(obj)
  def main(args: Array[String]) {
    val Array(srcfile, idxfile) = args
    val lines = Source.fromFile(srcfile).getLines
    var idx = new TreeMap[Bigram, Set[Int]]
    var n = 0
    for (line <- lines) {
      n += 1
      for (bi <- bigrams(line.stripLineEnd)) {
        val newval = idx.get(bi) match {
          case Some(s) => s + n
          case None    => TreeSet(n)
        } // withDefaultValue を使うとシリアライズできなくなるので
        idx = idx.update(bi, newval)
      }
    }
    save(idxfile, (n, idx))
  }
}

object Search {
  def load(file: String) = new ObjectInputStream(new FileInputStream(file)).readObject
  def main(args: Array[String]) {
    val Array(key, idxfile) = args
    val (num, idx) = load(idxfile).asInstanceOf[(Int, TreeMap[Bigram, Set[Int]])]
    val idx_d = idx.withDefaultValue(new TreeSet[Int])
    val bi_key = bigrams(key)
    // tf: Bigram => Int
    val tf = bi_key.foldLeft(new TreeMap[Bigram, Int].withDefaultValue(0)) {
      (tf, bi) => tf.update(bi, tf(bi) + 1)
    }
    def df(bi: Bigram): Int = idx_d(bi).size
    def w(bi: Bigram): Double = tf(bi) * Math.log(num.toDouble / (df(bi) + 1))

    val scores =
      for (linenum <- (1 to num).toList)
        yield (bi_key.foldLeft(0.0) {
          (sum, bi) => if (idx_d(bi).contains(linenum)) sum + w(bi) else sum
        }, linenum)

    for ((score, linenum) <- scores.sort{(l,r) => (l compare r) > 0}) {
      println("ID:" + linenum + " SCORE:" + score)
    }
  }
}

元記事から以下の点を変えました。

1. 元記事ではソースファイルに記事IDという列があったのを省いて単に行番号を付与した
2. インデックスファイルの作成には Java のシリアライザを使った
3. 検索プログラムのほうで [2] の記事に出てくる数式に対応する形ができるだけコード中にも出る感じにした
4. 全体に標準入出力は使わずコマンドラインオプションで指定にした

ファイル閉じていないとかは大目に見てください。

実行結果：

PS D:\scala> cat test.txt
これはペンです
最近はどうですか？
ペンギン大好き
こんにちは。いかがおすごしですか？
ここ最近疲れ気味
ペンキ塗りたてで気味が悪いです
PS D:\scala> scala Index test.txt test.idx
PS D:\scala> scala Search "最近ペンギンが好きです" test.idx
ID:3 SCORE:3.7013019741124933
ID:2 SCORE:0.8754687373538999
ID:5 SCORE:0.6931471805599453
ID:6 SCORE:0.587786664902119
ID:1 SCORE:0.587786664902119
ID:4 SCORE:0.1823215567939546

[1] http://chalow.net/2007-11-26-5.html
[2] http://chalow.net/2005-10-12-1.html

2007-12-01 18:41 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

Scala で Packrat Parsing　[Scala]

最近あちこちでこの名前を見かけてよく分からなくて気になっていたので [1] の文献を読みつつ（最後まで読んでないけど） Scala で書いてみた。lazy も導入されたのでこれは Scala 向きの問題のはず。ちゃんと検索すれば既にやっている人とかライブラリとか見つかるのかもしれないけど。

文献に出てくるのと同様の単純な電卓パーサーで、記法上のポイントは Scala の Option 型は for comprehension と組み合わせると Haskell の Maybe モナド + do 記法みたいに使えるという点です。また orElse は Option 型のメソッドで None だった場合のデフォルト値みたいなものです。

私の誤解がなければこれでよいはず…

case class Derivs(s: List[Char]) {
  type Result[T] = Option[(T, Derivs)]

  lazy val additive: Result[Int] = {
    for ((vLeft,  d1) <- multitive;
         ('+',    d2) <- d1.character;
         (vRight, d3) <- d2.additive)
      yield (vLeft + vRight, d3)
    } orElse multitive

  lazy val multitive: Result[Int] = {
    for ((vLeft,  d1) <- primary;
         ('*',    d2) <- d1.character;
         (vRight, d3) <- d2.additive)
      yield (vLeft * vRight, d3)
    } orElse primary

  lazy val primary: Result[Int] = {
    for (('(', d1) <- character;
         (v,   d2) <- d1.additive;
         (')', d3) <- d2.character)
      yield (v, d3)
    } orElse decimal

  lazy val decimal: Result[Int] = {
    character match {
      case Some(c, d1) if c.isDigit => Some(c.asDigit, d1)
      case _ => None
    }
  }

  lazy val character: Result[Char] = {
    s match {
      case c::s2 => Some(c, new Derivs(s2))
      case Nil => None
    }
  }
}

実行例は以下のような感じ。

scala> Derivs("2*(3+4)".toList).additive
res0: Derivs#Result[Int] = Some((14,Derivs(List())))

[1] http://pdos.csail.mit.edu/~baford/packrat/icfp02/

2007-09-09 05:17 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

ScalaCheck を試す (4) データ構造の生成と分布の制御　 [Scala]

ScalaCheck 1.0-RC1 がアナウンス [1] されました。

前回 [2] のカスタムジェネレータ作成では整数のジェネレータを扱いましたが、もちろん構造を持つデータを生成するジェネレータを定義することもできます。
こうした場合は基本的にはその型の文法をフォローするような形でジェネレータを書くことになるでしょう。例えば整数のリストの場合は

List[Int] ::= Nil
List[Int] ::= Int :: List[Int]

のような2つのプロダクションからなる文法を持つと考えられるのでジェネレータはこの文法に対応して

def arbInts: Gen[List[Int]] =
  oneOf(value(Nil), for (head <- arbitrary[Int]; rest <- arbInts) yield head::rest)

と書けばよさそうです。ここで oneOf は引数に2つのジェネレータを取りそのどちらかを生成するジェネレータを返すメソッドです。また value は常に引数の値を返すジェネレータです。

さて、このジェネレータには分かりにくい罠があります。oneOf は引数のどちらかを「等確率」で生成します。ということはこの arbInts が生成するテストケースはその半分が Nil で、4分の1が1要素のリストで8分の1が2要素のリストで…となるのです。意図や場合にもよるでしょうが、これはまあ偏りのある分布だと考えられます。

oneOf メソッドの代わりに frequency メソッドを使うと引数に重み付けをして分布を制御することができるようになります。ちなみにこれは ScalaCheck には 1.0-RC1 で新たに追加されたメソッドだと思います。

def arbInts2: Gen[List[Int]] =
   frequency(1 -> value(Nil), 4 -> {for (head <- arbitrary[Int]; rest <- arbInts) yield head::rest})

frequency は任意の数の (Int, T) のタプルを引数にとり、最初の整数によって重み付けをして値を選び出します。この場合 Nil が 1 に対してコンスは 4 の確率で値を選び出します。ちなみに 1 -> value(Nil) は (1, value(Nil)) と等価な Scala の syntactic sugar です。

[1] http://www.nabble.com/-scala--ANNOUNCE:-ScalaCheck-1.0-RC1-t4380903.html
[2] http://blog.so-net.ne.jp/rainyday/2007-08-26-1

2007-09-06 23:17 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

Scala の抽象データ型構築レシピ ver.2　[Scala]

前回の記事[1] は1日経ってみたら思い直すところがあり、以下のように修正した。

* Scala における抽象データ型構築レシピ

1. データ型のインターフェイスを決める。

2. 1で決めたインターフェイスの要素を以下の2種類に分類する

a. 当該データ型の値に対する何らかの操作。
b. 無から当該データ型の値を生み出すもの。定数。

3. 2で分類した a をメソッドとする abstract class を定義する。コンテナのように任意のデータ型に対して適用されるものの場合は型変数を付与する。以降この型変数を T とする。

4. 2で分類した b にあたるものを 3 のクラスを継承したクラスとして定義する。ここでデータ型が型変数を含まないならばこれをクラスではなく object としてよい。

5. 非定数について 3 のクラスを継承して実装を与える。

型変数があり、その型変数に特に制約（ [T <: X] のような形）を付けていなければ次の作業を行う。

6. これまでに定義したクラスの型変数を T から +T に変える。

7. 引数に T が現れるメソッドについて以下を行う。

a. T よりも上位（クラス階層図での上）の型 U を考えてメソッドに [U >: T] という型変数を付ける。
b. 引数の T を U に変える
c. 戻り値の T を U に変える

8. 2 で b に分類した定数に対応するクラスを obect に変える。ここで継承元のクラスの型変数は Nothing にする。

まず2の段階で「当該データ型の値から情報を抽出」と「新しい値を生み出す」を区別していたのをやめて a として統一した。前回の版ではこの区別を 7 の作業と結び付けていたのだが、よく考えると 7 の作業はその段階でのメソッドのシグニチャの字面から決まるものであって意味的な区別とは関係が無く、端的に間違っていた。

[後で例を追記]

それと前回悩んでいた 6 以降に進める基準は上述の書き方で事実上成立すると思う。「型変数に制約がついていても実は 6 以降に進める」ケースは2つ思いつくのだけどたぶんその２つとも実用上の用途はないと思われるからだ。

1つは元の型変数に対する制約が [T >: X] 　だった場合で、これはそもそもこういう制約を付けたいケースがたぶんない。もう一つは制約が [T <% X] だった場合で、これは [2] のコメント欄に書いたようなやり方で手順を全うできるが、そのようにして作った型が特に有用になるケースが思いつかない。

[1] http://blog.so-net.ne.jp/rainyday/2007-09-04
[2] http://blog.so-net.ne.jp/rainyday/2007-08-08

2007-09-05 21:25 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

Scala の抽象データ型構築レシピ　 [Scala]

Scala による抽象データ型定義の手順を誰でも追えるようなレシピ形式にするというのを考えていた。
まだこなれていないけど以下のようなもの。今のところ immutable なデータのことしか考えていない。

* Scala における抽象データ型構築レシピ

1. データ型のインターフェイスを決める。

2. 1で決めたインターフェイスの要素を以下の3種類に分類する

a. 当該データ型の値から何らかの情報を抽出するもの。
b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
c. 無から当該データ型の値を生み出すもの。定数。

3. 2で分類した a と b をメソッドとする abstract class を定義する。コンテナのように任意のデータ型に対して適用されるものの場合は型変数を付与する。以降この型変数を T とする。

4. 2で分類した c にあたるものを 3 のクラスを継承したクラスとして定義する。ここでデータ型が型変数を含まないならばこれをクラスではなく object としてよい。

5. 非定数について 3 のクラスを継承して実装を与える。

ここから以降は variance annotation を付ける作業。型変数がある場合のみ行える。

6. これまでに定義したクラスの型変数を T から +T に変える。

7. 2 で b に分類したメソッドについて以下を行う。

8. 2 で c に分類した定数に対応するクラスを obect に変える。ここで継承元のクラスの型変数は Nothing にする。

* ケーススタディ1: 非負の整数

ケーススタディとしてまず非負の整数を表現するデータ型 Num を考える。

1. Num のインターフェイスは以下4つから構成される。

isZero: 値がゼロか否かを判定する
succ: 値に1を加えた値を返す
pred: 値から1を引いた値を返す
Zero: ゼロを返す

2. 上記の4つの要素は以下のように分類される

isZero: a. 当該データ型の値から何らかの情報を抽出するもの。
succ: b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
pred: b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
Zero: c. 無から当該データ型の値を生み出すもの。定数。

3. 上記の a と b をメソッドとする abstract class を定義する。

abstract class Num {
  def isZero: Boolean
  def succ: Num
  def pred: Num
}

4. c に分類した Zero を上記のクラスを継承して定義する。Num は型変数を含まないので object とする。

object Zero extends Num {
  def isZero = true
  def succ = ...
  def pred = error("Zero.pred")
}

succ メソッドは非ゼロの値を生み出すがここではまだ実装を与えられない。

5. Num を継承して非定数（つまり非ゼロ）のクラスを実装する。

class NonZero(n: Int) extends Num {
  def isZero = false
  def succ = new NonZero(n + 1)
  def pred = if (n == 1) Zero else new NonZero(n - 1)
}

非ゼロの定義ができたので Zero の未実装だった succ メソッドを埋めることができる。

object Zero extends Num {
  def isZero = true
  def succ = new NonZero(1)
  def pred = error("Zero.pred")
}

Num は型変数を含まないので手順はここで終わり。最終形は以下のとおり。

abstract class Num {
  def isZero: Boolean
  def succ: Num
  def pred: Num
}

object Zero extends Num {
  def isZero = true
  def succ = new NonZero(1)
  def pred = error("Zero.pred")
}

class NonZero(n: Int) extends Num {
  def isZero = false
  def succ = new NonZero(n + 1)
  def pred = if (n == 1) Zero else new NonZero(n - 1)
}

このレシピは具体的な実装の方法については何も述べていない。
例えばメモリの許す限り大きい整数を表現できるような実装を与えたい場合、手順の 4 までは同一で 5 の段階で実装の差が現れる。

abstract class Num {
  def isZero: Boolean
  def succ: Num
  def pred: Num
}

object Zero extends Num {
  def isZero = true
  def succ = new NonZero(1, Zero)
  def pred = error("Zero.pred")
}

class NonZero(lsd: Int, rest: Num) extends Num {
  def isZero = false
  def succ = if (lsd < 9) new NonZero(lsd + 1, rest)
             else new NonZero(0, rest.succ)
  def pred = if (lsd == 1 && rest == Zero) Zero
             else if (lsd == 0) new NonZero(9, rest.pred)
             else new NonZero(lsd - 1, rest)
}

* ケーススタディ2: スタック

次に型変数が現れる例としてスタックを考える。これは最終的には Scala By Example に書いてあるのとほぼ同じ実装になります。

1. Num のインターフェイスは以下の5つから構成される。

isEmpty: スタックが空かどうかを判定する
top: スタックの一番上の要素を返す
pop: スタックの一番上の要素を取り除いた結果のスタックを返す
push: スタックに要素を追加して結果のスタックを返す
EmptyStack: 空のスタックを返す

2. 上記の5つの要素は以下のように分類される

isEmpty: a. 当該データ型の値から何らかの情報を抽出するもの。
top: a. 当該データ型の値から何らかの情報を抽出するもの。
pop: a. 当該データ型の値から何らかの情報を抽出するもの。
push: b. 当該データ型の値を元にして同じデータ型に属する新たな値を生成するもの。
EmptyStack: c. 無から当該データ型の値を生み出すもの。定数。

ここで pop が b でなく a だというのは自明ではない。pop と push はともにスタックを返すからだ。あとで 6 以降を行うときに少なくとも両者を区別するのが良いことが分かるのだが、この時点での基準としては不十分で、これはこのレシピがまだ洗練されていないということを意味する。

しかし次の 3 を行うにあたっては a と b の区別は重要ではないのでとりあえず先に進む。

3. 上記の a と b をメソッドとする abstract class を定義する。
ここでスタックは任意のデータ型について適用されるものなので型変数 T を導入する。

abstract class Stack[T] {
  def isEmpty: Boolean
  def top: T
  def pop: Stack[T]
  def push(elem: T): Stack[T]
}

4. c に分類した EmptyStack を上記のクラスを継承して定義する。

case class EmptyStack[T] extends Stack[T] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
  def push(elem: T) = ...
}

push の実装は例によってまだ埋められない。

なおここでは case class にしてみたけど case class にするかどうかはお好みでよいと思う。私は何かと便利なのでつい case class にするのが好きなのですが。

5. Stack[T] を継承して空でないスタックのクラスを実装する。

case class NonEmptyStack[T](head: T, rest: Stack[T]) extends Stack[T] {
  def isEmpty = false
  def top = head
  def pop = rest
  def push(elem: T) = NonEmptyStack(elem, this)
}

ここで NonEmptyStack の push を埋めることができる。

case class EmptyStack[T] extends Stack[T] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
  def push(elem: T) = NonEmptyStack(elem, this)
}

push メソッドが NonEmptyStack と EmptyStack で変わらないことに注目して実装を Stack の方に移してもよいかもしれません。

ここまででやめてもよいけど 6 以降を実行すると Stack[Int] に Double を push すると自動的に全体が Stack[AnyVal] になるといったような柔軟な型付けをしてくれるようになる。

6. これまでに定義したクラスの型変数を T から +T に変える。

abstract class Stack[+T] { ... }
case class NonEmptyStack[+T](head: T, rest: Stack[T]) extends Stack[T] { ... }
case class EmptyStack[+T] extends Stack[T] { ... }

7. 2 で b に分類した push メソッドについて以下を行う。

するとこうなります。

abstract class Stack[+T] {
  def isEmpty: Boolean
  def top: T
  def pop: Stack[T]
  def push[U >: T](elem: U): Stack[U] = NonEmptyStack(elem, this)
}
case class EmptyStack[+T] extends Stack[T] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}
case class NonEmptyStack[+T](head: T, rest: Stack[T]) extends Stack[T] {
  def isEmpty = false
  def top = head
  def pop = rest
}

8. 2 で c に分類したを EmptyStack を obect に変える。ここで継承元の Stack の型変数を Nothing にする。これで最終形は以下のようになります。

abstract class Stack[+T] {
  def isEmpty: Boolean
  def top: T
  def pop: Stack[T]
  def push[U >: T](elem: U): Stack[U] = NonEmptyStack(elem, this)
}

case object EmptyStack extends Stack[Nothing] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}

case class NonEmptyStack[+T](head: T, rest: Stack[T]) extends Stack[T] {
  def isEmpty = false
  def top = head
  def pop = rest
}

* レシピに対する考察

今2つほど問題があると思う。

一つは途中でも述べたように a と b の区別が必ずしも直感的に自明でない場面があり、かつ明確なクライテリアとして提示できていない。

もう一つは[1] の記事のコメント欄でみずしまさんに教えてもらったりした件なのだが、immutable で generic なデータ型だとしても 6 以降に進めない場合がある。この一般的な判断基準を述べることが出来ていない。

[1] http://blog.so-net.ne.jp/rainyday/2007-08-08

2007-09-04 01:26 nice!(0) コメント(0) トラックバック(0)
共通テーマ：パソコン・インターネット

前の10件 | 次の10件 Scala ブログトップ