WAT (WebAssembly Text Format) と Common Lisp で遊ぶ ～Common LispにWATを書かせる編～

Lisp Advent Calendar Lisp Common Lisp WebAssembly

lisp Advent Calendar 2020 15日目の記事です。

下記の続きになります。

eshamster.hatenablog.com

引き続き下記のリポジトリで遊んでいきます。

github.com

WATを書くという意味ではまだ準備編で、薄めのラッパーをかけてCommon LispにWAT (WebAssembly Text Format) を書かせる話になります。下記が動機です。

  • もう少しCommon Lispに寄せた構文で書きたい
  • せっかくS式だから（原始的な）マクロを導入したい！
  • なんか楽しそう

また、下記あたりを参考にしています。

追記：今回の部分は下記のライブラリに切り離してみました。

github.com

目次

できたもの

例

今回の範囲はリポジトリのwa/ フォルダ以下にまとまっているものになります。それを使うと下記のような感じでWAT用の関数などが定義できます。とりあえず例として階乗関数 factorial を書いてみます。

若干型指定がうっとうしいですが、 defun.wat あたりはCommon Lisperからするとまあまあ見慣れた印象を受けるのではないでしょうか。

(defimport.wat log console.log (func ((i32))))

(defun.wat main () ()
  (let (((x i32) (i32.const 5)))
    (log (factorial x))))

;; Common Lispと異なり返り値を明示する必要があるので、
;; 引数: ((x i32)) の横に返り値: (i32) が並んでいます（i32は型名）
(defun.wat factorial ((x i32)) (i32)
  (let ((result i32))
    (if (i32.ge-u (i32.const 1) x)
        (set-local result (i32.const 1))
        (progn (i32.mul x
                        (factorial (i32.sub x (i32.const 1))))
               (set-local result)))
    (get-local result)))

(defexport.wat exported-func (func main))

そして、これをロードしてから (princ (generate-wat-module)) すると下記のようにWATが吐き出されます（見易いように手でフォーマット*1）。

(module
  (import "console" "log" (func $LOG (param i32)))

  (func $MAIN
    (local $X i32)
    (set_local $X (i32.const 5))
    (call $LOG (call $FACTORIAL (get_local $X)))) ; -> 120

  (func $FACTORIAL (param $X i32) (result i32)
    (local $RESULT i32)
    (if (i32.ge_u (i32.const 1) (get_local $X))
      (then
        (set_local $RESULT (i32.const 1)))
      (else
        (i32.mul (get_local $X)
                 (call $FACTORIAL (i32.sub (get_local $X) (i32.const 1))))
        (set_local $RESULT)))
    (get_local $RESULT))

  (export "exported_func" (func $MAIN)))

パッと見で全体的にゴツくなった印象を受けるかと思いますが、defun.wat 周りに注目していくつか特徴を拾ってみます。

  • 変数に自動で $ をつけてくれている
    • 例. x → $X
  • 関数呼び出しでは関数名に $ をつけた上で call も付与してくれている
    • 例. (factorial ...) → (call $FACTORIAL ...)
    • これはimportした log 関数についても同様
    • 一方、 i32.mul など組み込みの演算子には call はついていない
  • 関数や組み込み演算子の引数に変数を指定した場合、自動で get_local をつけてくれている
    • 例. (factorial x) → (call $FACTORIAL (get_local $X))
    • 個人的には get_local が乱舞していると読む時に非常に疲れるので割と大事
    • （型情報を使って頑張れば直値指定についている i32.const も取れそうですがサボってます...）
  • let（もどき）や if が良い感じに展開されている
    • これはマクロとして実現していたりします

マクロも書ける

上記の例で使っている if, let も地味にマクロとして定義しているのですが、同じ枠組みを使って自分で定義することもできます。

若干長いですが、まあまあ複雑なものも書ける例として、任意個数の i32 型の引数をとってかけ算ができる i32* マクロを書いてみます。WATで i32 型のかけ算に使う i32.mul 演算子は引数が2つで固定なので、これをネストしていく感じになります。マクロ処理は単にCommon Lisp内でのリスト処理なので、普通のマクロと同じ感覚で書けます。 gensym すらない原始的な代物ではありますが...

(defimport.wat log console.log (func ((i32))))

(defmacro.wat i32* (&rest numbers)
  (flet ((parse-number (number)
           (cond ((numberp number)
                  `(i32.const ,number))
                 ((atom number)
                  `(get-local ,number))
                 (t number))))
    (case (length numbers)
      ;; 引数が0個の場合は固定で1を返すようにする
      (0 `(i32.const 1))
      (t (labels ((rec (rest-numbers)
                       (let ((head (car rest-numbers))
                             (rest (cdr rest-numbers)))
                         (if rest
                             ;; i32.mul をネストする
                             `(i32.mul ,(parse-number head)
                                       ,(rec rest))
                             (parse-number head)))))
           (rec numbers))))))

(defun.wat main () ()
  (let (((x i32) (i32.const 4)))
    (log (i32*))           ; -> 1
    (log (i32* 1 2 3))     ; -> 6
    (log (i32* 1 2 3 x)))) ; -> 24

(defexport.wat exported-func (func main))

先程の例と同じく (princ (generate-wat-module)) すると下記のようなWATが吐き出されます（相変わらず手でフォーマット）。マクロ定義は展開時にのみ使う情報なのでWAT側には出てきません。main部分はマクロが展開されてだいぶ長くなりました。

(module
  (import "console" "log" (func $LOG (param i32)))

  (func $MAIN
    (local $X i32)
    (set_local $X (i32.const 4))
    (call $LOG (i32.const 1))
    (call $LOG (i32.mul (i32.const 1)
                        (i32.mul (i32.const 2)
                                 (i32.const 3))))
    (call $LOG (i32.mul (i32.const 1)
                        (i32.mul (i32.const 2)
                                 (i32.mul (i32.const 3)
                                          (get_local $X))))))

  (export "exported_func" (func $MAIN)))

中身

全部は見ないですが、defun.wat 周りをかいつまんで中身の実装を見ていきます。再掲ですが、リポジトリのwa/ フォルダ以下の内容になります。説明を見ると分かりますが何かと雑な感じです...

基本的なアイディア

先程見た変換時の特徴を若干整理して再掲します。

  • 変数に自動で $ をつけてくれている
  • 関数呼び出しでは関数名に $ をつけた上で call も付与してくれている
    • 一方、 i32.mul など組み込みの演算子には call はついていない
  • マクロが展開される
  • 関数や組み込み演算子の引数に変数を指定した場合、自動で get_local をつけてくれている

最後の項目は割と展開時の小手先の話なので置いておくと、何らかの手段で展開時に変数や関数やマクロを識別していることが分かります。その識別のための情報を格納する仕組みさえできてしまえば、後は割と地道にパースしていくだけという感じになります。結論から言うとCommon Lispのシンボルシステムを（かなり雑に）参考にしています。

ということでCommon Lispの方を少し見てみます。(defun hoge...) で関数を定義すると何が起きるかというと hoge というシンボルの関数領域 = symbol-function に関数の実体が入ります。正確な言い方ではないですが、この辺りに入っている情報を見て (hoge) というリスト表現が hoge 関数の呼び出しであるという判断もつくようになります*2。

CL-USER> (defun hoge () 100)
HOGE
CL-USER> (hoge)
100
CL-USER> (symbol-function 'hoge)
#<Compiled-function HOGE #x30200149C13F>
;; 返されているのは関数の実体なので funcall して呼ぶこともできる
CL-USER> (funcall (symbol-function 'hoge))
100

;; 余談: symbol-function で symbol-function の実体も取り出せる
CL-USER> (symbol-function 'symbol-function)
#<Compiled-function SYMBOL-FUNCTION #x30000016720F>
CL-USER> (funcall (symbol-function 'symbol-function) 'symbol-function)
#<Compiled-function SYMBOL-FUNCTION #x30000016720F>

これを踏まえて、大まかな実装方針としては下記のようになります。

  • ユーザ定義の関数定義を格納するシンボル様の構造体を用意する
  • 上記構造体の集合を格納するテーブルをグローバルに用意する
  • defun.wat や defmacro.wat で定義したものは上記のテーブルに格納していく

wat-symbol と wat-environment

wa/environment.lispに定義した wat-symbol, wat-environment について見ていきます。上で書いた大まかな実装方針との関係は次のようになります。

  • ユーザ定義の関数定義を格納するシンボル様の構造体を用意する → wat-symbol
  • 上記構造体の集合を格納するテーブルをグローバルに用意する → wat-environment

wat-symbol

まず wat-symbol 構造体の定義は下記のようになっています。

(defstruct wat-symbol
  symbol
  import         ; defimport.wat したものを入れる
  function       ; defun.wat したものを入れる
  macro-function ; defmacro.wat したものを入れる
  var            ; ローカルな変数を格納する
  )

symbol にはCommon Lispのシンボルを入れて識別子に利用します*3。

残りのフィールドはそのシンボルにひもづいているものが入ります。例えば、後で詳しく見る defun.wat をすると function フィールドに関数の定義がセットされます。セット時は下記のように defsetf を定義しているので、 (setf (wsymbol-function wsymbol) 値) のようにセットできます。定義を見て分かるように、現状は複数のフィールドに同時に値が入らない形になっています。

(defun set-function-empty (wsymbol)
  (when (wat-symbol-function wsymbol)
    (warn "~A has been defined as WAT function"
          (wat-symbol-symbol wsymbol)))
  (setf (wat-symbol-function wsymbol) nil))

;; ～略～ 各フィールド用の set-XXX-empty 関数

(defun wsymbol-function (wsymbol)
  (wat-symbol-function wsymbol))

(defsetf wsymbol-function (wsymbol) (func)
  ;; 他のフィールドは全部クリアして function フィールドのみに値が入った状態にする
  `(progn (setf (wat-symbol-function ,wsymbol) ,func)
          (set-macro-function-empty ,wsymbol)
          (set-import-empty ,wsymbol)
          (set-var-empty ,wsymbol)
          ,wsymbol))
          
;; ～略～ 各フィールド用の getter (defun), setter (defsetf)

ここまで書いておいて何ですが、 wat-symbol にどのようなフィールドを持たせるべきか、どのような値をセットするべきかというところは正直十分に練れていません。例えば、現状は関数をインポートしてもメモリをインポートしても import フィールドに突っ込まれますが、プログラム上の扱いが異なるので適切に割り振る方が良い気がしています。現状パーサがそれほど賢くないので問題になっていないですが、もっと賢いこと（関数のシグネチャを見て何かしたいとか）をしようとしたときに問題になりそうです。

wat-environment

次に wat-environment ですが、これは現状どんな束縛が存在するかを表す構造体で、実体としては wat-symbol の集合を持っているだけです。なお、検索速度の都合上シンボルをキー、wat-symbol を値としたハッシュテーブルを持たせていますが、シンボルの情報は wat-symbol 自体にも含まれるので単なる wat-symbol のリストでも動作上は問題ありません。

(defstruct wat-environment
  (symbol-to-wat-symbols (make-hash-table)))

;; グローバルなwat-environmentの用意
(defvar *global-wat-env* (make-wat-environment))

この wat-environment から wat-symbol を取り出したり生成したりする最も基本的な関数が次の intern.wat になります。名前の通りintern関数を真似ていて、*global-wat-env* 内に識別子（シンボル）に対応する wat-symbol があればそれを返し、なければ生成 & *global-wat-env* に登録して生成したものを返します。

(defun intern.wat (sym)
  (let ((table (wat-environment-symbol-to-wat-symbols
                *global-wat-env*)))
    (multiple-value-bind (wsym found) (gethash sym table)
      (when found
        (return-from intern.wat wsym))
      (setf (gethash sym table)
            (make-wat-symbol :symbol sym)))))

先程見た wat-symbol に対する setf と合わせて見ると、例えば関数定義ですべきことは下記のような形になります。

(setf (wsymbol-function (intern.wat sym))
      値)

wat-environment の本質的な役目としては以上ぐらいで、あとは特定フィールドに値を持つ wat-symbol の（キーとなるシンボルの）一覧を取り出す wenv-xxx-symbols など補助的な関数が並びます（コードは略）。

defmacro.wat

定義系は関数定義の defun.wat とマクロ定義の defmacro.wat を見ていきますが、やっていることは意外とシンプルな後者のマクロの方から見ていきます。wa/defmacro.lisp が該当のファイルになります。

Lisp におけるマクロは結局のところ、引数を受け取って（式として評価可能な）リストを返すだけの関数に過ぎないので、プログラムがリストとして表されるS式の世界に導入するのは簡単です（なんの安全性もない原始的なものであればという話ですが）。マクロを定義する defmacro.wat とマクロを展開する macroexpand(-1).wat について見ていきます。

まずは defmacro.wat です。

(defmacro defmacro.wat (name lambda-list &body body)
  (with-gensyms (params env)
    `(progn (setf (wsymbol-macro-function (intern.wat ',name))
                  (lambda (,params ,env)
                    ;; ※env = wat-environment は渡す方法・使う方法を何も考えていないので、
                    ;;   現状Common Lispのマクロに合わせて受け取れるようにだけはしている状態です
                    (declare (ignorable ,env))
                    (destructuring-bind ,lambda-list (cdr ,params)
                      ,@body)))
            ;; エディタ上でマクロ展開結果を簡単に見られるようにCommon Lispのマクロも定義しておく。
            ;; CLパッケージのものを書き換えると怒られるので名前の後ろに "%" をつけて雑に避けています。
            (defmacro ,(symbolicate name "%") ,lambda-list ,@body))))

wat-environment の項で見たように (setf (wsymbol-macro-function (intern.wat ',name)) 値) のイディオムを使って wat-symbol に関数を登録しています。登録している関数については下記の例で考えてみます。

(defmacro.wat hoge-macro (a b)
  `(i32.add (i32.const ,a) (i32.const ,b)

これを利用するときは (hoge-macro 1 2) のように書きますが、このリスト自体が第1引数の params として渡ります。リストの先頭は不要なので残りの (1 2) を (destructuring-bind (a b) '(1 2)) ...) して変数 a, b に束縛します。あとは body 部でこれを利用するだけです。env はCommon Lispではlexical environmentを渡すために利用しますが、特に考えてないので置いておきます。

次に定義に従ってマクロを展開する macroexpand(-1).wat です。上記の例で言えば (macroexpand.wat '(hoge-macro 1 2)) とすると (i32.add (i32.const 1) (i32.const 2)) を返す関数です。

最初に補助関数として、渡されたformがマクロとして展開可能か、可能であれば登録された展開関数を返す macro-function-if-expandable を作ります。これはformの先頭のシンボルを元に intern.wat して wat-symbol を取り出し、その macro-function フィールドに値があるかで判別ができます。

(defun macro-function-if-expandable (form env)
  (when (atom form)
    (return-from macro-function-if-expandable nil))
  (let ((*global-wat-env* env))
    (let ((wsym (intern.wat (car form))))
      (wsymbol-macro-function wsym))))

この macro-function-if-expandable を呼んでマクロ展開関数が返ってきたらそれにformを渡して展開結果を返す、そうでなければそのままformを返す、とすれば macroexpand-1 のでき上がりです。 macroexpand は同じことを再帰的にやるだけです。これは後で見る body-parser の中でマクロを展開するのに利用します。

(defun macroexpand-1.wat (form &optional (env *global-wat-env*))
  (let ((mf (macro-function-if-expandable form env)))
    (if mf
        (funcall mf form env)
        form)))
 
(defun macroexpand.wat (form &optional (env *global-wat-env*))
  (labels ((rec (form)
             (let ((mf (macro-function-if-expandable form env)))
               (if mf
                   (rec (funcall mf form env))
                   form))))
    (rec form)))

defun.wat

関数を定義する defun.wat を見ていきます。該当のファイルはwa/defun.watになります。

defun.wat マクロの定義は次の通りです。

(defmacro defun.wat (name args result &body body)
  `(progn (setf (wsymbol-function (intern.wat ',name))
                (lambda ()
                  ;; generate-defun については後述
                  (generate-defun ',name ',args ',result ',body)))
          ;; 関数ジャンプしたりシグネチャをエディタに表示させたいので、
          ;; 空のCommon Lisp関数を定義しておく（CLパッケージのシンボルを除く）
          ,(unless (eq (symbol-package name)
                       (find-package "CL"))
             (defun-empty% name args))))

先程の defmacro.wat にもあった (setf (wsymbol-function (intern.wat sym)) 値) のイディオムが出てきます。ここで値として登録しているのは、呼び出すとWATとしてprint可能なリストを吐き出す関数です。リストそのものを登録しないのは、「マクロは純粋に関数的であるべき（引数以外に結果が左右されてはならない）」という原則を守るためです。というのは、defun.wat のbody部のパース処理はグローバルな *global-wat-env* に依存しているため、「純粋に関数的」ではないためです。実際的な問題としては、defun.wat の順序によってパース結果が変わってしまうという問題が起こります。

登録した関数の中で呼んでいる generate-defun は次の形になっています。

(defun generate-defun (name args result body)
  (multiple-value-bind (parsed-typeuse vars)
      (parse-typeuse (list args result))
    `(|func|
      ,(parse-arg-name name)
      ,@parsed-typeuse
      ,@(parse-body body vars))))
  • parse-arg-name: 受け取ったシンボルに $ プレフィックスをつけているだけです
    • 例. hoge → $hoge
    • 名前がよろしくない...
  • parse-typeuse: 引数と返り値のパースを行います
    • 例. ( ((a i32) (b i32)) (i32) ) → ((param a i32) (param b i32) (result i32))
      • param や result を一々書くのがうっとうしいなと思ったので分けて書く形にしてみました
    • 定義はwa/type.lispにあります
    • "typeuse" という名称はWATの仕様から取っています
  • parse-body: これは次節で詳しく見ますが、名前の通りbody部をパースします

短いものなので、ついでに空のCommon Lisp関数定義に利用している defun-empty% も載せておきます。

(defun defun-empty% (name args)
  ;; defun.wat の引数は ((a i32) (b i32)) の様に型情報がついているので、変数名だけ取り出す
  (let ((args-var (mapcar #'car args)))
    `(defun ,name ,args-var
       (declare (ignore ,@args-var)))))

body-parser

defun.wat で利用していた body-parser について見ていきます。ここまで来ればもう渡されたリストを地道にパースしていくだけです（と言えるのがS式の良い所ですね）。

ファイルはwa/body-parser.lispになります。

関数引数の束縛

parse-body の全体は下記のようになっています。

(defun parse-body (body args)
  (let ((*org-global-wat-env* *global-wat-env*)
        (*global-wat-env* (clone-wenvironment)))
    (dolist (arg args)
      (setf (wsymbol-var (intern.wat arg)) t))
    (flatten-progn-all
     (parse-form body))))

ここではまず、関数引数の束縛、すなわちbody部分をパースする中で関数自体の引数をローカル変数として認識できるようにします。次の2ステップで実現します。

  1. グローバルな wat-environment を保管する *global-wat-env* に自身のクローンを束縛する
  2. *global-wat-env* に (setf (wsymbol-var (intern.wat arg)) t) で各引数シンボルに対応する wat-symbol の var フィールドを設定する
    • ステップ1によりオリジナルの wat-environment には影響しない

要するに、該当の関数内だけで通用するローカルな wat-environment を構成しています。Common Lispで似たものはlexical environmentになりそうですが、こちらはlexical environment → global environmentの順で束縛を探す仕様です。つまりは同一シンボル（名）の隠蔽ができます。一方こちらはグローバルな wat-environment のクローンにそのまま値を突っ込んでいるのでそうした隠蔽ができません*4。そもそもWAT上で変数名が衝突するとエラーになるはずなので、まあそのぐらいの雑な対応で良いかという感じです（もちろんパーサで頑張れば擬似的に回避できるはずですが...*5）。

parse-form: パース処理の入口

さて、parse-body の残りの部分の (flatten-progn-all (parse-form body)) ですが、flatten-progn-all は最後に見るとして、パースの本処理である parse-form の方を見ていきます。

(defun parse-form (form)
  (cond ((atom form)
         (parse-atom form))
        ((special-form-p form)
         (parse-special-form form))
        ((built-in-func-form-p form)
         (parse-built-in-func-form form))
        ((macro-form-p form)
         (parse-macro-form form))
        ((function-call-form-p form)
         (parse-function-call-form form))
        (t (mapcar (lambda (unit)
                     (parse-form unit))
                   form))))

見ての通り、この関数自体はパース処理を何もしておらず、formの種類に応じて適切なパース関数に投げるだけの人です。投げた先でも困ったら取りあえずこの parse-form に投げるというように窓口的な関数です。以下で各パース関数を順に見ていきます。

※解説しやすい形で順序は適当に前後します（例えば、スペシャルフォームは関数でもマクロでもないもの、という感じなので parse-special-form は後ろの方で見ます）

parse-atom: atom（=リストでないもの）のパース

atom（=リストでないもの）をパースする parse-atom は次のようになります。

(defun parse-atom (atom)
  (if (var-p atom)
      (parse-arg-name atom)
      atom))

(defun var-p (sym)
  (some (lambda (syms)
          (find sym syms))
        (list (wenv-var-symbols)
              (wenv-function-symbols)
              (wenv-import-symbols))))

wat-symbol として登録されたシンボルであれば $ をプレフィックスにつける（例. hoge → $hoge）、そうでなければそのまま返すぐらいの仕事です。var-p がだいぶ大雑把なので (wenv-var-symbols) だけを見るようにしたいところですが、現状 parse-atom を雑に使っている影響があり、そこからのリファクタ案件です...。

parse-built-in-func-form: 組み込み関数のパース

組み込み関数をパースする parse-built-in-func-form は次のようになります。

(defun parse-built-in-func-form (form)
  `(,(convert-built-in-func (car form))
    ,@(mapcar (lambda (elem)
                (parse-call-arg elem))
              (cdr form))))

(defun parse-call-arg (arg)
  ;; ※これは後述の parse-func-call-form でも共通に使う
  (if (and (atom arg)
           (var-p arg))
      (parse-form `(get-local ,arg))
      (parse-form arg)))

parse-built-in-func-form について、まずはどのようなパースをしているのか例を見ます。

;; ※ "x" は関数の引数またはローカルな変数とする
(parse-build-in-func-form '(i32.add x (i32.const 1)))
-> (|i32.add| (|get_local| $x) (|i32.const| 1))

細かい部分の説明は省略しますが、

  • i32.add は convert-built-in-func によって |i32.add| になる
  • x, (i32.const 1) はそれぞれ parse-call-arg でパースする
    • x の場合は get-local をくっつけた (get-local x) をパースした結果、(|get_local| $x) になる
    • (i32.const 1) はそのままパースした結果 (|i32.const| 1) になる

といった感じになります。記事冒頭の例で示した「関数や組み込み演算子の引数に変数を指定した場合、自動で get_local をつけてくれている」はここでやっている訳です。

フォームの判別を行う built-in-func-form-p は次のような形で、wa/built-in-funcで定義している built-in-func-p を呼ぶだけです（組み込み関数は一通りハッシュテーブルに突っ込んでいるので、そこに入っているかを確認する程度の処理）。

(defun built-in-func-form-p (form)
  (built-in-func-p (car form)))

parse-function-call-form: 関数呼び出し処理のパース

関数呼び出し処理をパースする parse-function-call-form は次のようになります。

(defun parse-function-call-form (form)
  (destructuring-bind (func &rest args) form
    `(|call| ,(parse-atom func)
             ,@(mapcar (lambda (arg)
                         (parse-call-arg arg))
                       args))))

大体前項の parse-built-in-func と似たような感じですが、こちらも例を見てみます。

;; ※ "hoge" は関数、"x" は関数の引数またはローカルな変数とする
(parse-build-in-func-form '(hoge x (i32.const 1)))
-> (|call| $hoge (|get_local| $x) (|i32.const| 1))

parse-built-in-func と異なる部分についてだけ見ると、

となります。こうした違いがあるためパース関数を分けています。一方で、引数の処理についてはどちらも共通しています。

フォームの判別を行う function-call-form-p は次のようになります。

(defun function-call-form-p (form)
  (let ((sym (car form)))
    (some (lambda (syms)
            (find sym syms))
          (list (wenv-function-symbols)
                (wenv-import-symbols)))))

リスト先頭のシンボルに対応する wat-symbol の function または import フィールドに値が入っているかを調べています。前述のようにインポートしたものを区別せずに import に突っ込んでいる（関数のインポートの場合もある）ので、両方見る必要が出てきています...。 function フィールドの方を見るだけで良いようにリファクタリングすべき案件です。

parse-macro-form: マクロフォームのパース

マクロフォームをパースする parse-macro-form は次のようになります。

(defun parse-macro-form (form)
  (parse-form (macroexpand.wat form *org-global-wat-env*)))

先程見た macroexpand.wat を呼び出すだけです。第2引数としてはローカルな束縛が渡らないように、地味に parse-body で保存したグローバルな wat-environment を渡すようにしていますが、そもそも現状渡した env を利用していないので一応程度です。

フォームの判別を行う macro-form-p は次のようになります。リスト先頭のシンボルに対応する wat-symbol の macro-function フィールドに値が入っているかを調べるだけです。

(defun macro-form-p (form)
  (wsymbol-macro-function (intern.wat (car form))))

parse-special-form: スペシャルフォームのパース

スペシャルフォームをパースする specifal-form-p は長めなので抜粋して見ていきます。

(defun parse-special-form (form)
  (ecase (car form)
    (progn `(progn ,@(mapcar (lambda (unit)
                               (parse-form unit))
                             (cdr form))))
    (local (destructuring-bind (var type) (cdr form)
             (setf (wsymbol-var (intern.wat var)) t)
             `(|local| ,(parse-atom var)
                       ,(convert-type type))))
    ;; ～略～
    (set-local (parse-1-arg-special-form '|set_local| (cdr form)))
    ;; ～略～
    ))

(defun parse-1-arg-special-form (head args)
  `(,head ,(parse-form (car args))
          ,@(mapcar (lambda (unit)
                      (parse-call-arg unit))
                    (cdr args))))

progn はCommon Lispのそれと似たようなもので、cdr 以降の要素をそれぞれ parse-form した上で progn で包み直します。progn は一通りパースが終わるまでは残したままにしますが、WATとしてはゴミなので後から flatten-progn-all で取り除きます。

local は (local x i32) のような形でローカル変数を定義するための構文です。(setf (wsymbol-var (intern.wat var)) t) のようにして、環境に変数を登録しているのが特徴です。このように環境をいじることは関数やマクロとしては実現できないので、スペシャルフォームとして実現する必要があります。

set-local は (set-local x y) のような形でローカル変数に値をセットする構文です。パース後の形は (|set_local| $X (|get_local| $Y)) のようになりますが、関数のパースと比べると第1引数を特別扱いしている = |get_local| をつけていません。こうした特別扱いも関数やマクロとしてはやはり実現できません。

フォームの判別を行う special-form-p は単に並べたスペシャルフォームを表すシンボルに一致するかを見るだけです。

(defun special-form-p (form)
  (case (car form)
    ((progn local block loop get-local set-local get-global set-global br br-if)
     t)
    (t nil)))

flatten-progn-all

最後に (flatten-progn-all (parse-body body)) としてパース結果に対して呼んでいた flatten-progn-all です。

(defun flatten-progn-all (body)
  (labels ((progn-p (target)
             (and (listp target)
                  (eq (car target) 'progn)))
           (rec (rest)
             (cond ((atom rest)
                    rest)
                   (t (mapcan (lambda (unit)
                                (if (progn-p unit)
                                    (rec (cdr unit))
                                    (list (rec unit))))
                              rest)))))
    (rec body)))

これは、例えば ((progn 1 2) 3 ((progn 4 (progn 5)))) というリストが渡されたら (1 2 3 (4 5)) のように progn 部分をフラット化して返す関数です。これは主に、複数の式を並べて返すようなマクロを実現するために導入したものです。単純にリストに並べて返してもWATとしては余計なカッコが残ってしまうので、progn から始まるリストは親リストにくっつける目印に使うことにしました。

WATの書き出し

defun.wat の実装を振り返ると、単にWATとしてprint可能なリストを出力するための関数を登録していただけでした。ということで、実際にそれらをまとめて呼び出して出力する人が必要になります。

それがwa/module.lispの generate-wat-module です。

(defun generate-wat-module% ()
  `(|module|
    ,@(mapcar #'funcall (wenv-import-body-generators))
    ,@(mapcar #'funcall (wenv-function-body-generators))
    ,@(mapcar #'funcall (get-export-body-generators))))

(defun generate-wat-module ()
  (let ((str-list (clone-list-with-modification
                   (generate-wat-module%)
                   (lambda (elem)
                     (typecase elem
                       (symbol (symbol-name elem))
                       (string (format nil "~S" elem))
                       (t elem))))))
    str-list))

解説は省略していましたが defimport.wat, defexport.wat も関数を登録しているので、合わせて generate-wat-module% で呼び出して、頭に |module| をくっつけて結合します。詳細略ですが、 generate-wat-module はそれを呼び出した後、princ 関数でうまくWATとして解釈可能な文字列が出力されるように細かい調整をしています。

ということで、(princ (generate-wat-module)) の結果をファイルに出力すれば、1つのmoduleを定義したWATファイルが手に入るようになりました。

いくつかのデフォルトマクロ

WATを吐き出すパーサとしては以上ですが、条件分岐系でいくつかデフォルトのマクロを提供しているのでザックリ見てみます。ファイルはwa/default-macor.lispになります。

if

WATのif構文は (if 条件式 (then 複数の式) (else 複数の式)) という形式ですが、Common Lisp風に (if 条件式 then式 else式) で書けるようにします。

(defmacro.wat if (test-form then-form &optional else-form)
  `(|if| ,test-form
         ,@(if else-form
               `((|then| ,then-form)
                 (|else| ,else-form))
               `((|then| ,then-form)))))

then式、else式に複数の式を並べたい場合は、Common Lisp と同様に progn で囲います: (if (progn 複数の式) (progn 複数の式))

when/unless

if分岐のthenの部分だけ欲しい、elseの部分だけ欲しいということは割りとあるので、Common Lisp同様に when, unless をそれぞれ用意します。先程の if の上に乗っけるだけですね。

(defmacro.wat when (test-form &body form)
  `(if ,test-form
       (progn ,@form)))

(defmacro.wat unless (test-form &body form)
  `(if ,test-form
       (progn)
       (progn ,@form)))

cond

WATのif構文には、いわゆるelse ifにあたるものがないので、例えば分岐が3つ欲しい場合は下記のように書くことになります。

(if 条件1
    then式
    (if 条件2
        then式
        else式))

うっとうしいので、Common Lispの cond を真似て次のように書けるようにします。

(cond (条件1 複数の式)
      (条件2 複数の式)
      (t 複数の式))

実装は次の通りです。

(defmacro.wat cond (&rest clauses)
  (labels ((rec (rest-clauses)
             (unless rest-clauses
               (return-from rec))
             (let* ((clause (car rest-clauses))
                    (test-form (car clause))
                    (form (cdr clause)))
               (cond ((eq test-form 't)
                      `(progn ,@form))
                     ((cdr rest-clauses)
                      `(if ,test-form
                           (progn ,@form)
                           ,(rec (cdr rest-clauses))))
                     (t
                      `(if ,test-form
                           (progn ,@form)))))))
    (rec clauses)))

少々長いですが雰囲気だけ伝われば。1点だけ、条件式部分に t が来たときはelse部分だと思って以降は無視します。

こんな感じで欲しい構文をサクサク追加していけるのはマクロがあることの利点ですね。

今後

今後...といいつつ、特にWAT書いて何かしようという展望もないのでたぶんやらないやつです。

名前空間

wat-symbol の項の注釈でチラッと触れたのですが、現状シンボルのパッケージを無視しているので、関数名などの名前空間を分けることができません。単純な実現方法としては、パース時にパッケージ名をプレフィックスにつけてしまうというのがあるかなと思います。

複数module

現状 (generate-wat-module) で全ての定義済みの関数（など）をひとまとめにして1つの大きなmoduleにします。複数のmoduleからなるものを書きたい場合はそれでは困るのでどうにかする必要があります。深くは考えていないですが、3年前（そんな前だと...）のLisp Advent Calendar記事「Parenscript上でシンボルのインポートやエクスポートを模倣する」でやったように、起点となるパッケージから依存関係を調べて1つのmoduleにまとめるような処理が必要になりそうです。

ちゃんとしたlet

記事冒頭の例ではletっぽい何かを使っていますが、wa/default-macro.lispでデフォルトのマクロとしてそれっぽく実装しただけのもので、下記の制限があるもどきに過ぎません。

  1. 関数冒頭にしか置くことができない
    • これは中で利用しているWATのローカル変数定義の local 構文が関数冒頭にしか置けないことから来る制限です
  2. （1つ目制限から自明ですが）スコープは関数全体になります
    • 派生する話として、Common Lispの let は複数の変数を定義する場合、初期化で他の変数の値を参照することができません。が、letもどきの方はそうしたスコープの分離ができていません

これを解消するには下記のような修正が必要そうです。

  1. パース時、local はすぐに書き出すのではなく、いったん溜めておいて一通りパースしてから関数冒頭にまとめる
  2. 今は変数は単純に x → $x のように固定のプレフィックスをつけるだけだが、例えば見た目のスコープに合わせてグローバルな連番をつける（x → $x-999）などできるようにする
    • これをやるためには、letをマクロとしてではなくスペシャルフォームとして定義する必要が出てきます

前述の名前空間、複数moduleの話に比べるとまだやっておきたい気分はあるところです。

次回

今回色々書いたような気分になりますが、実はまだ肝心のWATを1行も書いていません。ということで、次回は今回作った基盤の上で簡単なものを書いて遊んでみます。

eshamster.hatenablog.com

*1:念のため、WATは改行と空白を区別しないのでWASMにコンパイルする上ではフォーマットは不要です。あくまで見易さのためです

*2:実際は関数としての定義を持たないシンボルに symbol-function を適用するとエラーを返すので判定には使えません。fboundp関数を適用した結果がtrueでかつマクロでなくかつスペシャルフォームでないもの、が正確な判定方法になるようです。さらに言うと、これはglobal environmentで定義された関数についての話で、lexical envrionmentに定義されたものはこの限りではありません

*3:現状名前空間を持たないので、割り切るならシンボルのパッケージは無視してキーワードなり文字列なりを識別子に利用するのが正しいです。が、名前空間の実装に未練があってそのままになっています...。同名で別パッケージのシンボルを入れてしまうと二重定義になるというように、実際問題があるのでよろしくないのですが...

*4:また、そもそもlexical environmentに入っているものはシンボルでないので、その点でも不正確な模倣ではあります

*5:現状ではwat-symbolのvarフィールドにtを入れているので値の有無ぐらいしか分からないのですが、ここに変換後のシンボルを返す関数を入れるようにすると、スコープもどきを実現できるのだろうな...とうっすら考えてはいます