2016/12/15
parameterizeの面倒くさい話
(この記事はLisp Advent Calendar 2016の16日めの記事です)
あらかじめ言っておくと、今日のエントリはやたら長いし、
parameterizeの仕様の重箱の隅をつつくような、面倒くさい話である。
Scheme処理系の実装者でもなければ「細けぇことはいいんだよ!」で流したくなるかもしれない。
でも、Schemeの一機能の話ではなく、
ぱっと見で簡単に見える仕様でも隙無く実装するのが難しいことがあるよ、って話だと
読んでもらえれば。
なお、文中のコードは https://github.com/shirok/parameterize-pitfalls に置いてある。
parameterizeとは
レキシカルスコープを採用したSchemeにおいて、 ダイナミックスコープをライブラリレベルで実現する仕組み。 いくつかの処理系に昔からあったが、2003年に基本部分がSRFI:39で規格化され、 R7RSにも取り込まれた (ただし、R7RSの仕様はsrfi-39とは微妙に違う)。 基本的には、動的束縛のメカニズムをクロージャの中に隠すという発想だ。
Common Lispの以下のようなコードは:
(defvar *special* 1) (defun get-special () *special*) (let ((*special* 2)) (get-special)) ;=> 2 (get-special) ;=> 1
parameterizeを使ってこう書ける。
(define special (make-parameter 1)) ; [1] (define (get-special) (special)) ; [2] (parameterize ((special 2)) ; [3] (get-special)) ;=> 2 (get-special) ;=> 1
make-parameter は、束縛を包み込んだクロージャを返す[1]。
引数無しで呼べば、現在の動的環境での値が返る[2]。
マクロparameterizeによって、動的スコープで値を変えることができる[3]。
(make-parameterが返すものは単なるクロージャで良いのだが、
以下では説明のために「パラメータオブジェクト」と呼ぶ。)
単なる変数ではなくパラメータオブジェクトにしてあるのは、 実装に柔軟性を持たせるためだ。単なる変数でも、動的束縛マクロの中で グローバルな値を差し替えてやれば動的変数のように振る舞わせることは可能だが、 例えば後から拡張してスレッド安全にしたくなっても、打つ手がひどく限られてしまう。 パラメータオブジェクトとして扱っておけば後からいろいろやりようがある。
さて、これから、パラメータオブジェクトとparameterizeの実装を何通りか
見てゆくけれど、中にはバグのあるものが混ざっている。
Schemeに心得のある読者は、「……ほんとに?」が出てきたら、
バグの解説を見る前に、問題を見抜けるかどうかちょっと考えてみてほしい。
実装例1
最もストレートな実装は、パラメータオブジェクトPを0個または1個の引数を取る
クロージャにして、(P)と呼ばれたら現在の値を返し、
(P newval) のように呼ばれたら、newvalを新たなパラメータの値に
するとともに以前の値を返す、ということにするものだ。
SRFI:39もこの線で仕様化されている。
(define (make-parameter init)
(case-lambda
[() init] ; 引数なしの時は現在値を返す
[(newval)
(begin0 init ; 引数ありの時はそれを新たな現在値にして元の値を返す
(set! init newval))]))
(define-syntax parameterize
(syntax-rules ()
[(_ ((param val) ...) body ...)
(let* ([params (list param ...)] ;paramのリスト
[vals (list val ...)] ;valのリスト
[saves (map (^[p v] (p v)) params vals)]) ;入る前の値を保存 [1]
(dynamic-wind
(^[] #f)
(^[] body ...)
(^[] (for-each (^[p v] (p v)) params saves))))])) ;[2]
parameterizeに入ったら入る前のパラメータの値を保存し、
パラメータを指定された値に書き換える。
パラメータオブジェクトは引数つきで呼ばれると「新しい値の設定と、古い値の返却」を
同時に行うので、[1]の行だけで「各paramに対応するvalの値を設定すると
ともに、savesに以前の値を保存する、というアクションが起きる。
bodyの実行中にエラーが起きた時でも確実にparamの値が復元できるように、
dynamic-windを使って保存されていた値を再設定している[2]。
実行してみよう。
gosh> (define special (make-parameter 1))
special
gosh> (define (get-special) (special))
get-special
gosh> (parameterize ((special 2))
(get-special))
2
gosh> (get-special)
1
parameterizeの実行中に呼び出されたget-special
はその時点での動的束縛である2を返し、外側で呼ばれたget-specialは元の値を
返している。
うまくいっているようだ。
……ほんとに?
実装例1の問題
dynamic-windの呼び出しが非対称だからこれはわかりやすかったかも。
問題が出るのはたとえば次のコード。
gosh> (define cc #f)
cc
gosh> (parameterize ((special 3))
(call/cc (lambda (c) (set! cc c))) ;[1]
(get-special))
3
gosh> (cc #f)
1
parameterizeの本体で継続を捕捉し、
parameterizeから抜けた後でその継続を再起動している。
つまり、(cc #f)の呼び出しは[1]の時点に戻る(引数#fは
[1]の式の返り値になるけれどここでは捨てられるので、何でも良い。)
そこで再びget-specialを呼ぶけれど、ここは再びparameterizeの
有効期間の中なので、動的束縛された3が返されなければならない。
(「一旦抜けてしまったら戻さない」という仕様を別途考えることもできる。 けれども、継続というのは「その時点の動的環境を捕まえるもの」なので、 パラメータを動的束縛の仕組みとするなら、値が戻るのが正しい。 例えば継続によるコルーチンを考えれば、値が戻ってくれないと困ることがわかるだろう。)
この問題をfixするのは易しい:
実装例2
make-parameterは実装例1と同じ。
parameterizeで、savesの設定をdynamic-windのbeforeサンクで
やるようにした。
(define (make-parameter init)
(case-lambda
[() init] ; 引数なしの時は現在値を返す
[(newval)
(begin0 init ; 引数ありの時はそれを新たな現在値にして元の値を返す
(set! init newval))]))
(define-syntax parameterize
(syntax-rules ()
[(_ ((param val) ...) body ...)
(let ([params (list param ...)] ;paramのリスト
[vals (list val ...)] ;valのリスト
[saves #f])
(dynamic-wind
(^[] (set! saves (map (^[p v] (p v)) params vals)))
(^[] body ...)
(^[] (for-each (^[p v] (p v)) params saves))))]))
call/ccによる再起動もok。
gosh> (define special (make-parameter 1))
special
gosh> (define (get-special) (special))
get-special
gosh> (define cc #f)
cc
gosh> (parameterize ((special 3))
(call/cc (lambda (c) (set! cc c)))
(get-special))
3
gosh> (cc #f)
3
gosh> (get-special)
1
これで無問題だ。
……ほんとに?
実装例2の問題
問題が出るのは次のようなケース。
gosh> (parameterize ((special 3))
(special 5) ; [1]
(call/cc (lambda (c) (set! cc c)))
(get-special))
5
gosh> (cc #f)
3
[1]でspecialの値が5に変更されているので、継続を再起動したら
5が見えなければならない。
ちなみに、specialの設定を"""call/cc""の後ろに持ってくると
一見動いてるように見えるんだけど:
gosh> (parameterize ((special 3))
(call/cc (lambda (c) (set! cc c)))
(special 5)
(get-special))
5
gosh> (cc #f)
5
こうしてみるとまずいことがわかる:
gosh> (parameterize ((special 3))
(call/cc (lambda (c) (set! cc c))) ; [1]
(print "special=" (get-special))
(special 5) ; [2]
(get-special))
special=3 ; printによる表示
5
gosh> (cc #f)
special=3 ; ここは5でないとならない
5
クロージャが静的環境(レキシカル環境)を捕捉するように、call/ccは
動的環境を捕捉する。[1]でcall/ccが捕まえるのはspecialの
値そのものではなく、その時点でparameterizeが作っている動的環境だ。
クロージャ内で閉じ込んだ変数にset!すればそのその変更が一旦クロージャから
抜けても残るように、動的変数の変更の効果は永続的でなければならない。
[2]によるspecialの値の変更は、parameterizeが作る動的環境の
変更なので、継続の再起動で[1]に戻ってきた時にはspecialは既に5になっているというわけ。
fixは次のとおり:
実装例3
やはりmake-parameterは同じ。
parameterizeのafterサンクで、「抜ける時点でのパラメータの値」を
再びvalsに保存しておく。bodyに再び戻ってきたら、抜けた時点での
値が復元される。
(define (make-parameter init)
(case-lambda
[() init] ; 引数なしの時は現在値を返す
[(newval)
(begin0 init ; 引数ありの時はそれを新たな現在値にして元の値を返す
(set! init newval))]))
(define-syntax parameterize
(syntax-rules ()
[(_ ((param val) ...) body ...)
(let* ([params (list param ...)] ;paramのリスト
[vals (list val ...)]) ;valのリスト 兼 現在の値のセーブ
(dynamic-wind
(^[] (set! vals (map (^[p v] (p v)) params vals)))
(^[] body ...)
(^[] (set! vals (map (^[p v] (p v)) params vals)))))]))
確認。
gosh> (define special (make-parameter 1))
special
gosh> (define (get-special) (special))
get-special
gosh> (define cc #f)
cc
gosh> (parameterize ((special 3))
(special 5)
(call/cc (lambda (c) (set! cc c)))
(get-special))
5
gosh> (cc #f)
5
gosh> (get-special)
1
実装例3は動的束縛を実現しているが、srfi-39およびR7RSのパラメータには追加仕様があって これだけでは不十分だ。その点については後で見て行くが、 その前にもうひとつ、気になる点に触れておく。
実装例4 中間リスト作成を避ける
実装例3では、parameterizeに入って抜けるまでにリストが4本作られる。
性能に敏感なSchemerはそこに眉をひそめるかもしれない。パラメータの数は
コンパイル時にわかるのだから、わざわざリストにせずとも、マクロ展開時に
同数の一時変数を用意してそれぞれにセーブしてやれば良い。
;; これは例3までと同じ
(define (make-parameter init)
(case-lambda
[() init] ; 引数なしの時は現在値を返す
[(newval)
(begin0 init ; 引数ありの時はそれを新たな現在値にして元の値を返す
(set! init newval))]))
;; 値のセーブをリストにするのではなく、各パラメータごとに一時変数を作る方式
(define-syntax parameterize
(syntax-rules ()
[(_ (binding ...) body ...)
(%parameterize (binding ...) () () () (body ...))]))
;; 補助マクロ。再帰しつつparam、valと同数のtmpを作る。
(define-syntax %parameterize
(syntax-rules ()
[(_ () (param ...) (val ...) (tmp ...) (body ...))
(let ((tmp val) ...)
(dynamic-wind
(^[] (set! tmp (param tmp)) ...)
(^[] body ...)
(^[] (set! tmp (param tmp)) ...)))]
[(_ ((param val) . rest) (p ...) (v ...) (t ...) bodies)
(%parameterize rest (p ... param) (v ... val) (t ... tmp) bodies)]))
syntax-rulesで不定個の一時変数を用意するのはちょっとまどろっこしい。
見慣れてない人は戸惑うかもしれないので1ステップづつ追っておこう。
入力が
(parameterize ((a x) (b y) (c z)) body)
の場合、まず補助マクロが
(%parameterize ((a x) (b y) (c z)) () () () (body))
と呼ばれる。これが%parameterizeの2番目の節にマッチして、再帰的に
束縛がひとつづつばらされて、対応する一時変数が追加されてゆく。
(%parameterize ((b y) (c z)) (a) (x) (tmp) (body)) ↓ (%parameterize ((c z)) (a b) (x y) (tmp tmp) (body)) ↓ (%parameterize () (a b c) (x y z) (tmp tmp tmp) (body))
束縛が空になったら%parameterizeの1番目の節がマッチして、
letとdynamic-windに展開される。
変数名tmpが重なっているように見えるが、衛生マクロによって
再帰の度に内部的には別変数として扱われるので衝突しない。
実際の展開例も示しておこう。macroexpand-allの出力は
わかりやすいようにインデントして示す。
gosh> (macroexpand-all '(parameterize ((a 3)(b 5)) (list a b)))
(letrec ((tmp.0 '3)
(tmp.1 '5))
(dynamic-wind
(lambda ()
(begin (set! tmp.0 (a tmp.0)) (set! tmp.1 (b tmp.1))))
(lambda ()
(list a b))
(lambda ()
(begin (set! tmp.0 (a tmp.0)) (set! tmp.1 (b tmp.1))))))
展開例でわかるように、この実装例は余分なリストを作らない。めでたしめでたし。
……ほんとに?
実装例4の問題と実装例5
実装例4には非常に微妙な問題がある。
gosh> (define special (make-parameter 1))
special
gosh> (parameterize ((special 3))
(set! special string->number))
*** ERROR: string required, but got 1
Stack Trace:
_______________________________________
0 (special tmp)
[unknown location]
1 (^ () (set! tmp (special tmp)))
[unknown location]
2 (eval expr env)
at "/usr/share/gauche-0.9/0.9.5/lib/gauche/interactive.scm":269
パラメータの保持する値ではなく、パラメータを指す変数そのものを書き換えてしまった 場合にエラーになる。
もちろんそんなことをする意味はほとんどない。specialにset!した後では
specialをパラメータとしては使えなくなる。それでも、parameterizeの
ボディ中でパラメータspeciallを一切参照していないにもかかわらず、
エラーが出てしまうのは抽象化の破れである。
このfixは簡単だ。parameterizeに与えられたパラメータ式自身も
一時変数に束縛しておけばよい。
;; 実装例5
(define-syntax %parameterize
(syntax-rules ()
[(_ () (param ...) (val ...) (ptmp ...) (vtmp ...) (body ...))
(let ((ptmp param) ...
(vtmp val) ...)
(dynamic-wind
(^[] (set! vtmp (ptmp vtmp)) ...)
(^[] body ...)
(^[] (set! vtmp (ptmp vtmp)) ...)))]
[(_ ((param val) . rest) (p ...) (v ...) (pt ...) (vt ...) bodies)
(%parameterize rest (p ... param) (v ... val)
(pt ... ptmp) (vt ... vtmp) bodies)]))
展開例は次のとおり。
gosh> (macroexpand-all '(parameterize ((a 3)(b 5)) (list a b)))
(letrec ((ptmp.0 a)
(ptmp.1 b)
(vtmp.2 '3)
(vtmp.3 '5))
(dynamic-wind
(lambda ()
(begin (set! vtmp.2 (ptmp.0 vtmp.2)) (set! vtmp.3 (ptmp.1 vtmp.3))))
(lambda ()
(list a b))
(lambda ()
(begin (set! vtmp.2 (ptmp.0 vtmp.2)) (set! vtmp.3 (ptmp.1 vtmp.3))))))
では次に、srfi-39/r7rsのフル仕様のサポートを考えよう。
converter手続きと実装例6
srfi-39/r7rsのmake-parameterは追加引数を取れる:
(make-parameter init-value [converter])
converterは1引数の手続きで、パラメータの値が変更される際に、 新たな値としてパラメータに渡された値を受け取る。 そこで適切な型変換をしたり、値の有効性をチェックしたりできる。
例えば、パラメータの値は常に文字列であって欲しいとしよう。次のとおり、 converter手続きで文字列に変換するようにしておけば:
(define prompt
(make-parameter
">"
(lambda (x)
(if (string? x)
x
(with-output-to-string (lambda () (write x)))))))
こうなる:
gosh> (prompt)
">"
gosh> (parameterize ((prompt '$))
(prompt))
"$"
では実装例3のmake-parameterを改造してconverter手続きをサポートしてみよう。
要は、newvalが与えられた時にconverterを噛ませてやればいいだけのはずだ。
(define (make-parameter init :optional (converter identity))
(let1 val (converter init)
(case-lambda
[() val]
[(newval) (begin0 val (set! val (converter newval)))])))
;; これは例3と同じ
(define-syntax parameterize
(syntax-rules ()
[(_ ((param val) ...) body ...)
(let* ([params (list param ...)] ;paramのリスト
[vals (list val ...)]) ;valのリスト
(dynamic-wind
(^[] (set! vals (map (^[p v] (p v)) params vals)))
(^[] body ...)
(^[] (set! vals (map (^[p v] (p v)) params vals)))))]))
これで、上のpromptの例も動く。簡単だね。
……ほんとに?
実装例6の問題
こんなパラメータspecialを作ってみる。
gosh> (define special
(make-parameter 1 -))
special
動的束縛時に与えられる値の符号を反転したものが値となる。
gosh> (special)
-1
gosh> (parameterize ((special -5))
(special))
5
動いているように見える。しかし…
gosh> (define cc #f)
cc
gosh> (parameterize ((special -5))
(call/cc (lambda (c) (set! cc c)))
(special))
5
gosh> (cc #f)
-5 ;; 5になるべき
継続ccでもってparameterizeの中に戻ったら、specialの
値の符号が反転してしまった。
実装例7
問題は、converterが冪等でない場合、動的束縛時と
値のリストア時で処理を変えなければならない点にある。
動的束縛時にはconverter手続きが適用されるが、値のリストア時はconverter手続きを
バイパスしなければならない。
これは、パラメータオブジェクトの保持する値を変更するのに、(P newval)以外の
もうひとつ別のチャネルが必要であることを意味する。
SRFI:39の参照実装ではパラメータオブジェクトの値を保持するセルを グローバルに見えるリストにつないでおいて、値の復帰はそちらを直接いじるようにしている。 でもこれまで各パラメータ内に値を保持してきたのだから、 ちょっとAPIをいじることで適合できないだろうか。 (昔のLispの用語を使えば、SRFI:39の方法はグローバルに環境をスタックして そこから探すのでdeep binding的、ここでやっている方法は各変数(パラメータ)が 動的状態を保持するのである意味shallow binding的と言える。)
動的束縛の値を変える二つの方法を区別できれば良いのだから、 例えばパラメータオブジェクトにこっそり、 converter手続きを通さない第3のモードを追加すれば実現できそうだ。
;; parameter手続きのインタフェースを変更
;; (proc) => 現在の値を返す
;; (proc newval) => newvalを新しい値とし、以前の値を返す
;; (proc newval something) => newvalをconverter手続きを通さずに直接セット
;; 3番目は内部的に使う
(define (make-parameter init :optional (converter identity))
(let1 val (converter init)
(case-lambda
[() val]
[(newval) (begin0 val (set! val (converter newval)))]
[(newval _) (begin0 val (set! val newval))])))
(define-syntax parameterize
(syntax-rules ()
[(_ ((param val) ...) body ...)
(let* ([params (list param ...)] ;paramのリスト
[vals (list val ...)] ;valのリスト
[saves #f])
(dynamic-wind
(^[] (if saves
(set! saves (map (^[p v] (p v #t)) params saves))
(set! saves (map (^[p v] (p v)) params vals))))
(^[] body ...)
(^[] (set! saves (map (^[p v] (p v #t)) params saves)))))]))
先の例は、今度は動く。
gosh> (define special
(make-parameter 1 -))
special
gosh> (special)
-1
gosh> (define cc #f)
cc
gosh> (parameterize ((special -5))
(call/cc (lambda (c) (set! cc c)))
(special))
5
gosh> (cc #f)
5
……ほんとに?
gosh> (define a (make-parameter 1 (^x (unless (number? x) (error "!!")) x)))
a
gosh> (define b (make-parameter 2 (^x (unless (number? x) (error "!!")) x)))
b
gosh> (parameterize ((a 10) (b 'abc)) (list a b))
*** ERROR: !!
Stack Trace:
_______________________________________
0 (error "!!")
at "(standard input)":61
1 (converter newval)
at "(standard input)":43
2 (map (^ (p v) (p v)) params vals)
[unknown location]
3 (^ () (if saves (set! saves (map (^ (p v) (p v #t)) params sa ...
[unknown location]
4 (eval expr env)
at "/usr/share/gauche-0.9/0.9.5/lib/gauche/interactive.scm":282
gosh> (a)
10 ; 1に戻ってない
実装例8
実装例7では、動的束縛を逐次処理していたが、converter手続きがエラーを投げた場合、 それまでに変更した束縛を元に戻すチャンスが無かった。 converter手続きがエラーを投げる可能性を考えると、束縛を変更する前に 以前の値を保存しておき、エラーが出たら巻き戻すようにすればいけそうだ。
;; これは例7と同じ
(define (make-parameter init :optional (converter identity))
(let1 val (converter init)
(case-lambda
[() val]
[(newval) (begin0 val (set! val (converter newval)))]
[(newval _) (begin0 val (set! val newval))])))
(define-syntax parameterize
(syntax-rules ()
[(_ ((param val) ...) body ...)
(let* ([params (list param ...)] ;paramのリスト
[vals (list val ...)] ;valのリスト
[saves #f]
[restarted #f])
(dynamic-wind
(^[] (if restarted
(set! saves (map (^[p v] (p v #t)) params saves))
(set! saves (map (^[p] (p)) params)))) ; 初回の値を保存
(^[]
(unless restarted ; 初回のみここで値をセット。エラーが起きたら巻き戻される
(set! saves (map (^[p v] (p v)) params vals)))
body ...)
(^[]
(set! restarted #t)
(set! saves (map (^[p v] (p v #t)) params saves)))))]))
やってみよう。
gosh> (define a (make-parameter 1 (^x (unless (number? x) (error "!!")) x)))
a
gosh> (define b (make-parameter 2 (^x (unless (number? x) (error "!!")) x)))
b
gosh> (parameterize ((a 10) (b 'abc)) (list a b))
*** ERROR: !!
Stack Trace:
_______________________________________
0 (error "!!")
at "(standard input)":78
1 (converter newval)
at "(standard input)":43
2 (map (^ (p v) (p v)) params vals)
[unknown location]
3 (eval expr env)
at "/usr/share/gauche-0.9/0.9.5/lib/gauche/interactive.scm":282
gosh> (a)
1
めでたしめでたし。
……ほんとに?
教訓
ここに上げた経緯は、ほぼGaucheのparameterize実装がたどった経緯である。
パラメータオブジェクトそのものはスレッドローカルな値を保存するように
細工がしてあるが、parameterizeの現時点の実装はロジックとしては
実装例8にあげたものと同等になっている。今のところ問題は見つかっていないが、
これで完璧かどうかはわからない。
SRFI:39の参照実装のようにグローバルな動的環境リストを持つようにしていれば、 そちらの方が落とし穴が少なかったかもしれない。 (パラメータオブジェクトの値の参照に毎回環境リストを探さねばならないという点で deep bindingの欠点を引き継ぐことになるが。) その意味では、最初の方針が悪かったせいで回り道をしたとも言えるが、 ここからいくつか教訓を引き出すことは可能だと思う。
単純であっても落とし穴がないとは限らない
「(p)で値の取得、(p v)で値の変更」という仕様は十分に単純に見える。
これを見たら多分真っ先にクロージャ内に現在の値を保持することを思いつくだろうし、
実装例2くらいまでならすぐに思い浮かびそうな気がする。
実際は、parameterizeを使わずに(p v)で直接値を変更できることが
落とし穴になっていた。動的束縛を実現したいのなら、必要なのはオブジェクトの
作成(make-parameter)、束縛された値の参照、および束縛の実現(parameter)
の3点であって、どうやって束縛された値を変更するかというのは実装に任せておけば
良かったのである。
実際、R7RSではパラメータオブジェクトの値の変更はparameterizeのみによって
行うことになっていて、パラメータオブジェクトに引数を渡した時の振る舞いは未規定である。
複数の役割を持たせることの危うさ
make-parameterのconverter手続き、および(p v)での値が変更できること、
という仕様は、「制御されたグローバル変数」としての用途を念頭においていたようにも
思える。(p v)でグローバルに見える状態を変更できるが、
converter手続きによって少なくとも変な値がセットされることを防いだり、
いつ変更されたかをトレースすることができる。
ナイーブに考えると、make-parameterにconverter手続きを追加することは
ちょっとしたハックに見える。
ちょっと変えればこっちの用途にも使えて便利じゃん、というノリだ。
実際は、converter手続きの存在によって、
パラメータオブジェクトの「値の変更」と「値のリストア」に別の操作が必要になってしまった。
元々、(p)と(p v)だけあればその上に抽象を組める、と思っていたのに、
ちょっとしたハックがその前提を壊してしまったわけだ。
「制御されたグローバル変数」としてのパラメータはそれはそれで便利なこともあるので、 このデザインが全く誤りだとい言いたいわけではないが、 一見無害なちょっとしたハックが思わぬ影響を及ぼすことがある、という教訓にはなるだろう。

Post a comment