開発環境
- OS X Lion - Apple(OS)
- Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
- プログラミング言語: MIT/GNU Scheme
計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.2(Scheme の変形 - 遅延評価)、4.2.2(遅延評価の解釈系)、評価器の修正、サンクの表現、問題 4.30を解いてみる。
その他参考書籍
問題 4.30
a.
for-eachでの並びの最初の式は、
((lambda (x) (newline) (display x)) 57)
これをeval(評価)したときの概要。
(apply-in-eval (actual-value '(lambda (x) (newline) (display x)) env)
'(57)
env)
(apply-in-eval (force-it (eval '(lambda (x) (newline) (display x))) env)
'(57)
env)
(apply-in-eval (force-it (make-procedure '(x)
'((newline) (display x)))
env)
'(57)
env)
(apply-in-eval (force-it '('procedure '(x)
'((newline) (display x))
env))
'(57)
env)
(apply-in-eval '('procedure '(x) '((newline) (display x)) env)
'(57)
env)
(eval-sequence '((newline) (display x))
(extend-environment '(x)
(list-of-delayed-args '(57) env)
env))
(newline)
(eval-sequence '((display x))
(extend-environment '(x)
(delay-it 57 env)
'()))
(eval '(display x)
(extend-environment '(x)
'('thunk 57 env)
'()))
(apply-in-eval (actual-value 'display
(extend-environment '(x)
'('thunk 57 env)
'()))
'(x)
(extend-environment '(x)
'('thunk 57 env)
'()))
(apply-in-eval (force-it (eval 'display
extend-environment '(x)
'('thunk 57 env)
'()))
'(x)
(extend-environment '(x)
'('thunk 57 env)
'()))
(display 57)
よってBenのfor-eachの振る舞いは正しい。(for-each手続きでリストの各要素に作用させる手続きのbodyが全て基本手続きだから、Cyの考えた問題は起こらなかった。)
確認。
コード(BBEdit)
sample.scm
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((begin? exp)
(eval-sequence (begin-actions exp) env))
((cond? exp) (eval (cond->if exp) env))
((application? exp)
(apply-in-eval (actual-value (operator exp) env)
(operands exp)
env))
(else
(error "Unknown expression type -- eval" exp))))
(define (actual-value exp env)
(force-it (eval exp env)))
;; 超循環表記ののapplyの定義の名前を替え、基本手続きの名前との衝突を避ける
(define (apply-in-eval procedure arguments env)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure
procedure
(list-of-arg-values arguments env)))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
(list-of-delayed-args arguments env)
(procedure-environment procedure))))
(else
(error
"Unknown procedure type -- APPLY" procedure))))
(define (list-of-arg-values exps env)
(if (no-operands? exps)
'()
(cons (actual-value (first-operand exps) env)
(list-of-arg-values (rest-operands exps)
env))))
(define (list-of-delayed-args exps env)
(if (no-operands? exps)
'()
(cons (delay-it (first-operand exps) env)
(list-of-delayed-args (rest-operands exps)
env))))
(define (delay-it exp env)
(list 'thunk exp env))
(define (thunk? obj)
(tagged-list? obj 'thunk))
(define (thunk-exp thunk) (cadr thunk))
(define (thunk-env thunk) (caddr thunk))
(define (evaluated-thunk? obj)
(tagged-list? obj 'evaluated-thunk))
(define (thunk-value evaluated-thunk) (cadr evaluated-thunk))
(define (force-it obj)
(if (thunk? obj)
(actual-value (thunk-exp obj) (thunk-env obj))
obj))
(define (eval-if exp env)
(if (true? (actual-value (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))
(define (eval-sequence exps env)
(cond ((last-exp? exps) (eval (first-exp exps) env))
(else (eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))
(define (eval-assignment exp env)
(set-variable-value! (assignment-variable exp)
(eval (assignment-value exp) env)
env)
'ok)
(define (eval-definition exp env)
(define-variable! (definition-variable exp)
(eval (definition-value exp) env)
env)
'ok)
(define (self-evaluating? exp)
(cond ((number? exp) true)
((string? exp) true)
(else false)))
(define (variable? exp) (symbol? exp))
(define (quoted? exp)
(tagged-list? exp 'quote))
(define (text-of-quotation exp) (cadr exp))
(define (tagged-list? exp tag)
(if (pair? exp)
(eq? (car exp) tag)
false))
(define (assignment? exp)
(tagged-list? exp 'set!))
(define (assignment-variable exp) (cadr exp))
(define (assignment-value exp) (caddr exp))
(define (definition? exp)
(tagged-list? exp 'define))
(define (definition-variable exp)
(if (symbol? (cadr exp))
(cadr exp)
(caadr exp)))
(define (definition-value exp)
(if (symbol? (cadr exp))
(caddr exp)
(make-lambda (cdadr exp)
(cddr exp))))
(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))
(define (make-lambda parameters body)
(cons 'lambda (cons parameters body)))
(define (if? exp) (tagged-list? exp 'if))
(define (if-predicate exp) (cadr exp))
(define (if-consequent exp) (caddr exp))
(define (if-alternative exp)
(if (not (null? (cddr exp)))
(cadddr exp)
'false))
(define (make-if predicate consequent alternative)
(list 'if predicate consequent alternative))
(define (begin? exp) (tagged-list? exp 'begin))
(define (begin-actions exp) (cdr exp))
(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))
(define (sequence->exp seq)
(cond ((null? seq) seq)
((last-exp? seq) (first-exp seq))
(else (make-begin seq))))
(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))
(define (cond? exp) (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define (cond-else-clause? clause)
(eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) (car clause))
(define (cond-actions clause) (cdr clause))
(define (cond->if exp)
(expand-clauses (cond-clauses exp)))
(define (expand-clauses clauses)
(if (null? clauses)
'false
(let ((first (car clauses))
(rest (cdr clauses)))
(if (cond-else-clause? first)
(if (null? rest)
(sequence->exp (cond-actions first))
(error "ELSE clause isn't last -- COND->IF"
clauses))
(make-if (cond-predicate first)
(sequence->exp (cond-actions first))
(expand-clauses rest))))))
(define (true? x)
(not (eq? x false)))
(define (false? x)
(eq? x false))
(define (make-procedure parameters body env)
(list 'procedure parameters body env))
(define (compound-procedure? p)
(tagged-list? p 'procedure))
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))
(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(define the-empty-environment '())
(define (make-frame variables values)
(cons variables values))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(define (add-binding-to-frame! var val frame)
(set-car! frame (cons var (car frame)))
(set-cdr! frame (cons val (cdr frame))))
(define (extend-environment vars vals base-env)
(if (= (length vars) (length vals))
(cons (make-frame vars vals) base-env)
(if (< (length vars) (length vals))
(error "Too many arguments supplied" vars vals)
(error "Too few arguments supplied" vars vals))))
(define (lookup-variable-value var env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(let ((val (car vals)))
(if (eq? val '*unassigned)
(error "Unassigned variable" var)
val)))
(else (scan(cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))
(define (set-variable-value! var val env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable -- SET!" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))
(define (define-variable! var val env)
(let ((frame (first-frame env)))
(define (scan vars vals)
(cond ((null? vars)
(add-binding-to-frame! var val frame))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(scan (frame-variables frame)
(frame-values frame))))
(define (setup-environment)
(let ((initial-env
(extend-environment (primitive-procedure-names)
(primitive-procedure-objects)
the-empty-environment)))
(define-variable! 'true true initial-env)
(define-variable! 'false false initial-env)
initial-env))
(define (primitive-procedure? proc)
(tagged-list? proc 'primitive))
(define (primitive-implementation proc) (cadr proc))
(define primitive-procedures
(list (list 'car car)
(list 'cdr cdr)
(list 'cons cons)
(list 'null? null?)
(list '* *)
(list '+ +)
(list '- -)
(list '/ /)
(list '< <)
(list '= =)
(list '> >)
(list 'apply apply)
(list 'atan atan)
(list 'cos cos)
(list 'display display)
(list 'eq? eq?)
(list 'error error)
(list 'eval eval)
(list 'list list)
(list 'log log)
(list 'max max)
(list 'min min)
(list 'newline newline)
(list 'not not)
(list 'number? number?)
(list 'pair? pair?)
(list 'quotient quotient)
;; (list 'random random)
(list 'read read)
(list 'remainder remainder)
(list 'round round)
;; (list 'runtime runtime)
(list 'set-car! set-car!)
(list 'set-cdr! set-cdr!)
(list 'sin sin)
(list 'symbol? symbol?)
(list 'vector-ref vector-ref)
(list 'vector-set! vector-set!)))
(define (primitive-procedure-names)
(map car primitive-procedures))
(define (primitive-procedure-objects)
(map (lambda (proc) (list 'primitive (cadr proc)))
primitive-procedures))
(define (apply-primitive-procedure proc args)
(apply
(primitive-implementation proc) args))
(define input-prompt ";;; L-Eval input:")
(define output-prompt ";;; L-Eval value:")
(define (driver-loop)
(prompt-for-input input-prompt)
(let ((input (read)))
(let ((output
(actual-value input the-global-environment)))
(announce-output output-prompt)
(user-print output)))
(driver-loop))
(define (prompt-for-input string)
(newline) (newline) (display string) (newline))
(define (announce-output string)
(newline) (display string) (newline))
(define (user-print object)
(if (compound-procedure? object)
(display (list 'compound-procedure?
(procedure-parameters object)
(procedure-body object)
'<procedure-env>))
(display object)))
(define the-global-environment (setup-environment))
(driver-loop)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.
Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Image saved on Friday April 13, 2012 at 9:02:52 AM
Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
Edwin 3.116
1 ]=> (load "./sample.scm")
;Loading "./sample.scm"...
;;; L-Eval input:
(define (for-each proc items)
(if (null? items)
'done
(begin (proc (car items))
(for-each proc (cdr items)))))
;;; L-Eval value:
ok
;;; L-Eval input:
(for-each (lambda (x) (newline) (display x))
(list 57 321 88))
57
321
88
;;; L-Eval value:
done
;;; L-Eval input:
End of input stream reached.
Moriturus te saluto.
$
b.
元々のeval-sequenceでは(p1 1)の値は(list 1 2)、(p2 1)の値は1。
eval-sequenceへCyの提案する変更での(p1 1)の値は(list 1 2)、(p2 1)の値は(list 1 2)。
確認。
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.
Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Image saved on Friday April 13, 2012 at 9:02:52 AM
Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
Edwin 3.116
1 ]=> (load "./sample.scm")
;Loading "./sample.scm"...
;;; L-Eval input:
(define (p1 x)
(set! x (cons x '(2)))
x)
;;; L-Eval value:
ok
;;; L-Eval input:
(p1 1)
;;; L-Eval value:
(1 2)
;;; L-Eval input:
(define (p2 x)
(define (p e)
e
x)
(p (set! x (cons x '(2)))))
;;; L-Eval value:
ok
;;; L-Eval input:
(p2 1)
;;; L-Eval value:
1
;;; L-Eval input:
End of input stream reached.
Moriturus te saluto.
eval-sequence手続きの修正。(REPLで手続きを修正できるように、上記のコードから最後の(driver-loop)を削除。)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.
Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Image saved on Friday April 13, 2012 at 9:02:52 AM
Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
Edwin 3.116
1 ]=> (load "./sample.scm")
;Loading "./sample.scm"... done
;Value: the-global-environment
1 ]=>
(define (eval-sequence exps env)
(cond ((last-exp? exps) (eval (first-exp exps) env))
(else (actual-value (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))
;Value: eval-sequence
1 ]=>
(driver-loop)
;;; L-Eval input:
(define (p1 x)
(set! x (cons x '(2)))
x)
;;; L-Eval value:
ok
;;; L-Eval input:
(p1 1)
;;; L-Eval value:
(1 2)
;;; L-Eval input:
(define (p2 x)
(define (p e)
e
x)
(p (set! x (cons x '(2)))))
;;; L-Eval value:
ok
;;; L-Eval input:
(p2 1)
;;; L-Eval value:
(1 2)
;;; L-Eval input:
End of input stream reached.
Moriturus te saluto.
c.
Cyの提案したeval-sequenceに変更する前も変更後も、aの例では並びの全ての式が評価されることに変わりはないからaの例の振る舞いに影響しない。
d.
遅延評価器で並びはCyの解決法よりも本文の解決法の方ががよさそう。無駄に並びを評価することも無く効率的だし、評価を強制することにより、並びの評価だけ遅延評価では無くなってしまう。(ただ、両方いずれの方法を指定して扱えるような解決法がより柔軟性があって、複雑な副作用も気にせずに良くなり望ましいかも。)
0 コメント:
コメントを投稿