最適化技法としてのマクロ

抽象としてのマクロ

高級なプログラミング言語の機能は__抽象化の道具__であると私は考えています。 抽象化というのは端的に言えばどう見せるかです。

たとえば、 C の関数をコンパイルするとスタック操作とジャンプになるのが一般的であることはよく知られていると思います。 しかし、プログラマにとってはそれはスタック操作とジャンプではなく関数に見えて関数のように考えられるということが重要なのです。

Scheme のマクロもまたそうです。

(let ((a 1)
      (b 2))
  (+ a b))

という記述は

((lambda(a b) (+ a b))
 1 2)

と同じ意味であることは仕様で保証されていますが、だからといって一時的な束縛をするために「後者で書くから let が無くてよい」という人はそう多くはないでしょう。 結果が同じでも、プログラマにとっては変数束縛のための構文に見えることが大事です。

平均を計算する

さて、 Scheme (またはその他の Lisp 系言語) におけるマクロはかなり重要な地位を持っています。 プログラミングに新しいパラダイム導入しようとすれば、新しい構文が欲しくなりますし、そのためにはマクロは活躍します。

一方で、マクロは何でも有りになりすぎるので__可能であれば手続きで書く__のが好ましいともされています。

ところが、与えられた数値の平均を計算するというのをある人がマクロで書いているのを先日見る機会がありました。 それを見た私は、それがマクロで書かなければならないようなものだろうかと疑問を持ったのですが……。

On Lisp にはマクロにした方が良い (こともある) 例として平均の計算が挙げられているということを教えてもらったので、あらためて読み返してみました。

最適化の道具としてのマクロ

マクロ展開が手続きに対して特徴的である点として、マクロ展開は実行前に行なわれるということが挙げられます。

実行前にプログラムの字面(じづら)からわかるような計算をマクロ展開時に出来るのであれば、実行をより高速にすることが出来るのです。

では、まずごく単純に平均を計算する手続きを定義するならこのようになります。

(define (average . args)
  (/ (apply + args)
     (length args)))

この手続きは高階手続きに渡すときを除いては、 (length args) の部分は実行前にわかっているはずです。 実行前にわかっていることは実行前に計算してしまうことで、実行速度をより高速に出来るようになります。

(define-syntax average
  (lambda(ctx)
    (syntax-case ctx ()
      ((_ args ...)
       #`(/ (+ a0 ...)
            #,(length (syntax->datum #'(a0 ...))))))))

このマクロを用いれば、たとえば (average 1 2 3) は (/ (+ 1 2 3) 3) に展開されるので、少しですが実行速度が速くなります。

そのような旨(むね)のことが On Lisp には書いてあります。 (On Lisp では Common Lisp を使っていますが。)

もっと速く

察しのよい人は、マクロ展開の段階でもっと畳み込めるのではないかということに気付いたかもしれません。

与えられたのが数値リテラルであればそのまま計算してしまえばよいのです。

(define-syntax average
   (lambda(ctx)
     (syntax-case ctx ()
       ((_ args ...)
        #'(letrec-syntax
              ((% (lambda(ctx2)
                    (syntax-case ctx2 ()
                      ((_ sum ())
                       #`(/ sum #,(+ (begin 'args 1) ...)))
                      ((_ sum (rt (... ...)))
                       #`(/ (+ sum rt (... ...))
                            #,(+ (begin 'args 1) ...)))
                      ((_ sum (rt (... ...)) r0 r1 (... ...))
                       (number? (syntax->datum #'r0))
                       #`(% #,(+ (syntax->datum #'r0)
                                 (syntax->datum #'sum))
                            (rt (... ...)) r1 (... ...)))
                      ((_ sum (rt (... ...)) r0 r1 (... ...))
                       #'(% sum (rt (... ...) r0) r1 (... ...)))))))
            (% 0 () args ...))))))

これを用いれば、たとえば (average 1 2 3) は 2 に展開されますし、 (average 1 a 3) なら (/ (+ 4 a) 3) に展開されます。

ここでは直接的に数値リテラルが与えられた場合のみを考慮していますが、もっと深くまで畳み込むことも可能です。

識別子構文

さて、上で定義した average マクロはあくまでマクロであって、高階関数に渡すことは出来ません。 Scheme には識別子構文 (または変数マクロ) と呼ばれるマクロがあるので、それを利用すれば高階関数に渡すことが可能なマクロを作ることも出来ます。

マクロというのは、リストの先頭に現れていくつかの引数を受け取るような形式がほとんどですが、識別子単独であたかも変数のようにふるまうマクロも定義できます。

それを用いて更に average マクロを改良するとこうなります。

(define (%average . args)
  (/ (apply + args)
     (length args)))

(define-syntax average
  (make-variable-transformer
   (lambda(ctx)
     (syntax-case ctx ()
       ((_ args ...)
        #'(letrec-syntax
              ((% (lambda(ctx2)
                    (syntax-case ctx2 ()
                      ((_ sum ())
                       #`(/ sum #,(+ (begin 'args 1) ...)))
                      ((_ sum (rt (... ...)))
                       #`(/ (+ sum rt (... ...))
                            #,(+ (begin 'args 1) ...)))
                      ((_ sum (rt (... ...)) r0 r1 (... ...))
                       (number? (syntax->datum #'r0))
                       #`(% #,(+ (syntax->datum #'r0)
                                 (syntax->datum #'sum))
                            (rt (... ...)) r1 (... ...)))
                      ((_ sum (rt (... ...)) r0 r1 (... ...))
                       #'(% sum (rt (... ...) r0) r1 (... ...)))))))
            (% 0 () args ...)))
       (_ #'%average)))))

たとえば (apply average '(1 2 3)) というように使用した場合には (apply %average '(1 2 3)) に展開され、要するに単純な手続き版に切り替えられるということです。 このとき、当然に事前の計算は何も行われませんが、もはや average マクロがマクロであることを意識する必要はなくなり、もしも average が手続きとして定義されていることをあてにした既存のコードがあったとしても問題なく差し替えることが出来ます。 しかし、可能な個所では少し最適化するので、既存のコードを壊さないように最適化する役に立つはずです。

意味ないかも？

とはいえ、高度な処理系では定数畳み込みの最適化くらいは入っていることも少なくないでしょう。 マクロ展開の段階で畳み込みをする必要があるかどうかは場合によります。

ただ、数値計算に限らず特定の形式の場合を特別扱いすることで高速化できる可能性があり、そのためにマクロを使うことも出来るということは示せたと思います。 処理速度をギリギリまでチューニングしたいようなときに既存のコードを変形させるよりは、マクロで内容を差し替える方がずっと安全です。