概要

Scheme では、伝統的に delay と force を使って遅延評価の真似ごとをしてきた。しかし、これらのプリミティブは 反復的な大規模遅延評価型アルゴリズムを実装するのに十分であるとはいえない。 実際、Scheme コミュニティには典型的な遅延評価型アルゴリズムを delay と force を使って書くと、際限なくメモリが必要になるという言い伝えがあるほどである。

この問題を解決するために、delay と force への様々な修正案が提案されてきた（例えば SRFI-40 discussion list 参照）が、どの案もすべて、下に示すベンチマークのどこかで失敗した。 我々の知るかぎり、本 SRFI は、この問題に対して、初めて包括的な解決策を提供する。

まず、動機づけとして、普通の delay と force だけを使った遅延評価では、真の遅延評価型言語では正しく末尾再帰になるような典型的なアルゴリズムの反復的なふるまいが破壊され、際限なくメモリが必要になってしまう仕組みを説明する。

そこで、lazy、delay、force のみっつの操作を導入してこの問題を解決する。 これらの操作により、プログラマは正しい末尾再帰のアルゴリズムを 一定の空間使用量で簡潔に書くことができるようになる。 また、これらのプリミティブの一般的な用法も示す。 さらに、効率性を重視する場合に先行順に評価されるプロミスをつくる eager という手続きを提供する。

この SRFI では delay と force を再定義するが、この拡張は保守的なもので、delay と force だけを使った場合、つまり lazy を使わない場合の意味論は R5RS に合致する。言い換えれば、 R5RS の delay と force の定義に従ってつくられたプログラムは、delay と force の定義を SRFI 45 のものに置き換えても 壊れない、ということである。

論理的根拠

Wadler らは How to add laziness to a strict language without even being odd [Wad98] で、delay と force を使って 任意の遅延評価型データ構造やアルゴリズムを 正格な言語に直接的に変換する方法を紹介した。

しかし、この変換法では、もとのアルゴリズムが 正しい末尾再帰で書かれていたとしても、メモリ消費量が際限なく増えてしまう ことがあるという問題がある（SRFI-40 discussion list 参照）。

例

以下の Scheme 風の構文の架空の遅延評価型の言語で書かれた 手続きについて考える。

(define (stream-filter p? s)
  (if (null? s) '()
      (let ((h (car s))
            (t (cdr s)))
        (if (p? h)
            (cons h (stream-filter p? t))
            (stream-filter p? t)))))

[Wad98] の変換をほどこすと、このアルゴリズムは Scheme では下のように書ける。

(define (stream-filter p? s)
  (delay (force 
          (if (null? (force s)) (delay '())
              (let ((h (car (force s))) 
                    (t (cdr (force s))))
                (if (p? h)
                    (delay (cons h (stream-filter p? t)))
                    (stream-filter p? t)))))))

本文書で修正の対象とする方法は次の通りである。

• すべての構築子（'()、cons 等）を delayで包む
• 値を分解する部分（car、cdr、 null? 等）の引き数に force を適用する
• 手続き本体を (delay (force ...)) で包む

しかし、以下のコードを十分な大きさの large-number について評価すると、もとの（遅延評価型）アルゴリズムは、反復的で、かつ結果のストリーム最初の要素を評価するには末尾呼び出しをするだけでよいのに、典型的な Scheme の実装ではメモリ不足が起こってしまう。

(define (from n)
  (delay (cons n (from (+ n 1)))))

(define large-number 1000000000)

(car (force (stream-filter (lambda (n) (= n large-number)) 
                           (from 0))))

space leak の原因

上の stream-filter の例で起こる問題は、 以下の架空の言語における無限ループでも起こりうる。

(define (loop) (loop))

これに [Wad98] の変換をほどこすと次のようになる。

(define (loop) (delay (force (loop))))

delay と force の意味論を簡単に説明すると、次のようになる。

(force (delay expr)) = expr の値で
                         promise : (delay expr) を更新し
                       プロミスの値を返す

従って、上の無限ループの例は以下のようになる。

(force (loop)) = (force (loop)) の値で
                      promise1 : (delay (force (loop))) を更新し
                 promise1 を返す
               = (force (loop)) の値で
                   promise2 : (delay (force (loop))) を更新し
                 promise2 を返し
                   この値で
                     promise1 : (delay (force (loop))) を更新し
                   promise1 を返す
               = (force (loop)) の値で
                   promise3 : (delay (force (loop))) を更新し
                 promise3 を返し
		   この値で
                     promise2 : (delay (force (loop))) を更新し
                   promise2 を返し
                     この値で
                       promise1 : (delay (force (loop))) を更新し
                     promise1 を返す
               = ...

このようにして、ヒープがあふれるまで更新待ちのプロミスの列が 無限に伸びていくのである。

上の例が call-by-need にならない理由

上のアルゴリズムを実際に delay と force を使って書いても、call-by-need の評価意味論には正確には合致しない。 例えば、素朴なグラフ簡約アルゴリズムを使った call-by-need の言語では、上のアルゴリズムは一定の空間使用量で実行される。 これは、素朴なグラフ簡約が tail safe だからである。 この問題については R. Jones の Tail recursion without space leaks [Jon98] が参考になる。

プロミスをグラフのノードとし、force を簡約とすれば、 我々の解くべき問題は、グラフ簡約と類似の問題になるだろう。 Jones によれば、space leak を防ぐためには、ノードの評価と上書きの順序に 注意しなければならないという。 我々の場合では、これはプロミスの評価順と force したときの上書き順にあたる。

上の例でいうと、素朴なグラフ簡約というのは、 根の部分にあるプロミスを各段階で次を評価する前に 書き換えること、すなわち、将来（不必要な）コピー操作になるプロミスの シーケンスを伸ばさないようにすることである。

解決法

上の例で、不必要にプロミスが累積してしまうのは 加速度的に入れ子になってゆく文脈のなかで force が中断しているためである。ここで素朴なグラフ簡約のようなことをするためには、 末尾部分で中断している force を反復的に 見つけ、その都度以前の結果を上書きする方法を見つけ出さなければならない。

この問題を解く方法が（これとは状況が違うが） Feely らの Compiling higher order languages into fully tail-recursive portable C [Fee97] で論じられている。ここで彼らは、末尾部分のコンテキストを 反復的に評価する方法として広く知られるトランポリンテクニックを 導入している。

トランポリンテクニックを今問題としている状況に合わせるために、 我々は lazy というプリミティブを導入する。 これは「不可分な」 (delay (force ...)) のように動作し、 手続きの先頭にある (delay (force ...)) の代わりになる。また、 delay と force を下のように再定義する。

; type Promise a = lazy (Promise a) | eager a 

(define-syntax lazy
  (syntax-rules ()
    ((lazy exp) 
     (box (cons 'lazy (lambda () exp))))))

(define (eager x)
  (box (cons 'eager x)))

(define-syntax delay
  (syntax-rules ()
    ((delay exp) (lazy (eager exp)))))

(define (force promise)
  (let ((content (unbox promise)))
    (case (car content)
      ((eager) (cdr content))
      ((lazy)  (let* ((promise* ((cdr content)))        
                      (content  (unbox promise)))                      ; *
                 (if (not (eqv? (car content) 'eager))                 ; *
                     (begin (set-car! content (car (unbox promise*)))
                            (set-cdr! content (cdr (unbox promise*)))
                            (set-box! promise* content)))
                 (force promise))))))

(*) この二行は、もとのプロミスを取り出し、let* の最初の行でプロミスが force された場合を
    チェックする。これが必要になる場合については、下の reentrancy test 3 を参照。

(define (box x) (list x))
(define unbox car)
(define set-box! set-car!)

そして、上で挙げた例は次のように書き換えられる。

(define (loop) (lazy (loop)))

こうすることで (force (loop)) を評価したときには、 後に続く中断部分が force により反復的に評価されるようになる。

[Fee97] の言語では、force のなかの反復的ループは ディスパッチャの役割をする。lazy フォームは 「control point」 （手続きの出入り口）の目印をつける。この方法は tail safe である。遅延評価すべき手続きは、ほかの遅延評価すべき手続きを呼ばずに、 単純に control point を表すものを返し、 これが force 内のディスパッチャループを次に通ったときに 呼び出されるからである。より詳しいことは [FMRW] を参照してほしい。

仕様

次のふたつのマクロを提供する。ここで簡単に説明するセマンティクスは下に挙げるリファレンス実装のセマンティクスに適合する。

• (delay expression) は任意の型 a 式を取り、(Promise a) 型のプロミスを返す。 プロミスは以降 force を呼び出した時点で式を評価し、 結果の値を返す。
• (lazy expression) は (Promise a) 型の式を受け取り (Promise a) 型のプロミスを返す。 この戻り値は以降 force を呼び出した時点で式を評価し、 結果の値を返す。

次のふたつの手続きを提供する。

• (force expression) は (Promise a) 型の引き数を取り、プロミスに対して a 型の値が計算されていた場合には その値を返す。さもなくは、まずそのプロミスを評価して、 得られたプロミスないし値で書き換え、そのプロミスに再び（反復的に） force を適用する。

• (eager expression) は a 型の引き数をとり、 (Promise a) 型の値を返す。delay とは対照的に先行順で評価される。意味論的には以下のように書いたのと 同等である。

  (let ((value expression)) (delay value))

  しかし、(eager expression) の方が不要な thunk の作成や評価がないため、より効率的である。 また、次のように書いたものも同じ意味である。

  (lazy (eager expression))

これらのプリミティブについて理解するのに、 以下の簡約ルールが役に立つかもしれない。 しかし、この簡約ルールは上で規定したメモ化やメモリ使用量については 触れていない。

  (force (delay expression)) -> expression
  (force (lazy  expression)) -> (force expression)
  (force (eager value))      -> value

型付けは以下のようになる。

    type Promise a = lazy (Promise a) | eager a
    
           expression  : a
    ------------------------------
    (eager expression) : Promise a
    
           expression  : Promise a
    ------------------------------
    (lazy expression)  : Promise a  

           expression  : a
    ------------------------------
    (delay expression) : Promise a 

           expression  : Promise a 
    ------------------------------
    (force expression) : a

本 SRFI では force の意味論を拡張しているが、 この拡張は保守的なものである。delay と force だけを使った場合、つまり lazy を使わない場合の意味論は R5RS の意味論に適合する。

用法

ここでは、遅延評価型アルゴリズムを Scheme で実装する場合の lazy、delay、force の一般的な用法を説明する。変換法を説明するには例をつかうのが一番であろう。 再び、架空の遅延評価型言語で表現した stream-filter アルゴリズムに ついて考えよう。

(define (stream-filter p? s)
  (if (null? s) '()
      (let ((h (car s))
            (t (cdr s)))
        (if (p? h)
            (cons h (stream-filter p? t))
            (stream-filter p? t)))))

このアルゴリズムは Scheme では下のようになる。

(define (stream-filter p? s)
  (lazy
     (if (null? (force s)) (delay '())
         (let ((h (car (force s)))
               (t (cdr (force s))))
           (if (p? h)
               (delay (cons h (stream-filter p? t)))
               (stream-filter p? t))))))

すなわち、

• すべての構築子（'()、cons 等） を delay 包む
• 値を分解する部分 （car、cdr、null? 等）で引き数に force を適用する
• 手続きの本体を (lazy ...) で包む

先に説明した [Wad98] との違いは三番目の規則の (delay (force ...)) を (lazy ...) に換えたことだけである。

下のリファレンス実装にはさらにまた別の例があげてある。

実装

リファレンス実装では R5RS のマクロを使っているが、 ほかの SRFI などのライブラリは一切使用していない。

また、ベンチマークコレクションも提供する。 これにより、この SRFI で規定した特別の場合がチェックできる。 ベンチマークを実行するためには、メモリ使用量が有限であるかどうかを 判断するために、ユーザーが実行時のメモリ使用量を調べられる必要がある。 このテストにパスすることが実装の正しさを意味するわけではない。

リファレンス実装

;=========================================================================
; Boxes

(define (box x) (list x))
(define unbox car)
(define set-box! set-car!)

;=========================================================================
; Primitives for lazy evaluation:

(define-syntax lazy
  (syntax-rules ()
    ((lazy exp)
     (box (cons 'lazy (lambda () exp))))))

(define (eager x)
  (box (cons 'eager x)))

(define-syntax delay
  (syntax-rules ()
    ((delay exp) (lazy (eager exp)))))

(define (force promise)
  (let ((content (unbox promise)))
    (case (car content)
      ((eager) (cdr content))
      ((lazy)  (let* ((promise* ((cdr content)))        
                      (content  (unbox promise)))                      ; * 
                 (if (not (eqv? (car content) 'eager))                 ; *
                     (begin (set-car! content (car (unbox promise*)))
                            (set-cdr! content (cdr (unbox promise*)))
                            (set-box! promise* content)))
                 (force promise))))))

; (*) These two lines re-fetch and check the original promise in case 
;     the first line of the let* caused it to be forced.  For an example  
;     where this happens, see reentrancy test 3 below.

;=========================================================================
; TESTS AND BENCHMARKS:
;=========================================================================

;=========================================================================
; Memoization test 1:

(define s (delay (begin (display 'hello) 1)))

(force s)
(force s)
               ;===> Should display 'hello once

;=========================================================================
; Memoization test 2:

(let ((s (delay (begin (display 'bonjour) 2))))
  (+ (force s) (force s)))

               ;===> Should display 'bonjour once

;=========================================================================
; Memoization test 3: (pointed out by Alejandro Forero Cuervo) 

(define r (delay (begin (display 'hi) 1)))
(define s (lazy r))
(define t (lazy s))

(force t)
(force r)
               ;===> Should display 'hi once

;=========================================================================
; Memoization test 4: Stream memoization 

(define (stream-drop s index)
  (lazy
   (if (zero? index)
       s
       (stream-drop (cdr (force s)) (- index 1)))))

(define (ones)
  (delay (begin
           (display 'ho)
           (cons 1 (ones)))))

(define s (ones))

(car (force (stream-drop s 4)))
(car (force (stream-drop s 4)))

               ;===> Should display 'ho five times

;=========================================================================
; Reentrancy test 1: from R5RS

(define count 0)
(define p
  (delay (begin (set! count (+ count 1))
                (if (> count x)
                    count
                    (force p)))))
(define x 5)
(force p)                     ;===>  6
(set! x 10)
(force p)                     ;===>  6
       

;=========================================================================
; Reentrancy test 2: from SRFI 40

(define f
  (let ((first? #t))
    (delay
      (if first?
          (begin
            (set! first? #f)
            (force f))
          'second))))

(force f)                     ;===> 'second 

;=========================================================================
; Reentrancy test 3: due to John Shutt

(define q
  (let ((count 5))
    (define (get-count) count)
    (define p (delay (if (<= count 0)
                         count
                         (begin (set! count (- count 1))
                                (force p)
                                (set! count (+ count 2))
                                count))))
    (list get-count p)))
(define get-count (car q))
(define p (cadr q))

(get-count)  ; =>   5
(force p)    ; =>   0
(get-count)  ; =>   10

;=========================================================================
; Test leaks:  All the leak tests should run in bounded space.

;=========================================================================
; Leak test 1: Infinite loop in bounded space.

(define (loop) (lazy (loop)))
;(force (loop))                               ;==> bounded space

;=========================================================================
; Leak test 2: Pending memos should not accumulate 
;              in shared structures.

(define s (loop))
;(force s)                                    ;==> bounded space 

;=========================================================================
; Leak test 3: Safely traversing infinite stream.

(define (from n)
  (delay (cons n (from (+ n 1)))))

(define (traverse s)
  (lazy (traverse (cdr (force s)))))

;(force (traverse (from 0)))                  ;==> bounded space

;=========================================================================
; Leak test 4: Safely traversing infinite stream 
;              while pointer to head of result exists.

(define s (traverse (from 0)))  
;(force s)                                    ;==> bounded space

;=========================================================================
; Convenient list deconstructor used below.

(define-syntax match
  (syntax-rules ()
    ((match exp 
       (()      exp1)
       ((h . t) exp2))
     (let ((lst exp))
       (cond ((null? lst) exp1)
             ((pair? lst) (let ((h (car lst))
                                (t (cdr lst)))
                            exp2))
             (else 'match-error))))))

;========================================================================
; Leak test 5: Naive stream-filter should run in bounded space.
;              Simplest case.

(define (stream-filter p? s)
  (lazy (match (force s)
          (()      (delay '())) 
          ((h . t) (if (p? h)
                       (delay (cons h (stream-filter p? t)))
                       (stream-filter p? t))))))

;(force (stream-filter (lambda (n) (= n 10000000000))
;                      (from 0)))
                                             ;==> bounded space

;========================================================================
; Leak test 6: Another long traversal should run in bounded space.

; The stream-ref procedure below does not strictly need to be lazy.  
; It is defined lazy for the purpose of testing safe compostion of 
; lazy procedures in the times3 benchmark below (previous 
; candidate solutions had failed this).  

(define (stream-ref s index)
  (lazy
   (match (force s)
     (()      'error)
     ((h . t) (if (zero? index)
                  (delay h)
                  (stream-ref t (- index 1)))))))

; Check that evenness is correctly implemented - should terminate:

(force (stream-ref (stream-filter zero? (from 0))
                   0))                              ;==> 0

(define s (stream-ref (from 0) 100000000))
;(force s)                                          ;==> bounded space

;======================================================================
; Leak test 7: Infamous example from SRFI 40. 

(define (times3 n)
  (stream-ref (stream-filter
               (lambda (x) (zero? (modulo x n)))
               (from 0))
              3))

(force (times3 7))
;(force (times3 100000000))                        ;==> bounded space

参考文献

[Wad98] Philip Wadler, Walid Taha, and David MacQueen. How to add laziness to a strict language, without even being odd, Workshop on Standard ML, Baltimore, September 1998

[Jon92] Richard Jones. Tail recursion without space leaks, Journal of Functional Programming, 2(1):73-79, January 1992

[Fee97] Marc Feeley, James S. Miller, Guillermo J. Rozas, Jason A. Wilson, Compiling Higher-Order Languages into Fully Tail-Recursive Portable C, Rapport technique 1078, département d'informatique et r.o., Université de Montréal, août 1997.