リンカのお勉強中デス。Binary Hacksのhack#25 「glibcを使わないでHello World」が面白そうだったので、アセンブリでやってみました。 .data hello: .ascii "Hello, World!!" .text .global _start _start: movl $4, %eax movl $1, %ebx movl $hello, %ecx …

アセンブリで再帰したら激しく便利なんじゃないかと思って、久しぶりにボクノスいじり。アセンブリと再帰の相性は抜群。retの代わりに、jmpを使えば末尾呼び出しの最適化まで出来ちゃう。ステキ。アセンブリ上なら再帰でも、gotoでも、whileだってforだって…

スゲー期待。 Scheme処理系言語Gauche（ゴーシュ）の初の解説書！ 本書はオープンソースのScheme処理系言語Gauche（ゴーシュ）の初の解説書。SchemeはLisp言語の一種で、非常にシンプルな言語仕様を持つ。従来のScheme / Lispに現代的な改良を加え、国際化対…

reverseを再帰で。という難解な設問。僕のScheme力が試される。 いっこめ strlenで。 void reverse_iter(char *s1, char *s2) { if (*s1 != '\0') { *s2 = *s1; reverse_iter(s1 + 1, s2 - 1); } } void reverse(char *s1, char *s2) { int len = strlen(s1)…

たまにはK&Rを。 演習 4-12 itoaを再帰で書け。という問題。再帰に慣れてるはずなのに、この問題はムズィ。 int itoa_iter(int n, char s[], int i) { if (n == 0) { s[i] = '\0'; return i; } else { int tail = itoa_iter(n / 10, s, i + 1); s[tail - i] …

もうひとつのデータ主導実装。メッセージパッシングについて学ぶ。 メッセージパッシング 前回は、環境がメソッドを知っていた。「賢明な手続き」という。主にC++/Javaみたいなコンパイル型言語で使う方法かな。今回のは、オブジェクトがメソッドを知ってる…

楽しげな問題なので、ちょっと改題。 問題 2.74 ボクノス有限責任会社(Boxnos Enterprises, Inc)は世界に類を見ない弱小企業である。社長tanakaは危機感を感じていた。このままでは、OSなんかいつまで経っても作れないぞ。「これはいかん」そこで、社長tanak…

やっと問題に入ります。 問題 2.73 前に作った記号微分プログラムをデータ主導に書き直す問題 a (deriv '(+ 2 x) 'x)ならば、'+と'derivにマッチする、手続きを検索し、見付かった手続きに、引数(2 x)と,'xを作用させる。この微分プログラムでは(+ ...)とい…

まだまだ解説が続きます。演習問題はまだかぁ〜データ主導ってことは、現在の主流。オブジェクト指向ライクな感じに仕立てあげていくみたい。 put,get 解説読もうと思ったら、 put,getは言語に組み込まれていると仮定しよう。 って、組み込まれてないよ・・…

まだまだ、解説が続く。 タグつきデータ 複素数表現を「型タグ」で表現しようというお話し。前回のが、 struct complex-rectangular { int type; double real; double imag; }; struct complex-poler { int type; double magnitude; double angle; }; となっ…

抽象データの多重表現に入ります。しばらく淡々と説明が続く。テーマが「複素数」というのが泣ける。相当苦しい章になりそうだ。 複素数の表現 ずっと前にやった有理数(分数)表現と同じような感じ。 しかし、今回は事情が違う。直行座標形式と、極座標形式と…

ちょっと早いけど今年を振り返ってみる。 Vimとの出会い 今年一番の出来事はこれだろう。Vimと出会わなければ今年が無いといっても過言では無い。今やVimの無い生活はありえない。 Linux転向 Windowsがクラッシュしたので、思い切ってLinuxの世界に飛び込ん…

ビット数計算やら、ステップ数計算やら。 問題 2.70 8つのワードがあるから、2^3で、3ビット必要。固定長符号で考えると歌詞は39ワードあるので、39words*3bit = 117bit必要となる。可変長な符号な場合、88bitに圧縮された。約25%の節約となった。単調な繰り…

今度は木の生成 問題 2.69 何も考えずにやるとこうかな。 (define (successive-merge leaf-set) (define (iter set tree) (if (null? set) tree (iter (cdr set) (make-code-tree (car set) tree)))) (iter (cdr leaf-set) (car leaf-set))) あっさりすぎ?ツ…

符号化に挑戦。 問題 2.68 符号木を元に、(A D A B B C A)を符号化せよ。という問題。ムズそうなので方針を練ります。 方針 符号化でのポイントは、履歴を返すという所。 葉が見付かったら、'()を返します。見付からなかったら#fを返します。枝の検索も同じ…

ハフマン木に入ります。JPEGやらLHAでも使われてるアルゴリズムだそうです。前回の二進木と違ってツリーのデータ型が二つに増えたという所が重要なポイント。 ハフマン符号化木 ハフマンさん頭良すぎ。ハフマン符号 - Wikipediaハフマン符号化木のポイントは…

MzSchemeの構造体を使って有限ステートマシン作りしてみました。らくちん過ぎる。 状態(state) 状態は4つあります。 ゲームステート V 戦闘ステート <--> 宿屋ステート V 死亡ステートデザパタで言うと、Stateパターンと同じような感じです。 HPによって状態…

リストで構造体作るのが面倒なので、MzSchemeの構造体を試します。ドキュメントはここら辺。 PLT MzScheme: Language Manual 構造体の定義 (define-struct book (title jp-title)) ふむふむ。(define-struct 構造体名 (フィールド))。 新規作成 うはナンダコ…

なんとなく気になったので、有限ステートマシンで遊んでみた。 人工知能初体験なのでまずは挨拶から。 挨拶マシーン1号 挨拶するだけです。ハイ。 (define (good-morning) (display "Good morning.\n") hello) (define (hello) (display "Hello AI World!!\n…

今回のリスト修行のテーマはパスカルの三角形に決定〜。SICPの問題では(combination n k)→値だったのであんまり三角形っぽくなかった!!ちょっと不満だったので、リストで求めたい。 方針 パスカルの三角形n列を求めるには、前のn-1列のリストを必要とします…

名前付きletなコードを見たけど、全然意味不明だったので、10から0まで足してみる。 名前付きlet (define (sum n) (let iter ((i n) (s 0)) (if (= i 0) s (iter (- i 1) (+ i s))))) (sum 10) ; 55 どうやら、反復の簡易記法として使えるみたい。宣言部は、…

さて、二進木の最後の問題。「データベースをつくろう」という問題。 問題 2.66 要約すると、idからデータを検索する二進木データベースの設計をせよ。という問題。 まずはデータ構造の変更 1レコードのデータ構造を変更します。なるべく変更点が少ない方が…

どうも二進木のリスト表示がわかりにくいので、Graphviz使うことに。 define (graph tree) (system (format "echo 'digraph G { ~a ~a }' | dot -Tpng | display" (entry tree) ; 一個だけだと表示が出来ないのでとりあえず最初のを挿入しとく (letrec ((mak…

うぅん。わからん。 問題 2.65 僕は一生懸命ツリーをつなぎ替えようとしてしまった。ツリーのつなぎ変えがイマイチうまくいかない・・・。回答を見ると、tree->listを使ってやる方法が書かれてた。イマイチ納得がいかない。ちょっと後回し。

次は順序づけられたリストを釣合った二進木へと変換する問題。 問題 2.64 とりあえず、let*に直す。 (define (partial-tree elements n) (if (= n 0) (cons '() elements) (let* ((left-size (quotient (- n 1) 2)) (left-result (partial-tree elements lef…

ポール・グレアム著ANSI Common Lispを読んでいきたいと思います(優先度低め)。本の略名はACLと勝手に命名しました。2章からバリバリ変態モード全開なので軟弱者の僕はScheme使っちゃうよ〜。 練習問題 2.1 評価る値を述べよ。 (+ (- 5 1) (+ 3 5)) ; 12 (li…

二進木に入ります。二進木初体験なので、ちゃんと読みたい。 二進木 Schemeで二進木を表すと、 (データ 左 右) リストは構造体にも化ける。便利だ。見にくければ、(左 データ 右)と書いても動くと思う。 リストを追加するのが面倒なので、entry-appendr作っ…

まだまだ集合が続きます。今回は順序づけられたリスト。つまり、 (1 3 5 7) ; OK (8 6 4 2) ; NG 順番は守ろう〜。というリスト。 問題 2.61 あ、前回、スペルミスしてたっぽい。ajoinだと思ったら、adjoinだった。英語の弱さも直さねば。 (define (adjoin-s…

いつも新宿の紀伊國屋なんだけど、はじめてジュンク堂へ行ってみた。いやぁ、すげぇ品揃え。もう僕ジュンク堂派っす。 で、買った本。ANSI Common Lisp (スタンダードテキスト)作者: ポールグレアム,Paul Graham,久野雅樹,須賀哲夫出版社/メーカー: ピアソン…

前回は、12の素因数分解をするときに、2〜12までのリストを作成し、それから素因数分解をしました。しかし、12が必要とする素数は2と3だけ。12までふるいをかけるのは無駄です。しかも、ふるいが重い!!そんなわけで、素数が必要となってから、素数を生成した…