³µÍ×

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.