SICP 読書ノート#54 - 4.1.7 構文解析から実行を分離する (pp.234-237)
久しぶりの更新です。
恐ろしいことにSICPを読み始めて１年が経ってしまいました。ここの進みの遅さ。激しく自省。。
特にサボっていたわけではなく、§4.3の非決定性計算を読んでいるうちに継続と戯れていたらこっちの更新が滞ってしまってました。継続の概念はようやくぼんやり理解できたので、元に戻って進めたいと思います。
SchemeによるScheme評価器
前回までRubyで実装していましたが、§4.2 遅延評価、§4.3 非決定性計算までそれでついて行くのは大変だなと思い、Schemeでいちから実装し直す。
環境の実装をRacket組み込みのHash Tableで書き直したりと、自分なりにいくつか修正。
構文解析と実行の分離
構文解析と実行の分離はRubyでの実装でもさんざんやったので理解できているつもりだが、SICP本文ではこう書いてある。
上で実装した評価器は単純だが, 式の構文解析がその実行と差し込みになっているので効率が悪い. プログラムが多数回実行されるなら, 構文は多数回解析される. ... 構文解析が一回だけ実行されるよう配慮して, 評価器を遥かに効率よく変形することが出来る. 式と環境をとるevalを二つに分ける. 手続きanalyzeは式だけをとる. これは構文解析を実施し, 解析された式を実行する時になすべき仕事をカプセル化した新しい手続き, 実行手続き(execution procedure)を返す. 実行手続きは引数として環境をとり, 評価を完成する. こうすると実行手続きが何回呼び出されても, 一つの式についてanalyzeは一回だけしか呼び出されないので, 仕事は節約になる.
実際にどうなるか動かして見てみる。
racket@> ,enter "repl.scm" ;;; M-Eval input: (define (add x y) (+ x y)) analize: (define (add x y) (+ x y)) analize: (lambda (x y) (+ x y)) analize: (+ x y) analize: + analize: x analize: y eval-proc: #<procedure:eval-definition> ;;; M-Eval value: #<void> ;;; M-Eval input: (define (mul x y) (* x y)) analize: (define (mul x y) (* x y)) analize: (lambda (x y) (* x y)) analize: (* x y) analize: * analize: x analize: y eval-proc: #<procedure:eval-definition> ;;; M-Eval value: #<void> ;;; M-Eval input: (add 1 (mul 2 3)) analize: (add 1 (mul 2 3)) analize: add analize: 1 analize: (mul 2 3) analize: mul analize: 2 analize: 3 eval-proc: #<procedure:eval-application> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-number-value> eval-proc: #<procedure:eval-application> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-number-value> eval-proc: #<procedure:eval-number-value> apply-proc: #1=(procedure (x y) #<procedure:eval-application> #0=(#hash((add . (procedure (x y) #<procedure:eval-application> #0#)) (false . #<procedure:...aluator/repl.scm:19:33>) (+ . (primitive #<procedure:+>)) (- . (primitive #<procedure:->)) (* . (primitive #<procedure:*>)) (/ . (primitive #<procedure:/>)) (= . (primitive #<procedure:=>)) (mul . #1#) (true . #<procedure:...aluator/repl.scm:18:32>)) #hash())) (2 3) eval-proc: #<procedure:eval-application> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-variable> apply-proc: (primitive #<procedure:*>) (2 3) apply-proc: #0=(procedure (x y) #<procedure:eval-application> #1=(#hash((add . #0#) (false . #<procedure:...aluator/repl.scm:19:33>) (+ . (primitive #<procedure:+>)) (- . (primitive #<procedure:->)) (* . (primitive #<procedure:*>)) (/ . (primitive #<procedure:/>)) (= . (primitive #<procedure:=>)) (mul . (procedure (x y) #<procedure:eval-application> #1#)) (true . #<procedure:...aluator/repl.scm:18:32>)) #hash())) (1 6) eval-proc: #<procedure:eval-application> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-variable> apply-proc: (primitive #<procedure:+>) (1 6) ;;; M-Eval value: 7
先程のSICP本文の引用通りになっていることがわかる。
- analyzeによる構文解析が再帰降下的に行われ、実行手続きが返される
- evalによってまずこの実行手続きが評価される
- この評価からapplyによって引数が適用され、さらに手続きの評価が続くといった具合に、eval/applyの循環呼び出しがspecial formsかprimitive proceduresに簡約されるまで続く
- eval/applyのフェーズではanalyzeが呼び出されることはない
問題 4.22
letをサポートするように評価器を拡張する。
構文構文解析では、operatorがletの場合は構文変換を行うような分岐を追加する
(define (analyze exp) (display (format "analize: ~A ~%" exp)) (cond ((number? exp) (analyze-number-value exp)) ((string? exp) (analyze-string-value exp)) ((symbol? exp) (analyze-variable exp)) ;; special forms ((tagged-list? exp 'quote) (analyze-quoted exp)) ((tagged-list? exp 'set!) (analyze-assginment exp)) ((tagged-list? exp 'define) (analyze-definition exp)) ((tagged-list? exp 'if) (analyze-if exp)) ((tagged-list? exp 'lambda) (analyze-lambda exp)) ((tagged-list? exp 'begin) (analyze-begin exp)) ;; derived expressions ((tagged-list? exp 'let) (analyze (let->combination exp))) ;; 追加 ;; application ((pair? exp) (analyze-application exp)) (else (analyze-error exp))))
letからlambdaへの構文変換は前節と同様。
(define (let->combination exp) (let ((variables (map car (cadr exp))) (expressions (map cadr (cadr exp))) (body (cddr exp))) (cons (cons 'lambda (cons variables body)) expressions)))
実行結果。lambdaへ変換された後で実行手続きに変換される。
(let ((x 1) (y 2) (z 3)) (+ x y z)) analize: (let ((x 1) (y 2) (z 3)) (+ x y z)) analize: ((lambda (x y z) (+ x y z)) 1 2 3) analize: (lambda (x y z) (+ x y z)) analize: (+ x y z) analize: + analize: x analize: y analize: z analize: 1 analize: 2 analize: 3 eval-proc: #<procedure:eval-application> eval-proc: #<procedure:eval-lambda> eval-proc: #<procedure:eval-number-value> eval-proc: #<procedure:eval-number-value> eval-proc: #<procedure:eval-number-value> apply-proc: (procedure (x y z) #<procedure:eval-application> (#hash((false . #<procedure:...aluator/repl.scm:20:33>) (+ . (primitive #<procedure:+>)) (- . (primitive #<procedure:->)) (* . (primitive #<procedure:*>)) (/ . (primitive #<procedure:/>)) (= . (primitive #<procedure:=>)) (true . #<procedure:...aluator/repl.scm:19:32>)) #hash())) (1 2 3) eval-proc: #<procedure:eval-application> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-variable> eval-proc: #<procedure:eval-variable> apply-proc: (primitive #<procedure:+>) (1 2 3) ;;; M-Eval value: 6
問題 4.23
この問題はおもしろい。僕も最初はAlyssaの例のように実装していました。
(define (analyze-sequence-by-alyssa exps) (define (execute-sequence procs env) (cond ((null? (cdr procs)) ((car procs) env)) (else ((car procs) env) (execute-sequence (cdr procs) env)))) (let ((procs (map analyze exps))) (if (null? procs) (error "analyze sequence: empty sequence") (lambda (env) (execute-sequence procs env)))))
この例ではシーケンスの個々の処理は解析されるが、
Alyssaの並びの実行手続きは, 組み込まれた個々の実行手続きを呼び出すというよりは, それらを呼び出すために手続きの中をループしている. 実際は, 並びの個々の式は, 解析されるが, 並び自身は解析されない.
と本文にあるように、シーケンスそのものはリストのまま解析されない。
例えば、以下のようなコードは、
(begin <proc A> <proc B> <proc C> <proc D>)
以下のような実行手続きを生成するため、シーケンスそのものは実行時に解釈される。
(lambda (env) (execute-sequence (list (lambda (env) (<eval-proc A> env)) (lambda (env) (<eval-proc B> env)) (lambda (env) (<eval-proc C> env)) (lambda (env) (<eval-proc D> env)))))
本文のanalyze-sequence手続きでは、さらに踏み込んで以下のような実行手続きを生成する。
(lambda (env) (lambda (env) (lambda (env) (lambda (env) (lambda (env) (<eval-proc A> env)) (<eval-proc B> env)) (<eval-proc C> env)) (<eval-proc D> env)))
どちらも正しく動くけど、Alyssaの例では実行時にシーケンスの解析を行ってしまうので、本文の方がよりよい解析処理と言えるだろう。
次回は「§4.2 Schemeの変形 -- 遅延評価」から。
