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

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

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

参照用 記事

変数なしプログラミングとお絵描き圏論

お絵描き圏論とCatyScriptの変数など」において、データフロー・ベースの(より正確にはデカルト圏ベースの)プログラミングでは変数なんて要らないのだ、という話をしました。しかし現実には、変数なしプログラミングは辛い、とも言いました。このへんのことをもうチョイ話します。(僕自身の参照用にリンクをたくさん入れてます。)

なお、実際にソフトウェアを動かしてみたい方はコチラを参照。

内容:

  1. もう一度あの例題
  2. デカルト圏にマップするための準備
  3. デカルト圏におけるお絵描き
  4. がんばってテキスト表現してみる
  5. データフローグラフとその応用
  6. 変数なしはつらいよ
  7. お絵描きプログラミング

chimaira.orgの記事:

もう一度あの例題

CatyScriptでは、リダイレクト記号 '>' により変数への代入(変数の生成と初期化)を行い、パーセント記号 '%' で変数を参照します。次の例を挙げました。


/* 変数tの値をコマンドfの入力として、
* fの出力を変数xに代入する。
*/
%t | f > x;

/* コマンドgの出力を変数yに代入する。
*/
g > y;

/* 変数xの値と変数yの値を使ってJSONオブジェクトを組み立て
* それをコマンドhの入力とする。
* コマンドhの出力を変数zに代入する。
*/
{"a": %x, "b": %y} | h > z;

/* コマンドkの引数に、変数x, 変数y, 変数zをこの順で渡す。
* コマンドkの出力がプログラム全体の出力となる。
*/
k %x %y %z

このプログラムを絵に描くと次のようになるのでした。

デカルト圏にマップするための準備

先の絵をデカルト圏のなかで描き直すことにします。プログラミング的な概念を純圏論的な概念にマップすることになります。

デカルト圏の直積を表現するデータ構造はタプルと呼ばれます。タブルには名前なしタプル名前付きタプルがあります。JSONで言えば、名前なしタプルは配列で、名前付きタプルはオブジェクトです。2種類のタプルがあることは、実用上は重要ですが、理論上は煩雑になるので、名前なしタプル(配列やリスト)だけを考えることにします。

次に、「お絵描き圏論とCatyScriptの変数など」で触れたように、パラメータは入力の一部として取り扱うことにします。

考えている圏はデカルト圏なので、f P :: X -> Y の代わりに f' :: P×X -> Y を使っても同じことです。



パラメータがいやなら、オーバーロードされたコマンドを複数の異なるコマンドに分けて、パラメータを直積により入力に押しこんでしまえば、入力と出力だけの議論に還元できます。

それと、絵を描く労力を減らすために、長さnのタプル入力をn個の入力と同じとみなします。関数の引数で言えば、h([x, y]) を h(x, y) とみなすことです。絵では、n本のワイヤーからタプルを構成する部分を省略してよいことになります*1

上の図で、XとYのタプル(直積)を入力とするコマンド(射)hは、XのワイヤーとYのワイヤーの2本が入る箱で描いてもいいわけです。

デカルト圏におけるお絵描き

さて、変数を使った例題プログラムに対応する絵を、純粋に圏論的にデカルト圏のなかで描き直すことにします。射 f, g, h, k のプロファイル(域と余域)を圏論の標準的記法で書いておきます。

  • f:T→X
  • g:1→Y
  • h:X×Y→Z
  • k:X×Y×Z→W

ちなみに、同じことをCatyScriptの宣言で書くと次のようです。


command f :: T -> X;
command g :: void -> Y;
command h :: [X, Y] -> Z;
command k :: [X, Y, Z] -> W;

データフローのトポロジーは一切変えずに、デカルト圏の概念だけで絵を描くと次のようになります。縦の点線や下側の番号は、後で引用するときに使用します。比較のために、すぐ下に元の絵も添えてあります。

「Yの形」を横倒しにして丸で囲んだところは、データをコピーする射で、対角(diagonal)と呼びます。「Xの形」を丸で囲んだところは、データの順序を交換する射で、対称(symmetry)と呼びます(「対称」以外にたくさん呼び名があります)。

がんばってテキスト表現してみる

デカルト圏内の絵を、テキストの式で表現してみましょう。使う記号は、対角がΔ、対称がσです。プロファイルを確認しておくと次のようです。

  • ΔX:X→X×X
  • σX,Y:X×Y→Y×X

下付き添字は省略することがあります。

先の絵で、縦の点線で区切った領域(スライスと呼びます)ごとにテキストに直していきましょう。まずはスライス1だけを考えます。

横割りにして考えると:

  • 上段: f;ΔX
  • 下段: g;ΔY

直積に組んでまとめると:

  • (f;ΔX)×(g;ΔY)

デカルト圏では交替律interchange law)が成立するので、縦割りにして考えても同じです。

  • (f×g);(ΔX×ΔY

同様にしてすべてのスライスをテキストで表現すると以下のようになります。

  1. (f;ΔX)×(g;ΔY)
  2. idX×σX,Y×idY
  3. h×idX×idY
  4. σZ,X×idY
  5. idX×σZ,Y
  6. k

実は、3本以上のワイヤーを(2本と1本のように)まとめ直すときに直積の結合律を表現する射(associator)をはさむ必要がありますが、面倒なので省略します。さらに、下付き添字は省略し、恒等射は対象で略記してできるだけ短く書くと次のとおり。

  • (f;Δ)×(g;Δ) ; X×σ×Y ; h×X×Y ; σ×Y ; X×σ ; k

僕はテキストで計算するのは嫌い(つうか出来ない)ですが、がんばればテキストでも表現と計算ができるってことです。

データフローグラフとその応用

変数を使ったプログラムを絵に描いて、変数ポイントを除去してしまうと、出来上がる図形は有向グラフです。この有向グラフのノードはデータ処理を表現し、有向辺はデータの流れを示します。データのコピー(対角Δ)や順序の交換(対称σ)、それとデータの破棄(終射!)などもノードになります。この有向グラフは、データの流れ(同時に制御の流れでもある)を表すのでデータフローグラフと呼びます。

CatyScriptの実行モードは飼い猫モードと山猫モードがあり、通常使う飼い猫モードでは繰り返し構文(エルゴット繰り返し)を持たないので、データフローグラフにサイクルは出現せずにDAG(directed acyclic graph)になります。データは一方向に流れるので、その解析は比較的に容易です。

フロー解析して何がうれしいでしょうか? すぐに思いつくのはコンパイル時の最適化です。現状のCatyScriptの利用場面では、せいぜい数行のスクリプトしか書かないので、最適化だの高速化だのはバカバカしい感じがするのですが、巨大なスクリプトを書いたら(誰が書くんだ)最適化の意味があるかも知れません。

デカルト圏の公理は等式的(equational)に書けます。公理からたくさんの等式が導かれます。例えば、<f, f> = f;Δ という等式がありあす。これは等式ですから左右を入れ替えても同じことです。しかし、プログラム実行の観点から考えると、<f, f> では同じ処理fが2個並列で走りますが、f;Δ ではfが1回と軽い処理であるコピーで済みます。つまり、コストを考えると、<f, f> ⇒ f;Δ という書き換えに意味があります。

コストを勘案して、等式を書き換え規則とみなすと、項書換え系(term rewriting system)ができます。記号テキストに限らず図形にも書換え系が定義できるので、フローグラフに対するグラフ書換え系もたぶん組み立てることができるでしょう。この系(システム)は、なんらかの同値性を保ちながら図形を変形していきます。変形の前より後のほうが、消費資源や速度で有利であれば、最適化ってことになります。

図形の変形はしなくても、単にフローを追いかけるだけでも、Webアプリケーションにおける清潔でない(汚染の可能性がある)データの検出に使えます。有向グラフのノードと辺に安全か(信頼できるか)そうでないかのフラグを付けておいて、全体として安全かを計算するのはそれほどの手間じゃありません。単なるフラグよりリッチな量を割り当てても、ダイクストラのアルゴリズムで集約値を計算できるケースは割とあります。

変数なしはつらいよ

そんなわけで、理屈の上では変数は要らないし、データフロー解析には変数を除去したほうが便利です。

しかし、有向グラフのテキスト表現であるスクリプトを変数なしで書くのは難しい。できなくはないのですが辛い。どのくらい辛いか? 今まで使ってきた例題を、変数なしスタイルのCatyScriptで書いてみます。データのコピー(対角)、順序の交換(ワイヤーの交差=対称)を全部明示的に書かなくてはなりません。そのとき使う道具は、恒等射を表すpassコマンドと配列のn番目を取り出す射影であるnthコマンドです。

次がそのスクリプトです。初期入力を与える変数%tだけは残っています。


// 変数なしプログラム

[
%t | f | [pass, pass],
g | [pass, pass]
] |
[
[
nth 1 | nth 1,
nth 2 | nth 1
] | h,
[
nth 1 | nth 2,
nth 2 | nth 2
]
] |
[
nth 2 | nth 1,
nth 2 | nth 2,
nth 1
] | k

まー、慣れればどうってことない … イヤッ、慣れないよ、こんなもん。

お絵描きプログラミング

代入('>')、変数参照('%')、パイプラインの一時的終端(';')を入れることで、CatyScriptはだいぶ書きやすくなり、普通のプログラミング言語に近くなりました。しかし、依拠しているモデルが本質的に図形的なので、テキストで表現することが最適なのかどうかは疑問があります。変数がないと辛いのもテキスト表現だからで、直接ワイヤーをいじれば変数(目印の名前)がなくても平気です。

ボックス&ワイヤーによる絵算(pictorial/graphical/diagrammatic calculation)を直接的に表現する絵図言語(pictorial/graphical/diagrammatic language)でプログラミングするのが自然じゃないかと思います。もっとも、僕自身はコマンドラインテキストエディタが好きで、不満も感じない*2ので、絵図言語の直接入力系=お絵描きツールへのモチベーションがいまいちなんですけどね。

*1:ここらへんの事情を正確に定式化するには、複圏(multicategory)や多圏(polycategory)という概念が必要です。

*2:お絵描きをしてないのではなくて、脳内お絵描きして、それをテキストで書き下してます。