約 2,744,757 件
https://w.atwiki.jp/sicpstudygroup/pages/90.html
SICP naga Exercise 5.7 (define expt-a (make-machine (continue n b val) (list (list = =) (list - -) (list * *)) (machine (assign continue (label expt-done)) expt-loop (test (op =) (reg n) (const 0)) (branch (label immediate-answer)) (save continue) (assign continue (label afterexpt)) (assign n (op -) (reg n) (const 1)) (goto (label expt-loop)) afterexpt (restore continue) (assign val (op *) (reg b) (reg val)) (goto (reg continue)) immediate-answer (assign val (const 1)) (goto (reg continue)) expt-done) )) (set-register-contents! expt-a b 2) (set-register-contents! expt-a n 5) (start expt-a) ;;gosh (get-register-contents expt-a val) ;;32 (define expt-b (make-machine (counter product n b) (list (list = =) (list - -) (list * *)) (machine (assign counter (reg n)) (assign product (const 1)) expt-loop (test (op =) (reg counter) (const 0)) (branch (label expt-done)) (assign counter (op -) (reg counter) (const 1)) (assign product (op *) (reg b) (reg product)) (goto (label expt-loop)) expt-done) )) (set-register-contents! expt-b b 2) (set-register-contents! expt-b n 6) (start expt-b) ;;gosh (get-register-contents expt-b product) ;;64 Exercise 5.8 (define ex5.8 (make-machine (a) (list ()) (start (goto (label here)) here (assign a (const 3)) (goto (label there)) here (assign a (const 4)) (goto (label there)) there) )) (start ex5.8) ;;gosh (get-register-contents ex5.8 a) ;;3 ;;; extract-labels で同じラベルがあるかどうかチェックする。 (define (extract-labels text receive) (if (null? text) (receive () ()) (extract-labels (cdr text) (lambda (insts labels) (let ((next-inst (car text))) (if (symbol? next-inst) (let ((p (assoc next-inst labels))) (if p (error "Duplicate label -- ASSEMBLE" next-inst) (receive insts (cons (make-label-entry next-inst insts) labels)))) (receive (cons (make-instruction next-inst) insts) labels))))))) ;;gosh (define ex5.8 ;; (make-machine ;; (a) ;; (list ()) ;; (start ;; (goto (label here)) ;; here ;; (assign a (const 3)) ;; (goto (label there)) ;; here ;; (assign a (const 4)) ;; (goto (label there)) ;; there) ;; )) ;;*** ERROR Duplicate label -- ASSEMBLE here Exercise 5.9 ;;; make-operation-exp で operand が label の時はエラーとする。 (define (make-operation-exp exp machine labels operation) (let ((op (lookup-prim (operation-exp-op exp) operation)) (aprocs (map (lambda (e) (if (label-exp? e) (error "Operations can be used only with registers and constants -- ASSEMBLE" exp) (make-primitive-exp e machine labels))) (operation-exp-operands exp)))) (lambda () (apply op (map (lambda (p) (p)) aprocs))))) (define ex5.9 (make-machine (a) (list (list + +)) (l (assign a (op +) (label l) (const 1)) ) )) ;;gosh (load "ex5_9") ;;*** ERROR Operations can be used only with registers and constants -- ASSEMBLE ((op +) (label l) (const 1)) Exercise 5.10 ;;; syntax って assembler の変更で対応できる範囲という事でいいのかな? ;;; という事で、 ;;; label にオフセット(省略可)を指定できるように syntax を変更する。 ;;; (label label-name ) - (label label-name offset ) ;;; ;;; offset が + の時は、label-name から求めた inst を進める。 ;;; - の時は2つのポインタを使い、controller-text の最初に ;;; 強制的に埋め込んだ label位置に ポインタを設定し、一方を ;;; -offset だけ進めた後、label-name から 求めた inst に先に ;;; 進めたポインタがたどり着くまで2つのポインタを進める。 (define (assemble controller-text machine) (set! contoller-text (cons **main** controller-text)) (extract-labels controller-text (lambda (insts labels) (update-insts! insts labels machine) insts))) (define (label-exp-label exp) (cdr exp)) ;label-exp-lable-expb (define (label-name label-expb) (car label-expb)) (define (label-offset label-expb) (cond ((null? (cdr label-expb)) 0) ((number? (cadr label-expb)) (cadr label-expb)) (else (error "Offset must be number -- LABEL-EXPB" label-expb)))) (define (lookup-label labels label-expb) (define (forward insts n) (if (= n 0) insts (if (null? (cdr insts)) (error "Out of range -- ASSEMLBE" label-expb) (forward (cdr insts) (- n 1))))) (define (forward2 insts lead target) (if (eq? lead target) insts (if (null? (cdr lead)) (error "Out of range -- ASSEMBLE" label-expb) (forward2 (cdr insts) (cdr lead) target)))) (let ((name (label-name label-expb)) (offset (label-offset label-expb)) (insts ())) (let ((val (assoc name labels))) (if val (set! insts (cdr val)) (error "Undefined label -- ASSEMBLE" name))) (if ( = offset 0) (forward insts offset) (let ((ip (cdr (assoc **main** labels)))) (forward2 ip (forward ip (* offset -1)) insts))))) ;; test program (define ex5.10 (make-machine (a continue) (list (list + +) (list display display) (list newline newline)) (ex5.10 (assign a (const 0)) (assign continue (label t1e)) (goto (label s)) t1e (assign a (const 0)) (assign continue (label t2e)) (goto (label s -1)) t2e (assign a (const 0)) (assign continue (label t3e)) (goto (label s 1)) t3e (goto (label ex5.10.done)) ; (assign a (op +) (reg a) (const 1)) s (assign a (op +) (reg a) (const 1)) (assign a (op +) (reg a) (const 1)) (perform (op display) (reg a)) (perform (op newline)) (goto (reg continue)) ; ex5.10.done) )) ;;gosh (start ex5.10) ;;2 ;;3 ;;1 ;;done Exercise 5.11 ;;; a ;;; afterfib-n-2 の直後の ;;; (assign n (reg val)) (restore val) ;;; を ;;; (restore n) ;;; としても同じ結果を得ることができる。 ;;; b と c ;;; stack の方法を stack-mode に保持する。 ;;; a オリジナル b レジスタチェック c レジスタ毎のスタック (define stack-mode a) ;;; register にスタックを設ける。 (define (make-register name) (let ((contents *unassigned*) (stack (make-stack))) (define (dispatch message) (cond ((eq? message get) contents) ((eq? message set) (lambda (value) (set! contents value))) ((eq? message pop) (stack pop)) ((eq? message push) (stack push)) ((eq? message initialize) (stack initialize)) (else error "Unknown request -- REGISTER" message))) dispatch)) ;;; make-new-machine のオペレーション定義 initialize-stack を変更 (list initialize-stack (cond ((eq? stack-mode c) (lambda () (for-each (lambda (regpair) ((cdr regpair) initialize)) register-table))) (else (lambda () (stack initialize))))) ;;; make-save の変更 (define (make-save inst machine stack pc labels) (let ((reg (get-register machine (stack-inst-reg-name inst)))) (lambda () (cond ((eq? stack-mode a) (push stack (get-contents reg))) ((eq? stack-mode b) (push stack (get-contents reg)) (push stack (stack-inst-reg-name inst))) ((eq? stack-mode c) (push reg (get-contents reg)))) (advance-pc pc)))) ;;; make-retore の変更 (define (make-restore inst machine stack pc labels) (let ((reg (get-register machine (stack-inst-reg-name inst)))) (lambda () (cond ((eq? stack-mode a) (set-contents! reg (pop stack))) ((eq? stack-mode b) (let ((reg-name (pop stack))) (if (equal? reg-name (stack-inst-reg-name inst)) (set-contents! reg (pop stack)) (error "Pop-value was saved from " reg-name inst)))) ((eq? stack-mode c) (set-contents! reg (pop reg)))) (advance-pc pc)))) ;;; b の test program (define ex5.11.b (make-machine (a b) (list (list display display) (list newline newline)) (ex5.11.b (assign a (const 11)) (save a) (restore a) (perform (op display) (reg a)) (perform (op newline)) (save a) (restore b) (perform (op display) (reg b)) (perform (op newline)) ) )) ;;gosh (start ex5.11.b) ;;11 ;;*** ERROR Pop-value was saved from a (restore b) ;;Stack Trace ;;; c の test program (define ex5.11.c (make-machine (a b) (list (list display display) (list newline newline)) (ex5.11.c (assign a (const 1)) (assign b (const 2)) (save a) (save b) (assign a (const 10)) (assign b (const 10)) (restore a) (restore b) (perform (op display) (reg a)) (perform (op newline)) (perform (op display) (reg b)) (perform (op newline)) ) )) ;;gosh (start ex5.11.c) ;;1 ;;2 Exercise 5.12 ;;; make-new-machine の dispatch に以下を追加 ((eq? message insts) the-instruction-sequence) ;;; コマンド追加 (define (static-analyze machine) (s-analyze (machine insts))) ;;; insts から重複のない instuction text listを得る。 (define (unique insts) (let ((uinstsl ())) (for-each (lambda (inst) (if (not (member (instruction-text inst) uinstsl)) (set! uinstsl (cons (instruction-text inst) uinstsl)))) insts) uinstsl)) (define (analyze-report-inst title keys) (display title) (newline) (for-each (lambda (key) (display " ") (display (car key)) (newline) (for-each (lambda (text) (display " ") (display text) (newline)) (rsort (cdr key)))) (rsort keys))) (define (analyze-report-reg title regs) (display title) (newline) (for-each (lambda (reg) (display " ") (display reg)) (rsort regs)) (newline)) ;;; リストをソートする。 (define (rsort items) (sort items (lambda (x y) (= (comp x y) -1)))) (define (comp x y) (cond ((and (null? x) (null? y)) 0) ((null? x) -1) ((null? y) 1) ((and (number? x) (number? y)) (compare x y)) ((number? x) -1) ((number? y) 1) ((and (string? x) (string? y)) (compare x y)) ((string? x) -1) ((string? y) 1) ((and (symbol? x) (symbol? y)) (compare (symbol- string x) (symbol- string y))) ((symbol? x) -1) ((symbol? y) 1) ((and (pair? x) (pair? y)) (let ((f (comp (car x) (car y)))) (if (= f 0) (comp (cdr x) (cdr y)) f))) (else 1) )) (define (s-analyze insts) (let ((analyze-1 ()) ; instructions (analyze-2 ()) ; registers refed by goto (analyze-3 ()) ; registers saved or restored (analyze-4 ())) ; assign instructions (for-each (lambda (text) (let ((insttype (assoc (car text) analyze-1))) (if (not insttype) (begin (set! insttype (cons (car text) ())) (set! analyze-1 (cons insttype analyze-1)))) (set-cdr! insttype (cons text (cdr insttype)))) (if (and (eq? (car text) goto) (register-exp? (goto-dest text))) (set! analyze-2 (cons (register-exp-reg (goto-dest text)) analyze-2))) (if (or (eq? (car text) save) (eq? (car text) restore)) (let ((reg (memq (stack-inst-reg-name text) analyze-3))) (if (not reg) (set! analyze-3 (cons (stack-inst-reg-name text) analyze-3))))) (if (eq? (car text) assign) (let ((reg (assoc (assign-reg-name text) analyze-4))) (if (not reg) (begin (set! reg (cons (assign-reg-name text) ())) (set! analyze-4 (cons reg analyze-4)))) (set-cdr! reg (cons text (cdr reg))))) ) (unique insts)) (analyze-report-inst ";;Instructions" analyze-1) (analyze-report-reg ";;Regs-refed-by-goto" analyze-2) (analyze-report-reg ";;Regs-refed-by-save-restore" analyze-3) (analyze-report-inst ";;Regs-source" analyze-4) )) ;; test program (define fib (make-machine (continue n val) (list (list ) (list - -) (list + +)) (machine (assign continue (label fib-done)) fib-loop (test (op ) (reg n) (const 2)) (branch (label immediate-answer)) ;; set up to compute Fib(n - 1) (save continue) (assign continue (label afterfib-n-1)) (save n) ; save old value of n (assign n (op -) (reg n) (const 1)); clobber n to n - 1 (goto (label fib-loop)) ; perform recursive call afterfib-n-1 ; upon return, val contains Fib(n - 1) (restore n) (restore continue) ;; set up to compute Fib(n - 2) (assign n (op -) (reg n) (const 2)) (save continue) (assign continue (label afterfib-n-2)) (save val) ; save Fib(n - 1) (goto (label fib-loop)) afterfib-n-2 ; upon return, val contains Fib(n - 2) (assign n (reg val)) ; n now contains Fib(n - 2) (restore val) ; val now contains Fib(n - 1) (restore continue) (assign val ; Fib(n - 1) + Fib(n - 2) (op +) (reg val) (reg n)) (goto (reg continue)) ; return to caller, answer is in val immediate-answer (assign val (reg n)) ; base case Fib(n) = n (goto (reg continue)) fib-done) )) ;;gosh (static-analyze fib) ;;;;Instructions ;; assign ;; (assign continue (label afterfib-n-1)) ;; (assign continue (label afterfib-n-2)) ;; (assign continue (label fib-done)) ;; (assign n (op -) (reg n) (const 1)) ;; (assign n (op -) (reg n) (const 2)) ;; (assign n (reg val)) ;; (assign val (op +) (reg val) (reg n)) ;; (assign val (reg n)) ;; branch ;; (branch (label immediate-answer)) ;; goto ;; (goto (label fib-loop)) ;; (goto (reg continue)) ;; restore ;; (restore continue) ;; (restore n) ;; (restore val) ;; save ;; (save continue) ;; (save n) ;; (save val) ;; test ;; (test (op ) (reg n) (const 2)) ;;;;Regs-refed-by-goto ;; continue ;;;;Regs-refed-by-save-restore ;; continue n val ;;;;Regs-source ;; continue ;; (assign continue (label afterfib-n-1)) ;; (assign continue (label afterfib-n-2)) ;; (assign continue (label fib-done)) ;; n ;; (assign n (op -) (reg n) (const 1)) ;; (assign n (op -) (reg n) (const 2)) ;; (assign n (reg val)) ;; val ;; (assign val (op +) (reg val) (reg n)) ;; (assign val (reg n)) Exercise 5.13 ;;; make-new-machine の内部定義手続き lookup-register を register ;;; が見つからなかったら作るよう変更する。 (define (lookup-register name) (let ((val (assoc name register-table))) (if val (cadr val) (begin (allocate-register name) (lookup-register name))))) ;; test program (define expt-b (make-machine () (list (list = =) (list - -) (list * *)) (machine (assign counter (reg n)) (assign product (const 1)) expt-loop (test (op =) (reg counter) (const 0)) (branch (label expt-done)) (assign counter (op -) (reg counter) (const 1)) (assign product (op *) (reg b) (reg product)) (goto (label expt-loop)) expt-done) )) (set-register-contents! expt-b b 2) (set-register-contents! expt-b n 6) ;;gosh (start expt-b) ;;done ;;gosh (get-register-contents expt-b product) ;;64 Exercise 5.14 (define n! (make-machine (continue n val) (list (list = =) (list - -) (list * *)) (machine (assign continue (label fact-done)) ; set up final return address fact-loop (test (op =) (reg n) (const 1)) (branch (label base-case)) ;; Set up for the recursive call by saving n and continue. ;; Set up continue so that the computation will continue ;; at after-fact when the subroutine returns. (save continue) (save n) (assign n (op -) (reg n) (const 1)) (assign continue (label after-fact)) (goto (label fact-loop)) after-fact (restore n) (restore continue) (assign val (op *) (reg n) (reg val)) ; val now contains n(n - 1)! (goto (reg continue)) ; return to caller base-case (assign val (const 1)) ; base case 1! = 1 (goto (reg continue)) ; return to caller fact-done) )) (define (ex5.14 num) (define (iter c) (if ( c num) done (begin ((n! stack) initialize) (set-register-contents! n! n c) (start n!) (format #t "n ~2d n! ~8d" c (get-register-contents n! val)) (display " ") ((n! stack) print-statistics) (iter (+ c 1))))) (iter 1)) ;;gosh (ex5.14 10) ;;n 1 n! 1 (total-pushes = 0 maximum-depth = 0) ;;n 2 n! 2 (total-pushes = 2 maximum-depth = 2) ;;n 3 n! 6 (total-pushes = 4 maximum-depth = 4) ;;n 4 n! 24 (total-pushes = 6 maximum-depth = 6) ;;n 5 n! 120 (total-pushes = 8 maximum-depth = 8) ;;n 6 n! 720 (total-pushes = 10 maximum-depth = 10) ;;n 7 n! 5040 (total-pushes = 12 maximum-depth = 12) ;;n 8 n! 40320 (total-pushes = 14 maximum-depth = 14) ;;n 9 n! 362880 (total-pushes = 16 maximum-depth = 16) ;;n 10 n! 3628800 (total-pushes = 18 maximum-depth = 18) ;;done Exercise 5.15 ;;; make-new-machine に追加 ;;ローカル変数追加 (instruction-counter 0) ;;内部定義手続き execute の末尾再帰の前に追加 (set! instruction-counter (+ instruction-counter 1)) ;;内部定義手続き追加 (define (inst-count) (let ((cnt instruction-counter)) (set! instruction-counter 0) cnt)) ;;メッセージ受付追加 ((eq? message instruction-count) (inst-count)) ;;; test program (define icnt (make-machine (n) (list (list = =) (list - -)) (machine loop (test (op =) (reg n) (const 1)) (branch (label loop-end)) (assign n (op -) (reg n) (const 1)) (goto (label loop)) loop-end) )) (define (ex5.15 num) (define (iter c) (if ( c num) done (begin (set-register-contents! icnt n c) (start icnt) (format #t "n ~d instruction-count ~d~%" c (icnt instruction-count)) (iter (+ c 1))))) (iter 1)) ;;gosh (ex5.15 5) ;;n 1 instruction-count 2 ;;n 2 instruction-count 6 ;;n 3 instruction-count 10 ;;n 4 instruction-count 14 ;;n 5 instruction-count 18 ;;done Exercise 5.16 ;;; (trace machine on/ off) ;;; make-new-machine に追加 ;;ローカル変数追加 (trace off) ;;内部定義手続き execute の instruction の実行の前に追加 (if (eq? trace on) (trace-out (car insts))) ;;メッセージ受付追加 ((eq? message trace) (lambda (mode) (set! trace mode))) ;;; コマンドとトレース出力追加 (define (trace machine mode) (if (or (eq? mode on) (eq? mode off)) ((machine trace) mode) (else (error "Mode must be on/ off" mode)))) (define (trace-out inst) (format #t "trace ~s~%" (instruction-text inst))) ;;; test program (define icnt (make-machine (n) (list (list = =) (list - -)) (loop (test (op =) (reg n) (const 1)) (branch (label loop-end)) (assign n (op -) (reg n) (const 1)) (goto (label loop)) loop-end) )) (define (ex5.16) (set-register-contents! icnt n 1) (start icnt) (format #t "n 1 instruction-count ~d~%" (icnt instruction-count)) ; (trace icnt on) (set-register-contents! icnt n 2) (start icnt) (format #t "n 2 instruction-count ~d~%" (icnt instruction-count)) ; (trace icnt off) (set-register-contents! icnt n 3) (start icnt) (format #t "n 3 instruction-count ~d~%" (icnt instruction-count)) ) ;;gosh (ex5.16) ;;n 1 instruction-count 2 ;;trace (test (op =) (reg n) (const 1)) ;;trace (branch (label loop-end)) ;;trace (assign n (op -) (reg n) (const 1)) ;;trace (goto (label loop)) ;;trace (test (op =) (reg n) (const 1)) ;;trace (branch (label loop-end)) ;;n 2 instruction-count 6 ;;n 3 instruction-count 10 ;;# undef Exercise 5.17 ;;; label 出力のため inst に label 情報を含める。 ;;; inst を ((text . proc) label-name1 ...) の形式にし、、 ;;; make-instruction, instruction-text, instruction-execution-proc, ;;; set-instruction-execution-proc!, make-label-entry を変更, ;;; instruction-labels を追加する。 (define (make-instruction text) (cons (cons text ()) ())) (define (instruction-text inst) (caar inst)) (define (instruction-execution-proc inst) (cdar inst)) (define (instruction-labels inst) (cdr inst)) (define (set-instruction-execution-proc! inst proc) (set-cdr! (car inst) proc)) (define (make-label-entry label-name insts) (let ((lentry (cons label-name insts))) (if (and (not (null? insts)) (not (eq? label-name **main**))) (set-cdr! (car insts) (cons label-name (instruction-labels (car insts))))) lentry)) ;;; 5.16 で作成した trace-out を変更する。 (define (trace-out inst) (if (not (null? (instruction-labels inst))) (for-each (lambda (x) (format #t "trace ~s~%" x)) (instruction-labels inst))) (format #t "trace ~s~%" (instruction-text inst))) ;;; test program (define expt-a (make-machine (continue n b val) (list (list = =) (list - -) (list * *)) (machine (assign continue (label expt-done)) expt-loop (test (op =) (reg n) (const 0)) (branch (label immediate-answer)) (save continue) (assign continue (label afterexpt)) (assign n (op -) (reg n) (const 1)) (goto (label expt-loop)) afterexpt (restore continue) (assign val (op *) (reg b) (reg val)) (goto (reg continue)) immediate-answer (assign val (const 1)) (goto (reg continue)) expt-done) )) (trace expt-a on) (set-register-contents! expt-a b 2) (set-register-contents! expt-a n 2) ;;gosh (start expt-a) ;;trace machine ;;trace (assign continue (label expt-done)) ;;trace expt-loop ;;trace (test (op =) (reg n) (const 0)) ;;trace (branch (label immediate-answer)) ;;trace (save continue) ;;trace (assign continue (label afterexpt)) ;;trace (assign n (op -) (reg n) (const 1)) ;;trace (goto (label expt-loop)) ;;trace expt-loop ;;trace (test (op =) (reg n) (const 0)) ;;trace (branch (label immediate-answer)) ;;trace (save continue) ;;trace (assign continue (label afterexpt)) ;;trace (assign n (op -) (reg n) (const 1)) ;;trace (goto (label expt-loop)) ;;trace expt-loop ;;trace (test (op =) (reg n) (const 0)) ;;trace (branch (label immediate-answer)) ;;trace immediate-answer ;;trace (assign val (const 1)) ;;trace (goto (reg continue)) ;;trace afterexpt ;;trace (restore continue) ;;trace (assign val (op *) (reg b) (reg val)) ;;trace (goto (reg continue)) ;;trace afterexpt ;;trace (restore continue) ;;trace (assign val (op *) (reg b) (reg val)) ;;trace (goto (reg continue)) ;;done Exercise 5.18 ;;; (register-trace machine regisetr-name on/ off) ;;; make-register の引数 name はこのために用意されていたのか? ;;; make-register 変更 (define (make-register name) (let ((contents *unassigned*) (stack (make-stack)) (trace off)) (define (dispatch message) (cond ((eq? message get) contents) ((eq? message set) (lambda (value) (if (eq? trace on) (format #t "reg [~s] ~s- ~s~%" name contents value)) (set! contents value))) ((eq? message pop) (stack pop)) ((eq? message push) (stack push)) ((eq? message initialize) (stack initialize)) ((eq? message trace) (lambda (mode) (set! trace mode))) (else error "Unknown request -- REGISTER" message))) dispatch)) ;;; 新規 (define (set-register-trace-mode! register mode) (if (or (eq? mode on) (eq? mode off)) ((register trace) mode) (else (error "Mode must be on/ off" mode)))) (define (register-trace machine register-name mode) (set-register-trace-mode! (get-register machine register-name) mode)) ;;; test program (define expt-a (make-machine (continue n b val) (list (list = =) (list - -) (list * *)) (machine (assign continue (label expt-done)) expt-loop (test (op =) (reg n) (const 0)) (branch (label immediate-answer)) (save continue) (assign continue (label afterexpt)) (assign n (op -) (reg n) (const 1)) (goto (label expt-loop)) afterexpt (restore continue) (assign val (op *) (reg b) (reg val)) (goto (reg continue)) immediate-answer (assign val (const 1)) (goto (reg continue)) expt-done) )) (set-register-contents! expt-a b 2) (set-register-contents! expt-a n 2) ;;gosh (register-trace expt-a val on) ;;on ;;gosh (register-trace expt-a n on) ;;on ;;gosh (start expt-a) ;;reg [n] 2- 1 ;;reg [n] 1- 0 ;;reg [val] *unassigned*- 1 ;;reg [val] 1- 2 ;;reg [val] 2- 4 ;;done ;;gosh (register-trace expt-a n off) ;;off ;;gosh (set-register-contents! expt-a n 2) ;;done ;;gosh (start expt-a) ;;reg [val] 4- 1 ;;reg [val] 1- 2 ;;reg [val] 2- 4 ;;done Exercise 5.19 ;;; n の解釈を、問題で指定されている方法とは変えて、ブレークポイントは ;;; n番目のインストラクションを実行した後に(内部的には n+1 番目の ;;; インストラクションを実行する前に)働くようにする。 ;;; 従って、label直後のインストラクションを実行する前にブレークポイント ;;; を働かせるためには、 ;;; (set-breakpoint machine label ) ;;; とする。 ;;; label n は ex5.10 の形式を使用する。 ;;; inst は ex5.17 の((text . proc) label-name1 ...) の形式を使用する。 ;;; breakpointの設定は、上記の proc を breakpoint 処理を行う手続き(make-bp ;;; が返す手続き)に、トレースが出力されないよう text を breakに変更する。 ;;; make-new-machine の内部手続き execute を instruction から break が返ると ;;; loop が終了するよう変更する。 (define (execute) (let ((insts (get-contents pc))) (if (null? insts) done (begin (if (eq? trace on) (trace-out (car insts))) (if (not (eq? make-bp ((instruction-execution-proc (car insts))))) (begin (set! instruction-counter (+ instruction-counter 1)) (execute)) ))))) ;;; make-new-machine の message に proceed 用を追加する。 ((eq? message execute) (execute)) ;;; inst 変更用の手続きを追加する。 (define (set-instruction-text! inst text) (set-car! (car inst) text)) ;;; breakpoint が設定されている時はトレースを抑制する。 (define (trace-out inst) (if (not (eq? (instruction-text inst) break)) (begin (if (not (null? (instruction-labels inst))) (for-each (lambda (x) (format #t "trace ~s~%" x)) (instruction-labels inst))) (format #t "trace ~s~%" (instruction-text inst))))) ;;; 設定されている breakpoint を (inst1 inst2 ...) の形で保持 (define breakpoint-list ()) ;;; breakpoint 設定 (define (set-breakpoint machine . label-exp) (let ((tis (machine insts)) (name (label-name label-exp)) (offset (label-offset label-exp))) (let ((insts (lookup-label-tis tis name offset))) (let ((val (memq (car insts) breakpoint-list))) (if (not val) (begin (make-bp (car insts) name offset) (set! breakpoint-list (cons (car insts) breakpoint-list)) (instruction-text (car insts))) (warn "already set breakpoint " label-exp)) )))) ;;; breakpoint 停止後の再開。再開instructionの変更は未実装。 (define (proceed-machine machine . label-exp) (if (eq? label-exp ()) (let ((insts (get-register-contents machine pc))) (let ((val (memq (car insts) breakpoint-list))) (if val (begin ((instruction-execution-proc (car insts)) proceed) (machine execute) ) (error "Internal error -- PROCEED")))) (begin ) )) ;;; breakpoint 解除 (define (cancel-breakpoint machine . label-exp) (if (eq? label-exp ()) (begin ;all (for-each (lambda (inst) (if (not (eq? inst ())) ((instruction-execution-proc inst) cancel))) breakpoint-list) (set! breakpoint-list ()) done) (begin ;the (let ((tis (machine insts)) (name (label-name label-exp)) (offset (label-offset label-exp))) (let ((insts (lookup-label-tis tis name offset))) (let ((val (memq (car insts) breakpoint-list))) (if val (begin ((instruction-execution-proc (car isnts)) cancel) (set-car! val ()) ok) (warn "not set breakpoint " label-exp)) )))))) ;;; breakpoint (define (make-bp inst label offset) (let ((proc (instruction-execution-proc inst)) ; save proc (text (instruction-text inst)) ; save text (flag break)) ; break on (set-instruction-text! inst break) ; trace抑制 (set-instruction-execution-proc! inst (lambda arg (if (null? arg) ;; run-time (cond ((eq? flag break) (format #t "break! ~s ~s~%" label offset) make-bp) ((eq? flag proceed) (set-instruction-text! inst break) (set! flag break) (proc)) (else (error "Undefined Breakflag " flag))) ;; command (cond ((eq? (car arg) proceed) (set-instruction-text! inst text) (set! flag proceed)) ((eq? (car arg) cancel) (set-instruction-execution-proc! inst proc)) (else (error "Undefined Breakflag " arg)))))))) ;;; ラベルとオフセットから insts を得る。 (define (lookup-label-tis tis name offset) (define (forward insts n) (if (= n 0) insts (if (null? (cdr insts)) (error "Out of range -- BREAKPOINT" (list name offset)) (forward (cdr insts) (- n 1))))) (define (forward2 insts lead target) (if (eq? lead target) insts (if (null? (cdr lead)) (error "Out of range -- BREAKPOINT" (list name offset)) (forward2 (cdr insts) (cdr lead) target)))) (let ((insts (find-tail (lambda (inst) (and (not (null? (instruction-labels inst))) (memq name (instruction-labels inst)))) tis))) (if (not insts) (error "Undefined label -- BREAKPOINT" name)) (if ( = offset 0) (forward insts offset) (forward2 tis (forward tis (* offset -1)) insts)))) ;;; test program (define ex5.19 (make-machine (continue) (list (list format format)) (machine (assign continue (label t1e)) (goto (label s -3)) t1e (assign continue (label t2e)) (goto (label s -1)) t2e (assign continue (label t3e)) (goto (label s 1)) t3e (goto (label ex5.19.done)) ;; (perform (op format) (const #t) (const "stop s -2~%")) (goto (reg continue)) (perform (op format) (const #t) (const "stop s~%")) s (goto (reg continue)) (perform (op format) (const #t) (const "stop s 2~%")) (goto (reg continue)) ;; ex5.19.done) )) ;;gosh (bp! s -2) ; (set-breakpoint machine label n ) の短縮形 ;;break ;;gosh (bp! s) ;;break ;;gosh (bp! s 2) ;;break ;;gosh (start ex5.19) ;;stop s -2 ;;break! s -2 ;;gosh (go) ; (proceed-machine machine ) の短縮形 ;;stop s ;;break! s 0 ;;gosh (go) ;;stop s 2 ;;break! s 2 ;;gosh (cbp!) ; (cancel-all-breakpoints machine ) の短縮形 ;;done ;;gosh (start ex5.19) ;;stop s -2 ;;stop s ;;stop s 2 ;;done
https://w.atwiki.jp/sicpstudygroup/pages/49.html
naga Todo 2.3長方形の別表現。セレクタの変更で済むようにしないと。 2.6 2.11問題を理解できているか? 2.14問題を理解できているか? 2.15 2.16 Exercise 2.1 (define (make-rat n d) (let ((g (gcd n d))) (cons ((if ( (* n d) 0) - +) (abs (/ n g))) (abs (/ d g))))) Exercise 2.2 (define (make-segment p1 p2) (cons p1 p2)) (define (start-segment s) (car s)) (define (end-segment s) (cdr s)) (define (make-point x y) (cons x y)) (define (x-point p) (car p)) (define (y-point p) (cdr p)) (define (midpoint-segment s) (make-point (/ (+ (x-point (start-segment s)) (x-point (end-segment s))) 2) (/ (+ (y-point (start-segment s)) (y-point (end-segment s))) 2))) Exercise 2.3 ;; 周囲 (define (rectangle-perimeter r) (+ (* (segment-length (v-rectangle r)) 2) (* (segment-length (h-rectangle r)) 2))) ;; 面積 (define (rectangle-area r) (* (segment-length (v-rectangle r)) (segment-length (h-rectangle r)))) (define (make-rectangle v h) (if (and (have-same-point? v h) (right-angle? v h)) (cons v h) #f)) ;; segmentが同じpointを持つか? (define (have-same-point? v h) (or (same-point? (start-segment v) (start-segment h)) (same-point? (start-segment v) (end-segment h)) (same-point? (end-segment v) (start-segment h)) (same-point? (end-segment v) (end-segment h)))) ;; 同じpointか? (define (same-point? p1 p2) (and (= (x-point p1) (x-point p2)) (= (y-point p1) (y-point p2)))) ;; segmentが直交するか? (define (right-angle? v h) (let ((dvx (- (x-point (end-segment v)) (x-point (start-segment v)))) (dvy (- (y-point (end-segment v)) (y-point (start-segment v)))) (dhx (- (x-point (end-segment h)) (x-point (start-segment h)))) (dhy (- (y-point (end-segment h)) (y-point (start-segment h))))) (cond ((or (and (= dvx 0) (= dvy 0)) (and (= dhx 0) (= dhy 0))) #f) ((or (and (= dvx 0) (= dhy 0)) (and (= dvy 0) (= dhx 0))) #t) ((or (and (not (= dvx 0)) (not (= dhy 0)) (= (/ dvy dvx) (/ dhx dhy))) (and (not (= dvy 0)) (not (= dhx 0)) (= (/ dvx dvy) (/ dhy dhx)))) #t) (else #f)))) ;; selectors for rectangle (define (v-rectangle r) (car r)) (define (h-rectangle r) (cdr r)) ;; segment長 (define (segment-length s) (sqrt (+ (square (- (x-point (start-segment s)) (x-point (end-segment s)))) (square (- (y-point (start-segment s)) (y-point (end-segment s))))))) ;;gosh (define p00 (make-point 0 0)) ;;p00 ;;gosh (define p40 (make-point 4 0)) ;;p40 ;;gosh (define p02 (make-point 0 2)) ;;p02 ;;gosh (define s0040 (make-segment p00 p40)) ;;s0040 ;;gosh (define s0002 (make-segment p00 p02)) ;;s0002 ;;gosh (define r (make-rectangle s0040 s0002)) ;;r ;;gosh (rectangle-perimeter r) ;;8.0 別の表現はパス。 Exercise 2.4 ;; (car (cons x y)) ;;- (car (lambda (m) (m x y))) ;;引数(cons x y)を評価 ;;- ((lambda (m) (m x y)) (lambda (p q) p)) ;;carを評価 ;;- ((lambda (p q) p) x y) ;;carに引数を適用 ;;- x ;;評価 (define (cons-f x y) (lambda (m) (m x y))) (define (car-f z) (z (lambda (p q) p))) (define (cdr-f z) (z (lambda (p q) q))) ;;gosh (cdr-f (cons-f x y)) ;;y Exercise 2.5 ;; 2と3は互いに素のため(expt 2 a)と(expt 3 b)も互いに素となりa,bの情報を保存できる。 (define (cons-a a b) (* (expt 2 a) (expt 3 b))) (define (car-a n) (if (not (= (remainder n 2) 0)) 0 (+ 1 (car-a (/ n 2))))) (define (cdr-a n) (if (not (= (remainder n 3) 0)) 0 (+ 1 (cdr-a (/ n 3))))) ;;gosh (define x (cons-a 7 13)) ;;x ;;gosh x ;;204073344 ;;gosh (car-a x) ;;7 ;;gosh (cdr-a x) ;;13 Exercise 2.6 後日 Exercise 2.7 ;; selectors (define (upper-bound x) (max (car x) (cdr x))) (define (lower-bound x) (min (car x) (cdr x))) Exercise 2.8 ;; difference (define (sub-interval x y) (make-interval (- (upper-bound x) (lower-bound y)) (- (lower-bound x) (upper-bound y)))) ;;gosh (define i32 (make-interval 3 2)) ;;i32 ;;gosh (define i1-1 (make-interval 1 -1)) ;;i1-1 ;;gosh (define r (sub-interval i32 i1-1)) ;;r ;;gosh (upper-bound r) ;;4 ;;gosh (lower-bound r) ;;1 Exercise 2.9 (define (width i) (/ (- (upper-bound i) (lower-bound i)) 2)) ;; ;;(define w1 (make-interval w1u w1l)) ;;(define w2 (make-interval w2u w2l)) ;;(width w1)- (w1u-w1l)/2 ;;(widht w2)- (w2u-w2l)/2 ;; ;;(define w1+w2 (add-interval w1 w2)) ;;(width w1+w2)- (/ (- (upper-bound w1+W2) (lower-bound w1+w2)) 2) ;;- ((w1u+w2u)-(w1l+w2l))/2- (w1u-w1l)/2+(w2u-w2l)/2 ;;- (+ (width w1) (width w2)) ;; ;;(define w1-w2 (sub-interval w1 w2)) ;;(width w1-w2)- (/ (- (upper-bound w1-w2) (lower-bound w1-w2)) 2) ;;- ((w1u-w2l)-(w1l-w2u))/2- (w1u-w1l)/2+(w2u-w2l)/2 ;;- (+ (width w1) (width w2)) ;; ;;gosh (define w1 (make-interval 2 1)) ;;w1 ;;gosh (define w2 (make-interval 4 3)) ;;w2 ;;gosh (define w3 (make-interval -1 -2)) ;;w3 ;;gosh (width w1) ;;1/2( ;;gosh (width w2) ;;1/2 ;;gosh (width w3) ;;1/2 ;;gosh (define w1+w2 (add-interval w1 w2)) ;;w1+w2 ;;gosh (define w1+w3 (add-interval w1 w3)) ;;w1+w3 ;;gosh (width w1+w2) ;;1 ;;gosh (width w1+w3) ;;1 ;;gosh (define w1*w2 (mul-interval w1 w2)) ;;w1*w2 ;;gosh (define w1*w3 (mul-interval w1 w3)) ;;w1*w3 ;;gosh (width w1*w2) ;;5/2 ;;gosh (width w1*w3) ;;3/2 Exercise 2.10 (define (div-interval x y) (if (not (and ( = (upper-bound y) 0) ( = (lower-bound y) 0))) (mul-interval x (make-interval (/ 1.0 (upper-bound y)) (/ 1.0 (lower-bound y)))) (error "interval spans zero " y))) ;;gosh (define w1 (make-interval 2 1)) ;;w1 ;;gosh (define w4 (make-interval 1 -1)) ;;w4 ;;gosh (div-interval w1 w4) ;;*** ERROR interval spans zero (1 . -1) ;;Stack Trace ;;_______________________________________ Exercise 2.11 (define (mul-interval i1 i2) (let ((i1u (upper-bound i1)) (i1l (lower-bound i1)) (i2u (upper-bound i2)) (i2l (lower-bound i2))) (cond ((and ( = i1u 0) ( = i1l 0)) (cond ((and ( = i2u 0) ( = i2l 0)) (make-interval (* i1u i2u) (* i1l i2l))) ((and ( = i2u 0) ( i2l 0)) (make-interval (* i1u i2u) (* i1u i2l))) (else (make-interval (* i1l i2u) (* i1u i2l))))) ((and ( = i1u 0) ( i1l 0)) (cond ((and ( = i2u 0) ( = i2l 0)) (make-interval (* i1u i2u) (* i1l i2u))) ((and ( = i2u 0) ( i2l 0)) (make-interval (* i1u i2u) (* i1u i2l))) (else (make-interval (* i1l i2l) (* i1u i2l))))) (else (cond ((and ( = i2u 0) ( = i2l 0)) (make-interval (* i1u i2l) (* i1l i2u))) ((and ( = i2u 0) ( i2l 0)) (make-interval (* i1l i2l) (* i1l i2u))) (else (make-interval (* i1l i2l) (* i1u i2u)))))))) ;;gosh (define i21 (make-interval 2 1)) ;;i21 ;;gosh (define i1-1 (make-interval 1 -1)) ;;i1-1 ;;gosh (define i-1-2 (make-interval -1 -2)) ;;i-1-2 ;;gosh (define i21*i21 (mul-interval i21 i21)) ;;i21*i21 ;;gosh i21*i21 ;;(4 . 1) ;;gosh (define i21*i1-1 (mul-interval i21 i1-1)) ;;i21*i1-1 ;;gosh i21*i1-1 ;;(2 . -2) ;;gosh (define i21*i-1-2 (mul-interval i21 i-1-2)) ;;i21*i-1-2 ;;gosh i21*i-1-2 ;;(-1 . -4) ;;gosh (define i1-1*i21 (mul-interval i1-1 i21)) ;;i1-1*i21 ;;gosh i1-1*i21 ;;(2 . -2) ;;gosh (define i1-1*i1-1 (mul-interval i1-1 i1-1)) ;;i1-1*i1-1 ;;gosh i1-1*i1-1 ;;(1 . -1) ;;gosh (define i1-1*i-1-2 (mul-interval i1-1 i-1-2)) ;;i1-1*i-1-2 ;;gosh i1-1*i-1-2 ;;(2 . -2) ;;gosh (define i-1-2*i21 (mul-interval i-1-2 i21)) ;;i-1-2*i21 ;;gosh i-1-2*i21 ;;(-1 . -4) ;;gosh (define i-1-2*i1-1 (mul-interval i-1-2 i1-1)) ;;i-1-2*i1-1 ;;gosh i-1-2*i1-1 ;;(2 . -2) ;;gosh (define i-1-2*i-1-2 (mul-interval i-1-2 i-1-2)) ;;i-1-2*i-1-2 ;;gosh i-1-2*i-1-2 ;;(4 . 1) Exercise 2.12 (define (make-center-percent c p) (let ((w (* c (/ p 100)))) (make-center-width c w))) (define (percent i) (* (/ (width i) (center i)) 100)) ;;gosh (define r6.8+-10% (make-center-percent 6.8 10)) ;;r6.8+-10% ;;gosh (width r6.8+-10%) ;;0.6799999999999997 ;;gosh (percent r6.8+-10%) ;;9.999999999999996 Exercise 2.13 ;; i1 = x+dx x-dx ;; i2 = y+dy y-dy ;; i1 =0,i2 =0,dx x,dy yとすると ;; i1*i2 = xy+ydx+xdy+dxdy xy-ydx-xdy+dxdy ;; dxdyが十分小さいとして良いので ;; = xy+ydx+ydy xy-(ydx+xdy) ;; これをpercentで表記するために変形すると ;; = xy+xy(dx/x+dy/y) xy-xy(dx/x+dy/y) ;; dx/x,dy/yはそれぞれi1,i2のpercentに当たるので (define (mul-center-percent i1 i2) (make-center-percent (* (center i1) (center i2)) (+ (percent i1) (percent i2)))) ;;gosh (define i1 (make-center-percent 100 0.1)) ;;i1 ;;gosh (define i2 (make-center-percent 1000 0.2)) ;;i2 ;;gosh (define i1*i2 (mul-interval i1 i2)) ;;i1*i2 ;;gosh (define i1*i2-simple (mul-center-percent i1 i2)) ;;i1*i2-simple ;;gosh (center i1*i2) ;;100000.20000000001 ;;gosh (percent i1*i2) ;;0.2999994000011927 ;;gosh (center i1*i2-simple) ;;100000.0 ;;gosh (percent i1*i2-simple) ;;0.3 Exercise 2.14 (define (par1 r1 r2) (div-interval (mul-interval r1 r2) (add-interval r1 r2))) (define (par2 r1 r2) (let ((one (make-interval 1 1))) (div-interval one (add-interval (div-interval one r1) (div-interval one r2))))) ;;以下のように乗算・除算ではwidthが比率として加算される。 ;;gosh (define a (make-center-percent 100 1)) ;;an ;;gosh (define b (make-center-percent 100 2)) ;;b ;;gosh (percent a) ;;1.0 ;;gosh (percent b) ;;2.0 ;;gosh (percent (div-interval a a)) ;;1.9998000199980077 ;;gosh (percent (div-interval a b)) ;;2.9994001199760016 ;;gosh (percent (div-interval b b)) ;;3.998400639744092 ;;gosh (percent (mul-interval a a)) ;;1.9998000199980004 ;;gosh (percent (mul-interval a b)) ;;2.9994001199760048 ;;gosh (percent (mul-interval b b)) ;;3.9984006397441028 ;;gosh (percent (div-interval (make-interval 1 1) a)) ;;1.0000000000000036 ;;gosh (percent (mul-interval (make-interval 1 1) a)) ;;1.0 ;;gosh (percent (par1 a a)) ;;2.999200239928031 ;;gosh (percent (par2 a a)) ;;1.000000000000007 Exercise 2.15 後日 Exercise 2.16 後日
https://w.atwiki.jp/scale/pages/10.html
関連ブログ @wikiのwikiモードでは #bf(興味のある単語) と入力することで、あるキーワードに関連するブログ一覧を表示することができます 詳しくはこちらをご覧ください。 =>http //atwiki.jp/guide/17_161_ja.html たとえば、#bf(ゲーム)と入力すると以下のように表示されます。 #bf
https://w.atwiki.jp/pokehackgames/pages/59.html
海外の改造作。Mantager氏発案の企画。 縁あってキャラクターデザインで当wiki管理人も参加。ライバルのTaran他モブトレーナーを多数担当。 現在はDemoバージョンが公開されており、全体の約30%程度が完成している。 https //www.pokecommunity.com/showthread.php?p=10557405
https://w.atwiki.jp/tmiya/pages/128.html
Scala ひと巡り sealed クラス (Sealed Classes) 原ページ sealed クラスは、継承するテンプレートを継承されるクラスと同じソースファイル中で定義する場合を除き、直接には継承できません。しかし、sealed クラスのサブクラスはどこででも継承できます。 sealed クラスは sealed 修飾子を使って定義できます。 もしパターンマッチのセレクタが sealed クラスのインスタンスなら、パターンマッチングのコンパイル時に、与えられたパターンセットが網羅的ではないと診断する警告が出ます。すなわち、実行時に MatchError [60] が発生する可能性があるということです。 @unchecked アノテーション [47] をマッチ式のセレクタに適用すると、そうでなければ発せられるはずの、非網羅的パターンマッチに関するあらゆる警告が抑制されます。 例えば、次のメソッド定義に対しては警告はありません。 def f(x Option[Int]) = (x @unchecked) match { case Some(y) = y } @unchecked アノテーションがなければ、Scala コンパイラはパターンマッチが非網羅的であると推論し、Optionが sealed クラスなので警告を発します。 Scala ひと巡り トレイト (Traits) 原ページ トレイトは、Java のインターフェースに似て、サポートするメソッドのシグニチャを記述することで、オブジェクトの型定義に使えます。Java と異なり、Scala のトレイトは部分的に実装できます。すなわち、複数のメソッドのデフォルト実装を定義できます。クラス [2]と異なり、トレイトはコンストラクタ・パラメータを持てません。 次は 1 つの例です trait Similarity { def isSimilar(x Any) Boolean def isNotSimilar(x Any) Boolean = !isSimilar(x) } このトレイトは 2 つのメソッド isSimilar と isNotSimilar からなります。isSimilar が具象の(具体的な)メソッド実装を提供せず(Java 用語では抽象)、メソッド isNotSimilar は具象実装を定義します。従って、このトレイトを統合するクラスだけが、isSimilar に具象の実装を提供する必要があります。isNotSimilar の振る舞いは、トレイトから直接に継承します。トレイトは通常、ミックスインクラス合成 [5]を用いて、クラス [61](あるいは他のトレイト)に統合されます class Point(xc Int, yc Int) extends Similarity { var x Int = xc var y Int = yc def isSimilar(obj Any) = obj.isInstanceOf[Point] obj.asInstanceOf[Point].x == x } object TraitsTest extends Application { val p1 = new Point(2, 3) val p2 = new Point(2, 4) val p3 = new Point(3, 3) println(p1.isNotSimilar(p2)) println(p1.isNotSimilar(p3)) println(p1.isNotSimilar(2)) } 次はプログラムの出力です false true true Scala ひと巡り 上限 型境界 (Upper Type Bounds) 原ページ Scala では、型パラメータ [16]と抽象型 [21]は、型境界による制約を受けます。そのような型境界は、型変数の具象値を制限し、型のメンバーについてさらに多くの情報を明らかにします。上限型境界 T A は、型変数 T が型 A のサブ型を参照することを宣言します。 次は、多相的メソッド [25] findSimilar の実装について、上限型境界に頼る例です trait Similar { def isSimilar(x Any) Boolean } case class MyInt(x Int) extends Similar { def isSimilar(m Any) Boolean = m.isInstanceOf[MyInt] m.asInstanceOf[MyInt].x == x } object UpperBoundTest extends Application { def findSimilar[T Similar](e T, xs List[T]) Boolean = if (xs.isEmpty) false else if (e.isSimilar(xs.head)) true else findSimilar[T](e, xs.tail) val list List[MyInt] = List(MyInt(1), MyInt(2), MyInt(3)) println(findSimilar[MyInt](MyInt(4), list)) println(findSimilar[MyInt](MyInt(2), list)) } 上限型境界アノテーションがなければ、メソッド findSimilar 中でメソッド isSimilar を呼び出すことはできません。 下限型境界の使用方法は、次で述べます [19]。 Scala ひと巡り 下限 型境界 (Lower Type Bounds) 原ページ 上限型境界 [18]は、型を他の型のサブ型へ制限し、他方、下限型境界は、型が他の型のスーパー型であると宣言します。項 T A は、型パラメータ T あるいは抽象型 T が、型 A のスーパー型を参照することを表します。 次はそれが役に立つ例です case class ListNode[T](h T, t ListNode[T]) { def head T = h def tail ListNode[T] = t def prepend(elem T) ListNode[T] = ListNode(elem, this) } 上記のプログラムは prepend (先頭に追加)操作を使って連結リストを実装します。残念ながら、この型は、クラス ListNode の型パラメータ中にあって、非変です; すなわち、型 ListNode[String]は 型 List[Object]のサブ型ではありません。変位指定アノテーション [17]の助けを借りて、このようなサブ型のセマンティクスを表現できます case class ListNode[+T](h T, t ListNode[T]) { ... } 残念ながら、共変の変位指定は型変数を共変の位置で使う場合のみ可能なので、このプログラムはコンパイルできません。型変数 T はメソッド prepend のパラメータ型として現われるので、この規則は破られています。しかし、下限型境界の助けを借りれば、T が共変の位置のみに現れる prepend メソッドを実装できます。 次は対応するコードです case class ListNode[+T](h T, t ListNode[T]) { def head T = h def tail ListNode[T] = t def prepend[U T](elem U) ListNode[U] = ListNode(elem, this) } 新しい prepend メソッドは、少しばかり制約の少ない型を持つことに注意してください。これにより、たとえば、既に存在するリストの先頭にスーパー型のオブジェクトを追加できます。得られるリストは、このスーパー型のリストです。 次は、そのことを示すコードです object LowerBoundTest extends Application { val empty ListNode[Null] = ListNode(null, null) val strList ListNode[String] = empty.prepend("hello") .prepend("world") val anyList ListNode[Any] = strList.prepend(12345) } Scala ひと巡り 明示的に型付けられた自己参照 (Explicitly Typed Self References) 原ページ 拡張可能なソフトウェアを開発するとき、値 this の型を宣言したくなることが時々あります。興味を引く例として、グラフデータ構造の小規模で拡張可能な表現を Scala で考えてみましょう。 次はグラフを記述する定義です abstract class Graph { type Edge type Node NodeIntf abstract class NodeIntf { def connectWith(node Node) Edge } def nodes List[Node] def edges List[Edge] def addNode Node } グラフはノードとエッジのリストからなり、それらノードとエッジの両方の型とも抽象のままです。 The use of abstract types [21] allows implementations of trait Graph to provide their own concrete classes for nodes and edges. 抽象型 [21]を使えば、ノードとエッジに対してそれら自身の具象クラスを提供できるようにする、トレイト Graph を実装できます。 さらに、グラフに新しいノードを加える、メソッド addNode があります。ノードはメソッド connectWith を使って連結します。 次のプログラムは、クラス Graph の 1 つの考え得る実装です。 abstract class DirectedGraph extends Graph { type Edge EdgeImpl class EdgeImpl(origin Node, dest Node) { def from = origin def to = dest } class NodeImpl extends NodeIntf { def connectWith(node Node) Edge = { val edge = newEdge(this, node) edges = edge edges edge } } protected def newNode Node protected def newEdge(from Node, to Node) Edge var nodes List[Node] = Nil var edges List[Edge] = Nil def addNode Node = { val node = newNode nodes = node nodes node } } クラス DirectedGraph は、部分的な実装を提供することで、Graph クラスを特化します。実装は本当に部分的です。なぜなら DirectedGraph をさらに拡張できるようにしたいからです。そのために、このクラスではすべての実装詳細をオープンにし、このようにノードとエッジの両方とも抽象のままにしています。にもかかわらず、クラス DirectedGraph は、クラス EdgeImpl へ境界を厳しくすることで、エッジ型の実装についてさらなる詳細を明示しています。また、クラス EdgeImpl と NodeImpl で表される、エッジとノードの準備的な実装がいくつかあります。部分的なグラフ実装の中で新しいノードとエッジオブジェクトを生成する必要があるので、ファクトリメソッド newNode と newEdge も加えなければなりません。メソッド addNode と connectWith は共に、これらのファクトリメソッドを使って定義します。メソッド connectWith の実装をよく見ると、エッジを生成するために、自己参照 this をファクトリメソッド newEdge に渡す必要があることがわかります。しかし this は型 NodeImpl に割り当てられており、それは対応するファクトリメソッドによって要請される型 Node に互換ではありません。その結果、上記のプログラムは正しくなく、Scala コンパイラはエラーメッセージを発行します。 Scala では、自己参照 this に他の型を明示的に与えることで、クラスを(将来実装されるであろう)もう 1 つの型に結び付けることができます。このメカニズムを使って上記コードを修正できます。明示的な自己型は、クラス DirectedGraph の本体中で指定します。 次は修正したプログラムです abstract class DirectedGraph extends Graph { ... class NodeImpl extends NodeIntf { self Node = def connectWith(node Node) Edge = { val edge = newEdge(this, node) // 今度は OK edges = edge edges edge } } ... } クラス NodeImpl の新しい定義では、this は型 Node を持っています。型 Node は抽象ですから、NodeImpl が本当に Node のサブ型かどうかはまだわからず、Scala の型システムは、このクラスのインスタンス化を許してくれません。 But nevertheless, we state with the explicit type_annotation of this that at some point, (a subclass of) NodeImpl has to denote a subtype of type Node in order to be instantiatable . しかしそれにもかかわらず、インスタンス化できるようにするために、ある時点で NodeImpl (のサブクラスの 1 つ)が型 Node のサブ型を表さなければならないことを、this の明示的なアノテーション型を用いて記述します。 次は、DirectedGraph の具象特化であり、すべての抽象クラスメンバが具象に変わっています。 class ConcreteDirectedGraph extends DirectedGraph { type Edge = EdgeImpl type Node = NodeImpl protected def newNode Node = new NodeImpl protected def newEdge(f Node, t Node) Edge = new EdgeImpl(f, t) } この場合、NodeImpl をインスタンス化できます。なぜなら、今度は NodeImpl が(単純に NodeImpl のエイリアスである)型 Node のサブ型を表すことがわかるからです。 次は、クラス ConcreteDirectedGraph の使用方法を示す例です object GraphTest extends Application { val g Graph = new ConcreteDirectedGraph val n1 = g.addNode val n2 = g.addNode val n3 = g.addNode n1.connectWith(n2) n2.connectWith(n3) n1.connectWith(n3) } Scala ひと巡り サブクラス化 (Subclassing) 原ページ Scala のクラスは拡張可能です。サブクラスの機構により、与えられたスーパークラスの全メンバーの継承と、クラスメンバの追加定義によって、クラスを特化できます。 次は 1 つの例です class Point(xc Int, yc Int) { val x Int = xc val y Int = yc def move(dx Int, dy Int) Point = new Point(x + dx, y + dy) } class ColorPoint(u Int, v Int, c String) extends Point(u, v) { val color String = c def compareWith(pt ColorPoint) Boolean = (pt.x == x) (pt.y == y) (pt.color == color) override def move(dx Int, dy Int) ColorPoint = new ColorPoint(x + dy, y + dy, color) } この例では最初に、場所を表す新しいクラス Point を定義します。次に、クラス Point を拡張するクラス ColorPoint を定義します。 これは次のような結果になります: クラス ColorPoint は、そのスーパークラス Point からすべてのメンバーを継承します。;この場合、メソッド move と同様、値 x、y も継承します。 サブクラス ColorPoint は、(継承した)メソッドの集合に新しいメソッド compareWith を加えます。 Scala ではメンバー定義をオーバライドできます; この場合、クラス Point から継承した move メソッドをオーバライドします。これにより、ColorPoint オブジェクトのクライアントは、クラス Point の move メソッドにアクセスできなくなります。クラス ColorPoint 内では、継承されたメソッド move は スーパー呼び出し super.move(...) を使ってアクセスできます。メソッドオーバーライドが非変の(つまり、オーバーライドするメソッドが同じシグニチャを持たなければならない) Java と異なり、Scala では反変/共変方式でメソッドをオーバライドできます。上の例では、このフィーチャーを利用してメソッド move に、スーパークラス Point で指定された Point オブジェクトを返す代わりに ColorPoint オブジェクトを返させています。 サブクラスはサブ型を定義します; このことは今の場合、Point オブジェクトが必要とされるときはいつでも、ColorPoint オブジェクトを使えることを意味します。 複数の他クラスを継承したい場合、純粋なサブクラス化ではなく、ミックスインベースのクラス合成 [5] を利用する必要があります。 Scala ひと巡り ローカルな型推論 (Local Type Inference) 原ページ Scala は、プログラマが明白なアノテーション型を書かなくても済む、組み込みの型推論機構を持っています。たとえば Scalaでは、変数の型を指定する必要がないことがよくあります。なぜなら、コンパイラが変数の初期化式から型を推論できるからです。同様にメソッドの戻り値型もしばしば省略できます。なぜなら、それらは本体の型に対応するので、コンパイラが推論できるからです。 次は 1 つの例です object InferenceTest1 extends Application { val x = 1 + 2 * 3 // x の型は Int val y = x.toString() // y の型は String def succ(x Int) = x + 1 // メソッド succ は Int 値を返す } 再帰的なメソッドについては、コンパイラは結果型を推論できません。次のプログラムは、この理由でコンパイルできません。 object InferenceTest2 { def fac(n Int) = if (n == 0) 1 else n * fac(n - 1) } 多相的メソッド [25]を呼ぶあるいは、ジェネリッククラス [16]をインスタンス化するとき、型パラメータの指定も必須ではありません。Scala コンパイラは、コンテキストや実際のメソッド/コンストラクタ・パラメータの型からそのような記述されていない型パラメータを推論します。 次はこのことを示す例です case class MyPair[A, B](x A, y B); object InferenceTest3 extends Application { def id[T](x T) = x val p = new MyPair(1, "scala") // 型 MyPair[Int, String] val q = id(1) // 型 Int } 上記プログラムの最後の 2 行は、推論された型をすべて明示した、次のコードに等価です val x MyPair[Int, String] = new MyPair[Int, String](1, "scala") val y Int = id[Int](1) ある状況では、次のプログラムが示すように、Scala の型推論機構に頼ることは非常に危険です。 object InferenceTest4 { var obj = null obj = new Object() } このプログラムはコンパイルできません。なぜなら、変数 obj の推論される型は Null だからです。この型の唯一の値は nullですから、この変数に他の値を参照させることはできません。 Scala ひと巡り 統合された型 (Unified Types) 原ページ Java と異なり、Scala ではすべての値はオブジェクトです(数値や関数を含めて)。Scala はクラスを基盤にしているので、すべての値はクラスのインスタンスです。下図は Scala のクラス階層を示しています。 imageプラグインエラー ご指定のURLはサポートしていません。png, jpg, gif などの画像URLを指定してください。 Scala クラス階層 全てのクラスのスーパークラスである scala.Any は直下にサブクラス scala.AnyValue と AnyRef を持っています。それらは 2 つの異なるクラスの系統 値クラスと参照クラスを代表しています。すべての値クラスは事前定義されています;それらは Java ライクな言語のプリミティブ型に対応します。他のすべてのクラスは参照型を定義します。ユーザー定義のクラスは、デフォルトでは参照型を定義します; つまり、それらはいつも(間接的に)scala.AnyRef のサブクラスとなります。Scala のユーザー定義クラスはすべて、暗黙のうちにトレイト scala.ScalaObject を拡張(継承)します。Scala 実行基盤からのクラス(つまり Java 実行時環境)は、scala.ScalaObject を拡張しません。もし Scala を Java 実行時環境のコンテキスト中で使うなら、scala.AnyRef は java.lang.Object に対応します。 上図は、値クラス間のビュー [24]と呼ばれる暗黙の型変換も示していることに注意してください。 次の例は、数、文字、論理値等と関数の双方とも、他のオブジェクトとまったく同じく、オブジェクトであることを示しています。 object UnifiedTypes { def main(args Array[String]) { val set = new scala.collection.mutable.HashSet[Any] set += "This is a string" // 文字列の追加 set += 732 // 数の追加 set += c // 文字の追加 set += true // 論理値の追加 set += main _ // main 関数の追加 val iter Iterator[Any] = set.elements while (iter.hasNext) { println(iter.next.toString()) } } } プログラムは、トップレベルのシングルトンオブジェクトの形で、main メソッドをもつアプリケーション UnifiedTypes を宣言します。main メソッドは、クラス HashSet[Any]のインスタンスを参照するローカル変数 set を定義します。プログラムはこの set に様々な要素を加えます。要素は、宣言されたセット要素型 Any に適合しなければなりません。最後に、すべての要素の文字列表現を印字します。 次はプログラムの出力です c true function 732 This is a string Scala ひと巡り 変位指定 (Variances) 原ページ Scala は、ジェネリッククラスの型パラメータ [16]の変位指定アノテーションをサポートします。Java5 (aka.JDK 1.5[58])と対照して、クラス抽象を定義するときに変位指定アノテーションを加えることができます。他方、Java5 では、変位指定アノテーションはクラス抽象を使うときにクライアントが与えます。(訳注:Scalaでは静的に表現できるということ) ジェネリッククラスについてのページに、ミュータブル(更新可能)なスタックの例がありました。クラス Stack[T] によって定義された型は、型パラメータについて非変のサブ型付けになると説明しました。それによりクラス抽象の再利用を制限できます。今度はこの制限を持たないスタックの関数型(つまり、イミュータブル(更新不可)な)実装を導きます。これが、明白ではない方法で多相的メソッド [25]、下限型境界 [19]、そして共変の型パラメータアノテーションの使用を結びつける、進んだ例であることに注意してください。さらにまた、スタック要素を明示的なリンクなしでチェインするために、内部クラス [20]を利用します。 class Stack[+A] { def push[B A](elem B) Stack[B] = new Stack[B] { override def top B = elem override def pop Stack[B] = Stack.this override def toString() = elem.toString() + " " + Stack.this.toString() } def top A = error("no element on stack") def pop Stack[A] = error("no element on stack") override def toString() = "" } object VariancesTest extends Application { var s Stack[Any] = new Stack().push("hello"); s = s.push(new Object()) s = s.push(7) Console.println(s) } アノテーション +T は、型 T が共変の位置でだけ使われると宣言します。同様に、-T は、T が反変の位置でだけ使われると宣言します。共変の型パラメータなので、この型パラメータについて共変のサブ型関係を得ます。この例では、もし T が S のサブ型なら、このことは、Stack[T] が Stack[S]のサブ型であることを意味します。 - とタグ付けられた型パラメータについては、反対のことが当てはまります。スタックの例では、メソッド push を定義できるようにするために、反変の位置で共変型パラメータ T を使う必要があります。スタックは共変のサブ型付けにしたいのですから、トリックを使います。メソッド push のパラメータ型上で抽象化します。push の型変数の下限境界として要素型 T を使う多相的メソッド [25]を得ます。これには、その共変型パラメータとしての宣言と協調する T の変位指定を持ち込む効果があります。今、スタックは共変です。しかしこのソリューションによれば、たとえば、整数スタック上に文字列をプッシュすることが可能となります。戻り値は型 Stack[Any] のスタックです。;整数スタックを期待するコンテキスト中で戻り値を使う場合にだけ、実際にエラーを検出します。そうでない場合、より汎用的な要素型のスタックを得ます。 Scala ひと巡り ビュー (Views) 原ページ 暗黙のパラメータ [63]とメソッドは、ビューと呼ばれる暗黙の型変換も定義できます。型 S から型 T へのビューは、関数型 S = T を持つ暗黙の値によって、あるいは、その型の値に変換可能なメソッドによって定義されます。 ビューは 2 つの状況で適用されます 式 e が型 T で、T が式の要請型(期待される型) pt に適合しないとき 型 T の e の選択 e.m 中で、セレクタ m が T のメンバーを意味しないとき 最初の場合は、 e に適用可能でその結果型が pt に適合するビュー v が検索されます。2 番目の場合は、e に適用可能でその結果型が m という名前のメンバーを含むビュー v が検索されます。 型 List[Int]の 2 つのリスト xs と ys 上の、次の操作は正しいです。 xs = ys ただし、下記で定義された 暗黙のメソッド list2ordered と int2ordered がスコープ中にあると仮定して implicit def list2ordered[A](x List[A]) (implicit elem2ordered a = Ordered[A]) Ordered[List[A]] = new Ordered[List[A]] { /* .. */ } implicit def int2ordered(x Int) Ordered[Int] = new Ordered[Int] { /* .. */ } list2ordered 関数は、型パラメータの可視境界(view bound:ビュー境界)を使っても表現できます implicit def list2ordered[A % Ordered[A]](x List[A]) Ordered[List[A]] = ... Scala コンパイラはこのとき、上記で与えられた list2ordered の定義に等価なコードを生成します。 暗黙のうちにインポートされる [64] オブジェクト scala.Predef は、いくつかの事前定義された型(たとえば Pair)とメソッド(たとえば error)ばかりでなく、いくつかのビューも宣言します。次の例は、事前定義されたビュー charWrapper のアイデアを示します final class RichChar(c Char) { def isDigit Boolean = Character.isDigit(c) // isLetter, isWhitespace, etc. } object RichCharTest { implicit def charWrapper(c char) = new RichChar(c) def main(args Array[String]) { println( 0 .isDigit) } } Scala ひと巡り XML 処理 (XML Processing) 原ページ Scala を使えば、XML ドキュメントの生成、解析、処理が簡単に行えます。Scala では、XML データをジェネリックなデータ表現を使うことであるいは、データに特化したデータ表現を用いて表現できます。後者の方法は、データ結合ツール schema2src によってサポートされます。 実行時表現 XML データはラベル付きのツリーとして表現されます。Scala 1.2から始まり(以前のバージョンでは -Xmarkup オプションを使う必要があります)、そのようなラベル付きノードを標準的な XML 構文を使って簡単に生成できます。 次の XML ドキュメントについて考えます。 html head title Hello XHTML world /title /head body h1 Hello world /h1 p a href="http //scala-lang.org/" Scala /a talks XHTML /p /body /html このドキュメントは、次の Scala プログラムで生成できます。 object XMLTest1 extends Application { val page = html head title Hello XHTML world /title /head body h1 Hello world /h1 p a href="scala-lang.org" Scala /a talks XHTML /p /body /html ; println(page.toString()) } Scala 式と XML をミックスできます。 object XMLTest2 extends Application { import scala.xml._ val df = java.text.DateFormat.getDateInstance() val dateString = df.format(new java.util.Date()) def theDate(name String) = dateMsg addressedTo={ name } Hello, { name }! Today is { dateString } /dateMsg ; println(theDate("John Doe").toString()) } データの結合 多くの場合、人は処理したい XML ドキュメントに関する DTD を持っています。そのための特別な Scala クラスを生成し、XML を解析し保存するためのコードがほしいことでしょう。Scala は、DTD を Scalaクラス定義 のコレクションに変えるといったことをあなたに代わって全部やってくれる、気のきいたツールになります。 schema2src ツールを使った文書化と例は、Burak のドラフト Scala xml book [65] にあることを書き留めておきます。 前 はじめ
https://w.atwiki.jp/sicpstudygroup/pages/43.html
naga Todo 1.40 Exercise 1.29 (define (integral f a b n) (let ((h (/ (- b a) n))) (define (next x) (+ x (* h 2))) (* (/ h 3) (+ (f a) (f b) (* 4 (sum f (+ a h) next (- b h))) (* 2 (sum f (+ a (* h 2)) next (- b (* h 2)))))))) ;;gosh (define (cube x) (* x x x)) ;;cube ;;gosh (integral cube 0 1 100) ;;1/4 ;;gosh (integral cube 0 1 1000) ;;1/4 Exercise 1.30 (define (sum term a next b) (define (iter a result) (if ( a b) result (iter (next a) (+ (term a) result)))) (iter a 0)) Exercise 1.31 (define (product-r term a next b) (if ( a b) 1.0 (* (term a) (product-r term (next a) next b)))) (define (product-i term a next b) (define (iter a result) (if ( a b) (* result 1.0) (iter (next a) (* (term a) result)))) (iter a 1)) (define (factorial n) (product-r (lambda (x) x) 1 (lambda (x) (+ x 1)) n)) ; ; 2/3*4/3が1項目,4/5*6/5が2項目 (define (pi-term x) (let ((x (* x 2)) (y (+ (* x 2) 1))) (/ (* x (+ x 2)) (* y y)))) (define (pi-next x) (+ x 1)) (define (pi-r n) (* 4 (product-r pi-term 1 pi-next n))) (define (pi-i n) (* 4 (product-i pi-term 1 pi-next n))) ;;gosh (factorial 6) ;;720.0 ;;gosh (time (pi-r 1000)) ;;;(time (pi-r 1000)) ;;; real 0.010 ;;; user 0.010 ;;; sys 0.000 ;;3.142377365093882 ;;gosh (time (pi-i 1000)) ;;;(time (pi-i 1000)) ;;; real 26.578 ;;; user 26.548 ;;; sys 0.010 ;;3.142377365093878 ;; iterativeは遅い??? (define (product-r term a next b) (if ( a b) 1 (* (term a) (product-r term (next a) next b)))) (define (product-i term a next b) (define (iter a result) (if ( a b) result (iter (next a) (* (term a) result)))) (iter a 1)) ; 2/3*4/3が1項目,4/5*6/5が2項目 (define (pi-term x) (let ((x (* x 2)) (y (+ (* x 2) 1))) (/ (* x (+ x 2)) (* y y)))) (define (pi-next x) (+ x 1)) (define (pi-r n) (* 4.0 (product-r pi-term 1.0 pi-next n))) (define (pi-i n) (* 4.0 (product-i pi-term 1.0 pi-next n))) ;;gosh (time (pi-r 1000)) ;;;(time (pi-r 1000)) ;;; real 0.010 ;;; user 0.010 ;;; sys 0.000 ;;3.142377365093882 ;;gosh (time (pi-i 1000)) ;;;(time (pi-i 1000)) ;;; real 0.010 ;;; user 0.010 ;;; sys 0.000 ;;3.1423773650938855 ;;pi-r,pi-nを次のように変更すると (define (pi-r n) (* 4.0 (product-r pi-term 1 pi-next n))) (define (pi-i n) (* 4.0 (product-i pi-term 1 pi-next n))) ;;gosh (time (pi-r 1000)) ;;;(time (pi-r 1000)) ;;; real 40.478 ;;; user 40.469 ;;; sys 0.000 ;;3.142377365093878 ;;gosh (time (pi-i 1000)) ;;;(time (pi-i 1000)) ;;; real 25.487 ;;; user 25.486 ;;; sys 0.000 ;;3.142377365093878 Exercise 1.32 ; recursive (define (accumlate-r combiner null-value term a next b) (define (op a) (if ( a b) null-value (combiner (term a) (op (next a))))) (op a)) ; iterative (define (accumlate-i combiner null-value term a next b) (define (iter a result) (if ( a b) result (iter (next a) (combiner result (term a))))) (iter a null-value)) ; product sum (define (product-r term a next b) (accumlate-r * 1 term a next b)) (define (product-i term a next b) (accumlate-i * 1 term a next b)) (define (sum-r term a next b) (accumlate-r + 0 term a next b)) (define (sum-i term a next b) (accumlate-i + 0 term a next b)) Exercise 1.33 (define (filterd-accumulate combiner null-value term a next b filter) (define (re a) (cond (( a b) null-value) ((filter a) (combiner (term a) (re (next a)))) (else (re (next a))))) (re a)) ; a (define (sum-square-prime a b) (filterd-accumulate + 0 (lambda (x) (* x x)) a (lambda (x) (+ x 1)) b prime?)) ; b (define (product-relatively-prime n) (define (rprime? i) (= (gcd i n) 1)) (filterd-accumulate * 1 (lambda (x) x) 1 (lambda (x) (+ x 1)) n rprime?)) ;;gosh (sum-square-prime 1 10) ;;88 ;;gosh (product-relatively-prime 10) ;;189 Exercise 1.34 (define (f g) (g 2)) ; ;(f f)- (f 2)- (2 2)...手続きでないエラー ;;gosh (f f) ;;*** ERROR invalid application (2 2) ;;Stack Trace ;;_______________________________________ Exercise 1.35 ;; 黄金比は x^2 = x+1 を満足するということから ;; x- 1+1/x ;;gosh ([[fixed-point]] (lambda (x) (+ 1 (/ 1 x))) 1.0) ;;1.6180327868852458 Exercise 1.36 (define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? v1 v2) ( (abs (- v1 v2)) tolerance)) (define (try guess step) (let ((next (f guess))) (display step) (display " ") (display guess) (newline) (if (close-enough? guess next) next (try next (+ 1 step))))) (try first-guess 1)) ;;gosh (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0) ;;1 2.0 ;;2 9.965784284662087 ;;3 3.004472209841214 ;;4 6.279195757507157 ;;5 3.759850702401539 ;;6 5.215843784925895 ;;7 4.182207192401397 ;; ;;31 4.555517548417651 ;;32 4.555547679306398 ;;33 4.555527808516254 ;;34 4.555540912917957 ;;4.555532270803653 ;;gosh (fixed-point (lambda (x) (average (/ (log 1000) (log x)) x)) 2.0) ;;1 2.0 ;;2 5.9828921423310435 ;;3 4.922168721308343 ;;4 4.628224318195455 ;;5 4.568346513136242 ;;6 4.5577305909237005 ;;7 4.555909809045131 ;;8 4.555599411610624 ;;9 4.5555465521473675 ;;4.555537551999825 Exercise 1.37 ;; a (define (cont-frac-i n d k) (define (iter k f) (if ( = k 0) f (iter (- k 1) (/ (n k) (+ (d k) f))))) (iter k 0)) ;; b (define (cont-frac-r n d k) (define (rec c) (if ( = c k) (/ (n c) (d c)) (/ (n c) (+ (d c) (rec (+ c 1)))))) (rec 1)) (define contcount-f (lambda (i) (cont-frac-i (lambda (i) 1.0) (lambda (i) 1.0) i))) (define (inc-contcount-loop contcount-f i) (define (iter c) (if ( i c) #t (begin (display c) (display " ") (display (contcount-f c)) (newline) (iter (+ c 1))))) (iter 1)) ;;gosh (inc-contcount-loop contcount-f 20) ;;1 1.0 ;;2 0.5 ;;3 0.6666666666666666 ;;10 0.6179775280898876 ;;11 0.6180555555555556 ;;12 0.6180257510729613 ;; ;;20 0.6180339850173578 ;;#t kを11以上に設定すれば4桁の精度が得られる。 Exercise 1.38 (define (e-2-cf i) (cont-frac (lambda (x) 1.0) (lambda (x) (if (= (remainder (+ x 1) 3) 0) (* (/ (+ x 1) 3) 2) 1.0)) i)) ;;gosh (inc-contcount-loop e-2-cf 20) ;;1 1.0 ;;2 0.6666666666666666 ;;3 0.75 ;;4 0.7142857142857143 ;;17 0.7182818284590651 ;;18 0.718281828459028 ;;19 0.7182818284590459 ;;20 0.7182818284590452 ;;#t ;;gosh (log (+ 2 (e-2-cf 20))) ;;1.0 Exercise 1.39 (define (tan-cf x k) (/ (cont-frac (lambda (i) (- (* x x))) (lambda (i) (- (* 2 i) 1)) k) (- x))) ;;pi/4を求めてtan-cfのxに設定してkを1→10に変化させてみる。 ;;gosh (/ (asin 1) 2) ;;0.7853981633974483 ;;gosh (define tan-cf-pi/4 (lambda (k) (tan-cf (/ (asin 1) 2) k))) ;;tan-cf-pi/4 ;;gosh (inc-contcount-loop tan-cf-pi/4 10) ;;1 0.7853981633974483 ;;2 0.9886892399342051 ;;3 0.9997876809149684 ;;7 0.9999999999998131 ;;8 0.9999999999999994 ;;9 1.0 ;;10 1.0 Exercise 1.40 後日 Exercise 1.41 (define (double f) (lambda (x) (f (f x)))) ;;gosh (((double (double double)) inc) 5) ;;21 Exercise 1.42 (define (compose f g) (lambda (x) (f (g x)))) ;;gosh ((compose square inc) 6) ;;49 Exercise 1.43 ;; function x - f(g(x)) (define (compose f g) (lambda (x) (f (g x)))) ;; (define (repeated-i f n) (define (iter g i) (if ( = i n) g (iter (compose f g) (+ i 1)))) (iter f 1)) (define (repeated-r f n) (if (= n 1) f (compose f (repeated-r f (- n 1))))) ;;gosh ((repeated-i square 2) 5) ;;625 ;;gosh ((repeated-r square 2) 5) ;;625 Exercise 1.44 ;; smoothing (define (smooth f) (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3))) (define (n-fold-smooth f n) ((repeated-r smooth n) f)) どうやって確認するか???
https://w.atwiki.jp/mtgflavortext/pages/10693.html
「変容する荒野は、我が氏族に永遠の保護を与えてくれる。その返礼を行うのは我らの義務である。」 ――ドロモカの戦士、カドリ "The Shifting Wastes provide our clan eternal protection. It is our duty to return the favor." ――Kadri, Dromoka warrior タルキール龍紀伝 【M TG Wiki】 名前
https://w.atwiki.jp/tmiya/pages/129.html
Scala ひと巡り (A Tour of Scala) 原ページ Published on The Scala Programming Language (http //www.scala-lang.org) . By admin . Created 2008-07-05, 20 31 ●学習者の参考になればと思って訳してみましたが、誤訳の可能性大ですので、正しいことを知りたい方は必ず原文をお読みください。ご意見その他は、このページの下へ投稿してください。 Scala は簡潔でエレガント、そして型安全な方法で共通のプログラミングパターンを表現できるよう設計された現代的なマルチパラダイム・プログラミング言語です。オブジェクト指向と関数型言語の特質をスムーズに統合します。 Scala はオブジェクト指向言語です すべての値がオブジェクトである [1]という意味で、Scala は純粋なオブジェクト指向言語です。オブジェクトの型と振る舞いをクラス [2]とトレイト [3]によって記述します。クラスはサブクラス化 [4]と、多重継承の欠点のない置換えである、柔軟なミックスインベースの合成 [5]メカニズムにより拡張されます。 Scala は関数型言語です すべての関数が値である[1]という意味で、Scala は関数型言語でもあります。Scala は無名関数の定義に簡単な構文 [6]を提供します。それは高階関数 [7]をサポートし、関数のネストを可能とし[8]、カリー化 [9]をサポートします。Scala のケースクラス [10]とパターンマッチング [11]の組み込みサポートは、多くの関数型プログラミング言語で使われる代数型をモデル化します。 さらに、Scala のパターンマッチングの概念は、右無視シーケンスパターン(right-ignoring sequence pattern) [13]の助けにより、XML データ [12]の処理へ自然に拡張されます。このコンテキストにおいて、シーケンス内包表記(sequence comprehensions) [14]はクエリの設計に役立ちます。 これらの特徴により Scala は、Web サービス[15]のようなアプリケーション開発に理想的なものとなっています。 Scala は静的な型付け言語です Scala は、抽象化が安全で首尾一貫した方法でなされることを静的に強制する、表現力豊かな型システムを備えています。 特に、型システムは次をサポートします。 ジェネリッククラス (generic classes [16]) 変位指定アノテーション (variance annotations [17]) 上/下限 型境界 (upper[18] and lower[19] type bounds) 内部クラスとオブジェクトメンバーとしての抽象型(inner classes [20] and abstract types [21] as object members) 複合型 (compound types [22]) 明示的に型付けされた自己参照 (explicitly typed self references [23]) ビュー (view [24]) 多相的メソッド (polymorphic methods [25]) ローカルな型推論 [26]機構のおかげで、ユーザーはプログラムに冗長な型情報で注釈を付ける必要がありません。これらフィーチャーの組み合わせは、プログラミング抽象の安全な再利用とソフトウェアの型安全な拡張に、強力な基盤を提供します。 Scala は拡張性に富んでいます 現場では、固有領域のアプリケーション開発はしばしば領域固有の言語拡張を必要とします。Scala は、新たな言語要素をライブラリの形でスムーズに容易に加えることのできる、言語メカニズムのユニークな組合せを提供します どのようなメソッドも中置あるいは後置演算子 [27]として使えます。そして 要請型(expected type 期待される型)に応じて、クロージャが自動的に構成されます[28](target typing ターゲットによる型付け)。 両フィーチャーの併用により、構文拡張なしで、またマクロのようなメタプログラミング機能の助けを借りずに、新しい構文を簡単に定義できるようになります。 Scala は Java や .NET と相互運用できます Scala は、ポピュラーな Java 2 実行環境(JRE [29])とうまく相互運用できるように設計されています。特に、主流のオブジェクト指向 Java プログラミング言語との相互作用は可能な限りスムーズです。Scala は、Java と同列のコンパイルモデル(ダイナミックなクラスローディング、分割コンパイル)を採用しており、既存の多数の高品質ライブラリにアクセスできます。.NET フレームワーク(CLR [30])のサポートも利用できます。 さらに次のページをお読みください。 Scala ひと巡り 抽象型 (Abstract Types) Scala ひと巡り アノテーション (Annotations) Scala ひと巡り クラス (Classes) Scala ひと巡り ケースクラス (Case Classes) Scala ひと巡り 事前定義された classOf 関数 (Predefined function classOf) Scala ひと巡り 複合型 (Compound Types) Scala ひと巡り シーケンス内包表記 (Sequence Comprehensions) Scala ひと巡り 抽出子オブジェクト (Extractor Objects) Scala ひと巡り ジェネリッククラス (Generic Classes) Scala ひと巡り 暗黙のパラメータ (Implicit Parameters) Scala ひと巡り 内部クラス (Inner Classes) Scala ひと巡り ミックスインクラス合成 (Mixin Class Composition) Scala ひと巡り 関数のネスト (Nested Functions) Scala ひと巡り 無名関数の構文 (Anonymous Function Syntax) Scala ひと巡り カリー化 (Currying) Scala ひと巡り 型依存クロージャの自動構築 (Automatic Type-Dependent Closure Construction) Scala ひと巡り オペレータ (Operators) Scala ひと巡り 高階関数 (Higher-Order Functions) Scala ひと巡り パッケージ (Packages) Scala ひと巡り パターンマッチング (Pattern matching) Scala ひと巡り 多相的メソッド (Polymorphic Methods) Scala ひと巡り 正規表現パターン (Regular Expression Patterns) Scala ひと巡り sealed クラス (Sealed Classes) Scala ひと巡り トレイト (Traits) Scala ひと巡り 上限 型境界 (Upper Type Bounds) Scala ひと巡り 下限 型境界 (Lower Type Bounds) Scala ひと巡り 明示的に型付けられた自己参照 (Explicitly Typed Self References) Scala ひと巡り サブクラス化 (Subclassing) Scala ひと巡り ローカルな型推論 (Local Type Inference) Scala ひと巡り 統合された型 (Unified Types) Scala ひと巡り 変位指定 (Variances) Scala ひと巡り ビュー (Views) Scala ひと巡り XML 処理 (XML Processing) 先頭 次 名前 コメント
https://w.atwiki.jp/jasagiri/pages/90.html
scala:http //www.scala-lang.org/ 基本JVM上で動作するバイトコードを吐く、静的だけど型推論により動的な、関数型オブジェクト指向言語だそうだ。 android上で動く。 GAE/J上で動く。 .Net用の msil を吐くライブラリがある。(.net でコンパイルできる) ScalaMecab Scala読物 ScalaDesignPatterns scalaメモ scala2.8変更点 Haskellぽい強力なパターンマッチング。 ErlangぽいActorモデル。 OCamlぽい型推論によるRubyぽい内部DSL向きな文法。 日本語でメソッド名とか変数名が書ける(ぉ)。 Rubyぽいカオスさ。 Java言語作った人が「お気に入り」と発言したらしい。(http //www.adam-bien.com/roller/abien/entry/java_net_javaone_which_programming) Groovy言語作った人が「知ってたら作らなかった」と発言したらしい。(http //macstrac.blogspot.com/2009/04/scala-as-long-term-replacement-for.html) Ruby言語作った人は「残念だ」と発言してる。(なんでrubyist.net繋がんないの?) ネタ: モジュール分割はオブジェクト指向、メソッドは関数型がわかりやすいかも(http //itpro.nikkeibp.co.jp/article/COLUMN/20090224/325385/?ST=develop)を検証する。 rubyのmonetaインタフェースをDuckTypingしたリソースライブラリ欲しい。(当面JRuby経由でDatamapperあわせて使うか?) phpのbearプロジェクトっぽいのが欲しい。 そろそろ要求定義からの流れを統一的に扱えるフレームワークが出てきてもいいころかと。 当面ラッパークラスの嵐になるのが悲しいのでpure scalaの勉強するべし。 http //www.codelogy.org/archives/2008/02/scala.html#more ツールやライブラリ: sbaz available で本家に登録されている一覧が出てくる。(日本語の説明は http //blog.takeda-soft.jp/blog/show/334) 名前 説明 備考 sbt Ant や Maven のようなBuild Tool。 Apache Ivy使ってるぽい。 ScalaTest 統一テスティング specs rspecクローン。 ソースきれい。 dispatch HTTPクライアント JSONとかOAuthとかもある scala-migration activerecord-migrationクローン scalamodules OSGi DSL Benchmark http //github.com/rakuto/benchmark-suite/tree/master ベンチマーク browse scala src browser scala-query jdbc base type-safe database api scalajdo JDOラッパー scalajpa JPAラッパー scala0.orm ORM surf CouchDBラッパー simpledb-scala-binding AmazonSimpleDBラッパー sbinary バイナリシリアライザ/デシリアライザ。 protobufやmessagepackぽいもの。 scala-dataflow Ozdataflowクローン jiva-ng 遺伝的アルゴリズム toolkit smr scara map reduce hadoopラッパー? kestrel starlingクローン twitter backend cachet HTTP Cache Proxy scalax The Scala Community Library scalanet プロトコルライブラリ? spmd port mapper daemon mittelos Event Calculus reasoning? simplemodeler モデリング2src Relaxerの浅海さん作 lift WEBフレームワーク Smalltalk の seaside ぽい? WebFlavor WEBフレームワーク web上で開発できるらしい。日本製 step sinatraクローン gdata-scala-client GDataクライアント scalify java2scala Scalaz steroidz? ScalaCheck?? dataset + machinist + fakerクローン テストデータ作成。 まだない? rcovクローン テストカバレッジ。jcoverageが使えるかも まだない? Heckleクローン 実装が壊れたときにテストが壊れるかどうか調べるツール まだない? rrクローン。 TestDoublesを実現。JRuby経由で十分か。RMockが使えるかも 必要ない? cucumber+webratクローン JRuby経由で十分か 必要ない? trac/redmine+hadson/CruiseControl+TestLinkクローン CIを実現。 必要ない? rackクローン jruby-rackで十分か。継続サーバっぽい使い方とかcometとか optional command line parsing scala-options ruby-OptionParserクローン joins Join演算ライブラリ scala-parallel パラレルコレクション? JSR166 p5scala processingラッパー ScalaIRCBot ircポット scalampp XMPPサーバ 話題のjabberプロトコル喋るサーバ qbert Actor based WEBサーバ dumpster webdavサーバ AIscala AIライブラリ メモ: supervisor:http //jonasboner.com/2008/06/16/erlang-style-supervisor-module-for-scala-actors/ protobufサンプル:http //github.com/eishay/protobuf-object-competability-example/tree/master toropy-scala:http //code.google.com/p/tropy-scala/ ScalaからMecabにアクセス:http //blog.xole.net/article.php?id=724 フィジカルコンピューティングデバイスGainerをscalaから触る:http //rainyday.blog.so-net.ne.jp/2009-01-04 scala + twitter :http //www.ibm.com/developerworks/jp/java/library/j-scala05059.html
https://w.atwiki.jp/dominions3/pages/366.html
Contact Nagini 人間の姿に変身できるNagaの姫Naginiを召喚します Contact Nagini ジェム 疲労 内部ID 201 25 使用 水中判定 効果 効果量 儀式 Summon Commander 主属性 主Lv 効果発生数 射程距離 Water 2 1 副属性 副Lv 効果範囲 命中補正 Earth 1 0 領域 Lv 防御判定 抵抗判定 Conjuration 4 専用国家 MA Bandar Log ゲーム内説明文 The Nagini is a Naga Princess from the Jeweled City of Patala. She is able to change her shape and wander the land of humans unnoticed. Naginis in human shape are strikingly beautiful and many young men have given up their comfortable lives to follow a Nagini into the Underworld. The Nagini can use their powers of seduction to lure generals from their masters and priests from their god. The Naginis are also skilled Water mages. In their Naga shape, their skill in Water magic is enhanced. 和訳 Naginiは、Patalaの宝石をちりばめた都市に住むNagaの王女です。彼女は姿を変えて、気付かれることなく人間の土地を歩き回ることができます。人間の姿をとったNaginiは非常に美しく、多くの青年がNaginiの後について冥界へと入るためその快適な生活を諦めました。Naginiは彼らの神から将軍や聖職者を離反させるために、その魅力を使うことができます。Naginiは熟練した水の魔術師でもあります。Nagaの姿をとると、彼女らの水の魔法の力はさらに強まります。 注記 Nagaの姫君、Naginiの召喚儀式。戦士としては優れているとは言い難いNagaだが、魔術師としては有能な傾向にあり、最下級のNaginiもそれに準ずる。 水1地1緑1聖1、追加で水地星緑から1を引く幅広い魔力が売りで、さらにNaga形態である限り水魔法に+1のブーストがかかるのが特徴。そのままでは靴が装備できないが、変身により魔力ボーナスは消えるが人間形態になれる。 身体的にはサイズ3としては見劣りするものの、それでも人間よりは丈夫。わざわざ前線に出したいとは思えないが、後方に控える分には事故死しにくく優秀。 変身中はStealthが付くが、補正がないので見つかり易い。包囲された要塞に出入りするなどの用途には支障はないが、警戒が厳しい敵地に入りこむのは危険。 そのためせっかくの誘惑能力もいまいち活かし難い。飛行能力のない彼女らでは味方領土に隣接した州でなくては誘惑を試みられないのもあり、その面での使い勝手はよろしくない。 コメント 名前 コメント