読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

CPSとSSA

Gauche

SSA(Static Single Assignment form, 静的単一代入)とは、一つの変数についての代入文がプログラム中で一度しか現れないような書き方のことを指します。
Scalaでいうと、すべての変数がvalになっているようなものですね。

プログラムをこの形式に変換することによって、データフロー解析がやりやすくなるらしいです。
実は、少し前までちょっとした言語処理系を書いていたので(これについてはそのうち記事を書きます)、もう少し早くSSAの存在を知っていればよかった……。

このSSA、実はCPSと(ある意味で)同じものとして捉えられるそうです。

確かに、以下の3つのプログラムは、どれも書き方の違いのみで、本質的には同じものとみなせそうです。

import scala.math._

// 元々のコード
object Simple extends App {
  val x = 1
  val y = 1
  println(sqrt(pow(x, 2) + pow(y, 2)))
}

// 静的単一代入形式
object SSA extends App {
  val x0 = 1
  val y0 = 1
  val x1 = pow(x0, 2)
  val y1 = pow(y0, 2)
  val n0 = x1 + y1
  val n1 = sqrt(n0)
  println(n1)
}

// 純粋関数型っぽいやつ
object PF extends App {
  ((x0: Int, y0: Int) =>
    ((x1: Double) =>
      ((y1: Double) =>
        ((n0: Double) =>
          ((n1: Double) => {
            println(n1)
          })(sqrt(n0))
        )(x1 + y1)
      )(pow(y0, 2))
    )(pow(x0, 2))
  )(1, 1)
}

// さらにCPSにしてみたバージョン
object CPS extends App {
  def add_CPS(x: Double, y: Double, cont: Double => Unit) = cont(x + y)
  def pow_CPS(x: Int, y: Int, cont: Double => Unit) = cont(pow(x, y))
  def sqrt_CPS(x: Double, cont: Double => Unit) = cont(sqrt(x))

  ((x0: Int, y0: Int) =>
    pow_CPS(x0, 2, (x1: Double) => {
      pow_CPS(y0, 2, (y1: Double) => {
        add_CPS(x1, y1, (n0: Double) => {
          sqrt_CPS(n0, (n1: Double) => {
            println(n1)
          })
        })
      })
    })
  )(1, 1)
}

これらの間の相互変換も、うまくやればいけそうなはず…?

確かに、ScalaでなくLispで考えてみると、上のSSAはすべての変数についてletしたもの、PFはletマクロを剥がした後の形、そしてCPSは継続を明示的に渡すようにしたものと考えてみると、これらの間には関連がありそうです。

そのうち詳しく勉強しておきたいです。

詳しくは以下の論文(有名なものらしいです)を参照してください:

Andrew W. Appel (April 1998). “SSA is Functional Programming”
Richard A. Kelsey (March 1995). “A Correspondence between Continuation Passing Style and Static Single Assignment Form”

まだざっくりと概要を追っただけなので、暇な時にでもしっかりと読んでおきたいです。