SICP 読書ノート#53 - 4.1.6 内部定義 (pp.230-234)

「§4.1.6 内部定義」を読みました。手続きの内部定義とその評価について考察します。

問題 4.19

変数を評価すると行っても色んなポリシーがあるという話。

自前の処理系

自前の処理系での実行結果は、(define b (+ a x))の評価の時点でローカル環境にaがないため外側の環境を参照しに行く。至ってシンプル。

> (let ((a 1))
    (define (f x)
      (define b (+ a x))
      (define a 5)
      (+ a b))
    (f 10))
=> 16

Racket

実行結果はAlyssaの見方と同じ。

racket@> (let ((a 1))
           (define (f x)
             (define b (+ a x))
             (define a 5)
             (+ a b))
           (f 10))
a: undefined;
 cannot use before initialization
  context...:
   /opt/homebrew-cask/Caskroom/racket/6.1.1/Racket v6.1.1/collects/racket/private/misc.rkt:87:7

おそらく(define (f x) ...)はテキストにあるような、

(define f
   (lambda (x)
     (let ((a "undefined")
           (b "undefined"))
       (set! b (+ a x))
       (set! a 5)
       (+ a b))))

と等価となるような変換が内部で行われるので、fに引数を適用すると(set! b (+ a x))の箇所でaが参照できずにundefinedとなる。

Evaの要件

Evaの要件f(10) => 20を満たすには(set! b (+ a x))でset!の引数を評価せず、bを参照するときに初めて(+ a x)を評価するようにすれば動くが、これでよいのかなぁ。

node

ちなみにnodeでの実行結果は、Alyssaの見立てと同じだった。

（返り値がNaNとなっているのはundefined + 数値 => NaNとなるため）

> (function() {
... var a = 1;
... var f = function(x) {
..... var b = a + x;
..... var a = 5;
..... return a + b;
..... };
... return f(10);
... })()
=> NaN

問題 4.20

a.

letrecの構文は、

(letrec ((<v1> <e1>) ... (<vn> <en>))
  <body>)

は以下のように構文変換できるので、

(let ((<v1> "*unassigned*)
      ...
      (<vn> "*unassigned*"))
 (set! <v1> <e1>)
 ...
 (set! <v1> <vn>)
 <body>)

処理系にそのように組み込めばよい。

b.

手続きの定義をletで行ったとして、letで定義した手続きの再帰呼び出しできない。

問題 4.21

Yコンビネータっぽい話。

a.

フィボナッチ数列のletrec版。

racket@> (letrec ((fib
                   (lambda (n)
                     (cond ((= n 0) 0)
                           ((= n 1) 1)
                           (else (+ (fib (- n 1))
                                    (fib (- n 2))))))))
           (fib 10))
=> 55

これをlet、letrecなしで実装すると以下のようになる。

racket@> ((lambda (n)
            ((lambda (fib)
               (fib fib n))
             (lambda (f k)
               (cond ((= k 0) 0)
                     ((= k 1) 1)
                     (else (+ (f f (- k 1))
                              (f f (- k 2))))))))
          10)
=> 55

b.

元々のコードに対して、

(define (f x)
  (define (even? n)
    (if (= n 0)
        true
        (odd? (- n 1))))
  (define (odd? n)
    (if (= n 0)
        false
        (even? (- n 1))))
  (even? x))

以下のように変換できる。

racket@> (define (f x)
           ((lambda (even? odd?)
              (even? even? odd? x))
            (lambda (ev? od? n)
              (if (= n 0) true (od? ev? od? (- n 1))))
            (lambda (ev? od? n)
              (if (= n 0) false (ev? ev? od? (- n 1))))))
racket@> (f 4)
=> #t
racket@> (f 5)
=> #f

次回は「§4.1.7 構文解析を実行から分離する」から。

@uents blog

Code wins arguments.