キューを作ります。Θ(1)にするためにデータをためるリスト本体と、その前端(front-ptr)と後端(rear-ptr)を保持するpairがデータ構造になります。 が、しかしここでの実装は 空っぽの場合、というのを front-ptr が nilを指してる場合、としています。空の状…

再帰を無名関数で行う法。 要するに引数の一つに自分への参照にしちゃう訳ですね。最小二乗法の検算にlisp使ってて、リストの長さを出す関数をふとワンライナー的に書きたくなって理解してしまった・・・（間抜けな動機。length使えば良いじゃんねえ・・・) …

mutation版のconsをprocedureとして再定義。 assignment というかset! があれば理論的にはmutable-data-objectが作れることを見せてます（当たり前な気が・・・いまいち理解できてないみたい）。

「同じ」ということの定義。schemeのeq?は単純明快で、ポインタが同じアドレス（実体）を指している物は同じ、、、というコンピュータ的には非常に素直な実装になっています（ポインタ恐怖症の人からしたらいやな表現なんだろうか？）。 (define x (list 'a …

昨日は鎌倉のM電機に出張。遠い。。。 新幹線の中って本読むのに微妙な環境です。

set-car!, set-cdr!の登場。cons cellのcar/cdrを直接書き換えるmutatorですね。*1 実は以前 scale-listあたりで、iterative と recursiveでできあがりのリストの順序のやりやすさをで悩んで、以下のようなことをしていた…ら、実はここのexerciseの内容先取…

します... そのうち復習で抜けた所も書こうかと思ってますが、ダメかも.... 昨日は、1.1.5 の substitution model から 3.2 のenvironment modelへの移行で、結構謎だった local variable, local state, inner-function などの仕組みが全て見えて感動でした。

d:id:tkuro:20061129 しつこく食い下がるような問題でもないんだけど、、、 x & (x-1) が 一番右の1のビットをカットすることを利用して、 int enum_bit(unsigned long x) { int counter = 0; while( x ) { counter++; x &= x-1; } return counter; } うーむ…

トリッキーなコードが早いとは限らないもので… 32bit の中の'1'bitの数を数え上げる、というコード。 おそらく普通なら以下のようにcounterを使うんじゃないかと思います。 counter版 enum_bits int enum_bits(unsigned long x) { int i; int counter = 0; f…

更新せずに２ヶ月近くたってしまった。 いかんいかん。その間にSICPはp.221まで進んだのですが・・・ 復習がてら書くようにしようかな。

Θ記法ですな。大抵みんな知ってるだろうし、大学で嫌という程やったので割愛。

Golden Ratio 実は良く知らなかったのでちょっと勉強した。 元の定義は となるような比率。*1 これから , 両辺 a^2 で割って とおくと --- なるほどねえ。 ここでを考えると、これがフィボナッチ数と絡んでくる。例えば , 同様に , と、係数にフィボナッチ数…

前回のTree型の再帰パターン、というか再帰で書かないとわけわからん！という例を解く。 ここでの例題は決められた通貨単位で指定された金額を払うための方法が何通りあるか、というもの。 確かに再帰で考えていくと結構簡単。今注目してる通貨(例えば500円…

さらにちょっとだけ進む。亀だ。本当に亀だ。

continuation なんて名前で呼ぶからわからなかったよー(不勉強） callcc 単なるスタックフレームの復帰ですね。Call/cc か。実はcallocと勘違いしてrubyの中を追っかけ回してて気がついたのだったり… 二重にアホだオレ orz

なんせ楽なのでついつい例題プログラムを作るとき、Emacsのlisp interactionでやってしまう。defunとdefine , cond のelse節 , 高階関数が使えない（のか？）など結構違いがあるので、使えるのは限られてるのですが。変なクセが付きそう。

線形の次はツリー型再帰だ。例題は良くあるフィボナッチ数の問題。素直に再帰で書くと各再帰深さにて２つのパラメータが未定（要再帰呼び出し）になったツリー状の演算グラフができる。これ、すごい数の無駄演算を行ってしまうが、簡単に書けて理解しやすい…

ちょっとだけ進む。

なんでも書き込むメモファイル。面倒臭いので .Mac の iDiskサービスに置いてます。んでどこでもアクセスできるようにしよう、と。家にいるときは良いんです。Mac か Linuxでいじるので。 会社にいると。。。窓しかないんです。イケてません。泣けます。EWS…

ここまではlanguage features、というか道具の仕組についての解説中心だったが、ここからは道具の使い方、パターンの説明にいよいよ入っていくようです。別段Lispを教えたい本ではなく、複雑な問題を切り分ける術、というのを教えたい本なんだそうなので、こ…

何を勘違いしたのか最近読み始めてしまったSICP。周りにも読んでる人がやたら多い。 現在 1.2 Procedure and the Process They generate. p.31- ちょこちょこ書いていこう