« November 2007 | Main | January 2008 »

2007.12.27

NDS買った

FF3のクオリティ高すぎ。
イベントシーンでも、ちゃんとジョブの格好している。

meganeinu村 レベルアップ中
http://meganeinu.myminicity.com/tra

| | Comments (7) | TrackBack (0)

2007.12.26

クリスマスのプログラミングの成果

Nagato_idle_2

ここまできた。

手順
nagato.gifを各自用意して、C:\Python25\Lib\idlelibに置く。
EditorWindow.py 195行目周辺

    text_frame.pack(side=LEFT, fill=BOTH, expand=1)

    #nagato
    self.nagato = PhotoImage(file='nagato.gif')
    text.image_create('1.0', image=self.nagato)
    text.pack(side=TOP, fill=BOTH, expand=1)

    text.focus_set()

太字部分を追加

| | Comments (3) | TrackBack (1)

2007.12.25

今日の日記

・風邪
風邪を引いてました。ずいぶんと楽になりましたが、一時は39.6度の高熱でした。インフルエンザかどうかを確認した後、何故か別室で有無を言わさず点滴を受けました。今年の風邪は仕事のやる気を下げるので、仕事で「やる気でないな」と思ったら風邪かどうか確認してください。

4K痩せたぜ。イェーイ。

・The Practice of Programming
カーニハン先生のありがたいお言葉を抜粋

Don't comment bad code, rewrite it.
Good code needs fewer comments than bad code.
Writing good code has much in common with writing good English.

最近は#defineの代わりにこんな風に書くの?
enum {
  MINROW = 1,
  MINCOL = 1,
  MAXROW = 24,
  NLET = 26,
  HEIGHT = MAXROW - 4,
  WIDTH = (MAXCOL-1)/NLET
};
intにしか使えないのと、ひとつのenumに同じ値が存在するのが嫌な感じがする。

chapter2 もまったり読んでいます。

・改行
コメントよりも丁寧に入っている改行の方が理解を高めるというのは聞いたことがあります。
僕も賛成です。

・雑記帖のきむら(K)さんから
メタ

> この方面で日本語で読める適当な(できれば入門レベルの)本なんてでてないですよねえ(^^;
英語でも良いので、C++に限らずメタプログラミングの入門レベルの本はないでしょうか。

こんなところにさりげなく!
>・Higher-Order Perl なつたんさんのお気に入り


・長門(ながと)のmini py
せっかく東大生に教わったのに絶賛放置中でしたが、ようやく勉強始めました。

・Computer Architecture A Quantitative Approach
Effective STLを読みたい気持ちをぐっと我慢して、ハードの勉強をする。読者を楽しませようって本じゃないのですが、Chap1がとてつもなくつまらない。

| | Comments (0) | TrackBack (0)

2007.12.19

myminicity

そこら中に農村が乱立していますが、普通に成長していく様子を見たいので村を絞り込み。

産業を上げるために、少しURL変更

http://heppoko.myminicity.com/ind/ 夜ばい村
http://meganeinu.myminicity.com/meganeinu村

| | Comments (0) | TrackBack (0)

2007.12.15

[HOP]Parsingの章終了

ようやくParsingの章を終了。手を動かす気力が無いので読んだだけです。

8.8 Backtracking Parsers
Perlで自力で継続をしながら、バックトラックをする話。

ソースはこんな感じで
sub lookfor {
 my $wanted = shift;
 my $value = shift || sub { $_[0] };
 my $u = shift;
 $wanted = [$wanted] unless ref $wanted;

 my $parser = parser {
  my ($input, $continuation) = @_;
  return unless defined $input;

  my $next = head($input);
  for my $i (0 .. $#$wanted) {
   next unless defined $wanted->[$i];
   return unless $wanted->[$i] eq $next->[$i];
  }
  my $wanted_value = $value->($next, $u);

  # Try continuation
  if (my ($v) = $continuation->(tail($input))) {
   return $wanted_value;
  } else {
   return;
  }
 };

 $N{$parser} = "[@$wanted]";
 return $parser;
}

SICPの継続の部分に構造は近い。引数に処理すべきリストと継続を渡し、成功/失敗によって自力で継続を呼び出すクロージャを返している。

同様にstreamを使ったparsingも簡単に説明。パースの選択肢がある時に、どちらかを選んで再帰していくのではなく、すべての選択肢を同時に計算していく。ここでStreamを使う。実用性はともかく発想は面白い。

8.9 Overloading
最後は、演算子のオーバーロードを使用してDSLっぽくする話。

この本で、ここまで書いてきたパーサーのソースがこれ。

$factor   = alternate(lookfor('INT'),
       T(
             concatenate(lookfor(['OP', '(']),
                  $Expression,
                  lookfor(['OP', ')'])),
        sub {$_[1]})
       );

ちなみにlookforは、引数をパースするだけのクロージャを返し、concatenateは引数のクロージャを連結したクロージャを返す。Tは、クロージャと手続きを引数にして、パースに成功したときにある手続きを読んでから値を返すクロージャを返す。最後にalternateは、複数のクロージャを引数に選択的に実行していくクロージャを返します。もうわけわかんない。

BNFからはほど遠くなっているので、Perlのオーバーロードを使用することで、こんな風に書けます。

$factor = lookfor('INT')
    | lookfor(['OP', '(']) - $Expression, lookfor(['OP', ')']
        >> sub {$_[1]})
    ;

これで確かに読みやすくなる。

こういうのに興味がある人はHigher-Order Perlお勧めですよ。

残りあと一章!

| | Comments (0) | TrackBack (0)

2007.12.14

今日の日記

OpenSparc T2
雑記帖のきむらさんに先を越された。
ええ、AirHで一晩かけてダウンロードしていますよ。
ちょこちょこバージョンアップしていたり、なんかよく分からなくなったりして3回くらいダウンロードしています。

>これまでのダウンロード数は6500回を数える。
僕ですら3回ダウンロードしているから、6500回は少ない気がする。

2006年3月に配布されて仕事が一段落したのが6月、ハッカーと画家を呼んでLispに走る→Pythonへ という流れです。(なにが?)

・親ばか
昨日は早く帰ったので珍しく家族の前でHigher-Order Perlを読む。3才の娘がやってきて「おとうさん、紫の本は?」と聞いてくる。もしやと思いSICPを渡すと、満面の笑みでうんうんとうなずく。前に真剣に読んでいたのを覚えていたらしい。半年前は一人で持てなかったのに、今はちゃんと持てるんだ。

SICPを必死で僕の横まで運んだ後「こっちの方がおもしろいでしょ」と言ったとき、萌え死ぬかと思った。

クリスマスプレゼントはこれにしようと思っていたが、もうちょっと考えよう。

・HOP
ちょっと電卓が動いたら一気に飽きだした。
SICPと同じで、少し動く→次はこう拡張してみよう→少し動く→こうしたらどうよ? みたいな流れなので、心に余裕がないと「最初からそっちで進めてくれ」と言いたくなってくる。もう一頑張り。

| | Comments (0) | TrackBack (0)

2007.12.12

[HOP]Pythonで相互に参照する

Paserを作っていて苦労したのでメモ。もっと良い方法があるはず。

いわいる数式のパーサで、数式の定義がこんな感じで与えられたとき、

expression = ["+"|"-"] term {("+"|"-") term} .
term = factor {("*"|"/") factor} .
factor = ident | number | "(" expression ")" .

対応する文法をPythonのclassを使って定義したい。
Higher-Order Perlから、そのままPythonに書き下ろすとこんな感じになる。expressionなどが、pasrerクラスのインスタンス。

expression = parse.alternate([parse.concatenate([term,
                        parse.lookfor(('OP', '+')),
                        expression])
               term])
term = parse.alternate([parse.concatenate([factor,
                      parse.lookfor(('OP', '*')),
                      term]),
            factor])
factor = parse.alternate([parse.lookfor(('INT',)),
             parse.concatenate([parse.lookfor(('OP', '(')),
                       expression_delegate,
                       parse.lookfor(('OP', ')'))])
             ])

上の定義とちょっと違うとかはさておき、問題は2つ。
・expressionの定義の中で自分自身が出てくる。
・expression,term,factorがお互いに参照しあっている。
普通の言語であれば、とりあえず何か入れておいて後で上書きするというのが使えそうなのだが、Pythonの場合は代入ではなく束縛なので上手く行かない。


YUKI.N> dummy = 0
YUKI.N> a = [1, dummy]
YUKI.N> b = [2, a]
YUKI.N> b
[2, [1, 0]]
YUKI.N> dummy = b
こうしたら上手く相互参照のリストができそうだけど、a は[1, 0]に束縛されているから、後からdummyだけ変えてもaは変わらない。
YUKI.N> a
[1, 0]

a[1] = bとすれば当然期待する動きになるんだけど、上に書いてあるような複雑な相互参照を手で設定していくのはかなり無謀。

そこで、手続きを渡すだけのclassを作って、後から参照を入れ替えられるようにした。
class delegate(parser):
  def set_parser(self, parser):
    self.parser = parser

  def parse(self, tokens):
    return self.parser.parse(tokens)

こんな感じで宣言して、
expression_delegate = parse.delegate()
term_delegate = parse.delegate()
factor_delegate = parse.delegate()

こんな風にexpressionを定義
expression_clause1 = parse.concatenate([term_delegate,
                    parse.lookfor(('OP', '+')),
                    expression_delegate])
expression = parse.alternate([expression_clause1,
               term_delegate])

最後に、仮で宣言した部分に実際のオブジェクトを登録
expression_delegate.set_parser(expression)
term_delegate.set_parser(term)
factor_delegate.set_parser(factor)

expression_delegate.parse(token)を呼ぶと、set_parserの引数で渡されたオブジェクトのparse()が呼ばれて丸く収まります。
それっぽく、上手く行ったソースはここ

| | Comments (0) | TrackBack (0)

今日の日記

・直線
ときどきの雑記帖 リターンズさんから

> そうそう。グラフィック画面に斜めの直線をきれいに描画するって意外に難しいんですよね。 実際にやらせてみると、たいていの人はがたがたな線になってしまったり、 ところどころドットが跳んだり。 まあこれもロストテクノロジーなんですかねえ(de-culture (笑))

あのアルゴリズムの出典はコンピュータグラフィックス 理論と実践です。初めて役に立ったのがデジタルフィルター関連のお仕事の時で、なんでも勉強しておくものだと思いました。

非力なCPUで使われていたアルゴリズムというのは、組み込みでもFPGAでも重宝します。ガウォークさながら、ハードソフトにとらわれることなく柔軟にいきたいですね。(やった、こっち方面でからんだ!)

神様なんて信じない僕らのためにのコメント欄
参加したいな~

スピーカ1000人プロジェクト
なんか、僕も引きこもっていないで外に出てみようかと思う。本当に人見知りが激しいので、黙り傾向が高い。

・モバ校勉強会開始
Implementation Patternsが届いたので、正式にモバ校勉強会が開催されました。
ペースはこれで。
●にょ<年内に前書きとChap1必須、できたらChap2まで

・なまこま
よく考えると生駒読書会開催くらいならロケーション的には、頑張れば参加できるな。あとは、時間だな。

・twitter
twitterは、いろんな人の出会いが楽しいです。

変態Prologer:http://lowcode.blogspot.com/
タバサ友達:yuyarinの日記
同人ゲームの人:へっぽこさんメモ
萌え絵を書くデザイナー:meganeinu

いろんな意味で世界が広がりました。

| | Comments (2) | TrackBack (0)

2007.12.11

[HOP] ちょっと停滞ぎみ

簡単なパーサーを組み合わせて、複雑なパーサーを作るところではまる。
パーツとしてのパーサーは、HOPに合わせてクロージャを使って生成していますが、再帰的なパースが上手くクロージャにならない。

expressin -> INT + expression

という再帰的なルールを、こう書きたい

$expression = concatenate(lookfor('INT'), lookfor(['OP', '+']), $expression));

これは、perlでもエラーになる。HOPでは、my $Expression = parser { $expression->(@_) };と書いて上手くリンクさせているのだが、Pythonでは、僕の実力的にどうにもこうにもならない。クロージャの中には、クロージャのリストがあって、そこを書き換えれば良さそうなんだけど、それが出来たらすでにクロージャじゃない。
しょうがないのでclassで書き直してみた。__setitem__で[]のアクセスができて感激。
それっぽくパースができた。

| | Comments (0) | TrackBack (0)

2007.12.10

Rapid System Prototyping with FPGAs

Rapid System Prototyping with FPGAs 読みました。
悪い本ではないのですが、買ってまで読むのを勧めるかというと微妙な所です。

内容はFPGAの基礎から、開発プロセス、FPGAの選択基準、ボードレベルの注意点、シミュレーション、最適化、テスト、IP等、浅く広く書かれています。最後は、用語集や設計時のチェックリストまでついています。

目次はここから。
http://www.elsevier.com/wps/find/bookdescription.cws_home/706092/description#description

こういう風にまとまっているのは素晴らしいのですが、英文というのがネックになります。この英文を読んでいくなら、素直にデータシートなり、ハンドブックを読んでいった方が良いですね。日本語でこの内容ならば、データシートを読みながら、分からないところをこの本で概要をつかむという読み方もできると思います。

ちなみに、AlteraのWebからもFPGA設計のチェックリストはダウンロードできます。

AN469: Stratix III Design Guidelines
http://www.altera.com/literature/an/an469.pdf

図表が多く、内容が英文を読まなくてもなんとなくわかるので、FPGAに関する英文集としては使えると思います。

| | Comments (0) | TrackBack (0)

2007.12.05

好きなアルゴリズム

プアーなハードで作る貧乏くさいアルゴリズムが好き

RS-232C 調歩同期のパリティ
初期値の設定と1bitの保持xorで作れる超簡単回路。この回路で、7bitだろうが、8bitだろうが、20bitだろうがどの長さにも対応できるのが凄すぎる。

CRCチェック
これもFF並べて特定のbitのxorを取るだけ。エラー検出率と使用リソースのパフォーマンスが高すぎる。これもパケット長に依存しない。

線形補完のアルゴリズム
y = 3/5 x のような直線を書くとき、順に3を足していって5を超えたところでyを1増やすと良い感じで直線が書ける。
足すのに使う変数をアキュムレータのaとして、5を超えるとオーバーフローして、超えた分だけの値を保持する。

x y a
0 0 0 aに3を足す
1 0 3 次にaに3を足すと6になってオーバーフローするので、yを1増やし、aは6-5で1になる。
2 1 1 aに3を足す
3 1 4 次にaに3を足すと7になってオーバーフローするので、yを1増やし、aは7-5で2になる
4 2 2 次にaに3を足すと5になってオーバーフローするので、yを1増やし、aは5-5で0になる
5 3 0 以下繰り返し
6 3 3
7 4 1
割り算しなくても、加算器+レジスタで直線が引ける不思議。

TIFFフォーマット
FAXで使われるモノクロ、英文字を前提としたアルゴリズム。符号化/復号化にはラインメモリとラインプリンタだけでOK。一行前と同じラインなら数ビットで表現する優れもの。
エラーが発生しても改ページで立ち直れ!

イーサのCSMA/CD
とりあえず送信始めてみて駄目だったらお互いに適当に待ってもう一回送るだけ。この発想はなかなかできない。

ドルアーガのマップ生成
1バイトから、各フロアのマップ生成。1フロアが2画面なのはマッピー基板を使い回したから。

アルゴリズムじゃないけど、貧乏くさくて好きな物
ワイヤードORとか、モノクロのインペーダゲームにセロファンを張って色を付けるとか。

関係ないけど、調歩同期って死語じゃね?

| | Comments (0) | TrackBack (0)

若いときに

若いころに云々から

書こう書こうと思っていたら、この写真のリア充っぷりを見て、一気に書く気が無くなって放置していた。

このまま10年前に戻れるなら、もう少しゲームの時間を減らして勉強に回したい。
10年前の自分へのアドバイス→ SICP読め、VHDLよりもVerilog、C++とPython今のうちに勉強しておけ
この日本語力もなんとかしたいな。とりあえずワインバーグの本買ってきた。
あとは、社会的常識っていうか、服装とか、身だしなみとか、そういうのも気にするようになれば良かった。

子供が生まれてから、みるみる時間を取られるようになってきた。昨日も夜中2時間くらい娘をあやし続けた。昼間は嫁が頑張るから、深夜だけでも頑張らないと。

大学に入学後に戻れるなら、おそらく同じ会社入って、同じ人と結婚して、同じように転職して、同じように娘に来て欲しいと思っているので、今までの人生は満足度高め。人生やり直して、娘に会えなくなるのは辛い。
大学が選べるなら、東大にいって凄い人たちと勉強するか、京大行ってKMC入りたいな。

2007年はビジネスマナーが駄目だったので、2008年は日本語とマナー向上を目指す。
今年の成長:掃除は人のためにする!

| | Comments (0) | TrackBack (1)

PEG勉強会

PEG勉強会
ustreamとlingerで見ていました。

・greedyに取っていくから、右側の再帰で無限ループ
→ greedyというより無限に先読みするってことと理解した。
・shinhさんの自己紹介、上手く見れなかった。
・kinabaさんのプレゼン面白い
・CFG → Context-free Grammar
・勉強会ってすごい。どんどん差が広がるわけだ。
・この人達は配列の大きさぐらいの感覚で、計算量の話をする。
・@hayamizuは凄い人の中でもどうどうとしていた。
・にしおさんは、普通によい人、見た目も普通、ただしコードはやばいらしい。
・バイナリパーサがあるらしい
→バイナリパーサは、TIFFの圧縮伸張ルーチンを書くときにあったら重宝した。
いまどきFAXのファーム書く人なんて少数派
Erlangとの共通点は、通信中にビットが化ける可能性があるからかな?
化けたときの復帰コードの解析とかは、TIFF(FAX)で使っているアルゴリズムと本質的な共通点がありそう。

参加者の皆さん、中継してくださったにしおさん、本当にありがとうございました。
とて良い刺激を受けました。

モニターの前で緊張しまくっていた時、気の利いた発言で緊張を場を和ませてくれた@ujihisaにも感謝。
えーえーえーえーえー

| | Comments (0) | TrackBack (0)

« November 2007 | Main | January 2008 »