2012/09/25

CPS変換の練習をしてみた

(define (foldr fun x args) (if (null? args) x (fun (car args) (foldr fun x (cdr args))))) を、CPS変換して末尾再帰にしようとした記録。

このページ なんでも継続 を参考にする。

foldr 自身より外側にある関数適用は fun であることを意識してやると、ちょっと簡単になった。

概形
(define (foldr/cps fun x args cont) (if (null? args) (cont x) ; something... ))
変換後に最も外側に来る関数は foldr/cps である(というかそれが目的)。
(define (foldr/cps fun x args cont) (if (null? args) (cont x) (foldr/cps fun x (cdr args) ; something... ))
最後に計算される(=最も外側の) fun に、内側の foldr の結果(res とする)を渡せば最終結果となる。
最終結果は外側の foldr の引数 cont に渡して(渡されて)終了となる。
; 最終的に(たぶん最後らへんに)実行されてほしい式 (cont (fun (car args) res))
最終的に内側の foldr/cps の第4引数(cont)が実行されることになるが、cont は手続きであるから、上の式を lambda で包む。
また、内側の foldr の計算結果(res)は、この lambda (内側の foldr から見た第4引数 cont)へ引数として渡されることに注意。
; 内側の foldr/cps の第4引数(cont) (lambda (res) (cont (fun (car args) res)))
合体!もうほとんどできてる。
(define (foldr/cps fun x args cont) (if (null? args) (cont x) (foldr/cps fun x (cdr args) (lambda (res) (cont (fun (car args) res))))))) ))
これで完成!
(define (foldr/cps fun x args cont) (if (null? args) (cont x) (foldr/cps fun x (cdr args) (let ((a (car args))) ; lambdaの中に(car args)を入れると計算が遅延されてしまう気がした (lambda (res) (cont (fun a res))))))) ))

ちょちょいと動かしてみたが、どうやら正しく動作してるっぽい。保証はできないけど。

結論。俺は説明が下手だ。あと、たぶんCPSの本質が掴めてない。

jdkのヘッダにパスが通ってなくてemergeが失敗した話。

media-video/aacskeys のビルドに失敗した。
原因はわかっていた。

src/aacskeys.h:8:17: 致命的エラー: jni.h: そのようなファイルやディレクトリはありません

調べたところ、jniとはJava Native Interfaceの略らしい。ということはjdk関連である。
さて、jdkのヘッダが無いとのことだが、ヘッダは確かに存在しており、
$JDK_HOME/include
にある($JDK_HOMEはユーザごとに異なる。rootではシステム全体の設定になっている)。
さて、これがmake時のINCLUDESとかgccの-Iオプションとかに入れられれば良いのだが、一筋縄にはいきそうにない。

今回は、gccが自動で読みにいく環境変数をいじる。
まず、システムのデフォルトのJava VMをJDKに変更する。(デフォルトの環境変数の設定を変更するため。後述)
# java-config -L でリストが出るので、左の番号を覚えておいて、たとえば

1) IcedTea JDK 7.2.2.1 [icedtea-7] 2) Sun JDK 1.6.0.33 [sun-jdk-1.6] *) Sun JRE 1.6.0.33 [sun-jre-bin-1.6]
となっているなら、2番のVMにしたいので # java-config -S 2 というふうにする。

で、gccがヘッダファイルを探しにいくパスは、Cなら C_INCLUDE_PATH 、C++なら CPLUS_INCLUDE_PATH である。
この両方にJDKのヘッダを追加したいが、あまり関係のないパッケージまで影響が及ぶようなところを弄りたくない。
そこで、portageには目的のパッケージのmergeのときだけ環境変数を変えられるような仕組みがあるので、それを利用する。

まず、 /etc/portage/package.env (無ければ作る)に

/etc/portage/package.env
media-video/aacskeys use-jdk-jni-headers

の1行を追加する。んで、 /etc/portage/env/use-jdk-jni-headers (新規ファイル)は

/etc/portage/env/use-jdk-jni-headers
C_INCLUDE_PATH="${JDK_HOME}/include:${JDK_HOME}/include/linux" CPLUS_INCLUDE_PATH="${JDK_HOME}/include:${JDK_HOME}/include/linux"

といった内容にする。
ここで、システムのVMがJDKでないとき(jreとか)は ${JDK_HOME}/include が存在しないので、パスの指定の意味がなくなってしまうことに注意。

これでmergeしなおすと、この場合なら media-video/aacskeys のビルドのときだけ jni.h がデフォルトで探索されるパスに含まれる。