SICPを読む上でよく見るメモ

ゼミのたびに「あの単語の意味ってなんだったっけ?」って事案が多発するので定義をまとめた記事を作ります。 適用順序評価と正規順序評価 正規順序評価(normal-order evaluation) 完全に展開してから簡約する。 適用順序評価(applicative-order evaluation)…

SICPゼミ第50回

練習問題4.22 (define (analyze-let exp) (analyze (let->combination exp))) (define (let->combination exp) (let ((defs (let-defs exp))) ((make-lambda (let-variable-from-defs defs) (let-body exp)) (let-defbody-from-defs defs)))) (define (let-d…

SICPゼミ第49回

練習問題4.21 a ((lambda (n) ((lambda (fib) (fib fib n)) (lambda (ft k) (if (< k 2) 1 (+ (ft ft (- k 2)) (ft ft (- k 1))))))) 5) by tube b (define (f x) ((lambda (even? odd?) (even? even? odd? x)) (lambda (ev? od? n) (if (= n 0) true (od? e…

SICPゼミ第48回

練習問題4.20b by チューブワアアアァァァァム

SICPゼミ第47回

練習問題4.20 4.18 と一緒なのでパス。

SICPゼミ第46回

練習問題4.18 (define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define dy (stream-map f y)) y) (define (solve_ f y0 dt) (let ((y '*hoge*) (dy '*hoge*)) (let ((a (integral (delay dy) y0 dt)) (b (stream-map f y))) (set! y a) (se…

SICPゼミ第45回

練習問題4.16 (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 )) (if (eq? (car vals) '*unassigned*) (error "Unassigned…

SICPゼミ第44回

練習問題4.14 なんかタグとかがうまく処理されないと思う。 by tube 練習問題4.15 ネゲートして自分を突っ込む。終わり。 by tube

SICPゼミ第43回

練習問題4.11 (define (make-frame variables values) (if (= (length variables values)) (if (null? variables) nil (cons (cons (car variables) (car values))) (make-frame (cdr variables) (cdr values))) (if (< (length variables) (length values))…

SICPゼミ第42回

練習問題4.7 (define (let*->nested-lets exp) (let ((defs (car exp)) (body (cdr exp))) (if (null? (cdr defs)) (list 'let (car defs) body) (list 'let (car defs) (let*->nested-lets (pair (cdr defs) body)))))) by dolicas 問題文で言ってる派生式…

SICPゼミ第41回

練習問題4.4 (define (eval-and exp env) (cond ((null? exp) #t) ((null? (cdr exp)) (eval (cdr exp) env)) ((not (eval (car exp) env)) #f) (else (eval-and (cdr exp) env)))) (define (and? exp) (tagged-list? exp 'and)) by dolicas 派生式の方もで…

SICPゼミ第40回

2章はやばいので4章に帰ってきました。 練習問題4.2 applicaionかどうかの判定 (application?) はタグを気にせずペアかどうかしか見ていない.これが最後でないと (define …) みたいなのも適用として扱ってしまうのでおかしくなる. call を使うことにするの…

SICPゼミ第39回

練習問題2.92 係数がy の多項式であるx の多項式と係数がx の多項式であるy の多項式の両方が与えられる問題だと考えるとなかなかえぐいので次回に続く。

SICPゼミ第38回

練習問題2.91 (define (install-polynomial-package) ;; 内部手続き ;; poly の表現 (define (make-poly variable term-list) (cons variable term-list )) (define (variable p) (car p)) (define (term-list p) (cdr p)) (define same-variable? eq?) (def…

SICPゼミ第37回

練習問題2.88 install-polynomial-package内に以下の関数を追加する。 (define (inversion termList) (if (empty-termlist? termList) termList (let ((term (first-term termList))) (if (eq? (type-tag term) 'polynomial) (adjoin-term (make-term (order…

SICPゼミ第36回

練習問題2.78からやり直し 練習問題2.78 (define (attach-tag type-tag contents) (if (eq? type-tag 'scheme-number) contents (cons type-tag contents ))) (define (type-tag datum) (if (pair? datum) (car datum) (if (number? datum) 'scheme-number (…

SICPゼミ第35回

練習問題2.82 例えば引数が長方形と菱形と正方形であるときを考えると、全ての引数を平行四辺形に強制型変換しなければならないが、各引数の型へと変換しようとする限り、平行四辺形にはたどり着かない。つまり、型の関係において分岐が生じており、その分岐…

SICPゼミ第34回

2章に帰ってきました。put, get など (define (key-compare a b) 0) (define (make-table) (let (( local-table (list '*table* ))) (define (lookup key-1 key-2) (let (( subtable (assoc key-1 (cdr local-table )))) (if subtable (let (( record (assoc…

SICPゼミ第33回

練習問題4.1 左から右 (define (list-of-values exps env) (if (no-operands? exps) '() (let ((val (eval (first-operand exps) env))) (cons val (list-of-values (rest-operands exps) env))))) 右から左 (define (list-of-values exps env) (if (no-oper…

SICPゼミ第32回

練習問題3.81 (define (rand-stream stream) (define (rand-stream-iter stream mt) (if (stream-null? stream) the-empty-stream (let ((message (stream-car stream))) (if (eq? message 'generate) (cons-stream (mt-random-integer mt 1000) (rand-strea…

SICPゼミ第31回

練習問題3.77 (define (integral delayed-integrand initial-value dt) (cons-stream initial-value (let ((integrand (force delayed-integrand))) (if (stream-null? integrand) the-empty-stream (integral (delay (stream-cdr integrand)) (+ (* dt (str…

SICPゼミ第30回

練習問題3.73 (define (RC R C dt) (define (calc i v0) (add-streams (scale-stream i R) (integral (scale-stream i (/ 1 C)) v0 dt))) calc) 民主主義しゅき〜〜(ドナルド・トランプ) 練習問題3.74 (define (sign-change-detector now last) (if (> (* …

SICPゼミ第29回

練習問題3.67 (define (pairs s t) (cons-stream (list (stream-car s) (stream-car t)) (interleave (interleave (stream-map (lambda (x) (list (stream-car t) x)) (stream-cdr s)) (stream-map (lambda (x) (list x (stream-car t))) (stream-cdr s))) (…

SICPゼミ第28回

練習問題3.63 Reasoner の方法では毎回新しい sqrt-stream (lambda closure の中) を作り出してひとつめの項から計算し直しているので、実質メモ化を行っていないのと同じで、無駄な計算が多くなる。by tube

SICPゼミ第27回

練習問題3.53 1,2,4,8,16.... 練習問題3.54 (define (mul-streams s1 s2) (stream-map * s1 s2)) (define factorials (cons-stream 1 (mul-streams (stream-cdr integers) factorials)))

SICPゼミ第26回

練習問題3.50 (define (stream-map proc . argstreams) (if (null? (car argstreams )) the-empty-stream (stream-cons (apply proc (map stream-car argstreams)) (apply stream-map (cons proc (map stream-cdr argstreams)))))) by dolicas 練習問題3.51 …

SICPゼミ第25回

練習問題3.48 ループができないから。serialized-exchange の実装例 ;今までの serialized-exchange と同じやつ (define (serialized-exchange account1 account2) (let (( serializer1 (account1 'serializer )) (serializer2 (account2 'serializer ))) ((…

SICPゼミ第24回

練習問題3.46 スレッド1が(car cell)した結果falseが返ってくる→スレッド1が(set-car! cell true)する前にスレッド2が(car cell)してfalseを得る→同時に2つのスレッドがmutexを獲得できたものとして実行されてしまう。 練習問題3.47 (a) (define (make-semap…

SICPゼミ第23回

練習問題3.38 a. 35 Peter->Mary->Paul 40 Mary->Peter->Paul (後ろ二人順不同) 45 Peter->Paul->Mary (前二人順不同) 50 Paul->Mary->Peterb. 60 by tube 練習問題3.39 100, 101, 121.by tube 練習問題3.40 10^k (k = 2,3,4,5,6)直列化すると10^6だけby dol…

SICPゼミ第22回

練習問題3.32 入力を 0,1 → 1,1 → 1,0 と変化させたとき振る舞いが変わる。 一回目の入力の変化で「出力を1にする」という予定が追加され、その後2回目の入力の変化で「出力を0にする」という予定が追加される。キューだとこの順番に処理されるので出力は最…

SICPゼミ第21回

練習問題3.31 実行環境 DrRacket > (define input-1 (make-wire )) (define input-2 (make-wire )) (define sum (make-wire )) (define carry (make-wire )) > (probe 'sum sum) > (probe 'carry carry) > (half-adder input-1 input-2 sum carry) 'ok > (pr…

SICPゼミ第20回

練習問題3.27

SICPゼミ第19回

練習問題3.24 (define (make-table same-key?) (let ((table (list '*table*))) (define (lookup key) (let ((record (assoc key (cdr table)))) (if record (cdr record) #f))) (define (assoc key records) (cond ((null? records) #f) ((same-key? key (c…

SICPゼミ第18回

練習問題3.21 (define (print-queue queue) (display (car queue))) Benはqueueの末尾のポインタを見てはっちゃけてるだけ。 by pine 練習問題3.22 (define (make-queue) (let ( (front-ptr '()) (rear-ptr '()) ) (define (empty-queue?) (null? front-ptr)…

SICPゼミ第17回

練習問題3.12 1つめの (cdr x) は (b) 2つめの (cdr x) は (b c d)1つめでは x が (a b) なので (b) が返る。 2つめでは x が append! にある set-cdr! のせいで (a b c d) になっているので (b c d) が返る。by tube 練習問題3.13 a -> b -> c -> a ->.....…

SICPゼミ第16回

練習問題3.10

SICPゼミ第15回

練習問題3.5, 3.6 は乱数生成のやつがなんかうまくいかないので飛ばし。 練習問題3.7 (define (make-joint acc password newpassword) (define (dispatch2 pw m) (if (eq? pw newpassword) (acc password m) (error "Incorrect password"))) (if (= ((acc pa…

SICPゼミ第14回

3章のテーブル演算の実装を読んでから2章の残りに帰ってくることにしました。 練習問題3.1 (define (make-accumulator initial) (lambda (amount) (begin (set! initial (+ initial amount)) initial))) by pine 練習問題3.2 (define (make-monitored func) …

SICPゼミ第13回

今日も人生がつらい。 Gauche ユーザリファレンス: 7.4 ジェネリックファンクションとメソッド 練習問題2.75 (define (make-from-mag-ang r theta) (define (dispatch op) (cond ((eq? op 'real-part) (* r (cos theta))) ((eq? op 'imag-part) (* r (sin th…

SICPゼミ第12回

ほげぴよ〜 練習問題2.71 こんな感じだから最も頻度が高い文字が1bitで最も頻度が低いものがn-1bit

SICPゼミ第11回

練習問題2.59 (define (union-set set1 set2) (cond ((null? set1) set2) (else (adjoin-set (car set1) (union-set (cdr set1) set2))) ) ) by dolicas 練習問題2.60 union-set、adjoin-setは実装が楽で計算も軽い。intersectionの効率が悪い。これ役に立つ…

SICPゼミ第10回

練習問題2.53 gosh> (list 'a 'b 'c) (a b c) gosh> (list (list 'george )) ((george)) gosh> (cdr '((x1 x2) (y1 y2))) ((y1 y2)) gosh> (cadr '((x1 x2) (y1 y2))) (y1 y2) gosh> (pair? (car '(a short list ))) #f gosh> (memq 'red '((red shoes) (blu…

SICPゼミ第9回

練習問題2.43 (queen-cols (- k 1)) をk回呼び出しているのでごみ。 注意 これから先の範囲は図形言語を前提としているので、tube は Racket で、ほか三人は Gauche でがんばって図形言語を入れました。

SICPゼミ第8回

練習問題2.33 (define nil '()) (define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence ))))) (define (map p sequence) (accumulate (lambda (x y) (cons (p x) y)) nil sequen…

SICPゼミ第7回

練習問題2.24 練習問題2.25 (car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9)))))) (car (car (list (list 7)))) (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))))))))))))) by …

SCIPゼミ第6回

練習問題2.12 (define (make-center-percent c p) (define w (* c (/ p 100))) (make-interval (- c w) (+ c w))) by どりきゃす

SICPゼミ第5回

練習問題2.1 正と負の両方の引数を扱うことができる改良版make-rat を定義せよ。make-rat は符号を正規化し、正の有理数であれば分子と分母の両方が正となり、負の有理数であれば分子のみが負になるようにする。 (define (numer x) (car x)) (define (denom …

SICPゼミ第4回

読んでるpdf github.com 練習問題1.29 (define (sum term a next b) (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) (define (sympthon f a b n) (define h (/ (- b a) (* n 1.0))) (define (sympthon-term x) (+ (* 2.0 (f x)) (* 4.0 (f (+ x h…

SICPゼミ第3回

読んでるpdf github.com 練習問題1.17 対数時間で掛け算を定義せよ(再帰的に) (define (fast-prod b n) (define (even? a) (= (remainder a 2) 0)) (define (double a) (* 2 a)) (define (halve a) (/ a 2)) (cond ((= n 0) 0) ((even? n) (double (fast-pro…

SICPゼミ第2回

読んでるpdf github.com 1.2 手続きとそれが生成するプロセス プロセスと手続きという単語が出てくるが、プロセスは所謂OS的な意味でのプロセス。手続きは演算処理と認識した。プロセスとプログラムとも換言できるかも。