2007/03/08

連番を作るのに integ のようなプロシージャを使うのはいいけど、Schemeでは引数の評価順が規定されていないので連番の順序はどうなるか保証はないよという話。次のようなコメントをいただいたので、これを復習してきちんと消化しよう。
ところで、

gosh> (list (integ) (integ) (integ))
(1 2 3)

は,R5RSには引数の評価順が規定されていないので,これが
(3 2 1)になっても文句はいえないと思う:)

そういえばSICPの第3章にもそんな問題(ex. 3.8)があった。評価順が左→右の実装では (+ (f 0) (f 1)) が 0 だけど、右→左の実装では 1 になるような f を定義しろという問題。

その昔、この問題を解いたときに定義したのはこんなグローバル変数を使った方法だった。
(define y 0)
(define (f x)
(if (= y 0)
(begin (set! y x) 0)
(begin (set! y 1) y)))
これはダサい。いまならこう書く(えらそう)。
(define f
(let ((y 0))
(lambda (x)
(if (= y 0)
(begin (set! y x) 0)
(begin (set! y 1) y)))))

さて、ふつうの実装は左→右で評価するので、これを試すには右→左で評価してくれる実装が必要だ。まあ、この問題だけなら引数の順番を入れ替えて (+ (f 0) (f 1)) と (+ (f 1) (f 0)) を Gauche で試せばいいんだけど、せっかくSICPの第4章でメタ言語評価器(つまりSchemeで定義するSchemeのインタプリタ)を作るので、それを右→左で評価するように改造して使うことにする。それに、ex. 4.1が、まさにそのように改造せよという問題だ。ここではletも必要なので、letを追加したdata-directed スタイルのバージョン(つまりex. 4.3と4.6の成果を取り込んだもの)を使う。たぶんここら(SICP Web Site for the Japanese Edition)あたりにもあると思うけど、オレ実装は以下(getとputが必要)。

metacircular-evaluator-right-to-left.scm

gosh> 
(define f
(let ((y 0))
(lambda (x)
(if (= y 0)
(begin (set! y x) 0)
(begin (set! y 1) y)))))

f
gosh> (+ (f 0) (f 1))
0
gosh> (driver-loop)

;;; M-Eval input:
(define f
(let ((y 0))
(lambda (x)
(if (= y 0)
(begin (set! y x) 0)
(begin (set! y 1) y)))))


;;; M-Eval value:
ok

;;; M-Eval input:
(+ (f 0) (f 1))

;;; M-Eval value:
1

もちろん(list (integ) (integ) (integ))も文句を言えない結果に。
;;; M-Eval input:
(list (integ) (integ) (integ))

;;; M-Eval value:
(3 2 1)

No comments :