プログラムを書くプログラム(を書く…)

2014-01-26
blog

Lispの文法は知ってるけど大きなプログラムは書いたことがなくて、また使っているイディオムも他の言語で書くときのような範囲でしか触っていない。On Lispによれば、「マクロはプログラムを書くプログラムだ」(Macros are programs that write programs)と言われる。なんかそういう、Lispならではということをしたい。

Lispでは、ペアの頭を返すcarや尻尾を返すcdrという基本的な関数があって、またそれらを組み合わせたcadarとかcddddrとかいう関数がある。こういうのを自動的に作り出してみよう。

古典的マクロを使って、

(define-macro (gen-cxxr cxxr)
`(define (,cxxr x)
,(let1 s (x->string cxxr)
(let loop ((i (- (string-length s) 2))
(acc 'x))
(if (>= i 1)
(case (string-ref s i)
((#\a) (loop (- i 1) (list 'car acc)))
((#\d) (loop (- i 1) (list 'cdr acc))))
acc)))))

これを使って

(gen-cxxr cadr)  ;=> (define (cadr x) (car (cdr x)))
(gen-cxxr cddr) ;=> (define (cddr x) (cdr (cdr x)))
(gen-cxxr caddr) ;=> (define (caddr x) (car (cdr (cdr x))))
(gen-cxxr cdddr) ;=> (define (cdddr x) (cdr (cdr (cdr x))))
...

と書けば、決まった法則で関数を生成できる。

これでもいいっちゃーいいんだけど、(gen-cxxr ...)とずらずら書くのがダルい。そこで複数のシンボルを定義するマクロを作ってやれば:

(define-macro (gen-cxxrs . cxxrs)
`(begin ,@(map (lambda (cxxr)
`(gen-cxxr ,cxxr))
cxxrs)))

(gen-cxxrs caar cadr) ;=> (begin (gen-cxxr caar) (gen-cxxr cadr))

ということができる。

ただ、機能的には他の言語でもできないこともなくて、例えばRubyで配列をペアに見立てて、carcdrというメソッドを定義しておいて:

class Array
def car
self[0]
end
def cdr
self[1]
end
end

gen_cxxrを:

# Ruby版A
def gen_cxxr(cxxr)
methods = cxxr[1..-2].each_char.map{|x| "c#{x}r".intern}.reverse
Array.class_eval do
define_method(cxxr) do
methods.inject(self) {|obj, method| obj.send(method)}
end
end
end

または:

# Ruby版B
def gen_cxxr(cxxr)
methods = cxxr[1..-2].each_char.map{|x| "c#{x}r"}.reverse
Array.class_eval do
eval <<EOD
def #{cxxr}
self.#{methods.join(".")}
end
EOD
end
end

みたいにすればできる。ただし動作は異なっている。Lispのマクロの場合には関数の生成はコンパイル時に行われて、実行時には通常の関数呼び出しと全く同じになる。

Ruby版Aは実行時にinject~sendによるメソッド呼び出しのオーバーヘッドが必要になっている。

Ruby版Bは、Rubyをコンパイルと実行の2段階に分けて考えるとLisp版と同じ動作だけど、明示的なevalが必要になっている。またメソッドの内容は文字列で構築しないといけないので、複雑な操作は難しい。

…なんか最初の目的とずれてるような気がするが、終わりです。