言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella

論文読み No Ifs, Ands, or Buts Uncovering the Simplicity of Conditionals http://lambda-the-ultimate.org/node/2148

スキマチック・テーブル(schematic table)という新しい手法を使って、ディシジョン・テーブルとデータフローを融合させる方法です。これによってプログラムを宣言的に記述できます。チキマチック・テーブルは、コード生成ツールとしても、ダイアグラム言語としても使えます。

次の OOPSLA で発表される予定の論文です。上の説明でピンと来る人はかなりの通。これもまた、プログラムを画像表現する手法についての話です。データフローと条件文というのは相当相性悪いのです。この人はスキマチック・テーブルという新発明で解決するらしいです。

導入

条件文は基本的なプログラム要素ですが、言語によって沢山のやり方があります。if then、case 文、パタンマッチング、ポリフォニズム。なんでそんなにあるかというと、ただの if then 文では直接意図を表現出来ないからです。身に覚えがある方は沢山いらっしゃると思いますが、ネストされた if then 文ほど読むのに苦痛な物はありません。条件文が全ての条件を網羅しているか、論理的にダブってないかと見つけるのはすごく大変です。

case 文、パタンマッチング、ポリフォニズムなどの新しい方式は、どれもプログラムを条件で分割して宣言的に書けるようになってますが、それでも if 文を完全に駆逐するに至っていません。

真理表は長らく論理を表すのに使われてきました。真理表の欠点は、組み合わされた条件を表現すると途端に複雑さが増大する事です。組み合わされた条件には、表より if 文による文章的な方法が適しているという調査もあります。また、命令と条件を同じ感覚で書ける if 文と異なり、真理表の中にコードを埋め込むと気持ちが分断されてしまいます。これを解決するスキマチック・テーブルのアイデアは以下のとおり。

  • 計算と論理は直行しているので、タテヨコに分けて書けば良い。
  • 二次元の表はただのテキストより便利で、コードが分断されるのを防ぐ。
  • 論理的な不変性を保つ事でプログラムの苦労が減る
  • スキマチックテーブルはプログラムの意味の同一性を保証出来る。手動レイアウトを不要にしてリファクタリングを簡単にする。
  • if 文、パタンマッチング、ポリフォニズムを同じ方法で表現できる。
  • 型宣言、断言、条件によってプログラムがくっつく。

単純なスキマチック・テーブル

  • 横向き(行)には、変数とその値が並んでいる。縦向き(列)には、状況が並んでいる。
  • 二列目は、if (a & b) {x = 1} の意味。丸で囲ったやつは predicates (述部、条件?) と呼ぶ。
  • x の行の二番目のセルにある数字の 1 を値と呼ぶ。その列の条件が合えば x に 1 が代入される。
  • 三列目は、if (!a | !b) {x = 2} の意味。論理和を表すのに縦の点線がある。点線の場合どちらかを満たせば良い。
  • 列の分け方は論理和標準形 (disjunctive normal form) を使う。条件はそれぞれ排他である(たぶん、(a|b|c)&(d|e)&(f|g|h|...) の形をしていると言いたいのだと思う)。

この方法の利点は、x = 2 になる条件がすぐ分かる事。if 文で、例えば if (a & b) {x = 1} else {x = 2} のように書いてしまうと、頭の中でド・モルガンの法則 (!(a & b) == (!a | !b)) が必要です。ただ、一方で表は読むのは簡単ですが、ちゃんとスキマ無くて表を作るのが面倒です。そこで、IDE を使い、自動的に表をメンテナンスします。

  • まず最初に、無条件に x = 2 の代入が起こる表を考えます。
  • (a & b) の時に x = 1 にする為に、メニューから新しい列を出します。
  • 適当な場所に y (真) を入力します。
  • すると入力した条件以外の条件の列が自動生成されます。

IDE は、条件がダブらないように、スキマが出来ないように自動調整します。

トランザクション編集

まだまだつづく!