このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

非決定性プログラミングだって絵を描いてみれば一目瞭然

字を書くのがなんかメンドクサイので、今日は蒸し返しの参照と引用、それとお絵描き*1

次の2つのエントリーで、プログラムを対象とした加減乗除のような計算を紹介しました。

同じことを計算ではなくてお絵描き(pictorial calculation)でやってみます。「続き&完結」の最後のところを引用しておくと:

プログラムの構造と実行フローも[補注:正規表現の構文図と]同様に図示できるはずですね。昔なつかしの流れ図(フローチャート)がそれですが、もうちょっと洗練された流れ図2.0(つかっちまったよ 2.0)もあります。今風流れ図の例は次の論文を(読まなくてもいいから)眺めるとお目にかかれます。

プログラムを表す絵の描き方

  1. プログラムの実行は左から右へ。
  2. A, Bなどの大文字はプログラム(文やブロック)、p, qなどの小文字は述語(真偽値を返す関数/式)を表す。
  3. プログラムのまとまりは四角い箱。述語は三角、上の枝がYES(true)で下がNO(false)。
  4. 必要があれば(必要なときだけ)、プログラム入り口を白丸、出口に太い矢印。

特殊なプログラムI(何もしない)とO(破綻)。順次結合「;」、非決定性選択「|」、非決定性繰り返し「*」、ガード「・」の描き方:

絵の同値変形

  1. [NOT]同値変形: ガード付きプログラム p・A ≡ if (p) then A else O は、 ¬pを使って if (not A) then O else A と書いても(描いても)よい。
  2. [IF]同値変形: if (p) the A else B は、p・A | (¬p)・B と書いても(描いても)よい。

他にも同値変形はあるけど、今回は使わないので割愛。

whileをガードと非決定性繰り返しで表現

下の(1)の流れ図を左(入り口)から右(出口)へと眺めれば、while (p) A だと分かりますね。これが実は…(絵の後に続く)


  1. (1)⇒(2) は、[NOT]同値変形で線(ひも)の交差をなくした。
  2. (2)⇒(3) は、[IF]同値変形で述語を2つにした。¬¬p ≡ p を使っている。
  3. (3)⇒(4) は、p・I を左にほうにズラしただけ。

最後に得られた絵(4)は、次のように解釈:

  1. 箱(a)は p・A (「・」の描き方を参照)
  2. 箱(b)は (p・A)* (「*」の描き方を参照)
  3. 箱(c)は (¬p)・I (Iと「・」の描き方を参照)
  4. 全体は (p・A)*; (¬p)・I (「;」の描き方を参照)

つまり、

  • while (p) A ≡ (p・A)*; (¬p)・I

その他、参考エントリー

*1:絵を描いてスキャンしたら、よけいにメンドクサイかも。