TypeScript + PEG.jsでデータフロープログラミング専用のDSL言語AsyncFlowを作った

概要

最近，自分でAsyncFlowというDSL(Domain Specific Language)を作りました．

技術スタックとしては

• Typescript v3.0.3
• PEG.js v0.10.0
• jest v23.5.0

といった感じで，主にTypeScriptで型をつけながら，PEGで構文解析を行い，基本的にはテストファーストなTDDをjestで行っていました．
単体のプログラミング言語として存在するわけではなく，ましてやチューリング完全でもありません．
イメージとしては「C++に埋め込んだLua」みたいなイメージで，「TypeScript上で動く別のプログラミング言語」のイメージ．もしくは，マクロ言語的な視点で見てもらえたら幸いです．

実際のコード

以下は，AsyncFlowを埋め込んで，素数の計算を行った例です．

import {
    AsyncFlowExecuter,
    IAst,
    Locals
} from '../src/AsyncFlowExecuter';
import { AsyncFlowParser } from '../src/AsyncFlowParser';
import {IfPipe} from '../src/IfPipe';
import {SimplePublisher} from '../src/SimplePublisher';
import {SimpleSubscriber} from '../src/SimpleSubscriber';
import {Transformer} from '../src/Transformer';

const pub = new SimplePublisher(1);
const relay = new Transformer((x: number) => x);
const inc = new Transformer((x: number) => x + 1);
const init = new Transformer((x: number) => [x, x]);
const dec = new Transformer((x: number[]) => [x[0] - 1, x[1]]);
const check = new IfPipe((x: number[]) => (x[0] > 1 && x[1] % x[0] !== 0));
const isPrime = new IfPipe((x: number[]) => (x[0] === 1 && x[1] !== 1));
const sub = new SimpleSubscriber((x: number[]) => {console.log(x[1]); });

const parser = new AsyncFlowParser().parser();
const executer = new AsyncFlowExecuter();
const locals: Locals = {
    pub: pub,
    relay: relay,
    inc: inc,
    init: init,
    dec: dec,
    check: check,
    isPrime: isPrime,
    sub: sub
};
const ast: IAst = <IAst>parser.parse(`
var *pub = pub
var relay = relay
var inc = inc
var init = init
var dec = dec
var check = check
var isPrime = isPrime
var sub = sub

pub.c -> relay
relay.c -> inc
inc.c -> relay
relay.c -> init
init.c -> dec
dec.c -> check
check.t -> dec
check.f -> isPrime
isPrime.t -> sub
`);

executer.run(locals, ast);

実行例

$ npx ts-node example/prime_extend.ts
2  
3  
5  
7  
11 
13 
17 

言語のコンセプト・なぜ作ったか

コンセプトとしては3つあります

• データフロー言語
• 不定な順序の言語
• テスト駆動開発でプログラミング言語を作る

データフロー言語

前々からデータフロープログラミングというものに興味がありました．

データフロープログラミング（英: dataflow programming）とは、データフローの原理とアーキテクチャを用いたプログラミングパラダイムであり、何らかの操作と操作の間でのデータの流れを有向グラフとしてプログラムを作成する。データフロープログラミング言語は関数型言語に一部似ており、一般に数値処理に適した言語に関数型言語的概念を導入するという形で開発された。

この概念自体はかなり昔からあるのですが，今一つ流行ったものがない．といったイメージです．思想としてはUnixのパイプなんかもこの概念の範疇ですが，逆にそれ以外の例は数が少なく，Streemなどの実験的なプロダクトになってしまいます．過去にPythonectというPython+データフロープログラミングの言語を紹介しましたが，日本語の記事が僕のQiitaぐらいしかないぐらいにマイナーでした．
そんなわけで，「データフロープログラミングしてみたいけど，言語がないなぁ」ぐらいの気持ちを持っていました．

不定な順序の言語

一般的なプログラミングは記述された文章が上から実行されることを前提とされています．

a = 1
b = a + 1

この順序を守らない言語とはなんだろうなぁ．みたいなことを考えていました．１つは先ほども紹介したデータフロー言語だったり，制約プログラミングの類だったりします．ほかには，自作で実行の順序が不定な言語を作った人もいます．

遺伝子をモチーフにした言語「Genomy」を作りました
(厳密には生成・消滅に関するルールのみが書かれており，実行の順序が不定ではないのですが，インスパイアを受けた元として記載しています)

そんななかで，ふとnode.jsのEventsのことが頭によぎりました．

const emitter = new EventEmitter();
emitter.on("event",(x) => console.log(x));
emitter.emit("event",2);

この**「EventEmitterのemitとonの仕組みって非同期じゃないか？」と．調べてみると，API的には非同期ではないのですが，setImmediateと併用することで，非同期っぽくできること．それと，もしEventEmitterで作ると明らかにクラス数が爆増して，イベント名が爆増して，フローの制御が爆増してカオスになる**というヤバい予感だけしていました．そういうわけで，「node.jsでも作れなくはない．」ぐらいの気持ちでいました．

テスト駆動開発でプログラミング言語を作る

最近，Ruby on Railsの開発をすることになり，私自身Rubyが初めてでした．その中で，適当にテストファーストで組むようにしたのですが，これがすごく書きやすかった．初見のRubyですら，スイスイと書けてしまったので，これはいいものだ．と思い，「テスト駆動開発」の本も買って，勉強しました．そして，その中でおもしろい記述を見つけました．

テストファーストでプログラミング言語のコンパイラやインタプリタをBNFから実際に使えるレベルまで育てることができない

と書かれていました．そもそも言語を作ること自体が難易度が高いため，それをテスト駆動でやっても，色々な分岐を網羅する必要があり，成功はしにくいだろう．という直感はありました．
そんな中で，ちょうどプライベートが暇になり，

でも，ぶっちゃけ簡単な言語だったら作れるでしょ？

と軽い気持ちで作り始めました．
上記したように，「EventEmitterでおそらく作れるだろう．」という算段でjavascript,AltJS系を考えていました．しかし，明らかにバグで死にそうになる．とも思ったので，せめて型の厳しいTypeScriptで．なおかつTDDができるように初期段階からjestの導入と考えて作り始めました．

文法

基本的な文法は2つしかありません

• 変数宣言
• フロー宣言

変数宣言

var [AsyncFlow内で使う変数名] = [Localsで渡される変数名]

AsyncFlowの言語の中で使う変数に，AsycFlowExecuterで渡されるlocalsのオブジェクトをバインドします．

フロー宣言

[AsyncFlow内の変数].[属性名] -> [AsyncFlow内の変数]

これは簡単には，「左辺の変数の属性」から「右辺の変数」へEventがemitされる．ということです．

pub.c -> relay

の例だと，pubというオブジェクトが発火した.もしくは，pubのpublishという関数が呼び出されたとき，relay.emit()が呼び出されます．この時，pubのcの属性の変数の値が渡され，これによりデータのフローを構築します．

発火変数宣言

これは1か所だけ使われていますが，

var *pub = pub

というのついた変数です．このがついた変数は，実行時にデータフローを構築した後，pub.publishが呼び出され，プログラムがキックされます．

既存の言語との相違

データフロー言語特有の部分があり，それは，relayとincの関係だと思います．

pythonだと，

c = 1
while 1:
  if(isPrime(c)):
    print(c)
  c+=1

のような形になり，ループの最初->isPrime->変数のインクリメント->ループの最後という処理フローになります．
しかし，AsyncFlowは常に変数をインクリメントし続け，インクリメントした結果をisPrimeでフィルターしているような処理になります．どちらかというとシェルで

$ seq 1 10000 | is_prime | echo

seqで数列を生成しながら，is_primeという素数判定をするプログラム（があったとする)でフィルターして出力しているようなイメージです．
ただシェルと異なる点として，何個も1つの出力を複数へ分けることができたり，1つのノードから複数の種類の違う値を出力できたりします．
前者の例だと，relayはinitへデータを送っていますが，同時にincへもデータを送っています．
後者の例は，checkで，送られてきたデータを判定して，結果がtrueの時，decへデータを送り，falseの時は，isPrimeへ送っています．
この辺りはシェルでも名前付きパイプを用いて行うことができますが，これを言語レベルに組み込んでいます．

言語を作ってみて

「プログラミング言語の作成において難関となるのは文字列のパース」

と思っていました．

「しかし，実際作ってみるとプログラミング言語の実行のほうがもっと難しい」

となりました．
テスト駆動の範疇においては，文字列のパース．構文解析木の構築においては，非常に役に立ちました．細かにテストを書いておくことで，適宜，回帰テストを回すことができます．**構文解析木の定義は１つ変えるだけで容易に壊れます．**そのため，バグを直したつもりが，バグを作りこんでる．とか，もともとの言語の文法と衝突してる．ということが，早期検知できるため，厄介なバグの作りこみはほとんどありませんでした．
一方で，パースしてオブジェクトになった後の実行．これに関しては，本当に困難でした．ここをもっと作りこんで，AsyncFlow自体をプログラミング言語まで昇華させようと思いましたが，やめました．しかし，これ自身は，それほど悪いことではなくて，TypeScriptでなれた処理を書くことができて，それをデータフローっぽくつなぎこめるという点では，自作でフルスクラッチでプログラミング言語を作るよりかは，幾分汎用的な言語になったように思います．自作で言語を作っても，かなりデバッグしにくく，記述性がいまいちで，中途半端なモノができてしまうことは容易に想像ができます．

言語として触ってみて

「変数宣言の記述性が悪い」

正直，フロー宣言の部分は，それほど悪い表記ではないと思います．しかし，一方で，「TypeScriptでオブジェクトを宣言」し，それを「localsとしてObjectに格納」し，「AsyncFlow言語の中で再度オブジェクトを宣言」する三重構造を余儀なくされているので，非常に煩雑です．1つ2つ変数を追加するだけで，3つ書き換える場所があるのは，なかなか実用上は辛いです．

「データフロー言語に合致した題材が難しい」

これは鶏と卵の関係もある気がしますが，やはり一般的な言語は上から下へ順々にフローが流れていきます．そのため，アルゴリズムの記述や処理の記述もそれにあった表記になっています．そのため，「データフローのほうが書きやすい」ような題材を見つけることは非常に難しいです．一度，AsyncFlowでFizzBuzzを書いてみたのですが，「これってデータフロー言語で書く意味あるっけ？」となります．それくらい手続き言語に思考が制限されているなぁ．という印象を受けました．

感想

自分としては，「完成しなくてもいいや．」ぐらいの気持ちだったのですが，何とか見せれる程度の形になってよかったです．始める前は，文字列のパースで嫌になって投げだすと思ってました．それが，そこそこフローも書けて，実行できるように作れたのは非常にうれしかったです．自分としては，すごく野心的な試みで，TypeScript自体もほぼ初見ながら，言語を作りこめたのは奇跡的でした．
本当に「自作言語をテスト駆動で作る」のはお勧めします．おそらく，テスト駆動してなかったら，ここまで形になることはなかったので．
久々に1つのバグで全体が崩壊するような難しいプログラムを作ったなーという感想でした．