情報隠蔽とパターンマッチ

情報隠蔽とパターンマッチを巡って考えたことなど。

OCaml にはシグニチャという仕組みがあってオブジェクト指向言語でいうところのインターフェイスのようなものとして使われる。

例として次のようなスタックの実装を考えてみる。

module StackImpl =
struct
  type 'a t = 'a list
  let empty = []
  let push x s = x::s
  let pop (x::xs) = (x, xs)
end

モジュール StackImpl は単純にリストとしてスタックを定義している。

# let s = StackImpl.empty;;
val s : 'a list = []
# let s = StackImpl.push 'a' s;;
val s : char list = ['a']
# let s = StackImpl.push 'b' s;;
val s : char list = ['b'; 'a']
# let s = StackImpl.push 'c' s;;
val s : char list = ['c'; 'b'; 'a']
# match s with [] -> '*' | x::xs -> x;;
- : char = 'c'

モジュールが定義している操作は push と pop だけだが、内部表現はリストなので型はそのように表示されるし最後の例のようにリストとしてのパターンマッチにかけることもできる。

しかし情報隠蔽の考え方からするとスタックは内部実装を晒さずに操作だけが定義されるのが望ましい。そこで使われるのがシグニチャである。

module type StackSig =
sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> 'a * 'a t
end

module MyStack = (StackImpl : StackSig)

StackSig がシグニチャで、スタックを操作するインターフェイスのみを定義したものである。ここでは型として 'a t を定義しているのみでそれがリストだということはどこにも表現されない。

MyStack はこのシグニチャを先の StackImpl に適用している。このようにすると MyStack の使用者にはそれがリストによる実装であるということが隠蔽される。

# let s = MyStack.empty;;
val s : 'a MyStack.t = <abstr>
# let s = MyStack.push 'a' s;;
val s : char MyStack.t = <abstr>
# let s = MyStack.push 'b' s;;
val s : char MyStack.t = <abstr>
# let s = MyStack.push 'c' s;;
val s : char MyStack.t = <abstr>
# match s with [] -> '*' | x::xs -> x;;
Characters 13-15:
  match s with [] -> '*' | x::xs -> x;;
               ^^
This pattern matches values of type 'a list
but is here used to match values of type char MyStack.t

このようにすることの利点は勿論実装を取り替えても使用者側のコードには影響がないということを保証できるということである。
一方でこうすることで OCaml の強力なツールであるパターンマッチは使えなくなってしまう。
別の言い方をすると一般にパターンマッチというのは内部構造を隠蔽しないことによってのみ可能になるものだということだ。つまりパターンマッチは情報隠蔽と相性が悪い。例えば以下のような疑似コードは OCaml では書けない。

match push 'a' (push 'b' empty) with
| push x s -> ...(* ここで x='a', s='b'だけのスタック*)

同様にパターンマッチは「構造のある」データに対してしか使えないということもいえる。例えばリストやタプルは構造を持ったデータだが、整数はそうではない。従って以下の例の前者は可能だが後者はそうではない。

let rec sum = function
| [] -> 0
| x::xs -> x + sum xs

let fact = function
| 1 -> 1
| (1 + n) as m -> m * fact n

実は Haskell ではこれに相当することは可能である。しかし加算以外とか整数以外に使えるような一般的なものではないようなので大した使い道はない。

fact 1 = 1
fact m @ (n + 1) = m * fact n

Scala で最近導入された extractor という概念は上記のような問題に対する試みと考えられる。Haskell 風の n+k パターンは Scala では下記のように書ける。

object add1 {
  def apply(x:Int):Int = x + 1
  def unapply(x:Int):Option[Int] = Some(x - 1)
}

object Fact {
  def fact(x:Int):Int = x match {
      case 1 => 1
      case m @ add1(n) => m * fact(n)
  }
  def main(args: Array[String]) = {
    Console.println(fact(args(0).toInt))
  }
}

ここで add1 は擬似的な関数オブジェクトである。もともと Scala の関数オブジェクトにはメソッドとして apply というのがあり、関数適用をした場合にこれが暗黙に呼ばれるのだが、その逆を行う unapply というメソッドを定義するとこのようなパターンマッチが可能となる。この unapply メソッドを extractor と呼ぶ。（実は現行のバージョンでは上記の m が期待通りの値に束縛されないが、次のバージョンで修正されるそうだ）

最初のスタックの例も下記のように書くことが出来る。

abstract class Stack[a] {
  def push(x:a): Stack[a]
  def pop(): Pair[a, Stack[a]]
}

class ListStack[a](l:List[a]) extends Stack[a] {
  def push(x:a) = {
    new ListStack(x::l)
  }
  def pop() = {
    Pair(l.head, new ListStack(l.tail))
  }
  override def toString = l.toString
}

 // 以下の2つを generic にするにはどう書いたらいいのか分からなかった
object push {
  def apply(x:int, s:Stack[int]) = s.push(x)
  def unapply(s:Stack[int]) = Some(s.pop)
}

object pop {
  def apply(s:Stack[int]) = s.pop
  def unapply(x:int, s:Stack[int]) = s.push(x)
}

object Main {
  def main(args: Array[String]) = {
    var s = new ListStack[Int](List())
    s = s.push(1)
    s = s.push(2)
    s = s.push(3)
    s = s.push(4)
    s match {
      case push(x, push(y, s)) => {
        Console.println("x = " + x)
        Console.println("y = " + y)
        Console.println("s = " + s)
        /*
          x = 4
          y = 3
          s = List(2,1)
        */
      }
    }
    Console.println("")
  }
}

ここで object push と object pop はインターフェイス Stack の操作のみを使用していて実装には依存しない。そのような関数オブジェクトを使って case push(x, push(y, s)) のようなパターンマッチを行うことができている。ここでは情報隠蔽とパターンマッチが両立しているといえる。

Scala のアプローチには問題らしきものもある。特に構文上もともとの加算演算子やメソッド呼び出しとは異なる構文を使わざるを得ない。また副作用や破壊的な操作を行う関数の unapply は書けないか少なくとも書きにくいだろうが、これは仕方ないと思われる。

そして extractor という概念はもう一つ興味深い問題を導入するように思われる。例えば絶対値を計算する abs 関数があったとしてその unapply はどのように書くべきだろうか。あるいは2項を取る add 関数は？

2007-07-25追記:

上記のコード中で「generic にするにはどう書いたらいいのか分からなかった」としている部分はその後以下のように書けばよいことが分かりました。

object push {
  def apply[a](x:a, s:Stack[a]) = s.push(x)
  def unapply[a](s:Stack[a]) = Some(s.pop)
}

object pop {
  def apply[a](s:Stack[a]) = s.pop
  def unapply[a](x:a, s:Stack[a])= s.push(x)
}