遅延評価とは値が必要になるまで計算しないという計算方法のことです。Schemeには遅延評価のプロミスを作成する delay と、プロミスを強制する force と、式がプロミスかを確認する promise? の３つの関数があります。
SICPで最初に示される delay の実装
計算機プログラムの構造と解釈（Structure and Interpretaion of Computer Program)に最初に示されている delay の実装は以下のようなものです。 delay の実装で検索しても出てくるのは同じものばかりです。
( define-syntax delay
( syntax-rules ()
((_ form)
( lambda () form))))
( define ( force x) (x))
この実装はもちろん正しくきちんと遅延評価の実装ができています。
Gaucheには delay と force と procmise? が用意されていますが delay と force は先ほど示したコードで上書きしてあります。そのため delay で作成したオブジェクトはプロミスではないので promise? の結果として #f が返されています。また、プロミスではないので force も自作しています。
画像の通り force して時はじめて評価される遅延評価となっています。
S9fESのdelayの実装
一方S9fES（Scheme 9 from Empty Space)での delay の実装は以下のようなものです。
( define-syntax delay
( syntax-rules ()
((_ form)
( let ((%%r #f))
( lambda ()
( cond (%%r (car %%r))
( else (set! %%r (cons form '()))
(car %%r))))))))
( define ( force x) (x))
最初の一回目は else 節が実行され局所変数 %%r に form の評価結果が代入されて2回目以降は %%r に代入された結果が返されます。
lambda で form が囲われてこの lambda が呼ばれるたびに form の結果を返すという点では一見したところSICPの delay の実装と変わりありません。むしろs9fesの実装のほうが無駄なことをしているように見えます。
実際s9fesの delay を実行してみると
と上のSICPの delay と変わらぬ動作をしています。
SICPとS9fESの delay の違い
２つの delay はまったく同じ動作をするように見えますがいくつかの手続きにおいては別な結果を表示します。それは 副作用がある手続きをプロミスにした時です。
副作用のある手続きは値を受け取り計算して値を返すという関数型言語において、値を返す他にも何らかの影響を与える手続きのことです。
Schemeでは display や set! などがそれに当たります。
これらの手続きをSICPとS9fESの二つの delay でプロミスにして force してみると２回目以降で明確な違いが出ます。
SICPの delay
S9fESの delay
display 手続きで比較してみるとSICPは2回目に force した時も hello, world! と表示されていますがS9fESでは2回目には #<undef> としか表示されていません。
また set! で比較してみるとSICPは2回目も変数 a の値が書き換えられているのに対して、S9fESでは2回目は書き換える値の2が表示されますが実際には変数 a の値は書き換えられていません。
つまりS9fESの delay は最初の１回目に force した時だけ form を評価しますが2回目以降は局所変数に束縛した form の評価結果として返された値を返しているだけということです。すなわち計算結果が局所変数にキャッシュされていることになります。
一方、SICPの delay はプロミスが force されるたびに form を評価しています。
S9fESの実装なら2回目以降は form を評価しないので高速に動作します。また副作用がある手続きについては最初の1回目のみ副作用を起こし、２回目以降は手続きから返された値を表示するだけなので副作用をもう一度発生させません。
どちらの実装が正しいのか
ではどちらの実装が正しいのかという話になってきます。ネットで検索するとSICPの実装を紹介してることが多いのですがScheme処理系のGaucheやRacketではS9fESと同じ実装をしています。
そしてSICPも delay の実装部分を少し読み進めると最初に force した後結果をキャッシュする実装が紹介されています。
(define (memo-proc proc)
(let ((already-run? false) (result false))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result)
result))))
(define (force delayed-object)
(delayed-object))
ただし、このコードはそのままでは動かないので memo-proc か force もしくは両方を修正する必要があります。
こうしてみると最初に force した結果をキャッシュするS9fESの実装が正しいような気がします。
新品価格
￥4,968 から
(2017/3/10 19:36時点)
タグ： Gauche
【このカテゴリーの最新記事】
-
-
- no image
- no image
-
