2014/08/18

syntax-rulesの書き方のコツのようなもの(Scheme)

 Scheme(R5RS)のマクロであるsyntax-rulesは, Lispの伝統的なマクロとは書き方や雰囲気も全く違います. 伝統的なマクロがないSchemeは, どこか言語として(Lispとして), 物足りない感じがしました.  しかし, そんな私も最近は, 折にふれて, ちょっとした作業でsyntax-rulesマクロを使うようにしたところ, Hygenicマクロへの抵抗感が薄れてきました. 使い慣れたついでの, Hygenicマクロの書き方のコツのようなもののメモです.

再帰的な関数の書き方

 どこで読んだのか覚えていないのですが, 関数型言語でプログラムを書くコツは,if(cond)式について, 特殊なケースから順に書いていくことだそうです.
 例えば,  フィボナッチ数を計算する関数は, 再帰呼び出しを用いて書く場合,
(define (fib n)
    ... ...
という形で最初に関数名と引数の数とその値の型について考えます. ここでは, nは整数(integer)です.
 次に, 特殊なケースについて, n = 0の時と, n = 1について考えます.
(define (fib n)
  (cond
    ((= n 0) 1)
    ((= n 1) 1)
    ... ...
それぞれ以上のように書けることは, 明らかです. 関数型言語を覚えたての頃は, 任意のnのケースについて考えるのが大変なのですが, フィボナッチ数はその性質から, fib(n - 1)とfib(n - 2)の和だということを考えると, 残りのプログラムが書けて, 
(define (fib n)
  (cond
    ((= n 0) 1)
    ((= n 1) 1)
    (else (fib (- n 1)) (fib (- n 2)))))
という感じで, プログラムを書いていきます.
 これだと, nに負の値を与えられた場合が問題になるので, throw-exceptionに継続をバインドして, 次のように書いてもいいかもしれません.
(define (fib n)
  (cond
    ((< 0 n) (throw-exception "wrong argument"))
    ((= n 0) 1)
    ((= n 1) 1)
    (else (fib (- n 1)) (fib (- n 2)))))
 これは, 普段プログラミングを行うときに自然にやっていることですが, 関数型言語風の書き方を始めたばかりの頃は, 再帰呼び出しでの書き方が分からず, 混乱した時に, このアドバイスに従い, 整理して, 書いていました. この方法論は, かなり(私には)有用で, 大抵のケースで, このアドバイスが応用できました.
 上記は数値の例ですが, 例えば, リスト処理や文字列の処理でも同じような考え方でコードを書いたのを覚えています.

syntax-rulesマクロの書き方

 この方法論は, syntax-rulesマクロを書くときにも応用できます. マクロの引数が1つ与えられている場合について考えるのです.
 次のようなフォームを反転させるマクロを実装してみます. 例えば, (1 2 3 4 5 6)が与えられるとそれを反転した(6 5 4 3 2 1)が, S式として展開されるようなマクロです. 実用性はさておき, syntax-rulesの柔軟性を調べるためには十分だと思います.
 実行結果は次のようになります.
gosh> (macro-list-reverse (1 2 3 4 5 6))
*** ERROR: invalid application: (6 5 4 3 2 1)
Stack Trace:
_______________________________________
gosh> (macro-list-reverse (1 2 3 4 5 +))
15
 これは, Schemeにおけるreverse関数をパターンマッチにより実装するのとさほど変わりません. ところで, 一般に, reverse関数は, cons関数と再帰呼び出しのために, 2つ引数をとります.  (reverse (1 2 3) ()) → (reverse (2 3) (1)) → (reverse (3) (2 1)) → (reverse () (3 2 1)) というふうに末尾再帰を繰り返すので, 2つの引数を想定します.
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ () ())
     ... ...
 次に特殊なケースについて考えます. 1つ目の引数が空リストの場合です. 2つ目の引数には, 反転されたリストが入っているので, そのリストを返せばよく,
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ () ())
     ())
    ((_ () (xs ...))
     (xs ...))
     ... ...
と書けます. (xs ...)は, 何らかのリストを意味しています. これがそのまま, 展開した結果として返されます.
最後に, 一般的なケースについて考えると, 左の先頭を右の先頭へ移す処理なので, (x xs ...)と分解して, 左の(ys ...)に(x ys ...)と加えて, 次のように書けます.
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ () ())
     ())
    ((_ () (xs ...))
     (xs ...))
    ((_ (x) (xs ...))
     (x xs ...))
    ((_ (x xs ...) (ys ...))
     (macro-list-reverse (xs ...) (x ys ...)))))
 これで, 与えられた要素が反転するマクロができますが, 初期値の空リストが冗長なので, パターンマッチでそのケースについて追加します.
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ (xs ...))
     (macro-list-reverse (xs ...) ()))
    ((_ () ())
     ())
    ((_ () (xs ...))
     (xs ...))
    ((_ (x) (xs ...))
     (x xs ...))
    ((_ (x xs ...) (ys ...))
     (macro-list-reverse (xs ...) (x ys ...)))))
 というわけで, 最初のmacro-list-reverseが完成します.

 パターンマッチが分岐の役割を果たし, 再帰的展開が普通の関数における再帰呼び出しに相当するため, Schemeにおける関数と遜色ない程度の計算力を持ったマクロがかけるようです.

0 件のコメント :