So-net無料ブログ作成

ScalaCheckへの疑念 [Scala]

「プロパティベースのテスト」について初めて知ったのは Fun of Programmingという本で、 それを読んだ当時ScalaにもScalaCheckがあることを知って少しさわっていたんだけど 結果的には「なんか微妙」という感想を持ってやめてしまった。[^1]

その後特にScalaCheckをさわってはおらず、Scalaからもかなり離れてしまったので感想も変わっていないんだけど Scalaのユーザーが増えるとともにScalaCheckも使われているようで、よく聞くようになった。

それで思い出したのでScalaCheckへの疑念を言語化することにした。 タイトルはScalaCheckとしたけれどもQuickCheckやその他の同様のフレームワークにも該当すると思う。

普通にテストケースを書いたほうがいいのではないか

ScalaCheckでは例えば「任意の1024以上の整数nについてP(n)が成立する」のような性質から、 nを例えば100通り自動生成してテストケースを実行してくれる。 人間がテストケースを書く場合、おそらく2,3個のケースを書くにとどまるだろう。

ここで「50倍ものケースを自動実行するのだからより大きい確証が得られるだろう」 ということが言えるだろうか。

人間が書くテストケースにおけるnはおそらく1024と、MAX_INTと、ひょっとしたらその間の適当な値である。[^2]

自動生成されるケースは1024以上MAX_INT以下のランダムな100個で、 1024とMAX_INTはそこに含まれるかもしれないし含まれないかもしれない。

この例で1024とMAX_INTはバグを見つけてくれそうなテストケースである。それは仕様の境界値だから。[^3] プログラムは「以上」と「より大きい」を勘違いしているかもしれないし、オーバーフローを考慮していないかもしれない。

これに対して1025からMAX_INT-1までの値はせいぜい1つ選べばよく、残りは無駄なテストである。 無駄なテストケースは100個あっても10000個あっても品質の向上に貢献しない。 ランダムに100回実行したから1回実行したよりも99回分多くの確信が得られると思うのは偽の確信である。 偽の確信はテストにおける害悪だ。

これらに対して「それはジェネレーターの定義次第だ」という反論があるかもしれない。 でもそれを意識してジェネレータを作るならば、 それは人間がテストケースを決めるのを遠回りにしただけではないだろうか。

ランダムな組み合わせはどうか

複数の変数に対する組み合わせテストを自動生成してくれる点が ScalaCheckなどの方法の有利な点だという考えがあるかもしれない。 これは確かに手で書くのは煩雑だ。

でも同じ自動生成するのでも直交表やPairwise法などの、経験的な研究に裏付けられた、 バグ検出に効率的な組み合わせの自動生成方法があり、 ランダムな生成が有利だという根拠はない。

確率的なものは難しい

以前ScalaCheckをさわっていた時の記事で、 確率的な分布を意識していないと有効なテストが生成されないことがあるという注意点を取り上げていた。

テストの中に確率的なものが現れるのは悪いことだと思う。 おそらく多くの開発者にとって確率はプログラムよりずっと理解しにくいからだ。 プログラムコードの結果を予測するよりもテストコードの結果を予測するほうが難しいというのは、 明らかに望ましい状況ではない。

再帰的なデータ構造についてはどうか

再帰的なデータ構造に対するテストデータの生成はScalaCheckのような方法が活躍できる領域かもしれない。 再帰的なデータ構造では変数の数自体が固定的でなく、 そのような問題に対して既存の組み合わせ技法をどう適用すればいいかはあまりはっきりしないからだ。

これについてもしかし、ランダムである必要があるのかという点についてはやはり疑問が残る。 (有界モデル検査のようにある決まった範囲を全網羅するような方法が代わりに考えられる)


以上ScalaCheckや類似の手法についての疑念を書いた。

大体においては 「同値分割や境界値分析やPairwiseなどの既存のテスト技法でテスト設計したほうがいいのでは」 と感じているということだ。

一方で「ScalaCheckは駄目だと思っている」かというとあまりそこは断言できない。

1つにはこれだけ皆使っているので自分の理解が何か間違っているのではないかという不安がある。 (上記に書いたようなことを補填するような洗練されたやり方が考案されているのかもしれない)

もう1つはテスト手法の良しあしは経験的に決まるものだという点で、 例えば「実際にプロパティベースのテストのほうが既存のテスト手法より良くバグを見つけるのだ」 という経験的研究結果があればなるほどそういうものかと思って納得するかもしれない。 (読んでいる人でご存知の人がいたら教えてください)

  • [^1] 左下の「ScalaCheckを試す」のリンク集を参照
  • [^2] n=1023でP(n)が成立しないこともテストするかもしれないが、比較のためここでは取り上げない
  • [^3] MAX_INTは「暗黙の」境界値であるともいえる

Scala から Gainer mini を使う [Scala]

このところマイコンを使った電子工作に興味を持ち始めました。電子工作をやっているといっても理科の知識は中学生未満だし半田付けもできるだけ避けたいという軟派な感じのものですが。

マイコンとしては主にPICという電子工作によく使われている廉価なものを使っていて、アセンブラかCで書いたプログラムをマイコンのフラッシュメモリに書き込むのですが、ちょっとした実験のために使い捨てプログラムが必要になることがあります。しかしそうしたプログラムをいちいちアセンブラやCで書いてライターで書き込むのは面倒くさい。多少の制約(時間的な精度とか)は受け入れても超高級言語が使いたい、と思うことがあります。

そこで Gainer mini [http://gainer-mini.jp/] というデバイスを買いました。これはPCとUSBケーブルで接続され、電子回路上の電圧の制御や読み取りがPC上のプログラミング言語から行えるようにパッケージ化されたものです。フィジカルコンピューティングデバイスというカテゴリに含まれるものですが、その言葉の意味はともかくとして、これを使うと電子回路の頭脳の部分を回路上のマイコンから外に出してPC上に移すことが出来ます。

プログラミング言語として公式には Flash+ActionScript、Processing、Max/MSP が使え、私はまず Processing を使ってみたのですが、いろいろと言語やライブラリに対する不満が出てきたため、Scala から使うためのライブラリを作ってみました。

まずは単純な使用例です。Gainer mini に LED を2つ(dout 0,1)、押しボタンスイッチを1つ(din 0)、ツマミ(可変抵抗)を1つ(ain 0)取り付けます。

DSCF6106.JPG
DSCF6107.JPG

この回路を使って、「周期的に LED を点滅させる。点滅周期の長さはツマミで制御し、スイッチが押されていないときは dout 0 につながった LED を、押されたときは dout 1 につながった LED を点滅させる。Gainer のオンボードスイッチが押されたら終了」ということをするプログラムを Scala で書きます。

val gainer = Gainer("COM3")

try {
  gainer.open()
  while (!gainer.button) {
    val led = if (gainer.din(0)) 0 else 1
    val interval = gainer.ain(0)
    gainer.dout(led) = true
    Thread.sleep(interval)
    gainer.dout(led) = false
    Thread.sleep(interval)
  }
} finally {
  gainer.close()
}

実行結果です。(動画です)

以下がライブラリのソースコードです。Gainer mini のライブラリが使っているのと同じ RXTX というシリアル通信用の Java ライブラリを使っています。RXTXcomm.jar を Scala の lib ディレクトリに、rxtxSerial.dll(Windows 前提で話していますが)をパスの通った場所においてください。

続きを読む


Programming in Scala が届いた [Scala]

記念写真です。結局当初の予定からどれだけ遅れたことになるんだろう。

DSCF5986.JPG

読む時間を作らないと…


Scala で怠惰なリテラル表記 [Scala]

本質的でない記述に嫌悪感を感じるセンスがあれば、同じキーが何度も現れていることを「めんどくさい」と感じるはずだ。そして、こんなふうに書けないだろうかと一度は思うはずだ。

data = %h{
  ['name', 'age', 'email'],
  ['Foo',   20,   'foo@mail.com'],
  ['Bar',   21,   'bar@mail.net],
  ['Baz',   22,   'baz@mail.org'],
}
「怠慢はプログラマの美徳」というけれど - kwatchの日記

Ruby はこんな書き方できるのか、面白いなー、と思ったらそうではなくて架空の文法みたいですね。

というわけで Scala ではどうするかと思って考えてみました。

元の例はハッシュを構造体的に使って、それを表組み形式で書けるコンストラクタを作るということですが、静的言語ではあまりそういうことをしないので問題を直接には翻訳できません。

まずこういう状況で一番手軽に使えるのはタプル型です。これは全然めんどくさくありません。

val data = List(
  ("Foo", 20, "foo@mail.com"),
  ("Bar", 21, "bar@mail.net"),
  ("Baz", 22, "baz@mail.org")
)

でもこれだけだと name, age, email のような名前を使ったアクセスができないのでちょっと工夫を入れます。

case class Profile(name: String, age: Int, email: String)
implicit def triple2profile(triple: (String, Int, String)): Profile = triple match {
  case (name, age, email) => Profile(name, age, email)
}

val data: List[Profile] = List(
  ("Foo", 20, "foo@mail.com"),
  ("Bar", 21, "bar@mail.net"),
  ("Baz", 22, "baz@mail.org")
)

そうすると例えばこう書けるようになります。

scala> data.foreach{ x => println(x.name) }
Foo
Bar
Baz

以上は元の問題の構造体的側面を Scala に置き換えるという観点です。

これで十分な気もしますが、今度は連想配列という点を重視して Scala に翻訳してみます。 この場合、型の混在が問題になってきますが、とりあえず値はすべて文字列ということにして話を進めます。 あと連想配列をさらにコレクションの中に入れるというデータ構造を Scala で作ることは実はあまりない気もしますが、その辺は無視します。

まず私は元記事で提案されている %h 表記があまりよいとは思いませんでした。 第一に、この書き方の意図するところは1行目がキー、2行目以降が値ということなのですが、1行目と2行目以降の意味の違いが表記上の違いとして現れていない。 Excel で表を作るときだってヘッダ行は色分けするし HTML でも th と tr は別物です。 第二に、列の数が固定なのだから行ごとの区切りは改行で十分で、内側の大括弧は不要です。

というわけで、大体このくらいがちょうどいいのではないかと思います。

%('name, 'age, 'email) (
  "Foo", "20", "foo@mail.com",
  "Bar", "21", "bar@mail.net",
  "Baz", "22", "baz@mail.org"
)

この書き方を可能にするための % メソッドは以下のように書きました。

def %[T,U](keys_ : T*)(values_ : U*): List[Map[T,U]] = {
  val len = keys_.length
  val keys = keys_.toList
  val values = values_.toList
  def construct(values: List[U], sofar: List[Map[T,U]]): List[Map[T,U]] = {
    if (values.isEmpty) sofar.reverse
    else {
      val m = keys.zip(values.take(len)).foldLeft(Map[T,U]()){(m, p) => m + p}
      construct(values.drop(len), m::sofar)
    }
  }
  construct(values, List())
}

試してみます。

scala> %('name, 'age, 'email) (
     |   "Foo", "20", "foo@mail.com",
     |   "Bar", "21", "bar@mail.net",
     |   "Baz", "22", "baz@mail.org"
     | )
res31: List[Map[Symbol,java.lang.String]] = List(Map('name -> Foo, 'age -> 20, '
email -> foo@mail.com), Map('name -> Bar, 'age -> 21, 'email -> bar@mail.net), M
ap('name -> Baz, 'age -> 22, 'email -> baz@mail.org))

文脈自由文法をチョムスキー標準形にする [Scala]

チョムスキー標準形 (Chomsky Normal Form: CNF) というのは文脈自由文法で書き換え規則が A → BC か A → a の形(大文字は非終端記号で小文字は終端記号)しかないもののことを言います。

これまでの書き換え [1] [2] で A → ε と A → B の規則は除去できたので、いま残っている規則でチョムスキー標準形になっていないのは右辺が3つ以上のものか、2つで終端記号をを含むものだけになります。

これを CNF に書き換えるにはまず右辺が2つ以上の規則の右辺に現れる終端記号を抽出して、例えば

Scale' → e Sign Integer

を、

Scale' → T1 Sign Integer
T1 → e

のように書き換えます。

まずは新しい非終端記号用のシンボルを生成するコードを用意しておきます。またも手抜きですが、こんな感じです。

object Gensym {
  var i = 0
  def apply(prefix: String) = {
    i += 1
    Symbol(prefix + i.toString)
  }
}

終端記号を別規則に取り出していくコードは以下のように書きました。

def replace2[T](l: List[T], p: T => Option[T]): (List[T], List[(T,T)]) = {
  l match {
    case x::xs =>
      val (xs2, substs) = replace2(xs, p)
      p(x) match {
        case Some(x2) => (x2::xs2, (x2, x)::substs)
        case None => (x::xs2, substs)
      }
    case Nil => (Nil, Nil)
  }
}

def replaceTerminals(g: Grammar) = {
  def isTerminal(v: V) = v match { case Terminal(_) => true case _ => false}
  def terminal2fresh(v: V) = {
    if (isTerminal(v)) Some(NonTerminal(Gensym("T")))
    else None
  }
  val newRules = g.rules.foldLeft(Set[Rule]()) { (rs, r) =>
    if (r.rhs.length >= 2) {
      val (newRhs, n2t) = replace2(r.rhs, terminal2fresh)
      val newRule = Rule(r.lhs, newRhs)
      val terminalRules = n2t map { case (n, t) => Rule(n, List(t)) }
      rs + newRule ++ terminalRules
    }
    else rs + r
  }
  Grammar(newRules, g.start)
}

これが済むと右辺が2つ以上の規則はすべて右辺が非終端記号の規則になります。

あとは残る右辺が3つ以上の規則を2つずつに分解していくだけです。例えば

Scale' → T1 Sign Integer

は、

Sclae' → N1 Integer
N1 → T1 Sign

のようになります。

def splitUp(g: Grammar) = {
  def step(rules: rules): rules = {
    val longRule = rules.find{ x => x.rhs.length >= 3 }
    longRule match {
      case Some(rule @ Rule(lhs, rhs)) =>
        val newNt = NonTerminal(Gensym("N"))
        val r1 = Rule(lhs, newNt::rhs.drop(2))
        val r2 = Rule(newNt, rhs.take(2))
        step(rules - rule + r1 + r2)
      case None => rules
    }
  }
  Grammar(step(g.rules), g.start)
}

最後にこれまでの文法書き換えをすべてあわせて、

def toCNF(g: Grammar) =
  splitUp(replaceTerminals(eliminateUnitRule(eliminateErule(grammar))))

とすれば任意の文脈自由文法をチョムスキー標準形に変換することが出来ます。

[1] http://rainyday.blog.so-net.ne.jp/2008-04-20
[2] http://rainyday.blog.so-net.ne.jp/2008-04-24


文脈自由文法から unit rule を取り除く [Scala]

前回の記事の続きで今度は unit rule と呼ばれるものを取り除く。

unit rule とは A → B のように右辺に単一の非終端記号がくる形をとるもの。 こういうのは B が左辺にくる規則を全部 A から直接派生する規則に置き換えてしまってよい。

def eliminateUnitRule(g: Grammar) = {
  def isTerminal(v: V) = v match { case Terminal(_) => true case _ => false}
  def isUnitRule(x: Rule) = x.rhs.length == 1 && !isTerminal(x.rhs(0))
  def step(rules: rules): rules = {
    val unitRule = rules.find(isUnitRule(_))
    unitRule match {
      case Some(rule) =>
        val newRules = rules filter {_.lhs == rule.rhs(0)} map {
          case Rule(_, rhs) => Rule(rule.lhs, rhs)
        }
        step(rules - rule ++ newRules)
      case None => rules
    }
  }
  Grammar(step(g.rules), g.start)
}

ここで以下のような文法を用意して、

val grammar = Grammar(
  Rules(
    'Number   ==> ('Integer),
    'Number   ==> ('Real),
    'Integer  ==> ('Digit),
    'Integer  ==> ('Integer, 'Digit),
    'Real     ==> ('Integer, 'Fraction, 'Scale),
    'Fraction ==> (Symbol("."), 'Integer),
    'Scale    ==> ('e, 'Sign, 'Integer),
    'Scale    ==> ('Empty),
    'Digit    ==> (Symbol("0")),
    'Digit    ==> (Symbol("1")),
    'Digit    ==> (Symbol("2")),
    'Digit    ==> (Symbol("3")),
    'Digit    ==> (Symbol("4")),
    'Digit    ==> (Symbol("5")),
    'Digit    ==> (Symbol("6")),
    'Digit    ==> (Symbol("7")),
    'Digit    ==> (Symbol("8")),
    'Digit    ==> (Symbol("9")),
    'Sign     ==> (Symbol("+")),
    'Sign     ==> (Symbol("-")),
    'Empty    ==> ()
  ),
  Start('Number)
)

前回のε規則の除去と合わせて以下のようにすると、

println(eliminateUnitRule(eliminateErule(grammar)))

こういう結果が得られて A → B の形の規則は存在しなくなる。(見やすく並べ替えた)

 Digit ==> 0
 Digit ==> 1
 Digit ==> 2
 Digit ==> 3
 Digit ==> 4
 Digit ==> 5
 Digit ==> 6
 Digit ==> 7
 Digit ==> 8
 Digit ==> 9
 Empty ==> ε
 Fraction ==> . Integer
 Integer ==> 0
 Integer ==> 1
 Integer ==> 2
 Integer ==> 3
 Integer ==> 4
 Integer ==> 5
 Integer ==> 6
 Integer ==> 7
 Integer ==> 8
 Integer ==> 9
 Integer ==> Integer Digit
 Number ==> 0
 Number ==> 1
 Number ==> 2
 Number ==> 3
 Number ==> 4
 Number ==> 5
 Number ==> 6
 Number ==> 7
 Number ==> 8
 Number ==> 9
 Number ==> Integer Digit
 Number ==> Integer Fraction
 Number ==> Integer Fraction Scale'
 Real ==> Integer Fraction
 Real ==> Integer Fraction Scale'
 Scale ==> e Sign Integer
 Scale ==> ε
 Scale' ==> e Sign Integer
 Sign ==> +
 Sign ==> -

文脈自由文法からε規則を取り除く [Scala]

文脈自由文法は右辺が空文字列を生成する規則を含んでも良い。右辺に何も書かないと収まりが悪いので代わりにεと書く。これをε規則という。例えば、

A -> ε

このようなε規則は文法から言語(=生成する文の集合)を変えずに取り除くことが出来る。

除去するには A を使っている他の規則について A あり版と A なし版の規則に書き換えてあげればよい。
A あり版を残すのは A が左辺にくる規則はε規則だけじゃないかもしれないからだ。例えば、A -> a b c というのがあるかもしれない。逆にε規則だけだった場合は A なし版だけでいい。
そうやって書き換えた後は A -> ε は安心して消してよいはずである、ということになる。

Parsing Techniques に書いてあるアルゴリズムはもうちょっと間接的だった。

1. B -> αAβ があったら B -> αA'β と B -> αβ に置き換え、この段階では A -> ε は消さない。
2. すべてのε規則についてそういう操作をした後で、例えば A -> a b c があったら A' -> a b c という規則を追加してやる。ただし A -> ε に対して A' -> ε は追加しない。また A が左辺にくる規則が A -> ε だけだった場合は A' を使っている規則を全部除去する。

こうすると実はε規則はまだ(消してないから)残るのだが、スタートシンボルからは到達しないようになっているのであとで [1] のような方法でゆっくり掃除すればいい。

これを 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: List[V]) {
  override def toString = {
    if (rhs.length == 0) lhs + " ==> ε" else
    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).toList)
  }
}
implicit def sym2lh(sym: Symbol) = new LeftHand(sym)

val grammar = Grammar(
  Rules(
    'S ==> ('L, 'a, 'M),
    'L ==> ('L, 'M),
    'L ==> (),
    'M ==> ('M, 'M),
    'M ==> ()
  ),
  Start('S)
)

def remove2[T](l: List[T], e1: T, e2: T): List[List[T]] = l match {
  case x::xs if (x == e1)
    => remove2(xs, e1, e2) flatMap { xs2 => List(xs2, e2::xs2) }
  case x::xs
    => remove2(xs, e1, e2) map { xs2 => x::xs2 }
  case Nil => List(List())
}

def prime(v: V) = v match {
  case Terminal(sym) => Terminal(Symbol(sym.name + "'"))
  case NonTerminal(sym) => NonTerminal(Symbol(sym.name + "'"))
}

def eliminateErule(g: Grammar) = {
  def isErule(x: Rule) = x.rhs.length == 0
  def step(rules: rules, vs: Set[V]): rules = {
    def seen(r: Rule) = vs.exists(_ == r.lhs)
    // find an ε-rule: A->ε
    val erule = rules find { r => isErule(r) && !seen(r) }
    erule match {
      case Some(Rule(lhs, rhs)) =>
        // get rules that refer ε-rules: B->αAβ
        val src = rules filter { x => x.rhs.exists(_ == lhs) }
        // replace each B->αAβ with B->αA'β and B->αβ
        val newRules = src.foldLeft(rules) { (rules, rule) =>
          // get B->αA'β and B->αβ from B->αAβ
          val replacedRules = remove2[V](rule.rhs, lhs, prime(lhs)).
                                map{ Rule(rule.lhs, _) }
          rules - rule ++ replacedRules
        }
        step(newRules, vs + lhs)
      case None => // no more ε-rules to eliminate
        addPrimeRules(rules, vs)
    }
  }
  def addPrimeRules(rules: rules, vs: Set[V]) = {
    vs.foldLeft(rules) { (rules, v) =>
      val primed = prime(v)
      val src = rules filter { x => x.lhs == v && !isErule(x) }
      if (src.isEmpty)
        rules filter { x => !x.rhs.exists(_ == primed) }
      else
        src.foldLeft(rules) { (rules, rule) =>
          rules + Rule(primed, rule.rhs)
        }
    }
  }
  Grammar(step(g.rules, Set[V]()), g.start)
}

println(grammar)
println(eliminateErule(grammar))

ε規則の除去は文脈自由文法をチョムスキー標準形にするための第一段階なのだが、続きはまたそのうち。

[1] http://rainyday.blog.so-net.ne.jp/2008-02-20


Unger's method による構文解析 [Scala]

Parsing Techniques で Unger's method として紹介されている方法は、割と分かりやすい一種の分割統治法です。
Expr := Term | Expr + Term
Term := Factor | Term * Factor
Factor := ( Expr ) | i

という文法があったとして、

「Expr は "(i+i)*i" を派生するか?」という問題は「Expr := Term | Expr + Term」という規則から

1. 「Term は "(i+i)*i" を派生するか?」
2. 「"(i+i)*i" を3つに分解すると、Expr, +, Term がそれぞれを派生するか?」

という問題に分割されます。さらに2の問いは、

2a. 「Expr が "i" を、+ が "+" を、Term が "i)*i" を派生するか?」
2b. 「Expr が "i" を、+ が "+i" を、Term が ")*i" を派生するか?」
2c. 「Expr が "i" を、+ が "+i)" を、Term が "*i" を派生するか?」
2d. 「Expr が "i" を、+ が "+i)*" を、Term が "i" を派生するか?」


などなどの問いに分割されます。これを再帰的に処理していけば必ず答えに辿り着くというわけです。終端記号がある文字(列)を派生するかどうかはそれ以上分割する必要のない問いです。

ここで気をつける必要があるのは、文脈自由文法一般を考えたときに、

1. 規則の右辺に長さゼロの文字列がくる場合がある(本当は「Expr が "" を、+ が "" を、Term が "(i+i)*i" を派生するか?」を最初に問わなければならない)
2. ループして同じ問いに辿り着く場合がある(1の結果としても、文法に固有の理由からも)

という点です。

これらは生じた場合に「問題が小さくならない」ということにつながります。再帰的なアルゴリズムで問題が小さくならないと結果は無限ループ(というかスタックオーバーフロー)になります。
したがってアルゴリズムは「これまでに発した問い」を覚えておいて前にも聞いたことがある問いが出てきた場合はそこで打ち切るようにしなければなりません。

以上を Scala で実装してみたのが以下です。object Unger より手前までの部分は [1] で使った定義の使い回しです。
import scala.collection.immutable._

// Type definitions for CFG
abstract class V
case class Terminal(sym: Symbol) extends V
case class NonTerminal(sym: Symbol) extends V
case class Rule(lhs: V, rhs: Seq[V]) 
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).toList)
  }
}
implicit def sym2lh(sym: Symbol) = new LeftHand(sym)

val grammar = Grammar(
  Rules(
    'Expr   ==> ('Term),
    'Expr   ==> ('Expr, Symbol("+"), 'Term),
    'Term   ==> ('Term, Symbol("*"), 'Factor),
    'Term   ==> ('Factor),
    'Factor ==> (Symbol("{"), 'Expr, Symbol("}")),
    'Factor ==> 'i
  ),
  Start('Expr)
)

object Unger {
  def partition(offset: Int, marbles: Int, cups: Int): List[List[(Int,Int)]] = {
    if (cups == 1) List(List((offset, marbles)))
    else
      if (marbles == 0) List(List.make(cups, (offset, 0)))
      else
        (0 to marbles).toList.flatMap{ l =>
          partition(offset + l, marbles - l, cups - 1).map{(offset, l)::_}
        }
  }
  def recognize(str: List[Symbol], grammar: Grammar) = {
    def -*->(v: V, str: List[Symbol], asked: Set[(V,List[Symbol])]): Boolean = {
      //println((v, str))
      if (asked contains Pair(v, str)) false
      else
        v match {
          case Terminal(sym) => str == List(sym)
          case nt @ NonTerminal(sym) => 
            grammar.rules.filter{_.lhs == nt} exists { rule =>
              partition(0, str.size, rule.rhs.size) exists { p =>
                (p zip rule.rhs.toList) forall {
                  case ((offset, len), v2) =>
                    -*->(v2, str.slice(offset, offset+len), asked + Pair(v,str))
                }
              }
            }
        }
    }
    -*->(grammar.start, str, ListSet.empty[(V, List[Symbol])])
  }
}

val str = args(0).split("").toList.tail.map{Symbol(_)}
println(Unger.recognize(str, grammar))

実行例:
PS D:\scala> scalac -Xscript Unger Unger.scala
PS D:\scala> scala Unger i
true
PS D:\scala> scala Unger i+
false
PS D:\scala> scala Unger i*i
true
PS D:\scala> scala Unger +i*i
false
PS D:\scala> scala Unger i+i*i
true
PS D:\scala> scala Unger "{i+i*i"
false
PS D:\scala> scala Unger "{i+i}*i"
true

今回の実装では文が言語の中に含まれるかどうかを判定するだけでセマンティクスは与えられていませんが、最初に見つけたパースだけで諦めずに全ての可能なパースを探すようにすれば文脈自由文法の構造的多義性にも対応可能なはずです。

ところでコード中の文法で括弧を中括弧にしたのは Windows 上の Scala でコマンドライン引数に閉じ小括弧を使うと変な動作になることを見つけてしまったからです。多分 scala.bat のバグだと思いますが…

[1] http://rainyday.blog.so-net.ne.jp/2008-02-20

Scala で tap メソッドを使う [Scala]

Ruby 1.9 で標準装備になったという tap メソッド [1] [2] というのがかなりかっこいい。この場合の tap って多分電源タップの意味だろうか。メソッドチェーンの流れを切るまいとする Ruby 的な発想なんだろうと思う。

というわけで Scala でもやってみた。仕組み自体はおなじみのもの。Scala でも特に問題無い様に思われる。

scala> class Tap[T](obj: T) {
     |   def tap(block: T => Unit): T = { block(obj); obj }
     | }
defined class Tap

scala> implicit def any2tap[T](obj: T): Tap[T] = new Tap(obj)
any2tap: [T](T)Tap[T]

scala> val l = List(2, 1, 4, 5, 3)
l: List[Int] = List(2, 1, 4, 5, 3)

scala> l.tap{x=>println(x)}.sort{_<_}.tap{x=>println(x)}.reverse.tap{x=>println(x)}
List(2, 1, 4, 5, 3)
List(1, 2, 3, 4, 5)
List(5, 4, 3, 2, 1)
res0: List[Int] = List(5, 4, 3, 2, 1)

scala> (123,"hello").tap{case (x,_)=>println(x)}.tap{case (_,y)=>println(y)}
123
hello
res1: (Int, java.lang.String) = (123,hello)


[1] http://www.infoq.com/jp/news/2008/02/tap-method-ruby19
[2] http://www.infoq.com/news/2008/02/tap-method-ruby19

Scala による diff の実装 [Scala]

「Scala で diff を書いてみた」[1] という記事に触発されて [2] の論文や [3] の解説を読んで diff のアルゴリズムを勉強して自分なりに Scala で実装してみました。

これは [2] で "An O((M+N)D) Greedy Algorithm" と呼ばれているほうの実装で、論文の後半では改良についても書いてあるけどそちらは読んでいません。

私なりに工夫をした部分は全体的に副作用を排除した所とエディットグラフの格子点をオブジェクトとして表現した点です。
元論文の擬似コードで "a number of simple optimizations are employed" とされている部分は可読性の観点から取り入れませんでした。ただ元論文が「D回の編集で到達する(対角線 k 毎の)最遠点の集合」を配列で管理しているのを Set で管理するようにしたのは本当はよろしくないかもしれません。

abstract class Edit[+T]
case class Ins[T](pos: Int, ch: T) extends Edit[T]
case class Del(pos: Int) extends Edit[Nothing]

case class Vertex[T](x: Int, y: Int, a: List[T], b: List[T], h: List[Edit[T]]) {
  val k = x - y

  lazy val right =
    if (a.isEmpty) None
    else Some(Vertex(x + 1, y, a.tail, b, Del(x + 1)::h))

  lazy val down =
    if (b.isEmpty) None
    else Some(Vertex(x, y + 1, a, b.tail, Ins(x, b.head)::h))

  lazy val diagonal =
    if (a.isEmpty || b.isEmpty || a.head != b.head) None
    else Some(Vertex(x + 1, y + 1, a.tail, b.tail, h))

  lazy val snake: Vertex[T] = diagonal match {
    case Some(v) => v.snake
    case None => this
  }

  def isGoal = { a == Nil && b == Nil }
}

def diff[T](a: List[T], b: List[T]) = {
  def extend[T](d: Int, vs: Set[Vertex[T]]): List[Edit[T]] = {
    vs.find {_.isGoal} match {
      case Some(v) => v.h.reverse
      case None =>
        val next =
          vs.flatMap{v => v.right ++ v.down}.map{_.snake}
            .foldLeft(Set[Vertex[T]]()) { (vs, v) =>
              vs.find {w => w.k == v.k} match {
                case Some(w) => if (v.x > w.x) vs - w + v else vs
                case None => vs + v
              }
            }
        extend(d + 1, next)
    } 
  }
  extend(0, Set(Vertex(0, 0, a, b, Nil).snake))
}

val a = args(0).toList
val b = args(1).toList

println(diff(a, b))

実行例:

PS D:\scala> scala Diff.scala abcabba cbabac
List(Del(1), Ins(1,c), Del(3), Del(6), Ins(7,c))

[1] http://d.hatena.ne.jp/h-hirai/20080202/1201939297
[2] http://citeseer.ist.psu.edu/myers86ond.html
[3] http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm