(2015/09/15追記) SICPテキストのストリームでは問題3.77のテスト実行で返ってこないため、ここではracket/stream版を使っています。ソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.5.4.scm https://github.com/uents/sicp/blob/master/ch3/racket-streams.scm 前節で出てきた積分器integralを使ってフィードバックループを持つ信号処理システムを考える。大学では制御工学を専攻していたのでこういうの大好きです。 このフィードバックシステムは以下のように実装される。 (define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define d

前半はある一定の値に収束していく無限ストリーム(数列)の収束を加速させる手法や、対のストリームについて。数学的なトピックが中心だと思うので、バッサリ飛ばします。早く4章に行きたいのも大きいけど… 後半の「信号としてのストリーム」の節はストリームの工学的応用で気になるので解いて行きたいと思います。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.5.3.scm (2015/09/06追記) その後「対の無限ストリーム」が§4.4のquery systemの内部実装で登場したので戻ってきて解きました。結果的にストリームの理解が深まったのでよかったかな 反復をストリームとして形式化する まずはsqrt-streamを写経して動かす。わりとすぐに収束しているのがわかる。 racket@> (map

問題 3.59 べき級数、聞き覚えはあるから習ったことはあるんだろうけど、さっぱり思い出せない。こんな時はWikipedia。先生いつもありがとう。 冪級数 - Wikipedia (a) べき級数の項のストリームを引数に取り、それを積分した結果の項のストリームを返すintegrate-seriesを実装する。 引数のストリームを \( \{s_{n}\} \) とすると、 \( i_{0} = s_{0} \) \( i_{1} = \frac{1}{2} s_{1} \) \( i_{2} = \frac{1}{3} s_{2} \) \( i_{3} = \frac{1}{4} s_{3} \) ... \( i_{k} = \frac{1}{k} s_{k} \) のようなストリームを返す手続きを実装すればよいので、 (define (integrate-series s) (de

“To inifity and beyond” トイ・ストーリーでのBuzz Lightyearの決め台詞です。 無限ストリーム(infinite streams)を極めると、さらにその先の世界が見えるかもしれない :) トイ・ストーリー MovieNEX [ブルーレイ+DVD+デジタルコピー(クラウド対応)+MovieNEXワールド] [Blu-ray] 出版社/メーカー: ウォルト・ディズニー・ジャパン株式会社発売日: 2013/11/20メディア: Blu-rayこの商品を含むブログを見る 無限ストリームとは 無限に1が続くonesというストリームは以下のように定義できる。 (define ones (cons-stream 1 ones)) 至ってシンプル。今の僕ではこんなの逆立ちしても思いつかない… 実際に操作してみる。stream->listは永遠に評価し続けるので返ってこない

いよいよストリームへ。 生まれて初めてその概念に触れたけど驚きの連続。特にdelayとforceによる実装が何とも直截的で素敵すぎる。やはりSICPはもっと早くに読むべきだった… ストリームを使うには (2015/08/20追記) 実行環境がRacketの場合、ストリームを使うには2つの方法があります。 racket/streamを使う 自前でストリームを実装する racket/streamを使う 基本はracket/streamをrequireするだけ。わりと楽 http://docs.racket-lang.org/reference/streams.html racket/streamにないものはSICPから転用 #lang racket (require (prefix-in strm: racket/stream)) (define-syntax cons-stream (syn

前節までに局所状態を持つオブジェクトを取り入れたけれど、局所状態とは即ち「時」を意識することになる。ここでは異なるタイミングで複数のプロセスから共有オブジェクトの状態を参照したり変更したりする場合に、どういった課題があるかといったことを検証して行く。 並列プログラムの正しい振る舞い 問題 3.38 (a) 残高(balance)の遷移は次の6パターン。 パターン1 (★a) 100 -> (Peter) -> 110 -> (Paul) -> 90 -> (Mary) -> 45 パターン2 100 -> (Peter) -> 110 -> (Mary) -> 55 -> (Paul) -> 35 パターン3 (★a) 100 -> (Paul) -> 80 -> (Peter) -> 90 -> (Mary) -> 45 パターン4 100 -> (Paul) -> 80 -> (Mar

「§3.3.5 制約の拡散」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.5.scm 原本のタイトルは "Propagation of Constraints" なので「拡散」というよりかは「伝播」の方が適切かもしれない。 前節では論理回路のシミュレータを考えたが、ここではさらに抽象的な概念として「制約」とその制約同士をつなぐ「コネクタ」について考える。ちょうどいまSICPと並行して読んでいるダニエル・ヒリスの「思考する機械 - コンピュータ」の一節を検証するかのようだ。 驚異的にサイズを小さくすることを除けば、コンピュータチップの作成にシリコン・テクノロジーを使わなければならない特別な理由など存在しない。コンピュータチップは、大量の「スイッチ」とコネクタ」を提供できるテクノ

前回の作業から Yosemiteにアップグレードまで済ませたので、さらにHomebrewをインストールし直した際の作業メモ。 環境 Mac OS X Yosemite 10.10.1 Xcode Command Line Toolsはすでにインストール済み インストールしていなくて、Homebrewをインストールする際にセットでインストールされる Homebrewのインストール Homebrewのウェブサイトのトップページを参考に、ターミナルからコマンドを実行する。 http://brew.sh/ % ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" インストールが完了し、 ==> Installation successful! ==> Next steps

「§3.3.4 ディジタル回路のシミュレータ」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.4.scm 回路の実装 論理回路の実装 テキストのこの章のコードを写経しないとシミュレーションを走らせることができないので、 先に全て写経してしまう。 まずは入出力を反転させるinverterから。 after-delayは、手続きを指定した時間分だけ遅延させて実行させる set-signal!は、回線の信号を新しい値に変更する acc-action!は、回線の信号が値を変えた時、手続きを実行させる よってinputの信号が変わるとinvert-inputが実行され、*interter-delay*時間後にoutputへ新しい値が設定される。 (define (inverter inp

「§3.3.3 表の表現」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.3.scm 問題 3.24 解答は省略。 make-table にテスト関数を引数で渡せるようにし、 assoc-tree 内の equal? の代わりに そのテスト関数を使えばよいだけ。 問題 3.25 テキストの例がわかりづらいのと、問題3.26でリスト構造を 単方向リストから二分木へ入替を睨んで、以下のようにモジュール分割する。 key、valueの対で持つrecord recordをリスト構造で管理するtreeとその操作 テーブル本体 (treeの操作で実装) まずはrecord。key、valueの対である。 (define (make-record k v) (cons k v)) (defi

「§3.3.2 キューの表現」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.2.scm ところで、最近の１カ月半は通勤時間もコードを書くほど忙しかったので、 Schemeを忘れてないか心配だったけど、意外とそんなことはなかった。 2章でみっちりとやり込んだおかげかもしれない。 キューの表現 キューをFIFOで実現するという話。insertをO(n)で実現するために、 front, rearへのポインタも忘れてはいけない。 まずはテキストのコードを写経。 (define (make-queue) (cons '() '())) (define (front-ptr queue) (car queue)) (define (rear-ptr queue) (cdr queue))

「§3.3 可変データのモデル化」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.1.scm 可変リスト構造 構成子、選択子とは別にオブジェクトを修正する変更子(mutator)を導入する。 例えばpairの場合、 手続き 呼び方 cons 構成子 (constructor) car, cdr 選択子 (selector) set-car!, set-cdr! 変更子 (mutator) ミュータブルなリストの導入 (2015/08/20追記) 実行環境がRacketの場合、Pairs and Listsはデフォルトではimmutableなので、以下のいずれかの方法でmutableなリストを導入できます。(他にもあったら教えてください) r5rsモジュールをロードする Muta

会社でボードゲームしてる人たちがいる。 僕はボードゲーム苦手で、たまにやっても全然勝てない。 将棋とかイメージすると、こっちがこういう手を出すと相手はどうするか、そしてその次は、というのを予測すればよいのだけど、なんかそれがめんどうで、なんでこんなこと考えないといけないのか、とか考えだしてくたびれてしまう。 ずっと論理的に考えるのが苦手で、すぐめんどうになってやめてしまう。 普段、仕事や遊びでソフトウェア作ってるのだけど、よく考えると、ソフトウェアの動作が論理的なだけで、ソフトウェア作るのは勘でできる。 ソフトウェアが正しく動くかどうかは論理的に決められて、電卓アプリなら計算結果が狂ってたら間違っているけど、その電卓アプリがどのように作られたか、には正しさはない。逆立ちして作っても、猿にタイプライターを渡して作っても、計算結果合ってれば良い。 過去のデータとか経験によると猿に書かせるのは効

はてブで興味深い記事を見つけたのでその感想。ブコメも含めておもしろい。 10年プログラマをやってきたけど、最近の僕の中ではプログラミング技術とは、 モデリング力とその処理系の実装スキル、だと思っている。 制御対象を分析し、抽象化・簡略化し、それを制御する処理システムを作る。まあこんな感じ。 現実世界は複雑なので、要件を分析して詳細仕様を詰めたり、 仕様を簡略化することももちろんプログラマとして必要な要素だと思う。 単にコードを書くだけのお仕事ではないはず。 古来から、プログラミングは数学なのか、芸術なのか、工学なのか、みたいな話題があるけど、最新の僕の感想では、勘だと思う。 勘というのが直観力やセンスのことなら一理あると思う。 よい実装にしろデバッグにしろ、良いプログラマは始めのアタリの付け所が上手い。 ただ、プログラミングに対する直観力は後天的なもので、 良いコードや良い本に出会って勉強