型無しラムダ計算での不動点オペレータの導出

公式は覚えるものではなく, 必要に応じて導出するものだよ (?)

不動点オペレータ

不動点オペレータ (大抵 fix という名前, コンビネータ計算の文脈では Y とも) は Haskell では以下のように定義される関数である.

fix f = f (fix f)

つまり, fix f は関数 f の不動点となっている.

OCaml のような値呼びの言語では, 評価順序の影響で, 定義は以下のようになる.

let rec fix f = f (fun x -> fix f x)

fix が何に使えるのかは直感的にはわかりにくいが, これは再帰関数を定義するときに便利である. 例えば let rec は fix を用いた式の糖衣構文と見ることもできる.

以下では型無しラムダ計算での不動点オペレータの導出?を行う. 型無しラムダ計算の説明は省く (面倒なので). あと文法は例によって謎の ML 風のアレ.

再帰関数の定義

型無しラムダ計算には組み込みの fix のようなオペレータは存在しない. それではどのように再帰関数を定義するのかというと, 例えば階乗を計算する関数は素朴には以下のように書ける.

let factorial f n =
  if n = 0 then 1
  else n * f f (n - 1)

let ans = factorial factorial 10 

このままだと n の階乗を計算するためには factorial factorial n のように factorial にそれ自身を引数として明示的に与えてやる必要がある. これは面倒なので, 次のように定義し直す.

let factorial =
  let m f = fun n ->
    if n = 0 then 1
    else n * f f (n - 1)
  in
  m m

let ans = factorial 10

一般に再帰関数は次のように書ける.

let recursive =
  let m f = C[f f] in
  m m

ここで C[f f] となっているのは f f を含む項という程度の意味で, 上の階乗の例では C[t] = fun n -> if n = 0 then 1 else n * t (n - 1) だった.

この let m f = ... in m m という部分はどのような再帰関数に対しても同じなので, C を外部から与えるようにしてしまえば, 再帰関数を定義するための関数が作れる.

let recursive g =
  let m f = g (f f) in
  m m

あるいは let を使うのをやめると,

let recursive g = (fun f -> g (f f)) (fun f -> g (f f))

これは以下のように使用できる.

let factorial = recursive (fun f n ->
    if n = 0 then 1
    else n * f (n - 1)
  )

また, recursive g の呼び出しを適当に評価してやると,

recursive g
~> (fun f -> g (f f)) (fun f -> g (f f))
~> g ((fun f -> g (f f)) (fun f -> g (f f)))
== g (recursive g)

となっており, 実は最初に挙げた Haskell での fix と同じ動きをするということが分かる. というわけで, 以降 recursive ではなく fix と呼ぶことにする.

let fix g = (fun f -> g (f f)) (fun f -> g (f f))

関数の不動点という, いかにも数学的な概念そのもののような定義の fix だが, そのまま便利な道具として使えるのは少し面白い.

値呼びでの注意点

ところでこの関数の呼び出しは値呼びだと問題があり, 評価を追ってみると,

fix g
~> (fun f -> g (f f)) (fun f -> g (f f))
~> g ((fun f -> g (f f)) (fun f -> g (f f)))
~> g (g ((fun f -> g (f f)) (fun f -> g (f f))))
~> ...

のように引数部分を延々と評価し続けてしまい, g が呼び出されることはない. 一方で最初に定義した factorial の動作に問題はなかった. なぜこのようになってしまったかというと, C[f f] を g (f f) で置き換えたとき, 元の定義では f f は直ちに評価されなかったのが, 置き換えた後では g の呼び出し前に評価するようになってしまっているためである.

この f f の評価されるタイミングを調整する (遅延させる) ため, f f の代わりに同じ動きをする関数 fun x -> f f x (η-expansion とかいう名前がついている) を g に与えるように変更する.

let fix' g =
  let m f = g (fun x -> f f x) in
  m m

あるいは let を使わずに書けば,

let fix' g = (fun f -> g (fun x -> f f x)) (fun f -> g (fun x -> f f x))

このようにすることで, f f が評価されるタイミングが元と同じになる. 実際, 呼び出しの評価がどのように行われるかを見てみると,

fix' g
~> (fun f -> g (fun x -> f f x)) (fun f -> g (fun x -> f f x))
~> g (fun x -> (fun f -> g (fun y -> f f y)) (fun f -> g (fun y -> f f y)) x)
== g (fun x -> fix' g x)

となり, 正しく g が呼び出されるようになる. また, この挙動は一番最初に挙げた OCaml での fix と一致する.

このように変更しても使い方は変わらない.

let factorial = fix' (fun f n ->
    if n = 0 then 1
    else n * f (n - 1)
  )

JavaScript 処理分岐どう書く問題

JavaScript で (バリアント的な) 複数の可能性がある値について処理を分岐するときに, どのように書くのが良いかという話.

ここでは具体例として簡単な数式の計算プログラムを考えます. 数式を表すクラスは以下の通り.

// literal
class Lit {
  constructor(val) {
    this.val = val;
  }
}

// left + right
class Add {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }
}

// left - right
class Sub {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }
}

以下ではこれらを使って表した数式を計算する処理 evaluate をいくつかの方法で書いて比較してみます.

各方法の評価ポイントは,

• (Flow を使って) 静的に型検査ができるか (ここでは型書かないけど)
• 新しく要素 (例えば掛け算など) を追加したときに, 対応していないと静的にエラーを出せるか
• 柔軟性 (デフォルト処理 (例えばリテラル以外ならば, のような) のようなものが書けるか, など)
• 見た目
• パフォーマンス

あたりです.

メソッドを追加する

最も簡単には各クラスにメソッドを追加すれば良いでしょう.

// literal
class Lit {
  constructor(val) {
    this.val = val;
  }

  evaluate() {
    return this.val;
  }
}

// left + right
class Add {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }

  evaluate() {
    return this.left.evaluate() + this.right.evaluate();
  }
}

// left - right
class Sub {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }

  evaluate() {
    return this.left.evaluate() - this.right.evaluate();
  }
}


// (2 + 4) - 1
console.log(
  new Sub(new Add(new Lit(2), new Lit(4)), new Lit(1)).evaluate()
);
// -> 5

利点

• Flow による静的な型検査が可能
• 新しく要素を追加したとき, evaluate メソッドがなければ静的にエラーを出せる

欠点

• 柔軟性は悪い
  • ちょっとした分岐がある度にメソッドを追加するのはつらい
  • そもそもメソッドを追加できないときには不可能
• 定義の場所が要素ごとに散らばる

というわけで以下ではメソッドを使わずに, 外部の関数として定義する方法を考えます.

instanceof を使う

オブジェクトがどのクラスに所属するかを判別するためには instanceof が使えます.

// literal
class Lit {
  constructor(val) {
    this.val = val;
  }
}

// left + right
class Add {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }
}

// left - right
class Sub {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }
}

function evaluate(expr) {
  if (expr instanceof Lit) {
    return expr.val;
  }
  else if (expr instanceof Add) {
    return evaluate(expr.left) + evaluate(expr.right);
  }
  else if (expr instanceof Sub) {
    return evaluate(expr.left) - evaluate(expr.right);
  }
  else {
    throw new Error("unknown expression");
  }
}

// (2 + 4) - 1
console.log(
  evaluate(new Sub(new Add(new Lit(2), new Lit(4)), new Lit(1)))
);
// -> 5

利点

• 静的な型検査が可能
• デフォルト処理が簡単に書ける

欠点

• 新しく要素を追加したとき, 動的にしかエラーを出せない
• 見た目が悪い (きがする)
• instanceof のパフォーマンスはあまり良くない

ちなみに最後の else if を else にしたいかもしれませんが, そうしてしまうと新しく要素が追加されたときに壊れます.

typeOf メソッドを用意

あらかじめ一般的に使えるような, 各クラスの種類を表す値を返すようなメソッド typeOf を用意しておきます.

const Type = {
  Lit: "lit",
  Add: "add",
  Sub: "sub"
};

// literal
class Lit {
  constructor(val) {
    this.val = val;
  }

  typeOf() {
    return Type.Lit;
  }
}

// left + right
class Add {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }

  typeOf() {
    return Type.Add;
  }
}

// left - right
class Sub {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }

  typeOf() {
    return Type.Sub;
  }
}

function evaluate(expr) {
  switch (expr.typeOf()) {
    case Type.Lit: return expr.val;
    case Type.Add: return evaluate(expr.left) + evaluate(expr.right);
    case Type.Sub: return evaluate(expr.left) - evaluate(expr.right);
    default: throw new Error("unknown expression");
  }
}

// (2 + 4) - 1
console.log(
  evaluate(new Sub(new Add(new Lit(2), new Lit(4)), new Lit(1)))
);
// -> 5

利点

• デフォルト処理が簡単に書ける
• 見た目は良さ気
• パフォーマンスは良い

欠点

• 新しく要素を追加したとき, 動的にしかエラーを出せない (追記あり)
• (Flow では) 静的な型検査ができない
  • typeOf は自己申告なので, 本当にそのクラスなのかの保証がない

追記

typeOf をメソッドではなくプロパティとして持たせたらいけた.

// @flow
type Expr = Lit | Add | Sub

// literal
class Lit {
  type: "lit";
  val: number;

  constructor(val) {
    this.type = "lit";
    this.val  = val;
  }
}

// left + right
class Add {
  type: "add";
  left: Expr;
  right: Expr;

  constructor(left, right) {
    this.type  = "add";
    this.left  = left;
    this.right = right;
  }
}

// left - right
class Sub {
  type: "sub";
  left: Expr;
  right: Expr;

  constructor(left, right) {
    this.type  = "sub"
    this.left  = left;
    this.right = right;
  }
}

function evaluate(expr: Expr): number {
  switch (expr.type) {
    case "lit": return expr.val;
    case "add": return evaluate(expr.left) + evaluate(expr.right);
    case "sub": return evaluate(expr.left) - evaluate(expr.right);
    default: throw new Error("unknown expression");
  }
}

// (2 + 4) - 1
console.log(
  evaluate(new Sub(new Add(new Lit(2), new Lit(4)), new Lit(1)))
);
// -> 5

Visitor パターン

有名な Visitor パターンです. あらかじめ accept メソッドを定義しておいて, そこに各クラスに対応する処理を持った visitor を渡してやる方法です.

これ書いてて思ったんですけど, ほぼ Scott エンコーディングですね.

// literal
class Lit {
  constructor(val) {
    this.val = val;
  }

  accept(visitor) {
    return visitor.visitLit(this.val);
  }
}

// left + right
class Add {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }

  accept(visitor) {
    return visitor.visitAdd(this.left, this.right);
  }
}

// left - right
class Sub {
  constructor(left, right) {
    this.left  = left;
    this.right = right;
  }

  accept(visitor) {
    return visitor.visitSub(this.left, this.right);
  }
}

const visitor = {
  visitLit: val => val,
  visitAdd: (left, right) => evaluate(left) + evaluate(right),
  visitSub: (left, right) => evaluate(left) - evaluate(right)
};

function evaluate(expr) {
  return expr.accept(visitor);
}

// (2 + 4) - 1
console.log(
  evaluate(new Sub(new Add(new Lit(2), new Lit(4)), new Lit(1)))
);
// -> 5

利点

• 静的な型検査が可能
• 新しく要素を追加したとき, 対応していなければ静的にエラーを出せる
• 見た目は良い
  • 各パラメータを変数に束縛することもできる (上の例のように)
• パフォーマンスも良い

欠点

• 柔軟性はやや悪い
  • デフォルト処理だけなら visitDefault みたいなメソッドを作ってやればできなくはないが

まとめ

以上をまとめるとこんな感じ.

	静的型検査	要素追加時のエラー	柔軟性	見た目	パフォーマンス
メソッド追加	◯	◯	✕	△	◯
instanceof	◯	✕	◯	△	✕
typeOf メソッド	✕	✕	◯	◯	◯
type プロパティ	◯	✕	◯	◯	◯
Visitor パターン	◯	◯	△	◯	◯
(おまけ) 本当のパターンマッチ	◯	◯	◯	◯	?

個人的には柔軟性が高いのが良くて, かつ静的型検査ができないのは論外という感じで, 普段雑に書いている時は instanceof を使いがちです. 適材適所で Visitor パターンなんかと使い分ける方が良いのだろうけれど統一感がなくなってにゃんこ.

もっと良い方法あったら教えてください.