R6RS:変更点:mapとcall/cc

R6RS:変更点:mapとcall/cc

(map proc lis) の proc 実行中に継続が捕捉されて、 後からその継続が再起動された場合、mapも途中から結果のリストを作り直すことになります。 この時、R6RSでは、以前に返した結果のリストをmapは変更してはならない、と規定されています。

Gauche 0.8.11のmapはこの条件を満たしません。

gosh> (define *cont* #f)
*cont*
gosh> (define (proc x) (if (= x 2) (call/cc (lambda (c) (set! *cont* c) x)) x))
proc
gosh> (let* ((r '())
             (a (map proc '(1 2 3))))
        (set! r (cons a r))
        (if (= (length r) 2)
          r
          (*cont* 'boo)))
(#0=(1 boo 3) #0#)

mapからは2回返って来ます。最初のmap呼び出しは単純に(1 2 3)を返します。 ただし、この時2を処理するタイミングでprocが継続を*cont*に格納しています。 そして、(*cont* 'boo) の呼び出しにより、一回目は2を返したprocが booを返すところから処理が再開されます。二回目にはmapは(1 boo 3)を 返すはずです。2回のmapの戻り値がそれぞれ変数rにpushされ、2回目は *cont*を呼ばずにrが返されるわけなので、結果は ((1 boo 3) (1 2 3)) とならなければなりません (mapの実装によってはリストの末尾を共有して ((1 boo . #0=(3)) (1 2 . #0#)) となっても良い)。

Gauche 0.8.11のmapは、procをリストの頭から適用して、結果のリストの 末尾に新しい結果を次々と破壊的に追加してゆくように書かれています。 この場合、(*cont* 'boo)の呼び出しによってリスト構築が再開されると、 「以前返したリスト」の途中から破壊的に再びリスト構築を行ってしまうため、 前回返したリストが変更されてしまうわけです。

R6RSの規格を満たすには、中間リストの破壊的変更を避けるしかありません。 先頭からprocを適用していって逆順の中間リストを作り、最後にreverseするか:

(define (map proc lis)
  (let loop ((lis lis)
             (res '()))
    (if (null? lis)
      (reverse res)
      (loop (cdr lis) (cons (proc (car lis)) res)))))

非末尾再帰で尻尾から結果リストを作るか:

(define (map proc lis)
  (if (null? lis)
    '()
    (cons (proc (car lis)) (map proc (cdr lis)))))

どちらにせよO(n)の中間領域が作られ、実行時にもオーバヘッドがあります。


Last modified : 2012/02/02 11:45:41 UTC