Schemeの遅延評価delayの２つの実装: いおりのプログラミングめも

2017年03月10日

Schemeの遅延評価delayの２つの実装

Schemeの遅延評価のdelayの実装についてです。S9fESの最後でdelayの実装がありますが初見ではなにやら無駄なコードに見えましたがきちんと理由があったのでその記録です。

遅延評価とは値が必要になるまで計算しないという計算方法のことです。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))