この記事は traP Advent Calendar 2017 40日目 の記事です。
担当の Double_oxygeN です。
この記事は，終始問答形式で書かれています。ご了承ください。
はじめに
早速ですが，曲を作りました。
Q. これは？
Waltzです。3/4拍子を特徴とする舞曲です。日本語で円舞曲とも言います。
Q. 今回の紹介はこれ？
違います。
Q. なんで載せたのか？
今回ネタが薄くなりそうでしたので急遽作って載せました。聴きながらブログも読んでいただけると嬉しいです。そう，急遽作曲したといえば，今日はtraP2DTMを開催する日です。テーマだけでも是非考えて，Twitter:@traP2dtmにリプを送っていただきたいですね。
WaltZとは
Q. タイトルにもなっているが，WaltZとは何？
私が作ろうとしている新しいプログラミング言語の名前です。変換先がWebAssemblyであること，現在WebAssemblyにトランスパイルすることのできるC/C++やRust等の代替物(alternative)を作ることを目的としていることから，WとaltをとってWaltZという名前になっています。Zなんてただの飾りです。 両端が大文字なのは私のIDを模倣しています。
Q. WebAssemblyの記事は前にも書いたことあるようだが？
はい，新歓ブログリレー2017で私が紹介しました。
あたらしいWebAssemblyのはなし【新歓ブログリレー2017 9日目】
また，今回Clojureも使っているので，昨年のAdCとも関連があります。
Clojure, Elixir でプロセス間通信 〜TCP通信でBF & UDS通信でなんでも掲示板〜
Q. これで何ができるか？
理想としては，WaltZの文法でソースコードを作りコンパイラを通すと，WebAssemblyのテキスト形式になって出てきます。これをwat2wasm等でバイナリ形式に変換することで，WebAssemblyとして使うことができるようになります。
WebAssemblyの使い方については，上記ブログに書いてありますのでそちらも是非。
実装
Q. これはどうやって作られるか？
実装にはClojureを用いています。ライブラリとしてinstaparseという字句構文解析ライブラリを用いました。依存関係は(現状)以下の通りです(Leiningen)。
:dependencies [[org.clojure/clojure "1.8.0"]
[instaparse/instaparse "1.4.8"]
[rhizome/rhizome "0.2.9"]]
Q. instaparse？
言語を作るには，その言語を解釈するものが少なくとも必要です。字句解析・構文解析には一般的にCやC++のyacc/lex，JavaのANTLR4などが有名だと思います。私も最初これらのツールを使おうとしましたが，C++やJavaは言語経験が浅く使いこなせないのと，Cは高度なことをするには大変なので，どちらも断念しました。慣れたClojureでANTLR4を使う方法を調べていたら，たまたまinstaparseというものを見つけたので使うことにしました。
Q. instaparseは使いやすいのか？
個人的な感想ですが，他に試したツールに比べると随分使いやすいように感じます。例えば，字句や構文のルールを記述する部分は，様々な書き方が許容されます。次の4行は全て同じ文字列を受理するルールを表しています。
token = Epsilon | #"[Tt]he"? foo | "bar" "bar"*.
token : '' | #"[Tt]he"? foo | 'bar'+ ;
token := ε | [#'[Tt]he'] foo | "bar" {"bar"}
token ::= eps | (#'[Tt]he')?, foo | #'(bar)+'
他の良い点としては，左再帰，右再帰ともに問題なく通るところや，非決定的な構文を全て探索するところ，rhizomeライブラリと共に用いることで構文木を可視化できるところなどが挙げられます。
ダメな点として，空白や改行等を読み飛ばす処理がまだ試験段階であること，解析して返される構文木が若干読みにくいこと(パターンマッチがあれば少しは改善されそう？)などは実際に使ってみて実感しました。
Q. 現状どこまで実装が進んでいる？
var foo:Int <- 42
val bar:Float := 3.14159f
export val baz:Double := 1e-9
これ(test.w3z)を
$ lein run test.w3z
こうして
(module
(memory 1)
(table 1 anyfunc)
(global $foo (mut i32) i32.const 42)
(global $bar f32 f32.const 3.14159)
(global $baz (export "baz") f64 f64.const 1.0E-9))
こう(out.wat)なります。
コードは長いので一部だけお見せしますが，まずは文法をresourcesフォルダにあるファイルから読み込み，単純に解析する関数parse-naturalを作ります。
(ns waltz-compiler.parser
(:require [instaparse.core :as insta]
[clojure.java.io :as io]
[clojure.edn :as edn]))
(def waltz-parser
(insta/parser (io/resource "waltz-grammar.ebnf")))
(defn parse-natural
([s]
(insta/parse waltz-parser s))
([s start]
(insta/parse waltz-parser s :start start)))
文法ファイル(resources/waltz-grammar.ebnf)はこんな感じになっています。Scala-likeで作りましたが，代入には=を使いたくないというこだわりから，<-や:=を代わりに使っています。
module : (globalDecl | <WSBR>)* ;
<globalDecl> : <WS?> varDecl <WS?> <EOL>
| <WS?> valDecl <WS?> <EOL>
;
varDecl : 'var' <WS> varName <WS?> typeAnnotation <WS?> '<-' <WS?> expr
;
varName : Id ;
valDecl : ('export' <WS>)? 'val' <WS> varName <WS?> typeAnnotation <WS?> ':=' <WS?> expr
;
typeAnnotation : ':' <WS?> type ;
type : Id
;
expr : literal
;
literal : integerLiteral
| floatingPointLiteral
;
integerLiteral : (DecimalNumeral | HexadecimalNumeral) IntegerSignSuffix? IntegerSizeSuffix? ;
floatingPointLiteral : DecimalNumeral? '.' FractionalPart ExponentPart? FloatingPointSizeSuffix?
| DecimalNumeral ExponentPart FloatingPointSizeSuffix?
| DecimalNumeral FloatingPointSizeSuffix
;
<WS> : #'[ \t]+' ;
<BR> : #'[\r\n]+' ;
<WSBR> : #'[ \t\r\n]+' ;
<EOL> : ';' | BR ;
<NonZero> : #'[1-9]' ;
<Digit> : #'[0-9]' ;
<HexDigit> : #'[0-9a-fA-F]' ;
<Lower> : #'[a-z]' ;
<Upper> : #'[A-Z]' ;
<Alpha> : Lower | Upper ;
<AlNum> : Alpha | Digit ;
<IdSymbol> : #'[_$]' ;
DecimalNumeral : '0' | NonZero Digit* ;
HexadecimalNumeral : '0x' HexDigit+ ;
FractionalPart : Digit+ ;
<ExponentPart> : #'[eE]' #'[\+-]'? DecimalNumeral ;
<IntegerSignSuffix> : #'[uU]' ;
<IntegerSizeSuffix> : #'[yYsSiIlL]' ;
<FloatingPointSizeSuffix> : #'[fFdD]' ;
Id : (IdSymbol | Alpha) (IdSymbol | AlNum)* ;
parse-with-infoという関数で，より詳細な構文木を作ります。insta/add-line-and-column-info-to-metadataで，メタデータにその記号列を読んだ行と列の情報を付加し，デバッグをより容易にします。insta/transformで，木の先端の部分を先に処理してしまいます。
(defn parse-with-info
[& args]
(->> args
(apply parse-natural)
(insta/add-line-and-column-info-to-metadata (first args))
(insta/transform
{:Id read-Id
:DecimalNumeral read-DecimalNumeral
:HexadecimalNumeral read-HexadecimalNumeral
:FractionalPart read-FractionalPart
:integerLiteral read-integer-literal
:floatingPointLiteral read-floating-point-literal
:literal read-literal})))
そうしてできた構文木を，左から順に整理しつつ文字列に変換します。
(defn- module-to-wat [module]
(letfn [(memory-to-wat [memory] [(str "memory " memory)])
(table-to-wat [table] [(str "table " table " anyfunc")])
(expr-to-wat [exprs]
(->> exprs
(map (fn [expr] (str (:opcode expr) " " ((:converter expr) (:operand expr)))))
(clojure.string/join "\n")))
(global-vars-to-wat [global-vars]
(->> global-vars
(map (fn [x]
(let [wasm-type (:wasm-type (:type x))]
(parenthesize [(str "global "
\$ (:name x) " "
(when (:export x) (str "(export \"" (:name x) "\") "))
(if (:mutable x) (str "(mut " wasm-type ") ") (str wasm-type " "))
(if (= (:opcode (last (:start-expr x))) (str wasm-type ".const"))
(expr-to-wat (:start-expr x))
(str wasm-type ".const 0")))]))))
(apply concat)))]
(parenthesize
(concat
["module"]
(parenthesize (memory-to-wat (:memory module)))
(parenthesize (table-to-wat (:table module)))
(global-vars-to-wat (:global-vars module))))))
(defn compile-to-wat [tree]
(letfn [(process-tree [m token]
(case (first token)
:varDecl (let [variable (->> token rest (compile-var-decl m))]
(-> m
(update :global-vars conj variable)))
:valDecl (let [variable (->> token rest (compile-var-decl m))]
(-> m
(update :global-vars conj variable)))
m))]
(->> tree
rest
(reduce process-tree DEFAULT-MODULE)
module-to-wat
(clojure.string/join "\n")
println-str)))
肝心なところがお見せできていないのですが，フィーリングで補ってください。
これで，大域変数に定数を代入する処理については無事WebAssemblyに変換することができました。
Q. 今できている処理はこれだけ？
すみません。これだけです。本当は計算式を代入したり関数を定義したりしたかったのですが，AdCの前の課題やテストが予想以上に長引いてしまって，これ以上の進捗は産めませんでした(言い訳)。そしておそらく現在の実装方法では拡張性が低くなってしまいそうなので，作り直す可能性も大きいです。
Q. どこで詰まっている？
型の解決が現状最も難関です。私が型というものをあまり理解できていないということもありますし，こういう型のついた言語を処理するのが初めてということも一因です。
おわりに
なんとなくの思いつきでWaltZを作り始めたのですが，想像以上に難しいということがわかりました。今後勉強を重ねて，いつかは完成させたいと思いますが，先はまだまだ長そうです……。
参考リンク集
instaparse - GitHub
Semantics - WebAssembly
ここまで読んでいただきありがとうございました。明日のAdCはRLook_さん，MENTOSさんが担当です。お楽しみに。
