syntax-rulesズンドコキヨシ、またはマクロ展開時ズンドコキヨシ

Scala の型レベルでズンドコキヨシができるなら Scheme の syntax-rules マクロでも書けるだろう、ということで書いてみた。定式化は 型レベルズンドコキヨシ 2に倣い線型合同法を使った。詳しくはそちらを参照されたい。

Scheme の syntax-rules マクロは、伝統的な Lisp のマクロとは異なり、プログラムの変形にふつうの Lisp 関数が使えるわけではない¹。代わりに、 syntax-rules という、パターンマッチとテンプレート出力のための、マクロ定義 DSL を使う。これはこれで制限も多く、人によって好みは分かれるのだけれど、計算能力としてはチューリング完全なので、今回のように、自然数を表現してその上で線型合同法を書いたりすることもできる。

計算を表現する

Scheme のマクロは最外簡約・名前呼び出しの言語であり、内側の計算の結果を使って外側の計算を実行する……、といった、ふつうのプログラムによくある処理が素直に書けない。

よくある方法としては、継続渡しスタイル（Continuation Passing Style; CPS）でマクロを書き、実行順序を明示してやるというのが知られているが、読み書きにはそれなりに慣れが必要である。今回は syntax-rules マクロ上で CK 抽象機械（CK abstract machine）を表現し、その上で動作する値呼び出しの関数型言語を解釈実行する方法を取る。

CK 抽象機械を使ったマクロ（CK スタイルマクロ）の書き方については Applicative syntax-rules: macros that compose better を参照。以降で現れる ck マクロはリンク先にある定義を使う。

CK 抽象機械自体については、例えば Programming Languages and Lambda Calculi 等を参照。

CPS でのマクロの書き方については Systematic Macro programming を参照。

自然数を表現する

syntax-rules マクロでは、真偽値オブジェクト、数値オブジェクト、文字オブジェクト、文字列オブジェクト、識別子といった不可分な値、またそれらをリストまたはベクタにしたもの、さらにそれらをリストまたはベクタにしたもの……（R6RS Scheme の言葉で言うと syntactic data）が扱える。だが、ここでいう数値というのは、 syntax-rules マクロにとっては式の中に表れる何らかの値のひとつに過ぎず、それ以上詳細に立ち入ることはできない。例えば、 1 というオブジェクトは、実行時にはそこから別の数値を引いたり、別の数値と比較したり、と値の中身を見ることができる。しかし、マクロ展開時には単なる 1 という値であり、それ以上分解することはできず、せいぜい、自分自身と等しいかどうか調べることくらいしかできない。

そのため、 syntax-rules レベルで計算をしようとすると、何か他のもので数値を表現してやる必要がある。

今回は (1 2 3 4 5) のような、長さ n のリストが自然数 n を表すものとした（ただし、リストの中身に特に意味はない。 (1 2 3 4 5) のような表現は単に長さをわかりやすくするためのものである）。

こうして表現した自然数の足し算を以下のように定義する。 ck マクロのおかげで普通の関数とよく似た見た目で処理を書ける。

(define-syntax ck-add
  (syntax-rules (quote)
    ((_ s '() 'n)
     (ck s 'n))
    ((_ s '(_ . m) 'n)
     (ck s (ck-add 'm '(1 . n))))))

CK スタイルのマクロは、マクロ自体の引数に加えて第一引数として CK 機械のスタックを受け取る。マクロは引数に応じて計算を1ステップ進め、スタックと次の状態とを引数に ck マクロを呼び出す。引数に関する場合分けは syntax-rules のパターンマッチで表現する。また、値は quote をつけて表現する。

ck-add では (ck-add '() 'n) （0 + n）の場合は 'n を結果とし、 (ck-add '(_ . m) 'n) （(1 + m) + n）の場合はさらに (ck-add 'm '(1 . n)) （m + (1 + n)）を計算する（第一引数側が小さくなるので停止する）。

引き算と掛け算の場合も同様である。

(define-syntax ck-sub
  (syntax-rules (quote)
    ((_ s '() 'n)
     (ck s '()))
    ((_ s 'm '())
     (ck s 'm))
    ((_ s '(s1 . m) '(s2 . n))
     (ck s (ck-sub 'm 'n)))))

(define-syntax ck-mul
  (syntax-rules (quote)
    ((_ s '() '_)
     (ck s '()))
    ((_ s '(_ . m) 'n)
     (ck s (ck-add 'n (ck-mul 'm 'n))))))

今回は自然数だけを扱うので、 n > m の場合の m - n は 0 と定義した。

条件分岐は値呼び出しでは書けないので、 CK スタイルではなく継続渡しスタイルで書く。 (syn-nat< m n kt kf) は m < n であれば成功継続 kt を起動し、そうでなければ失敗継続 kf を起動する。

(define-syntax syn-nat<
  (syntax-rules ()
    ((_ _ () then else)
     else)
    ((_ () _ then else)
     then)
    ((_ (s1 . m) (s2 . n) then else)
     (syn-nat< m n then else))))

あとは、剰余を定義してやれば、線型合同法で次の値を求める処理が定義できる。 lcg = Linear congruential generators である。

(define-syntax ck-mod
  (syntax-rules (quote)
    ((_ s 'm '())
     (ck s 'm))
    ((_ s 'm 'n)
     (syn-nat< m n
               (ck s 'm)
               (ck s (ck-mod (ck-sub 'm 'n) 'n))))))

(define-syntax ck-lcg-next
  (syntax-rules (quote)
    ;; X_{n+1} = (A X_n + C) \pmod{M}
    ((_ s 'a 'xn 'c 'm)
     (ck s (ck-mod (ck-add (ck-mul 'a 'xn) 'c) 'm)))))

リストを表現する

リストは syntax-rules で何も考えずに扱える。ズンドコキヨシの途中状態をリストで持ち、最後に reverse したいので、そういう CK スタイルマクロを定義しておく。

(define-syntax ck-cons
  (syntax-rules (quote)
    ((_ s 'h 't)
     (ck s '(h . t)))))

(define-syntax ck-revappend
  (syntax-rules (quote)
    ((_ s '() 'ys)
     (ck s 'ys))
    ((_ s '(x . xs) 'ys)
     (ck s (ck-revappend 'xs (ck-cons 'x 'ys))))))

(define-syntax ck-reverse
  (syntax-rules (quote)
    ((_ s 'xs)
     (ck s (ck-revappend 'xs '())))))

ズンドコを表現する

ck-zundoko マクロは、線型合同法の前の状態とこれまでのズンドコのリストを受け取り、リストが「ズンズンズンズンドコ」というパターンで終わっていたら、「キ・ヨ・シ！」をリストの先頭に追加して reverse したものを返す。ズンドコは逆順のリストになっていることに注意。

そうでなければ、 ck-zundoko-next と ck-zundoko-next~ で、線型合同法の次の状態を求めて次のズンドコをリストに追加し、また ck-zundoko に戻る。

(define-syntax ck-zundoko
  (syntax-rules (quote)
    ((_ s 'xn '("ドコ" "ズン" "ズン" "ズン" "ズン" . rest))
     (ck s
         (ck-reverse
          (ck-cons '"キ・ヨ・シ！"
                   '("ドコ" "ズン" "ズン" "ズン" "ズン" . rest)))))
    ((_ s 'xn 'zs)
     (ck s (ck-zundoko-next 'xn 'zs)))))

(define-syntax ck-zundoko-next
  (syntax-rules (quote)
    ((_ s 'xn 'ys)
     (ck s (ck-zundoko-next~
            ;; X_{n+1} = (5 X_n + 3) \pmod{8}
            (ck-lcg-next '(1 2 3 4 5)
                         'xn
                         '(1 2 3)
                         '(1 2 3 4 5 6 7 8))
            'ys)))))

(define-syntax ck-zundoko-next~
  (syntax-rules (quote)
    ((_ s 'xn+1 'ys)
     (syn-nat< xn+1 (1 2 3 4)
               ;; 0, 1, 2, 3 のとき
               (ck s (ck-zundoko 'xn+1 '("ドコ" . ys)))
               ;; 4, 5, 6, 7 のとき
               (ck s (ck-zundoko 'xn+1 '("ズン" . ys)))))))

実行はこんな感じにする。

(define-syntax ck-quote
  (syntax-rules (quote)
    ((_ s 'x)
     (ck s ''x))))

(for-each (lambda (x)
            (display " ")
            (display x))
          (ck () (ck-quote (ck-zundoko '(1) '()))))
(newline)

次のような出力が得られる。

 ドコ ドコ ドコ ズン ズン ズン ズン ドコ キ・ヨ・シ！

実行してしまうとわかりにくいが、マクロ展開時に (ck ...) の部分が展開され、下のようなプログラムが実行されている。

(for-each (lambda (x)
            (display " ")
            (display x))
          ("ドコ" "ドコ" "ドコ"
           "ズン" "ズン" "ズン" "ズン" "ドコ" "キ・ヨ・シ！"))
(newline)

ck マクロの定義を含めた全体のソースコードは gist に置いてある。 Racket の Macro Stepper を使えばマクロ展開の様子を一段ずつ追うことができる。また、ポータブルに書いてあるので、 import 部分を調節すれば、だいたいの R5RS, R6RS, R7RS Scheme 処理系で動くと思う。

---

1. 今回の場合、任意のLisp関数が使えてしまうと、マクロ展開時に音を鳴らしたり、 eject をしたりということも簡単にできてしまうし、線型合同法を書いたくらいでは面白みがない。 ↩