勝手にevalしない言語をRustで作ったら意外なものになった

概要

この記事は言語実装Advent Calendar 2017 25日目用として書かれたものです。 Advent Calendar初参加です。迷っていたら25日が空いていたので、思い切って飛び込んでみました。 でもよく見たら、なんだかテーマは高度なことばかり。 私はそのようなことは全然書けるような実力はありませんので、できることだけをやりました。こわい。すいません。

ソースコード

Epiqsという名前です。たらい関数とfibonacciは動いてますよー。 READMEは古い記述がたくさん残ってるので直したいよー。 github.com

動機

たくさんある。なんだか思いの丈がまとまっていないが、そのまま書く。 ちなみに私は「ポエム」という表現を使うのは好まない。 書いていて気づいたが、言語実装というよりは言語「設計」という趣である。

コンスセル大好き

Lisp系言語が好きなのだが、最近、どちらかというとコンスセルが好きなのだと気付いた。 Lispの書籍には最初、初心者用に正方形が二つ横に並んだものが矢印で結ばれた図が載っている。あれである。 あれが至高。むしろ私の志向がアレなのかもしれないが。

コンスセルをepiqと呼ぶことにした

既存の名前は好きじゃない
  • cons/car/cdrという名前は好みではない
  • first/restも惜しいがもう一声欲しい
piq

というわけで、ある日突然、コンスセルにpiqという名前をつけた。「ぴっく」と読む。

  • 目を細めてみると、pとqがそれぞれ二つのポインタに、間のiが仕切りに見える気がする。
  • この言語ではcarのことはpと呼び、cdrのことはqと呼ぶ。pとqがアルファベットで隣同士なのもポイント高し。
  • 昔作ったものがBriqsDBだったので、それと語呂を合わせたかった（BriqsDBは変なDB(？)とそのクエリ言語）。

コンスセル大好きだけど、情報が足りない

「コンスセルを使えばあらゆる構文を表現できる」のは確かだ。ただ、ポインタ2つだけではもの足りないというか、効率が悪いと常々感じていた。「カッコだけだから統一感があって美しい」にはほぼ賛成なのだが、キーワードに複雑さを転化しているとも解釈できる。

あと一つ情報を付け足すとしたら

それでは、コンスセルに付け足してメモリ効率を上げられるような最低限の情報ってなんだろう、と考えて、結局、読み取り専用タグをつけた。こうして、piqはタグ（otag、pの前のアルファベットなので）を持つことになり、「タグ埋め込み」という意味を込めてepiqと呼ぶことにした。言語名はここから来ている。epicとかけたのも、もちろんある。

暗黙の動作をなくしたい

勝手にevalしない

マクロの複雑さは、evalが再帰呼出されるから？

Lispでマクロを書く時には、特にマクロを生成するマクロなんかだと、quoteとunquoteがこんがらがる。この点に関してはいくつかの解決策や妥協案があるが、そもそもそれって、evalしたら再帰的に評価を行うからなんじゃないの？という疑問が浮かんできた。

evalの再帰性は、共犯関係から成り立っている？

SICPにも出てくる評価機を見ても、evalから呼ばれる各種special formやapplyは、それぞれの要素に対してevalを呼び直しているのだ。つまりevalが再帰的に実行されるのは当然ながら単体でなされたものではなく、evalと他の言語要素との共犯関係が前提にあってのことである。

evalではなくてwalk

というわけで、デフォルトでは何もせず、評価させたい部分だけをevalするアイディアが浮かんだ（ただ、言語を作った今だから言えるが、実際にはそんな簡単な話ではなかった）。だから、"REPL"ではなくRead-Walk-Print-Loop(RWPL?)になる。walkする中で、evalが明示的に呼び出されている部分だけが評価される。evalを使わずにコードを返す関数を書けば、それはマクロ定義になる。

applyはたくさんのことを一度にやりすぎ

applyって結構、色々なことをやっている。ここでのapplyは、apply関数というよりは、通常の関数適用のことだと考えてほしい。

  • シンボルを解決して関数本体を取得する
  • そして引数のリストを評価する
  • それを関数本体にバインディングする（必要ならばパターンマッチも）
  • 環境も整える
  • ようやく中身の実行

最低限でもこれだけある。これらもなるべく分解して、明示的にしたいと考えた。わかりやすさと柔軟性を求めてのことである。Epiqsのapplyは、「シンボル解決」「引数リストの評価」「戻り値を返す方法の指定」は他のオペレータに任せている。

ASTをそのまま書きたい

これも「暗黙的なものを晒したい」という動機の一部である。Elixirのマクロの内部構造がイメージに近く、あれをなるべくマシな形で書きたい、とも言い換えられる。その代償として、syntax sugarなしでは、かなり冗長なソースコードになってしまった（下記参照）。

なぜRustで作ったのか

以前公開した言語はC++で作ったのだが、いざ出来上がったものを動かしていると、謎のメモリエラーが出てデバッグに難儀したが、そこで出会ったのがRustだった。だいたい以下の話。

  • 安全性
  • モダンなツールチェイン（モジュールシステムやパッケージマネージャ）
  • 構文面（パターンとか）
  • 型システム
  • 将来性

Rustで作る時のハマったポイント

所有権/ライフタイム

慣れるまではきつい。安全性のためなので学習コストが高いのは仕方ないかな、という印象。今回作ったインタプリタは内容としてはC++の時と大差なく、構造は単純でLL(1)パーサとAST書き換えを行なっているだけだが、所有権/ライフタイムの高い壁に阻まれまくった。ただし、Rustはどちらかというと「リソース管理に関わるコストをきちんと可視化して」ユーザーにコストを意識させる設計になっていると感じているし、それはEpiqsでやろうとした、「暗黙の要素をなるべく明示的に指定する」というポリシーとも近くて、要するに個人的には相性が良い言語である。

とにかくASTの書き替えができない

かなりの時間が吸われた。丁寧なエラーメッセージを読んで、ライフタイムを書き換え、参照と各種スマートポインタ（とその組み合わせ）を縦横無尽に試しながら、コストを最小限に抑えつつビルドを通すにはどうしたら良いのかを考えさせられた。まだまだ非効率な部分も多くて、誘惑に負けてcloneしてしまった部分もたくさんある。

とにかく思った通りのフローで処理を書かせてもらえない

所有権周り

変数のスコープを短く保つためには、適当に書くわけにはいかない。他の言語では見慣れない、ブロック囲みのスコープ限定をたくさんやることになる。

エラーハンドリング

方法がいくつかあるが、これも明確な基準がないと他の方法に切り替えるためのコストが結構かかった。try!が?になったのとか、どんどん書きやすくはなっているのは間違いないが、「なんとなく」が恐ろしいほど通用しない言語だということは骨身に染みて理解した。

でも良い言語

ある程度理解できれば、強い味方になってくれるので、次回からはそこまで悩まずにRustが書けると思う。基本的にはとても良い言語だと感じています。

実装面

言語実装Advent Calendarなので、できる限り実装面のことも書いてみる。

全体の構造

Lexer / Parser / Walker(not Evaluator) / Printerと分かれている。 Rustの練習を兼ねているので、全て手書きである。

Lexerをモジュール化してみた

Web開発界隈ではBabelやPostCSSなどを使って、JavaScriptやCSSに、部分的に構文を付け足すことができる。これと似たようなことを実現したいと考えて、Lexerの中で、Scannerという名前で構文ごとにstructを持つようにした。ただ実行効率を考えて、Babelなどのように外部から指定するのではなく、あくまでも内部でモジュール分解しただけである。静的ディスパッチにしたくて色々試したが、勉強不足からか結局動的にしか書けなかった。実質Lexerはイテレータのように作った（下記コードのtokenise()メソッドがいわゆるnext()にあたる）のだが、大変なのでIteratorトレイトの実装は見送った。ちなみにParserやWalkerに関しても、時間がなくてモジュール化は断念した。

    let scanners: &mut Vec<&Scanner> = &mut vec![
        &DelimiterScanner,
        &AlphabetScanner,
        &ZeroScanner,
        &IntegerScanner,
        &EOFScanner,
    ];

    let mut iter = text.bytes();
    let mut lexer = Lexer::new(&mut iter, scanners);
    lexer.tokenize();

ASTと記号表

ASTというかRustで木構造を書き換えることの難しさはこの後に書いてあるが、試行錯誤の末、ASTの中枢部はArenaと呼ばれるものを利用することになった。メインデータであるEpiqにNodeという中間物を挟んでVec<Node<Epiq>>になっている。困ったのは、記号表であるSymbolTableの中身だった。最初はVec<Vec<(String, &Epiq)>>にしたいと考えていたのだが、どうしてもこの中の参照に適切なilfetimeを与えられず、結局Vec<Vec<(String, usize)>>と、参照ではなくてindexを持つように変更することになった。あとは、これらをstructにまとめてRc<RefCell<_>>の形にして、各モジュールはASTからEpiqを貸し出してもらう、という形に落ち着いた。ただ、真面目に作ろうとすると中身の要素がどんどん増えっぱなしでゴミになったepiqを制御できていない問題をなんとかしなければならないだろう。

仕様

epiq

繰り返すが、コンスセルのことである。以下のように書く。pとqが要素である。

|: p q

実は最初の|はディスパッチャであり、次の:がこのepiqが単純なコンスセルであることを示すotagになっている。 他にも以下のようなepiqがある（現在の実装とは実は噛み合っていないが）。 ちなみに;はUnitであり、リストの末尾などに多用される。

その他のepiq一覧

  • |: pval qval linked-list(normal cons cell)
  • |# smbl valu bind
  • |. trgt kynm access
  • |\ envn body function piq block
  • |! func args apply
  • |% ; prms environment
  • |@ ; smbl resolve symbol
  • |> ; aexp exec eval

最後にevalがあるが、これはつまり、基本的にevalは全て明示的に指定する必要がある、ということでもある。

ディスパッチャ

epiqの引数は必ず2つあるが、いつも片方（大抵はqの方）しか指定しないepiqもある。このような場合は|の代わりに'を使う。 '> aexpと書けば、それは|> ; aexpと同じ意味である。

リスト

見た目は（カンマ区切りじゃないけど）Haskellと同じである。 [a b c]であり、これはepiqで書くと|: a |: b |:c ;である。a:b:c:;という中置記法があるのもHaskellっぽい。

たらい関数

恐る恐る作って回してみたが、ちゃんとある程度の時間で返ってきてよかった。tak(12, 6, 0)で70秒ほど。 なんの工夫も最適化もしていない木構造のインタプリタとしてはマシなのでは。Rustありがとう。 ただし、記述が冗長すぎて1行が長い。eval(|>)を逐一指定しているのは大きな一因だろう。 というわけで、syntax sugarを入れたものを2段階に分けて載せておく。

(defun tak (x y z)
  (if (<= x y)
    y
    (tak (tak (1- x) y z)
      (tak (1- y) z x)
      (tak (1- z) x y))))

(tak 12 6 0)

syntax sugarなし

|> ; ^> -1 [
   |# tak |\ |% ; [x y z] ^> -1 [
          |? |> ; |! |> ; |@ ; ltoreq [|> ; |@ ; x |> ; |@ ; y]
             |: |> ; |@ ; y
                |> ; |! |> ; |@ ; tak [
                     |> ; |! |> ; |@ ; tak [|> ; |! |> ; |@ ; decr [|> ; |@ ; x] |> ; |@ ; y |> ; |@ ; z]
                     |> ; |! |> ; |@ ; tak [|> ; |! |> ; |@ ; decr [|> ; |@ ; y] |> ; |@ ; z |> ; |@ ; x]
                     |> ; |! |> ; |@ ; tak [|> ; |! |> ; |@ ; decr [|> ; |@ ; z] |> ; |@ ; x |> ; |@ ; y]
                ]
   ]

   |! |> ; |@ ; tak [12 6 0]
]

tarai関数(with syntax sugar1, 実装中)

|>>>> [
   |# tak |\ '% [x y z] ^>> [
          |? '> |! '> @ltoreq ['> @x '> @y]
             |: '> @y
                '> |! '> @tak [
                   '> |! '> @tak ['> |! '> @decr ['> @x] '> @y '> @z]
                   '> |! '> @tak ['> |! '> @decr ['> @y] '> @z '> @x]
                   '> |! '> @tak ['> |! '> @decr ['> @z] '> @x '> @y]
                ]
   ]

   |! '> @tak [12 6 0]
]

tarai関数(with syntax sugar2, 草案)

^>>>> [
   |# tak |\ '% [x y z] ^>> [
          |? @ltoreq!, @x, @y
             |: @y
                @tak! [
                   @tak!, @decr! [@x], @y, @z
                   @tak!, @decr! [@y], @z, @x
                   @tak!, @decr! [@z], @x, @y
                ]
   ]

   @tak!, 12, 6, 0
]

下まで来ると、見た目はだいぶマシになる。まだ実装していないけど。 ちなみにfibonacciも作った。(fib 30)が15秒ぐらい。

(letrec 
  fib 
    (lambda n
      (if (eq n 0)
        0
        (if (eq n 1)
          1
          (+ (fib (- n 2)) (fib (- n 1))))))
  (fib 30))

fibonacci数(with syntax sugar2, 草案)

^>>>> [
   |# fib |\ '% [n] ^>> [
          |? @eq!, @n, 0
             |: 0
                |? @eq!, @n, 1
                   |: 1
                      @plus! [
                        @fib!, @minus! [@n 2]
                        @fib!, @minus! [@n 1]
                      ]
   ]

   @fib!, 30
]

振り返って気づくこと

Lisp系以外の言語構文の馴染みやすさ

前置記法から初めて、なんとか自分なりに見やすく、かつなるべくsyntax sugarというかマクロで実装できそうな形で置き換えることを考えた結果、他の言語の構文がなぜそうなっているのか、気づく点が多々あった。様々な言語(C系/ML系/Erlang/Prolog...)の独特な見た目も、構文を考えると「なるほどな」となることがあった。 「こうして色々な言語が産まれていっているのだな」「みんなある程度、問題意識は同じ部分に収束していくのだな」という気づきがあった。

テンプレート言語を作ったことになった

これが今回の一番の驚きだった。「evalを勝手にしない言語を作りたい」と思って作っていたら、ある日「これってエントリポイントがたくさんあるってことだよなあ」と気づく。木構造を部分的に書き換えることもできるわけで、それってつまりはWAFとかでよく見るテンプレート言語じゃないか、と思った次第。そういう用途で機能を追加してみようと思う。

さいごに

読んでくださってありがとうございます。 みなさま、メリークリスマス、そしてよいお年を！