Glispを開発している中で、このエントリにも上げたような問題があったので言語処理系自体を、一般的なLisp評価器とは異なった、よりGUIやデザインとの親和性の高いものへとアップデートしようとしています。しかしまた色々行き詰まった所が出てきたので、言語化も兼ねて今一度悩んでいるところを書き出しておきます。

言い訳までに、僕はただの映像専攻の美大中退者でして、言語処理系に関して何の専門教育を受けたこともないので、車輪の再発明をしているような予感もありますし、以下の考察も適切ではないかもしれません。もし、この辺勉強するとスッキリするよ～とか、こういう概念があるんよ～みたいなアドバイスがあれば、断片的にでも構わないので教えてくださるととても嬉しいです。

Lispの何が問題だったか?

• そのシンボルが指し示す値、関数の実体、そして型が、評価されるまで分からない（Lispは動的型付けなので）
  • その関数の引数や、シンボルの型に合った適切なUIを表示出来ない
• ある式の一部が置き換えられながら、繰り返し再評価されるような用途を想定していない
  • Incremental evaluation（差分評価?）の実装の難しさ。Glispでは構文木そのものをプロジェクトファイルの階層として扱うが、ある式の一部の数値やシンボル名が更新されるたびに、プロジェクト全体を再評価するのは効率が悪い

プログラミング言語におけるシンボル

ここで考え直したのが、プログラミング言語における「シンボル」の意味です。コードは「手順」を表すこともありますが、より抽象的に捉えるとデータ同士の結合の仕方を表した有向非巡回グラフ構造でもあります。例えば以下の式

(+ 1 (+ 2 3))

は、このようなグラフを成します。

ここまでは普通の抽象構文木の説明ですが、それは文字通り「木構造」でしかないので、データの合流しか表現できません。シンボルの本質は、あるノードに「別名」を付け、その木構造の直接の親子関係ではない別のノードから何度でも参照できるようにすることによって、データ処理のグラフに「分流」を表現することにあります。

(def a (+ 2 3))
(+ a (* a 2))

ですから、評価時でシンボルが指し示すノードを解決するのではなく、前もって名前解決を済ませ、構文木にこのようなグラフ構造を仕込んでおくことで、そのシンボルの値までは分からないかもしれないにせよ、少なくともどのノードから出力されているか（どの関数の返り値か）によってその「型」は予めわかります。例2の場合、シンボル a は、足し算ノードから出力されているので数値型です。UIには、数値ボックスにa というエクスプレッションを表示しておき、そこをクリックすることで (2 + 3) の式へとジャンプさせることができます。（一度でもグラフ全体が評価されているなら、5という評価結果を表示することも可能です）最近こういうデータ構造のことをProgram Dependency Graph（PDG）と呼ぶことを教わりました。

グラフ構文

今Glispでは、そうしたシンボルの役割をより明示的に表現すべく、スコープや「順番に実行される式の列」という概念を取り去り、こうしたグラフ構造を直接記述する新しい構文を試しています。それは中かっこで囲い、シンボルと式のペアと、最後にグラフ全体が返すシンボル名を並べることで表現します。

{symbol1 expression1
 symbol2 expression2
 ...
 returned-symbol}

ツリービューが入れ子構造のS式だとすると、グラフはノードベースUIに対応します。

シンボルは「値の容れ物」ではなく、グラフの分流を表現するための別名でしかないので、以下のような再代入は不正です。

{x 10        ; let x = 0
 x (+ x 1)   ; x += 1
 x}          ; return x

先の例のconst a = (2 + 3); (a + (a * 2)) は、グラフ構文ではこうなります。

{a (+ 2 3)
 o (+ a (* a 2))
 o}

上記の式をパース、解析（名前解決）することで、このようなPDGを生成します。

このグラフを、求めたいノードから上流へと辿ることで、最終的な評価後の値を得るという算段です。

シンボル a をノードとして残しているのは、PDG全体を構文木のスーパーセットにするためです。(* a 2) にはあくまで (* (+ 2 3) 3) という展開後の式ではなく a というエクスプレッションと 2 の掛け算としてGUI上に表示されていてほしいですよね。また、UI表示上の都合だけではなく、常にPDG全体が文字列のコードへと変換され得ることを保証するためにも a というシンボルは残してあります。

一度PDGが構築されれば、そこに「式の実行順」という考え方もなくなります。例えば以下のような式もvalidです。

{a (+ b 2)
 b 1
 a}

一方で循環参照は不正となります。

{a (+ b 1)
 b (+ a 1)
 a}

こうしたPDGを構築するメリットは

1. あるノードを変更した時、その下流（親）に当たるノードだけを再計算させることで差分評価が実装できる
2. 式全体を評価せずとも、任意のノードだけを評価することができる
3. 構文木の各要素に「パス」を割り当てることができる

3はもう少し説明が必要です。多くのデザイン系ツールは、シンボル名を明示的に宣言せずとも、パラメータ同士を直接参照することができます。AfterEffectsでいう thisLayer.transform.position 、Houdiniでいう ch("../radius") 、TouchDesignerの `op('/project1/effect/transform1').par.tx のようなエクスプレッションです。

Glispでもグラフ構文のシンボル名や、関数のパラメータ名から成るパスを構文木に割り当てられる仕組みにする予定です。そしてそれらを相対パスや絶対パスから成る「パスシンボル」を通して、明示的にシンボル名を宣言せずとも構文木の各部分同士に直接参照関係を貼ることができるようになります。

度々例に上がるこのような式は、パスシンボル構文を使えばこのようなワンライナーで表現できます。

(+ (+ 1 2) (* @`../0` 2))
; あるいは
(+ @`./2/1` (* (+ 1 2) 2))

そしてこうした表現は、Houdiniのパラメーター編集画面やAfterEffectsのエクスプレッションなどでとられている表現にも近しいものになっています。

ここでまとめます。シンボルの考え方を再定義し、コード全体を「手続きの連なり」ではなく「グラフ」として解釈するような構文をとることとのメリットを、具体的にデザインツールにおける機能に置き換えるとこのようになります。

1. ツリービュー、ノードベースUIの両方が使える（グラフ構文、S式）
2. パラメーター欄にエクスプレッションが貼られていても、その型に合ったUIが親切に表示されてくれる（静的型解析）
3. 巨大なプロジェクトでも、ほんの一部にしか影響しないパラメーターをチマチマ変更した時にはそんなに更新がモタつかない（差分評価）
4. レイヤーやコンポジションなんかをソロ表示すると、それが元々非表示に設定されていたとしてもちゃんと正しく表示されてくれるし、しかも軽くなる（部分評価）
5. パラメーターをパス表現を介して直接参照することが出来る（パスシンボル）

一方で悩ましい点もあります。あるノードの評価結果を知るには、その上流（子）のノードを辿って評価する必要があります。また一方で、あるノードを変更した時、その変更によってどのノードを再計算する必要が生じるかを下流へとたどりながらマークする必要があります。つまり、あるノードは上流ノード、下流ノードの両方への参照を持っている必要があるのです。

こうした双方向の参照をもったグラフ構造は、ActionScriptやPaper.js、Three.jsなどのステージオブジェクトにも見て取れます。つまり、それぞれのステージオブジェクトが children() や parent() メゾットを持っているということです。このような場合、どのようにしてイミュータブルなノードの更新をやってのけるか に個人的に悩んでいます。親から子への参照しか持たない木構造の場合は、このようなことになります。

しかし親から子、子から親へと両方の参照を持つ場合、そもそもグラフ全体をdeep cloneしないからには、双方向の参照の整合性を保ったままのイミュータブルなノード置換は出来ません。

Paper.jsなど場合は、そもそもミュータブルに更新していく（それぞれのノードが needsUpdate のようなフラグを持っていて、レンダリング時に走査してフラグが立っているオブジェクトを再キャッシュする）仕組みとなっているので、そもそもこの問題は起きませんが、Vue.jsやReactのような、フラグを使わずイミュータブルなデータ構造全体の置き換えを検知することでコンポーネントを更新するライブラリ上では、うまくreactivityが効いてくれないことになります。そして仮に forceUpdate() のような汚い方法を取ったところで、データが永続的ではないので undo/redo の実装が難しくなります。

バインドデータが単なる木構造の場合は、そもそも子コンポーネントがデータ更新を emit すれば済むので、子ノードが親ノードへの参照を持つ必要はありませんが、DAGの場合はあるノードの親（下流ノード）が複数になることもあるので、props – emit の枠組みではうまく扱えません。

…と、色々悩んでます。DAGをガチャガチャする夢を観るくらいに気が休まらないので、例のMV制作の方で気持ちを落ち着けつつ、少しずつ開発進めて行こうと思います…。