簡単なマクロ機構を実装していく。

背景

shift/resetが実装されたらやってみたいことの一つが@dico_lequeさんの発表「モナドをつくろう」をいろいろ試してみること。

モナドをつくろう from dico_leque

www.slideshare.net

スライド１９に出てくるreifyがマクロなので、それを再現できるようにしたい。

(define-syntax reify
  (syntax-rules ()
    ((_ expr)
     (reset (let ((v expr))
              (some v)))))

Schemeのマクロは強力でいろんな機構があるが、このマクロ自体は比較的簡単。

(reify expr)

を

(reset (let ((v expr))
         (some v))

に置換する、というもの。何故これがマクロなのかというと、ただの関数だと関数適用の前に引数が評価されるので、exprの中でshiftがあった場合reify内で使われているresetに捕捉されない問題が生じるため。

このreifyが再現できる最低限のマクロ機構と考えると

マクロ本体の中に出てくる仮引数と一致する変数を、実引数に当たる式と置換する
引数の式はマクロ適用時は評価せず、式のままマクロ本体に代入される
マクロはクロージャを持たず、マクロ定義時ではなく呼び出し時の変数環境を使って変数解決するダイナミックスコープ

という形で実装してみる。

ちなみに何故マクロだけダイナミックスコープにしているかというと、レキシカルスコープにするとマクロの引数となる式がマクロ定義時の変数環境で評価されることになってしまうからで、それを避けるような機能を実装するのも可能だが関数のレキシカルスコープに比べてかなり大変になる、というのが理由。

（ちなみに後々reifyを書いてみるときは、someは(fn [x] (cons "Some" x))で代用するつもり。代数的データ型がないので・・・）

使い方

fnと同じように、macroというキーワードで無名マクロを作成できるようにする。そのまま使うも変数に束縛して使うも自由：

  ((macro [x y] (do [y x]))
     (println "hello")
     (println "goodbye")))

(let [m (macro [x y] (do [y x]))]
  (m (println "hello")
     (println "goodbye")))

普通の引数と違ってマクロ適用の時点では引数が評価されないので、上記の例は二つとも"hello"の前に"goodbye"が出力される。

コード解説

前回とのコード差分：

Comparing v0.12...v0.13 · zehnpaard/kontlang · GitHub

Exp.tにMacroコンストラクタを追加（比較のためにFnも載せている）：

type t =
| Fn of string list * t
| Macro of string list * t

Val.tにも同様:

type t =
| Fn of string * string list * (string * t) list ref * Exp.t
| Macro of string list * Exp.t

Exp.MacroとVal.Macroがまったく同一なのがわかるかと思う。仮引数のリストと本体の式だけ。Fnの場合、Val.FnはExp.Fnの内容に加えてクロージャに当たる(string * t) list refが追加されているが、Macroの場合はダイナミックスコープにしてあるのでクロージャはなし。

次にマクロの根本である「部分式の置換」を行う関数substituteを持つ新しいMacroモジュールを定義：

let substitute e ss es =
  let env = List.combine ss es in
  let rec f = function
  | Exp.Int _ as x -> x
  | Exp.Str _ as x -> x
  | Exp.Macro(ss, e) -> Exp.Macro(ss, f e)
  | Exp.Var s as e -> (match List.assoc_opt s env with
    | Some e' -> e'
    | None -> e)
  | Exp.Call(e, es) -> Exp.Call(f e, List.map f es)
  | Exp.If(e1, e2, e3) -> Exp.If(f e1, f e2, f e3)
  | Exp.Cond(ees) ->
      Exp.Cond(List.map (fun (e1, e2) -> (f e1, f e2)) ees)
  | Exp.Let(ves, e2) ->
      Exp.Let(List.map (fun (v, e) -> (v, f e)) ves, f e2)
  | Exp.Lets(ves, e2) ->
      Exp.Lets(List.map (fun (v, e) -> (v, f e)) ves, f e2)
  | Exp.Fn(params, body) -> Exp.Fn(params, f body)
  | Exp.LetFn(fns, e) ->
      Exp.LetFn(List.map (fun (v, ps, e) -> (v, ps, f e)) fns, f e)
  | Exp.LetRec(fns, e) ->
      Exp.LetRec(List.map (fun (v, ps, e) -> (v, ps, f e)) fns, f e)
  | Exp.Do es -> Exp.Do (List.map f es)
in
f e

substitute関数内で（変数*式）リストのenvとそれを使って再帰的に部分式を置換していくf関数が定義されている。

マクロ変数環境であるenvはExecute.evalで使われているEnv.tとは型からして違うことに注意（Env.tは(string * Val.t) list list）。

fの実引数が変数Exp.Varだった場合、マクロ変数環境を調べて式が束縛されていれば完全に置換、そうでないなら変数のまま残す。

fの実引数がそれ以外の式だった場合、その式の部分式にfを再帰的に適用する。

これらを使う形でExecuteモジュールを変更する。まずはExecute.eval：

let eval env cont = function
...
  | Exp.Macro(ss, e) -> ApplyCont(env, cont, Val.Macro(ss, e))

Exp.Macro式はそのままVal.Macro値に変換してから残りの継続に渡す。

Execute.apply_cont：

let apply_cont env cont v = match cont with
...
| Cont.Call(e::es as es', []) :: cont' -> (match v with
  | Val.Macro (ss, me) ->
      let paramcount = List.length ss in
      let argcount = List.length es' in
      if paramcount = argcount then
        Eval(env, cont', Macro.substitute me ss es')
      else failwith @@ Printf.sprintf "Macro called with incorrect number of args: expected %d received %d" paramcount argcount
  | _ -> Eval(env, Cont.Call(es, [v]) :: cont', e))

マクロの実行も関数と同じくCont.Call継続を使う。ただし、「引数の式が一つも評価されていない状態のCont.Call」ケースを場合分けに追加していて、ここでオペレータ部分がVal.Macroならマクロ呼び出し。別の値なら今までどおり引数の評価に移行する。

マクロ呼び出しでは：

仮引数と実引数の数が一致することを確認
それらとMacro.substituteを使ってマクロ本体の式を置換
その置換された式をCont.Callを外した残りの継続で評価

という流れとなる。

これでマクロも実装できた。

次回

次回は評価ステップごとにインタプリタの状態が見えるようにする。

Arantium Maestum

プログラミング、囲碁、読書の話題

めざそう言語処理系の沼　〜shift/resetへの旅〜　その１３マクロ

背景

使い方

コード解説

次回