Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 | 

2017年12月10日

[][]letrec と letrec*

R5RS 以前の letrec は実装に依存します。 R6RS でセマンティック・エラーになる書き方をしてみると……

(let ((a 4) (b 5))
 (list
  (letrec ((a (begin (set! b 2) b))
           (b (begin (set! a 3) a))
           (f (lambda (t) (cons a b))))
   (f #t))
  (cons a b))) ;=> ((3 . 3) (4 . 5)) か ((2 . 2) (4 . 5)) か ((2 . 3) (4 . 5)) のどれか

letrec* は実装に依存しません。 これも、 R6RS でセマンティック・エラーになる書き方ですが……。

(let ((a 4) (b 5))
 (list
  (letrec* ((a (begin (set! b 2) b))
            (b (begin (set! a 3) a))
            (f (lambda (t) (cons a b))))
   (f #t))
  (cons a b))) ;=> ((3 . 3) (4 . 5))

この letrec* を使った式の評価結果は、 次のように書いた式と同じ評価結果になります。

(let ((a 4) (b 5))
 (list
  (let ((a 'UNSPECIFIED) (b 'UNSPECIFIED) (f 'UNSPECIFIED))
   (set! a (begin (set! b 2) b))
   (set! b (begin (set! a 3) a))
   (set! f (lambda (t) (cons a b)))
   (f #t))
  (cons a b))) ;=> ((3 . 3) (4 . 5))

letrec を letrec* の評価・束縛の順不同版と考えると、 b を a より先に評価・束縛する場合もありえます。

(let ((a 4) (b 5))
 (list
  (letrec* ((f (lambda (t) (cons a b)))
            (b (begin (set! a 3) a))
            (a (begin (set! b 2) b)))
   (f #t))
  (cons a b))) ;=> ((2 . 2) (4 . 5))

R7RS に従って、 letrec を中間変数を使って書くと評価順に依存しなくなり、 letrec* で得ることができない値になります。

(let ((a 4) (b 5))
 (list
  (let ((a 'UNSPECIFIED) (b 'UNSPECIFIED) (f 'UNSPECIFIED)
        (t1 'UNSPECIFIED) (t2 'UNSPECIFIED) (t3 'UNSPECIFIED))
   (set! t1 (begin (set! b 2) b))
   (set! t2 (begin (set! a 3) a))
   (set! t3 (lambda (t) (cons a b)))
   (set! a t1) (set! b t2) (set! f t3)
   (f #t))
  (cons a b))) ;=> ((2 . 3) (4 . 5))

(let ((a 4) (b 5))
 (list
  (let ((a 'UNSPECIFIED) (b 'UNSPECIFIED) (f 'UNSPECIFIED)
        (t1 'UNSPECIFIED) (t2 'UNSPECIFIED) (t3 'UNSPECIFIED))
   (set! t3 (lambda (t) (cons a b)))
   (set! t2 (begin (set! a 3) a))
   (set! t1 (begin (set! b 2) b))
   (set! f t3) (set! b t2) (set! a t1)
   (f #t))
  (cons a b))) ;=> ((2 . 3) (4 . 5))

2017 年 12 月 11 日追記 原理原則に従って letrec 構文を ML の let rec と同様に Y コンビネータを使うのと等価な再帰手続きを書くための構文と捉えると、 《Y コンビネータの戻り値は手続き》なので、 R6RS のセマンティックですら生ぬるく初期化式の値が手続き以外だと型エラーにするのが本来でしょう。 一方、 letrec* は内部定義の意味を明確にするために導入された構文なので、 R6RS 以降の定義に従っていれば良いのでしょう。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/tociyuki/20171210/1512882866
 |