ガバガバAltJSを作った(言語実装 Advent Calendar 2017)

qiita.com

JavaScriptを書いていると、頻出する継続渡しのリフレインにうんざりさせられる。

foo.bar(function(result){
  qux.baz(function(data){
    hoge(function(r){
  ...
    });
  });
});

そこで、腕試しに継続モナドをベースにしたAltJS、jatkoを作った。フィンランド語で「継続」という意味だ(継続戦争から知った人も多いだろう)。しかし、なんの考えもなしに653行Haskellを書いた結果ガバガバな言語になってしまった。

Hello, world

Haskellにだいぶ近いのでなんとなく読めるはず。

infixr 1 ->
infixr 0 $

($) = \x -> x

constructor String : Type
constructor (->) : Type -> Type -> Type
constructor JSAction : Type -> Type
constructor JSCont : forall b r. ((b -> r) -> r) -> JSAction b

register return JSAction = \a -> JSCont $ \cont -> cont a
register bind JSAction = \m k -> JSCont $ \cont -> case m of
  JSCont f -> f $ \a -> case k a of
    JSCont c -> c cont

console'log = [|function(str){ return function(cont){console.log(str); cont(null);}|]
  : String -> JSAction Unit

main = (do
  console'log "hello,";
  console'log "world") JSAction
console'log = [|function(str){ return function(cont){console.log(str); cont(null);}|]
  : String -> JSAction Unit

この部分が重要で、継続渡しスタイルな生JSをBSDブラケットで囲むことでアクションを定義でき、do記法でフラットに組み合わせることができる。

ガバガバポイントその1: 型と値を区別しない

型も値も同じ構造で扱うという、JavaScriptもびっくりなガバガバ仕様を採用した。すべてはこのExpr型の値として表される。

data Literal = LInt !Int | LDbl !Double | LStr !String
  | LJavaScript !String
  deriving (Show, Eq)

data Expr a = Var a -- ^ 変数
  | Expr a :$ Expr a -- ^ 適用
  | Con !Name [Expr a] -- ^ コンストラクタ
  | Lit !Literal
  | Lam !Name (Expr a)-- ^ ラムダ
  | Case [(Name, [Name], Expr a)] -- ^ パターンマッチ
  | Expr a ::: Expr a -- ^ 型シグネチャ
  | Forall !Name (Expr a) -- ^ 全称量化
  | Coerce (Expr a)
  deriving (Show, Eq, Functor, Foldable, Traversable)

ガバガバポイントその2: 後付けできるパターンマッチ

register return JSAction = \a -> JSCont $ \cont -> cont a

とすると、returnが種Type -> Typeの型tを受け取り、a -> t aを返す関数として定義され、JSActionに対する実装が追加される。実装を後から増やすことが可能で、型クラス相当の役割を担うが、クラスに相当する宣言が今の所存在しない。

ガバガバポイントその3: 怪しい型推論

型推論器は何も参考にせず勝手気ままに実装した。それっぽく振舞うが、高い確率で欠陥がある。

気づきなど

構文解析にはparsers、実装としてtrifectaを使った。これがなかなか使いやすく、二項演算子からリテラルまでだいたい欲しいものが揃っている。特に面白いのは、「改行をスキップしない」のようなパーサーの変化をモナド変換子によって実現しているところだ。これは「モナド変換子の代替」とされるExtensible effectsでは素直にはいかないだろう。

オフサイドルールの実装はなかったので、同じようにモナド変換子として実装を試みたが、do記法がうまく扱えなかった。しっくりくる実装ができたらプルリクエストを送りたい。

演算子の優先順位などの情報を共有したり、型推論器で状態を扱うのにもReaderT、StateTなどが役に立つ。まとめると、パーサーコンビネータモナド変換子があれば言語処理系が作れるというわけだ。