SICP exhibit, MIT Museum Includes a battered copy of SICP, the original class notes that were turned into the textbook, and a collection of translated editions. Done

まだ 2 問残っている上にスルーした箇所もあるのですが感想を投入。 先日、ひげぽんさんにお会いした時にも「一番ハマッたのどこよ??」みたいな質問されたりしてたのですが、後天性記憶不全のためか微妙な回答しかできず。 # ゴメンナサイゴメンナサイ ただ、SICP な取り組みの中では辛くて苦しくて、なソレは皆無だったように思います。とは言え、SICP を手に入れてしばらくは 2 章の 8queen らへんまでしか目を通す事ができていませんでした (もしかすると仕事で 8queen ガラミのネタが必要で途中をスッ飛ばしてそこだけチェックしたのかも。8queen の問題とか理解不能でしたが、数え上げてフィルタかけて集約というソレは大いに参考になった記憶あり)。処理系はその頃 guile 入れてて Kent Dyvbig さんのテキストも購入してたりしたのですが手が動かず。 さすがに手を動かさずぼさっ

ひげぽんさんの所をパクってテンプレートにして書いてみました。 練習問題をスキップしつつ、私も約半年でで読み終えました。とても楽しい日々を過ごすことができました。 SICPを読む過程で得たもの ・遅延評価とstream ・制約プログラミング、ロジックプログラミング、amb ・Emacs(Meadow)＋gauche＋Quackの組み合わせ便利 ・同じ事を表現するのに、抽象度を上げたり、下げたりできること。 ・手加減してあればLispのソースも追えるようになった。手加減していないのは駄目。 ・Lisp特有の、手続きを評価する→S式ができる→また評価する→S式ができる、という気持ち悪い再帰の存在。 ・SICP読み仲間ではないけどいろんなblogつながり。組み込みとFPGAだけでない、いろんな世界がある事をあらためて感じた。 SICPを読みはじめたときの動機を振り返る ・関数型言語について Lis

約半年をかけて計算機プログラムの構造と解釈(SICP)を読み終わりました。 （途中で、練習問題をスキップしたりしましたが・・・） 半年もかけたのでちょっとだけ振り返って見ます。 SICPを読む過程で得たもの まずはSICPを読む過程で得たものからざっと列挙してみよう。 構文解析を理解し自前で実装できるようになった 字句解析を理解し自前で実装できるようになった ストリームを理解した 遅延評価を理解した 手続きが first class objectである言語での考え方を学んだ 型変換の導入の動機とその意味を理解した 手続きの抽象化の導入の動機と過程を学んだ 高階関数を使ったり書けるようになったりした クロージャを理解した Schemeを書けるようになった 再帰処理を自然に書けるようになった フルスクラッチでインタプリタを書けるようになった コンパイラを自前で書くことが出来そうだとの感触を得た

しばらくサボっていたので反省して一気に読み進める。 ちょっと難しいところにさしかかったので、まとめて読んだ方が忘れなくて良い。 レジスタ計算機は、仮想的な話なのだけどコンピュータの奥底を眺めているようで不思議な気持ち。 5.1.2 レジスタ計算機の記述言語 データパスと制御器の話。データパスの図が僕にとって直感的にみづらく苦労した。 5.1.3 サブルーチン いわゆる call の話。共通手続きを共有しようという意図なのはもともと理解できていたが、導入の動機が「ハードウェア的に同じような計算器を組み立てるのは経済的でない」ってのは新鮮な切口だった。 5.1.4 再帰を実装するためのスタックの使用 スタックデータ構造が必要だよねという話。 5.1.5 命令の要約 5.2.1 計算機モデル レジスタ計算機のシミュレータの話。CPUの創り方という本で学んでいたのと、多少のアセンブリの知識があるの

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の４章ではSchemeのインタプリタをSchemeで実装します。 勉強のためにC++で実装してみます。 基本はScheme->C++に置き換えています。（そんなに簡単じゃないけど） 置き換え以外の部分が字句解析・構文解析です。 なぜ構文解析が必要か Schemeインタプリタ(以後インタプリタ)をScheme(以後Gauche)で実装する場合と入力の扱いが違うからです。 インタプリタでは入力を受け付けますが、実際にはGaucheが入力を受け取り、Gaucheが手続き eval にそのまま渡します。 この際、Gaucheが受け取る入力はS式ですが、Gaucheはそれ自体S式をS式として認識しているので特に難しい作業は必要ありません。 一方、C++で実装する場合、入力は"(+ a b)"のように文字列で与えられ

4章では Scheme の上に Schemeインタプリタを作る過程でいろいろなものを学んでいきます。 このように、被実装言語と実装言語が同じなことを metacircular というらしいのですが、読んでいるだけでドキドキしてきます。 実際4章を読み進めていくと、とても面白いのですが、所々で引っかかるところがあります。 どうも読んでいるだけでは解決しないモヤモヤがあって、それは被実装言語と実装言語の境界に関する問題のように思えてきました。 metacircularだと、どこまでが被実装言語の機能で、どこからが実装言語の機能なのか分からなくなってきてしまうのです。 こんな経緯もあり、4章で書かれているSchemeインタプリタを「ほぼそのまま」C++で実装してみようという思いに至りました。 最近SICP日記を更新できなかったのはこのあたりに悩んでいたからです。 いろいろと困難あるでしょうが、試

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))))

テクノロジー 関数型言語の勉強にSICPを読もう - (52) 4章 - 超言語的抽象(213-217ページ) - apply - higepon blog

上のエントリでは、これまで考察してきたクロージャについての簡単なまとめを行ないました。そのエントリで最後に書いたブロックにも着目しながら、これまで考察してきたクロージャについて、コードを挙げて検証してみようと思います。 さて、上のエントリでは、クロージャの基盤となっている三つの仕様を挙げています。 しかし、これらのうちの幾つかが欠ける場合でも、Scheme で言うところのクロージャではないかもしれませんが、有効に利用可能な手続きを活用することは可能であると、私は考えています。 これは、上で挙げた三つの仕様が揃わない言語環境に於いて、クロージャの様な仕組みを活用することが可能か、という視点に置き換えることができます。例えば、Emacs Lisp や Java などでクロージャの様なコードを書けるか否か、ということですね。 ;; Java にもクロージャを導入可能に (?) といった動きもある

これまで考察してきたクロージャの件ですが、まだまだ頭の中では発散しているのですけど、一旦、簡単にまとめておきたいと思います。 ただ書き散らかしているだけでは意味ない (いや、意味はあると思ってるんですけど。自己矛盾だ。) ですからね。 Rui さん、shiro さんのコメントに助けられて、今では、 手続きをファーストクラスオブジェクトとして扱える。 静的スコープを持つ。 無限のエクステントが保証されている。 の三つの基盤が揃うことで、クロージャが実現されていると考えるに至りました。 Scheme 以外ではどうか判りませんが、こと Scheme に於いては、上の仕様に立脚する形でクロージャが実現されていると考えて差し支えないと思っています。 ただ、言語設計の推移としては、shiro さんから頂いたコメントで示唆されている様に、動的スコープに於ける環境問題 (FUNARG problem) が

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 を渡すところが思いつくのに時間のかかった部分だった。 ということで答え

待ちに待っていたデジタル回路のシミュレーション。 オラ、何だかワクワクしてきたぞ！ 問題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

実用っぽいコードを書かないと中々上達しないと思うので無理やり書いてみました。 引数で受け取ったファイルを開いて、ファイル内を置換する。 「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

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)

#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

問題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