SICP 読み (399) 未読了ですが纏め - yamanetoshi's diary
まだ 2 問残っている上にスルーした箇所もあるのですが感想を投入。 先日、ひげぽんさんにお会いした時にも「一番ハマッたのどこよ??」みたいな質問されたりしてたのですが、後天性記憶不全のためか微妙な回答しかできず。 # ゴメンナサイゴメンナサイ ただ、SICP な取り組みの中では辛くて苦しくて、なソレは皆無だったように思います。とは言え、SICP を手に入れてしばらくは 2 章の 8queen らへんまでしか目を通す事ができていませんでした (もしかすると仕事で 8queen ガラミのネタが必要で途中をスッ飛ばしてそこだけチェックしたのかも。8queen の問題とか理解不能でしたが、数え上げてフィルタかけて集約というソレは大いに参考になった記憶あり)。処理系はその頃 guile 入れてて Kent Dyvbig さんのテキストも購入してたりしたのですが手が動かず。 さすがに手を動かさずぼさっ
ひげぽん OSとか作っちゃうかMona- - 「計算機プログラムの構造と解釈(SICP)」を読み終えて
約半年をかけて計算機プログラムの構造と解釈(SICP)を読み終わりました。 （途中で、練習問題をスキップしたりしましたが・・・） 半年もかけたのでちょっとだけ振り返って見ます。 SICPを読む過程で得たもの まずはSICPを読む過程で得たものからざっと列挙してみよう。 構文解析を理解し自前で実装できるようになった 字句解析を理解し自前で実装できるようになった ストリームを理解した 遅延評価を理解した 手続きが first class objectである言語での考え方を学んだ 型変換の導入の動機とその意味を理解した 手続きの抽象化の導入の動機と過程を学んだ 高階関数を使ったり書けるようになったりした クロージャを理解した Schemeを書けるようになった 再帰処理を自然に書けるようになった フルスクラッチでインタプリタを書けるようになった コンパイラを自前で書くことが出来そうだとの感触を得た
関数型言語の勉強にSICPを読もう - (80) 5章 - レジスタ計算機での計算(295-319ページ) - higepon blog
しばらくサボっていたので反省して一気に読み進める。 ちょっと難しいところにさしかかったので、まとめて読んだ方が忘れなくて良い。 レジスタ計算機は、仮想的な話なのだけどコンピュータの奥底を眺めているようで不思議な気持ち。 5.1.2 レジスタ計算機の記述言語 データパスと制御器の話。データパスの図が僕にとって直感的にみづらく苦労した。 5.1.3 サブルーチン いわゆる call の話。共通手続きを共有しようという意図なのはもともと理解できていたが、導入の動機が「ハードウェア的に同じような計算器を組み立てるのは経済的でない」ってのは新鮮な切口だった。 5.1.4 再帰を実装するためのスタックの使用 スタックデータ構造が必要だよねという話。 5.1.5 命令の要約 5.2.1 計算機モデル レジスタ計算機のシミュレータの話。CPUの創り方という本で学んでいたのと、多少のアセンブリの知識があるの
関数型言語の勉強にSICPを読もう - (61) 4章 - 超言語的抽象(220ページ) C++でSchemeインタプリタを作ろう10 - higepon blog
Primitive Procedureの実装をした。 例えば + という手続きがあるがこれはSchemeインタプリタが primitive に持つ手続きである。 Schemeのオブジェクト define/lambda/Variableなどを組み合わせだけでは作れないものである。 このような Primitive Procedureはインタプリタ起動時に Environment に追加される。 environment->defineVariable(new Variable("+"), new Plus());Plusは PrimitiveProcedureクラスを継承したクラスで、"+"という名前でアクセスできるようになります。 applyでは Primitive Procedureかどうかで分岐し、Plus::applyが呼ばれます。 結構適当な実装です。桁あふれとか考慮してません。 Ob
関数型言語の勉強にSICPを読もう - (57) 4章 - 超言語的抽象(220ページ) C++でSchemeインタプリタを作ろう5 - higepon blog
最近、字句解析とか構文解析をしていましたが、その試行錯誤のサマリです。 前提 SICPの４章ではSchemeのインタプリタをSchemeで実装します。 勉強のためにC++で実装してみます。 基本はScheme->C++に置き換えています。（そんなに簡単じゃないけど） 置き換え以外の部分が字句解析・構文解析です。 なぜ構文解析が必要か Schemeインタプリタ(以後インタプリタ)をScheme(以後Gauche)で実装する場合と入力の扱いが違うからです。 インタプリタでは入力を受け付けますが、実際にはGaucheが入力を受け取り、Gaucheが手続き eval にそのまま渡します。 この際、Gaucheが受け取る入力はS式ですが、Gaucheはそれ自体S式をS式として認識しているので特に難しい作業は必要ありません。 一方、C++で実装する場合、入力は"(+ a b)"のように文字列で与えられ
関数型言語の勉強にSICPを読もう - (53) 4章 - 超言語的抽象(216ページ) C++でSchemeインタプリタを作ろう1 - higepon blog
4章では Scheme の上に Schemeインタプリタを作る過程でいろいろなものを学んでいきます。 このように、被実装言語と実装言語が同じなことを metacircular というらしいのですが、読んでいるだけでドキドキしてきます。 実際4章を読み進めていくと、とても面白いのですが、所々で引っかかるところがあります。 どうも読んでいるだけでは解決しないモヤモヤがあって、それは被実装言語と実装言語の境界に関する問題のように思えてきました。 metacircularだと、どこまでが被実装言語の機能で、どこからが実装言語の機能なのか分からなくなってきてしまうのです。 こんな経緯もあり、4章で書かれているSchemeインタプリタを「ほぼそのまま」C++で実装してみようという思いに至りました。 最近SICP日記を更新できなかったのはこのあたりに悩んでいたからです。 いろいろと困難あるでしょうが、試
関数型言語の勉強にSICPを読もう - (52) 4章 - 超言語的抽象(213-217ページ) - apply - higepon blog
apply 実装の肝は apply と env のあたりだということに気づく。 (define (apply procedure arguments) (cond ((primitive-procedure? procedure) (apply-primitive-procedure procedure arguments)) ((compound-procedure? procedure) (eval-sequence (procedure-body procedure) (extend-environment (procedure-parameters procedure) arguments (procedure-environment procedure)))) (else (error "Unknown procedure type -- APPLY" procedure))))
クロージャとブロック (前編) - Teny's Log
上のエントリでは、これまで考察してきたクロージャについての簡単なまとめを行ないました。そのエントリで最後に書いたブロックにも着目しながら、これまで考察してきたクロージャについて、コードを挙げて検証してみようと思います。 さて、上のエントリでは、クロージャの基盤となっている三つの仕様を挙げています。 しかし、これらのうちの幾つかが欠ける場合でも、Scheme で言うところのクロージャではないかもしれませんが、有効に利用可能な手続きを活用することは可能であると、私は考えています。 これは、上で挙げた三つの仕様が揃わない言語環境に於いて、クロージャの様な仕組みを活用することが可能か、という視点に置き換えることができます。例えば、Emacs Lisp や Java などでクロージャの様なコードを書けるか否か、ということですね。 ;; Java にもクロージャを導入可能に (?) といった動きもある
クロージャについて: 一旦、簡単にまとめてみます。 - Teny's Log
これまで考察してきたクロージャの件ですが、まだまだ頭の中では発散しているのですけど、一旦、簡単にまとめておきたいと思います。 ただ書き散らかしているだけでは意味ない (いや、意味はあると思ってるんですけど。自己矛盾だ。) ですからね。 Rui さん、shiro さんのコメントに助けられて、今では、 手続きをファーストクラスオブジェクトとして扱える。 静的スコープを持つ。 無限のエクステントが保証されている。 の三つの基盤が揃うことで、クロージャが実現されていると考えるに至りました。 Scheme 以外ではどうか判りませんが、こと Scheme に於いては、上の仕様に立脚する形でクロージャが実現されていると考えて差し支えないと思っています。 ただ、言語設計の推移としては、shiro さんから頂いたコメントで示唆されている様に、動的スコープに於ける環境問題 (FUNARG problem) が
遅延評価によるストリーム、Perl で。 : torus solutions!
SICP の 3.5 節「ストリーム」に出てきたストリームを Perl で実装してみた。 意外と簡単に書けた。 SICP のお買い上げは、アマゾンの 『計算機プログラムの構造と解釈』 のページからどうぞ〜。 概要 ストリームを使うと、 プログラムに状態変化を持ち込むことなく、 物事の変化を扱うことができるらしい。 必要な時に必要なだけの計算をするのに、 実際に計算をする部分と、 その計算された値を使う部分を完全に分離した形でコーディングできるので、 非常に強力なテクニックとなり得る。 ストリームは遅延リストとして実装するので、 まず遅延評価を実現するための手続き delay と force をそれらしく作り、 その上にストリームを構成するいくつかの関数を書いてみた。 実装 以下に、 テキストに出てきた Scheme でのコードと、 それに対応する Perl のコードを順番に載せます。 スト
関数型言語の勉強にSICPを読もう - (47) 3章 - 標準部品化力、オブジェクトおよび状態 (191ページ) - higepon blog
4章を先読みとかしているくせに、全然3章が進んでいないので反省中。 今日は問題3.50が解けるまで寝ない！と決めたらわりとすぐに解けた。 問題3.50 cons-streamや、stream-carをまだ定義していなくて、テストができないので cons/carで実装してみた。 (define (hige-map proc . argstreams) (if (null? (car argstreams)) '() (cons (apply proc (map car argstreams)) (apply hige-map (cons proc (map cdr argstreams)))))) (display (hige-map + (list 1 2 3) (list 4 5 6)))mapに car や cdr を渡すところが思いつくのに時間のかかった部分だった。 ということで答え
関数型言語の勉強にSICPを読もう - (40) 3章 - 標準部品化力、オブジェクトおよび状態 (156-163ページ) - higepon blog
待ちに待っていたデジタル回路のシミュレーション。 オラ、何だかワクワクしてきたぞ！ 問題3.24-27 略。 問題3.28 and とほぼ同じ。 今の段階では add-action の実装が見えないので or-action-procedure が2回呼ばれておかしくなるんじゃないかと心配。 と思ったけどよく考えれば入力は同時に届くことはありえないのでこれで正しい。 (define (or-gate a1 a2 output) (define (or-action-procedure) (let ((new-value (logical-or (get-signal a1) (get-signal a2)))) (after-delay or-gate-delay (lambda () (set-signal! output new-value))))) (add-action! a1 or
関数型言語の勉強にSICPを読もう - (39) 3章 - 小休止 ファイルI/Oと正規表現 - higepon blog
実用っぽいコードを書かないと中々上達しないと思うので無理やり書いてみました。 引数で受け取ったファイルを開いて、ファイル内を置換する。 「sedとかPerlならすぐに書けるよ」とか「もっと汎用化したスクリプトを書いたほうが良い」というのは分かるのですがまずは練習ということで。 まだ完成していなくて、現在分かっている問題点は 入力と出力ファイルを同じにするとおかしくなる 結果文字列が""で囲まれてしまう 改行コードがなくなってしまう などなど。 気長に直していこう。 #!/usr/bin/env gosh (use file.util) (define (main args) (define (replace-text file) (let ((lines (file->string-list file)) (result "")) (for-each (lambda (line) (set
関数型言語の勉強にSICPを読もう - (36) 3章 - 小休止 port-foreach - higepon blog
Ruiさんよりコメントを頂きました。 Schemeに慣れた人が書くとこんなにもきれいなのか。ありがとうございます。 このようにコードを見せていただくことはとても勉強になります。 sum は (apply + list) と書けますね。Gaucheだとport-for-eachという便利な高階手続きがあって、それをつかうと全体は次のようになります。(一時ファイルを使わないで済むよう、call-with-input-fileの代わりにcall-with-input-stringを使いました。) たしかに、sum は (apply + list)ですね。何で気づかなかったんだろう。 (port-for-each (lambda (list) (print (apply + list))) (call-with-input-string ”(1 2 3) (4 5 6)” (lambda (in)
関数型言語の勉強にSICPを読もう - (35) 3章 - 小休止 外の世界とつながろうファイルを読む - higepon blog
#scheme-jp(wide系 IRCチャンネル)でのネタふりで、ファイルの読み込みを学んでみました。 Schemeは port を介して入出力するようです。 面白いのが read の戻り値がS式だということです。（これはひらっちさんから教えてもらいました。) なのでファイルの中身がS式だといろいろと面白いことが出来そうなので作ってみました。 まず data.scm を用意します。 (list 1 2 3 4 5 6 7 8 9) (list 1 1 1 1 1 1 1 1 1) 次はプログラム本体です。 data.scmを読み込んで、read した S式のlistの要素を sum して表示します。 (define (sum l) (if (null? l) 0 (+ (car l) (sum (cdr l))))) (call-with-input-file "data.scm" (l
関数型言語の勉強にSICPを読もう - (34) 3章 - 標準部品化力、オブジェクトおよび状態 (156ページ) - higepon blog
問題3.22 え？手続きで出来るの?と思って一瞬でも疑った自分を恥じます。 Scheme楽しいよ。楽しすぎるよ。 (define (make-queue) (let ((front-ptr '()) (rear-ptr '())) ;; public interface (define (empty-queue?) (null? front-ptr)) (define (front-queue) (if (empty-queue?) (error "empty queue") (car front-ptr))) (define (insert-queue! item) (let ((new-pair (cons item '()))) (cond ((empty-queue?) (set! front-ptr new-pair) (set! rear-ptr new-pair)) (els
関数型言語の勉強にSICPを読もう - (32) 3章 - 小休止 beginを利用した print デバッグについて - higepon blog
以前、traceを利用したデバッグ方法を紹介しました。 今日は begin を利用した print デバッグの方法を紹介します。 SICPを1ページ目から順に読んでいくと begin がなかなか出てこないのですが、今日 begin を知りこのデバッグ方法に気づきました。 例えば (define (a) (let ((state 0)) (define (b) (if (some-condition) (some-func) (else-func) ))) たくさんの処理 )のような手続きがあるとします。 このときに手続き b の戻り値は (some-func)か、(else-func)なのですが、(some-codition)を実行後に state の値を知りたい場合があると思います。 この場合 (display state)をどこかに挿入すればよさそうなのですが、if の中に隙がなさそう
関数型言語の勉強にSICPを読もう - (28) 3章 - 標準部品化力、オブジェクトおよび状態 (127-133ページ) - higepon blog
3章はいよいよ代入とかオブジェクトとかが登場します。 参照透明性という概念や、代入という概念の導入で何が変わるかとかそのあたりが書いてあるようです。 代入と局所状態 問題3.1 この程度ならスラスラ書けるようになった。 (define (make-accumulator start) (lambda (num) (set! start (+ start num)) start)) (define A (make-accumulator 5)) (define B (make-accumulator 10)) (display (A 3)) (display (B 3)) (display (A 3)) 問題3.2 (define (make-monitored f) (let ((counter 0)) (define (dispatch m) (if (eq? m 'how-many-c
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
『関数型言語の勉強にSICPを読もう - (52) 4章 - 超言語的抽象(213-217ページ) - apply - higepon blog』へのコメント
関数型言語の勉強にSICPを読もう - (33) 3章 - 標準部品化力、オブジェクトおよび状態 (152-155ページ) - higepon blog