SICP 4.1.6 Internal Definitions
ノート
内部定義。
テキストの評価器はdefineが出て来る度にその定義を環境に保存するが、それとは違う方法を取る事も出来る。
テキストの例のodd?のスコープは手続きf全体であって、fのスコープのうちodd?が定義されて以降ではない。と言う事はeven?とodd?はあたかも同時に手続きf内に定義されたかの様な動作をしなければならない。
テキストの実装ではたまたま問題なく動いている。と言うのは全てのdefineが出揃ってから手続きの本体が定義される約束にしているので、それらの手続きが使われる時には全て定義されているから。
一つの別の方法としてはdefineで関数を定義した時のlambdaへの変換で、本体内のdefineを全て探してletによる変数に変換してしまうと言うもの。set!で拘束する時には参照する変数そのものは必ず存在する事になる。
ただしこれは関数を定義した時に限って有効で、普通の変数ではやはり前方参照の様な事は実現出来ない。
更に別の方法としては文法としてあとから定義される変数（や手続き）を参照しては行けないと言うルールにする事も出来る。
Exercise 4.16
a.
(define (lookup-variable-value var env) (define (env-loop env) (if (eq? env the-empty-environment) (error "Unbound variable" var) (let ((val (dict-ref (first-frame env) var (lambda () (env-loop (enclosing-environment env)))))) (if (eq? val '*unassigned*) (error "The variable is not assigned yet:" var) val)))) (env-loop env))
動作確認
> (eval '(define a (quote *unassigned*)) the-global-environment) 'ok > (eval '(define b 2) the-global-environment) 'ok > (eval 'a the-global-environment) . . The variable is not assigned yet: a > (eval '(cons a b) the-global-environment) . . The variable is not assigned yet: a > (eval 'b the-global-environment) 2 >
b.
それこそinternal definitionをふんだんに使って
(define (scan-out-defines contents) (define (skip-null lst) (filter (lambda (v) (not (null? v))) lst)) (define (local-vars contents) (let ((vars (skip-null (map (lambda (exp) (if (definition? exp) (list (definition-variable exp) '(quote *unassigned*)) '())) contents)))) (if (> (length vars) 0) (list 'let vars) null))) (define (init-vars contents) (skip-null (map (lambda (exp) (if (definition? exp) (list 'set! (definition-variable exp) (definition-value exp)) '())) contents))) (define (body contents) (filter (lambda (exp) (not (definition? exp))) contents)) (let ((vars (local-vars contents))) (if (> (length vars) 0) (list (append vars (init-vars contents) (body contents))) (body contents))))
出力がちょっとややこしい。internal definitionがある時には全体をletで囲む必要があるのでリストが１段深くなる。
動作確認
> (scan-out-defines '((define (d e f) (cons e f)) (define (g h i) (cons h i)) (define j (+ i e)) (d b 1) (g c j))) '((let ((d '*unassigned*) (g '*unassigned*) (j '*unassigned*)) (set! d (lambda (e f) (cons e f))) (set! g (lambda (h i) (cons h i))) (set! j (+ i e)) (d b 1) (g c j))) > (scan-out-defines '((g c j))) '((g c j)) > (scan-out-defines '((g c j) (d e f))) '((g c j) (d e f)) >
quoteは扱いが難しく、内部でどうなっているのか分からないが、REPLが入力を解釈する時だけでなく出力の際にもquoteを解釈して出力してしまう模様。
> 'quote 'quote > (list 'quote) '(quote) > (list 'quote '*unassigned*) ''*unassigned* >
出力として(quote *unassigned*)とどうしても出せない。
c.
(define (make-procedure parameters body env) (list 'procedure parameters (scan-out-defines body) env))
- procedure-bodyはlambda定義の中のパラメータ以外の部分を取り出す関数であって、更にその中身を書き換えてしまうと言うのは単一責任の原則から外れて好ましくない。
- procedure-bodyは式を評価するとき以外にも呼ばれるので（こう言うケースがあるから単一責任であるべきなのだが）勝手に変換するのは不都合
動作確認。
> (driver-loop) ;;; M-Eval input: (define (f x) (define (even? n) (if (= n 0) true (odd? (- n 1)))) (define (odd? n) (if (= n 0) false (even? (- n 1)))) (if (even? x) (/ x 2) (/ (+ x 1) 2))) ;;; M-Eval value: ok ;;; M-Eval input: (f 10) ;;; M-Eval value: 5 ;;; M-Eval input: (f 11) ;;; M-Eval value: 6 ;;; M-Eval input: .
Exercise 4.17
defineをそのまま解釈した時の環境。
図では「sequential」な部分は表現されていないが、defineを評価する毎にu、vが環境に足されて行く。
scan outした時の環境（letが使用され、そのletはlambdaに展開される）
こちらは一つ余計な環境が作られた時点でu、v共に'*unassignedが割り当てられる。
余計なフレームはletを展開したlambdaを評価する時に作られる。
実質この二つに違いが現れない理由は、u、vを順番に作ってもいっぺんに作っても、
余分なフレームは作らずに名前を同時に作る。
「同時に」の意味次第だが、変数を初期化する段階で（値は何にしろ）全ての変数が定義されて見えている状態になっていれば良いのであれば、普通にdefineで変数を作って、初期化をその後に行えば良い。
(define (scan-out-defines contents) (define (skip-null lst) (filter (lambda (v) (not (null? v))) lst)) (define (local-vars contents) (skip-null (map (lambda (exp) (if (definition? exp) (list 'define (definition-variable exp) ''*unassigned*) '())) contents))) (define (init-vars contents) (skip-null (map (lambda (exp) (if (definition? exp) (list 'set! (definition-variable exp) (definition-value exp)) '())) contents))) (define (body contents) (filter (lambda (exp) (not (definition? exp))) contents)) (skip-null (append (local-vars contents) (init-vars contents) (body contents))))
実行結果
> (scan-out-defines '((define (d e f) (cons e f)) (define (g h i) (cons h i)) (define j (+ i e)) (d b 1) (g c j))) '((define d '*unassigned*) (define g '*unassigned*) (define j '*unassigned*) (set! d (lambda (e f) (cons e f))) (set! g (lambda (h i) (cons h i))) (set! j (+ i e)) (d b 1) (g c j)) > (scan-out-defines '((g c j))) '((g c j)) > (scan-out-defines '((g c j) (d e f))) '((g c j) (d e f)) >
但しこれはdefineを順番に評価して取り敢えず変数を作って行くだけなので、set!の順番を考慮しないと前方参照は当然出来ない。
Exercise 4.18
defineだとどうしても一つ一つの順番にしか定義出来ないのに対し、letは一応名前の定義を括弧で括って本文の前に持っているので、名前を同時に定義しているかの様に見えなくもない。そこでdefineは使わずに半ば無理矢理letだけで実現しようとした形。
solveを変換すると。
(define (solve f y0 dt) (let ((y '*unassigned*) (dy '*unassigned*)) (let ((a (integral (delay dy) y0 dt)) (b (stream-map f y))) (set! y a) (set! dy b)) y))
aの初期化の時点でdyはまだ*unassignedだが、ここはdelayによって評価は先送りされるので問題無し。
問題はbの初期化の方。こっちはstream-mapの引数としてまだ*unassignedのままのyを参照してしまうのでエラーになる。
Exercise 4.19
ちなみにRacketでテキストのコードを評価すると
> (let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10)) . . +: contract violation expected: number? given: #<undefined> argument position: 1st other arguments...: 10 >
となり、Alyssaの解釈と一致している。
数学的な考え方だと定義が書いてある順番に依存するべきではないと思うので、理想的にはEvaの様に解釈されるべき。
ブロックの本体よりも前に全てのdefineが記述されている前提であれば、手続きの定義だけでなく値の定義もdelayして、初めて使う所でforceしてあげれば良さそう。
> (let ((a 1)) (define (f x) (define b (delay (+ a x))) (define a 5) (+ a (force b))) (f 10)) 20 >
我々の評価器にはdelayもforceも実装していないので、これはそのままでは実装出来ないし、そもそもdelayとforceを自動的に組み込む必要があり、ちょっとこの段階では無理。
Exercise 4.20
a.
Exercise 4.18の様にletを二重に構える必要は無く、letで変数を*unassigned*で初期化した後、順にset!で初期化すれば良い。
(define (eval exp env) (cond ((self-evaluating? exp) exp) …中略 ((let? exp) (eval (let->combination exp) env)) ((let*? exp) (eval (let*->nested-lets exp) env)) ((letrec? exp) (eval (letrec->let exp) env)) …以下省略 (define (letrec? exp) (tagged-list? exp 'letrec)) (define (letrec-vars exp) (map car (cadr exp))) (define (letrec-inits exp) (map cadr (cadr exp))) (define (letrec-body exp) (cddr exp)) (define (letrec->let exp) (append (list 'let (map (lambda (sym) (list sym '(quote *unassigned*))) (letrec-vars exp))) (map (lambda (sym init) (list 'set! sym init)) (letrec-vars exp) (letrec-inits exp)) (letrec-body exp)))
動作確認。
> (letrec->let '(letrec ((even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))) (if (even? x) (/ x 2) (/ (+ x 1) 2)))) '(let ((even? '*unassigned*) (odd? '*unassigned*)) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) (if (even? x) (/ x 2) (/ (+ x 1) 2))) > (letrec->let '(letrec ((fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))))) (fact 10))) '(let ((fact '*unassigned*)) (set! fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1)))))) (fact 10)) > (eval '(define (f x) (letrec ((even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))) (if (even? x) (/ x 2) (/ (+ x 1) 2)))) the-global-environment) 'ok > (eval '(f 10) the-global-environment) 5 > (eval '(f 11) the-global-environment) 6 > (eval '(letrec ((fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))))) (fact 10)) the-global-environment) 3628800 >
defineがsequentialに見えるからletrecを使うのであれば、letrecは無理にletに展開しなくてもdefineに展開した方が余計なフレームを使わず、余計な変換もせず効率的な気がする。
b.
頭の整理：letではeven?とodd?の相互再帰が使えない理由は、lambda式を評価する時に定義されていない手続き等を参照する事（odd?が定義される前にeven?の定義としてodd?を使う事）に問題は無いが、そのlambdaで作った手続きが参照する環境はletのスコープの外側である為、let内で定義される値を参照出来ない事にある。letはlambdaに展開されて、初期化部分はlambdaの実引数として手続きを呼び出す前に評価されるので、その環境はlambdaの外側でありeven?とodd?と言う名前は存在しない。
Letrecを使った場合。
even?とodd?の手続きが双方が拘束されている環境を参照している。
Letを使った場合。
even?とodd?は互いへの参照を持っていない環境を参照しているのでeven?からodd?を呼び出す事は出来ない。
Exercise 4.21
やっぱり出て来たYコンビネータ。脚注にはY operatorと書いてある。
a.
FactorialをRacket上で動かしてみる。
> ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 10) 3628800 >
効率は兎も角、定義通りのフィボナッチ数だと
> ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (cond ((= k 0) 0) ((= k 1) 1) (else (+ (ft ft (- k 1)) (ft ft (- k 2)))))))) 10) 55 >
- 再帰する関数を、次に適用する関数を引数で受け取ってそれを適用する形に変更。
- 次に適用する時には、その次に適用出来る様に引数として自分が受け取った関数を渡す。
- 最初に適用する関数に、この再帰させる関数を渡す。
- 最初に適用する関数は、引数として渡された関数と更に必要な引数に対して渡された関数を適用する。
b.
> (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)))))) > (f 0) #t > (f 1) #f > (f 2) #t > (filter f '(0 1 2 3 4 5 6 7 8 9 10)) '(0 2 4 6 8 10) >
最初の関数は引数xに対してeven?として渡された関数を適用する。引数には次に適用出来る様にeven?とodd?も渡す。
even?とodd?に相当する関数は、次に適用するべき関数を引数として受け取る事、次に適用する時にこれらの関数も引数とする事以外は普通に記述する。
Louis Reasoner is confused by all this fuss about internal definitions. The way he sees it, if you don't like to use define inside a procedure, you can just use let.
Amazingly, Louis's intuition in exercise 4.20 is correct.
defineを使わないのは兎も角、letを使った訳ではないのにLouisの何が正しかったのだろうとも思うが、letをlambdaに展開するのと同様に、defineする名前を引数としてlambdaに変形して実引数として手続きを定義して渡すと言う同じ手法を取っている意味で「Letを使えば良い」と言うのであればそれは正しい様に思う。ただし引数として渡す手続きも自分自身を含めて必要な関数を全て引数で受け取る形に変換する必要がある。この変換をscan-out-definesで自動的に行うのは難しそう。関数が二つあって相互再帰しているパターンを検出とかしなければならないので。
