問題4-7〜8

問題4-7。nested-lets式を普通のlet式に変換します。以下のようなnested-lets式を、その下のlet式に変換することを目的とします。

;;変換前
(let* ((x 3)
       (y (+ x 2))
       (z (+ x y 5)))
  (* x z))

;;変換後
(let ((x 3))
  (let ((y (+ x 2)))
    (let ((z (+ x y 5)))
      (* x z))))

let*は、(list 'let* nested-bindings body)のような構造になっていますので、nested-bindingsの部分を砕いていって、let式を作っていけばよさそうです。そのため、まずはlet式を作成するための手続きを定義します。

(define (make-let bindings body)
  (cons 'let (cons bindings body)))

次に、nested-lets式かどうかを判別する手続きと、nested-letsの各要素を取得する手続きを定義します。

(define (let*? exp) (tagged-list? exp 'let*))

(define (lets*-bindings exp) (cadr exp))
(define (lets*-body exp) (caddr exp))

さらに、nested-letsの中の束縛リストから、任意の情報を引き出すための手続きを定義します。

(define (last-lets*-binding? bindings) (null? (cdr bindings)))

(define (first-lets*-binding bindings) (car bindings))
(define (rest-lets*-bindings bindings) (cdr bindings))

最後に、let*->nested-letsを定義します。make-nested-letsの引数は、let*のbindingsとbodyです。bindingsに束縛の対が一つしかなければ、それをそのまま利用してlet式を作ります。複数の束縛がある場合も、新しいlet式を作成しますが、let*の先頭束縛のみを新しいletの束縛として指定しつつ、そのbodyには、再帰的に呼び出すmake-nested-letsの結果を配置します。再帰的に呼び出すときに、let*の残りの束縛を渡してやるようにすれば、うまいこと、nestedされたlet式ができあがるのではないかと思われます。

(define (let*->nested-lets exp)
  (define (make-nested-lets bindings body)
    (if (last-let*-binding? bindings)
        (make-let bindings body)
        (make-let (first-lets*-binding bindings)
                  (make-nested-lets (rest-lets*-bindings bindings)
                                    body))))
  (make-nested-lets (lets*-bindings exp)
                    (lets*-body exp)))

問題4-8。let->combinationで｢名前つきlet｣を扱えるようにします。例えば、以下のような変換が可能になるということです。

;;変換前
(define (fib n)
  (let fib-iter ((a 1)
                 (b 0)
                 (count n))
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))

;;変換後
(define (fib n)
  (define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

まずは、let式が｢名前つき｣かどうかを判別するために、以下のような手続きを定義します。letに第四の要素があるかどうかを調べています。

(define (named-let? exp) (not (null? (cdddr exp))))

named-letから必要な要素を取り出すための手続きを以下のように定義しました。

(define (named-let-var exp) (cadr exp))
(define (named-let-bindings exp) (caddr exp))
(define (named-let-body exp) (cadddr exp))

また、define式を作成する必要があるので、それを行なう手続きも定義します。

(define (make-definition var value)
  (cons 'define (cons var value)))

named-letを変換する手順としては、まず反復プロセス手続きを定義し(define fib-iter)、その後に、その反復プロセスをキックするための処理を書きます(fib-iter 1 0 n)。これを順番に行なうために、beginを利用しました。

(define (let->combination exp)
  (if (named-let? exp)
      (make-bigin
       (cons (make-definition
              (cons (named-let-var exp)
                    (make-let->lambda-vars (named-let-bindings exp)))
              (named-let-body exp)))
       ((named-let-var exp) (make-let->lambda-exps (named-let-bindings exp))))
      (;;このelse部分は、問題4-6で書いた処理
       )))

make-let->lambda-vars/make-let->lambda-expsは、問題4-6で定義した、let式からbindingsの束縛変数・束縛された値をリスト化するための手続きです。これを利用して、defineの仮パラメータや、定義した手続きに渡すパラメータを作成しています。
問題4-9と10は飛ばしました。いずれにしても、この章に登場した問題に取り組んだ結果が正しかったかどうかを検証する術は、もう少し先へ進まないと手に入れることができなそうにありません。検証できるようになったら、これまでに作成した自前手続きが上手く動くかどうかを試してみたいと思っています。