計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)
開発環境
- OS X Mavericks - Apple(OS)
- Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
- Scheme (プログラミング言語)
- Gauche (処理系)
計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力、オブジェクトおよび状態)、3.3(可変データでのモデル化)、3.3.3(表の表現)、二次元の表、局所表の作り方、問題 3.26.を解いてみる。
その他参考書籍
- Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
- プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
問題 3.26.
コード(BBEdit, Emacs)
sample3_26.scm
#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-
(define (make-table)
(define key-= =)
(define key-< <)
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
(list entry left right))
(define (adjoin-set x set)
(if (null? set)
(make-tree x '() '())
(let ((e (entry set)))
(if (key-< (car x) (car e))
(make-tree e
(adjoin-set x (left-branch set))
(right-branch set))
(make-tree e
(left-branch set)
(adjoin-set x (right-branch set)))))))
(let ((local-table '()))
(define (lookup-record key table)
(if (null? table)
#f
(let ((record (entry table)))
(let ((k (car record)))
(cond ((key-= key k) record)
((key-< key k)
(lookup-record key (left-branch table)))
(else
(lookup-record key (right-branch table))))))))
(define (lookup key)
(let ((record (lookup-record key local-table)))
(if record
(cdr record)
#f)))
(define (insert! key value)
(let ((record (lookup-record key local-table)))
(if record
(set-cdr! record value)
(set! local-table (adjoin-set (cons key value)
local-table))))
'ok)
(define (print-tree tree)
(define (display-indent n)
(if (= n 0)
(display "")
(begin (display " ")
(display-indent (- n 1)))))
(define (inner tree indent)
(if (null? tree)
(begin (display-indent indent)
(print "()"))
(begin (inner (left-branch tree)
(+ indent 1))
(begin (display-indent indent)
(print (entry tree)))
(inner (right-branch tree)
(+ indent 1)))))
(inner tree 0))
(define (dispatch m)
(cond ((eq? m 'lookup-proc) lookup)
((eq? m 'insert-proc!) insert!)
((eq? m 'p) (print-tree local-table))
(else (error "Unknown operation -- TABLE" m))))
dispatch))
test_sample3_26.scm
#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-
(load "./sample3_26.scm")
(define t (make-table))
(for-each (lambda (pair)
(print ((t 'insert-proc!) (car pair) (cdr pair)))
(t 'p))
(list (cons 5 'a)
(cons 7 'b)
(cons 9 'c)
(cons 6 'd)
(cons 8 'e)
(cons 10 'f)
(cons 1 'g)
(cons 2 'h)
(cons 3 'i)
(cons 4 'j)))
(for-each (lambda (key)
(print key ": " ((t 'lookup-proc) key)))
(list 1 2 3 4 5
11 12 13 14 15))
(for-each (lambda (pair)
(print ((t 'insert-proc!) (car pair) (cdr pair)))
(t 'p))
(list (cons 5 'j)
(cons 7 'i)
(cons 9 'h)
(cons 6 'g)
(cons 8 'f)
(cons 10 'e)
(cons 1 'd)
(cons 2 'c)
(cons 3 'b)
(cons 4 'a)))
(for-each (lambda (key)
(print key ": " ((t 'lookup-proc) key)))
(list 1 2 3 4 5
11 12 13 14 15))
入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))
$ ./test_sample3_26.scm
ok
()
(5 . a)
()
ok
()
(5 . a)
()
(7 . b)
()
ok
()
(5 . a)
()
(7 . b)
()
(9 . c)
()
ok
()
(5 . a)
()
(6 . d)
()
(7 . b)
()
(9 . c)
()
ok
()
(5 . a)
()
(6 . d)
()
(7 . b)
()
(8 . e)
()
(9 . c)
()
ok
()
(5 . a)
()
(6 . d)
()
(7 . b)
()
(8 . e)
()
(9 . c)
()
(10 . f)
()
ok
()
(1 . g)
()
(5 . a)
()
(6 . d)
()
(7 . b)
()
(8 . e)
()
(9 . c)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(5 . a)
()
(6 . d)
()
(7 . b)
()
(8 . e)
()
(9 . c)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(5 . a)
()
(6 . d)
()
(7 . b)
()
(8 . e)
()
(9 . c)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . a)
()
(6 . d)
()
(7 . b)
()
(8 . e)
()
(9 . c)
()
(10 . f)
()
1: g
2: h
3: i
4: j
5: a
11: #f
12: #f
13: #f
14: #f
15: #f
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . d)
()
(7 . b)
()
(8 . e)
()
(9 . c)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . d)
()
(7 . i)
()
(8 . e)
()
(9 . c)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . d)
()
(7 . i)
()
(8 . e)
()
(9 . h)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . g)
()
(7 . i)
()
(8 . e)
()
(9 . h)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . g)
()
(7 . i)
()
(8 . f)
()
(9 . h)
()
(10 . f)
()
ok
()
(1 . g)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . g)
()
(7 . i)
()
(8 . f)
()
(9 . h)
()
(10 . e)
()
ok
()
(1 . d)
()
(2 . h)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . g)
()
(7 . i)
()
(8 . f)
()
(9 . h)
()
(10 . e)
()
ok
()
(1 . d)
()
(2 . c)
()
(3 . i)
()
(4 . j)
()
(5 . j)
()
(6 . g)
()
(7 . i)
()
(8 . f)
()
(9 . h)
()
(10 . e)
()
ok
()
(1 . d)
()
(2 . c)
()
(3 . b)
()
(4 . j)
()
(5 . j)
()
(6 . g)
()
(7 . i)
()
(8 . f)
()
(9 . h)
()
(10 . e)
()
ok
()
(1 . d)
()
(2 . c)
()
(3 . b)
()
(4 . a)
()
(5 . j)
()
(6 . g)
()
(7 . i)
()
(8 . f)
()
(9 . h)
()
(10 . e)
()
1: d
2: c
3: b
4: a
5: j
11: #f
12: #f
13: #f
14: #f
15: #f
$
0 コメント:
コメントを投稿