« March 2008 | Main | May 2008 »

2008.04.30

Virtual Machineの本

もっと早く紹介しようと思ったのに、忙しすぎた。
例によってトラックバックは上手くいかないので、ひげぽんさんが拾ってくれることを期待。

Virtual Machinesお勧め。

全体としてはスタックベースのVMについて、浅く広く書かれています。所々にLispの文字が見えますが、Lisp用のアーキテクチャについてはあまり載っていません。

目次から
chap1 Introduction:ここでLispとかSECDマシーンが少し出てきます。
chap2 VMs for Prtability BCPL:BCPLという言語を使ってVMにどのような命令があるのかの説明。
chap3 The Java Virtual Machine:Java VMの説明 25ページほど
chap4 DIY VMs:ALEXという俺様VMの説明。仕様と問題提起
chap5 More Stack-Based VMs:オブジェクト指向言語、並列言語、など突っ込んだ話
chap6 Case Study:An Event-Driven Language:非ノイマン型のVMについて。プロセッサの制御をオブジェクトのキューで行うとか、マルチスタックとか。ルールベースで、各ルールにコードと命令のポインターを持つとか。さっぱり分からないけど、SmallTalkの文字列発見。
chap7 The Register-Transfer Model:レジスタベースのVMについて。Parrot キタ━━━━━━(゚∀゚)━━━━━━!!!!Parrotの構造についても5ページほど。あとは、俺様RTM VMの説明。
chap8 Implementation Techiques:スタック型と、レジスタマシーンの両方について書かれています。あまり濃い事は書いてません。
chap9 Open Issue:ブレインストーミング的な話題が21個。セキュリティ、分散VM、コードモーフィング、データベースとの統合等々。

具体的な高速化の為のテクニックは書いていないのですが、VMを設計する上で面白そうなトピックが上手くまとまっていると思います。英語も分かりやすいですし、面白そうな所だけ読むこともできます。本当はこの辺りでお勧めする予定だったのですが、気がついたら4月の終わりになってしまいました。

ちなみに同じような題名でも、Virtual Machines: Versatile Platforms for Systems and Processes はひげぽんさんが求めている情報とは違います。どちらかというと、エミュレータを作るためのトピックが多め。実機とVMのメモリマップをどうするかだとか、キャッシュやMMUをどうするかとか。

http://en.wikipedia.org/wiki/Parrot_(virtual_machine)が、アンサイクロペディアでもそのまま使えそうな記述で頭を抱える。 "one bytecode to rule them all,とか、サポート言語にアドベンチャーゲームのzorkが入っていたり。

| | Comments (2) | TrackBack (0)

2008.04.29

SICP勉強会

お前、行ってないだろ!という突っ込みはさておき、すかいらーくだけは参加したよ。

当日は朝から、Yuyarinといろいろと話す。いくつか素敵なプレゼントももらいました。ありがとう。僕ばっかりしゃべっていたので、次はYuyarinの話をじっくり聞こうと思う。

お昼からすかいらーくに入り、yaottiと合流。緊張して上手くしゃべれない。ていうか、緊張しまくって食欲がでないので、一人アイスコーヒー。yaottiに仕事の内容が伝わらなくて絶望する。今度ゆっくりとお話をしたい。

そうこうしている間にsnow-bellと合流。一気に騒がしくなる。いっぱい相手をしてもらって気が楽に。初めてのオフで、ひとりぼっちになったらどうしようって人はsnow-bell経由で参加すれば良いと思うよ。

優秀な大学生2人を前にしながら、娘のおむつの話でもりあがる。どうもすいません><。

naoya_tとはあえず。また次の機会に。

緊張しまくりつつも、オフに参加するという目的は達成したのでよしとする。徐々に行動範囲を広げていこう。

| | Comments (0) | TrackBack (0)

2008.04.27

$の話

$を最後の意味で使うのはどこからきたのかな。
ずっとMS-DOS経由でCP/Mが元祖だと思っていたのだが、よく考えると正規表現の行末も$だし、コンパイラの本でも生成規則のお尻が$(End of inputとか)使っているのがある。

| | Comments (0) | TrackBack (0)

LALR

コンパイラの本充になったので、ようやくLRなパーサの勉強をする。ざっくり読んで、雰囲気は分かった。実際手を動かしてみると、予想以上の難易度で驚く。

ありがちな数式の定義(http://kaiunix.cs.shinshu-u.ac.jp/Lesson/ProgLangT/2008/SyntaxAndSemantics.htmlとか)を考えたとき、(1 + 2) * (3 + 4) なら簡単にできるんだけど、1 + 1 + 1 + 1 + 1 になると、難しかったりする。1 + 1 + ・・・の段階では、どの+も右側が確定しないから、何にもできない。一番最後の式の終わりで、初めてこれtermじゃんって事がわかって、右から順番に、俺もterm、実は俺もterm・・・という感じでパースが終わる。アルゴリズム分かったけど、どうプログラムに落とすのかが、想像もつかない。

もう一度本に戻ると、状態遷移の表を作るらしい。表を追って、ひとりでああなるほどと納得する。じゃあ、この表をどうやってつくるんだとう当たり前の疑問。ここで、yaccの出番か!

| | Comments (0) | TrackBack (0)

2008.04.26

バイナリアンへの道は遠い

ぱた☆へねでいろんなクロスコンパイラを使っているのだが、objdumpが面倒。どう面倒かというと、ターゲットによってsde-objdumpとか、sh-elf-objdumpとか、コマンドを使い分けないといけない。つい素のobjdumpを使って、objdump: Can't disassemble for architecture UNKNOWN! と怒られる。コンパイル時は意識してターゲットCPUのgcc呼び出せるんだけど、転がっている.oを逆アセして比較しようとすると良く怒られる。

いろいろ考えてみた。

お前の肩の上についているのは、頭かカボチャかっ! by 橘 征二郎 

そうだ、elfのヘッダーみてobjdumpの起動コマンド変えたらどうよ

readelfの結果を使えばPythonで簡単にできそう。Pythonで外部プロセスの起動の勉強に。

めざせバイナリアンだしCで書いてみる?

shinhさんの所に詳しい説明が。ほれぼれする。http://shinh.skr.jp/binary/shdr.html

流れでここを見て前言撤回。変態すぎる。http://d.hatena.ne.jp/shinichiro_h/20060830#1156876307

ふと、cygwin + gcc が出力するのはelfではない、という当たり前の事に気がつく。

もうやる気無い ←今ここ

x86-elf-gccを作るのは逆向きの全力疾走。ELFのマジックナンバーが無かったらx86(PE)にすれば良いのは分かるけど、なんだかな。こういうのは、思いついたときに勢いでやらないと駄目だとあらためて思った。敷居を下げようと無料のWindows環境にこだわったことが、かえって敷居を上げてしまった気がする。

# objcopy --output-target=elf32-i386 test.o test.elf.o は知ってますが、これすらも面倒。

| | Comments (2) | TrackBack (0)

コンパイラの本がいっぱい

ときどきの雑記帖 i戦士篇を見て、「ジェネレーティブ・プログラミング」「ビューティフルコード」を本屋で購入。ついでに、「Googleを支える基盤技術」も購入。

Amazon.comから、Parsing Techniques、Modern Compiler Implementation in C、到着。

Amazon.co.jpから、To Mock a Mockingbird、はじめてのコンパイラ - 原理と実践、コンパイラの構成と最適化、Compiler Design Using FLEX and YACC

買いすぎだろ!

これでコンパイラの本の有名どころはそろった気がするので、「○○という本には、××について載っていますか?」という質問には答えられる。本屋に置いていない本も多いので、質問はお気軽にどうぞ。Parsing Techniquesは、650ページもあってボリュームたっぷり、その割には鞄に入る大きさなのでポイントが高い。勢いで買ったが猫に小判すぎる。何かしら詰まったら読んでみようと思う。

コンパイラの本をずらずらと並べて拾い読みをしたところ、LRのパーサについては、「はじめてのコンパイラ」読んで、「コンパイラの構成と最適化」を読めば十分だと判断し、ドラゴンブックはしまうことにする。というか、「コンパイラの構成と最適化」があれば、ドラゴンブック(の少なくとも前半)は、読まなくても良い気がした。

| | Comments (10) | TrackBack (1)

2008.04.23

今日の日記

・Verilogの規格書の買い方
JZ5 さんから教わった規格書ですが、3日ほど試行錯誤してようやく買えました。
http://ieeexplore.ieee.org/xpl/standardstoc.jsp?isnumber=33945
最初は手順をまとめていたのですが、gdgdになったので要点だけ。

 Opera使うな、IE使え。OperaだとなぜかLoginできない。登録の情報が反映されていないのか、何か英文を読み忘れているのかと、ここで2日ほど停滞。
 上のURLから買えそうだけど、実際の購入はこっち
https://sbwsweb.ieee.org/ecustomercme_enu/start.swe?SWECmd=Start&SWEHo=sbwsweb.ieee.org

これは頑張ったと思う。

・書店
コンピュータ関係の専門書だけ扱ってくれる本屋とか需要ないのかな。2chの推薦図書に出てくる本が、原書、翻訳と並べてずらっとそろっているところ。東京に一店くらいあっても良い気がする。ベンチャーで一発当てて、お金持ちになったら考えよう。

Lisp In Small Pieces到着。
期待していた本と違うw。SICPの4章を詳しくし、最後にS式からC言語のソースを出すような感じ。C言語をLispでパースしてほしかった。老後の楽しみに積んでおく。

twitterで、Cheney on the M.T.A.使ってます?と、いきなり難しい事を聞かれたが、そんなレベルではないです。ガベコレの方法として、Boehmが紹介されているレベルです。

Embedded Core Design with FPGAs
こっちも僕にとってははずれ。論理式の基礎、Quartusの使い方、スイッチの仕組みなど、基本的なところの説明がある。学生ならともかく、僕が求めているレベルではなさそう。とはいえ、説明は丁寧だし、面白い事が書いてある可能性も捨てきれないのでこれも積んでおく。AmazonのBetter Together(あわせて買いたい)にAdvanced-FPGA-Designが一緒に出てくるけど、完全に罠だから。対象読者が違いすぎる。

・ドラゴンブック
3章まで読んだ。ここまでの話なら、東大のmini pyHigher-Order Perlの組み合わせの方がわかりやすい。ようやく本命の4章に入る。4章を読み終えたら手を動かそう。

・ときどきの雑記帖 i戦士篇から
http://www.kt.rim.or.jp/~kbk/zakkicho/08/zakkicho0804c.html#D20080422-7

> ああ、そのときの事情をまるきり無視して現時点での視点と論理で文句つける人は多いですよね。 もちろんそれがすべての免罪符になるかというと微妙なところはあると思うんですが、 なぜそういう選択をしたかということに思いが及ばないというのはなんとも。

どうすれば、その当時の雰囲気を残せるのかな。僕が作ってきたプロダクトでも一応議事録なるものは残ってはいるのですが、新しく入ってきた人に全部読めというのは厳しい。あとで来る人の為に、どういう形でどのような記録を残せば良いのかが難しく、ずっと悩んでいる。失敗学の本は参考になるところが多く面白かったけど、結局実践できていないのが駄目すぎる。仮にいろいろ書いたとしても、1年もあれば残しておきたいことが100個を超えてしまうので、結局読まれない気がする。まずはちゃんと手を動かして記録を残し、それに対して読み手の視点でのレビューを交えて、サイクルを回していかないと駄目なのか。今感じている一番有効な手法は共同作業。一緒に仕事をすることで、なんでこうなってるんですか?という会話がでてくる。結局これが一番伝わる。

| | Comments (0) | TrackBack (0)

2008.04.16

今日の日記

・コンパイラ
ドラゴンブックの2章を読んでいる所。スコープに入っていく時のシンボルテーブルの動きが、SICPで勉強したことに近い。SICP万歳。
ときどきの雑記帖 リターンズi戦士篇できむら(K)さんに、いくつもコンパイラの情報を教えてもらう。ありがとうございます。「4.5 LR 構文解析法」と聞いて、はじめてのコンパイラ - 原理と実践 -をアマゾンで購入。rubyはさっぱりわからないがぼちぼち読む。

・アマゾン
Place in order in JPY のようなボタンがあり、てっきり日本円で表示かと思ってクリックしたら注文されていた。なにがなんだか(ry。その流れで、Lisp in Small Piecesを購入してしまった。「It describes 11 interpreters and 2 compilers, including very recent techniques of interpretation and compilation.」に期待。特に、recentの辺り。

・オブジェクト指向とか
 OOで最後まで読んだ本が、オブ脳、憂鬱本、Object thinkingしかない僕はやばい気がした。Object thinkingは、object万歳な本で、Because everything is an object, there is no data.とか書いてある。信じて良いものだろうか。

C++で継承使って何か書く→すでにstd::vectorに乗らない→参照を渡したら動かない→なんか演算子のオーバーロードも動かない→virtualの存在意義が分からない。で、OOは挫折。C++ D&Eを読んでみて、「デフォでCと同じパフォーマンスを出す」という縛りというか、熱い思いがあるんだなと感じつつも、やっぱり難しいと思う。

時は流れて2007年、Pythonで同じ事をやってみたら、簡単にできたので驚いた。今ここ。

・経理の勉強
我が社の社員は、電車の通勤期間中に簿記の勉強をすること、というお達しが来ました。専門用語と会社としてやらないといけないことを、一通り頭に入れること。ただし、理由を考えるな。というスタンスらしい。小さい会社では、コンパイラの作り方よりは簿記の方が役に立つことは間違いない。残念だけど。

 経理のお姉さんが、経理と財務の違いについて「Wikipediaでも読んでろカス」の意味で「ウィキってください」と言った。かなり新鮮。


・thread
あろはさんに、twitterで教わる。
http://twitter.com/alohakun/statuses/789962635

pthreadって使ったことが無いけど、こんな感じなのか。
http://morihyphen.hp.infoseek.co.jp/prog/pthreadkill.html

>・Win32スレッドがWaitFor(Single/Multiple)Object(s)で全部待てるのに対して、pthreadは mutex、cond、sem、join のどれか、しかも一つだけしか待てない
>・Win32のオブジェクトはシグナル状態を保持し続けるのに対して、pthreadの条件変数は、シグナル待ちになっていない状態でcond_signalを受けると、シグナルは消えてなくなる
>・POSIXのシグナルがそもそも微妙。やっぱりこれもうまく受け取らないと消えてなくなる

この辺りにデジャブ感があると思ったら、SystemCのイベントってこんな感じだった気がする。Pthreadをそのまま使っているのか、エミュレートしているのかは分からないけど、説明を聞いていて微妙どころが無茶苦茶使いにくく感じた。

・大阪が盛り上がってます。
4月20日は、技術者の家族同士で交流を深めてみようやん第1回(仮)

4月26日は、SICP勉強会が大阪で。

20日は家族の用事入れたので駄目です。26日は、新大阪近くなら顔出しくらいできるだろうか。

| | Comments (2) | TrackBack (0)

2008.04.11

今日の日記

ドラゴンブックは一章を読み終えて、二章に入る。電車の中で読んでいるとほぼ100%の確率で眠くなって意識を失う。電卓の文法はもう10回ほど勉強している気がする。

こっちで、クロスコンパイル充になった。
もともとの発端は、http://twitter.com/yadokarielectri/statuses/784191149でした。って、僕向けのつぶやきじゃない。なってこったい。

クロスコンパイル環境で、各プロセッサの出すアセンブラ出力を比較してにやにやしているところ。すでに、パタもヘネも関係無い。一番得意だと思っていたSHプロセッサが、16bit固定の命令セットだと気がついて驚いた。ずっと32bit固定だと思っていました。SH特有の、プログラムの領域にぶつぶつと32bit即値が入ってジャンプでとんとんと追い越していくコードは、日立のコンパイラが駄目な子だとばっかり思っていました。本当にごめんなさい。

| | Comments (2) | TrackBack (0)

2008.04.05

パタヘネ始めました

目標のはてぶ10個を突破したので、はてなの方でちょこちょこと書き始めようと思います。

ドラゴンブックも始めてしまったので、当面は週に一回の更新を目標にしています。

テーマはgomi_boxさんが作った物が、シンプルながらも力強さを感じる素晴らしいデザインなので、使わせていただくことにしました。

| | Comments (2) | TrackBack (0)

ドラゴンブック始めました

いくつもはてぶやトラバをもらったのに、違う方向へ行ってしまい本当にすいません。自分のバカさ加減に愛想が尽きているところです。パタヘネを一緒に勉強する人募集中、めざせバイナリアン!を書いた後に、ちょっと事件が起きてしまいました。

Verilog2001の勉強をしていて、小さいプロジェクトで使ってみたら、結構便利で早速標準化しようと思っていました。ところがですね、モジュールや入出力の宣言方法を変えたら、ちょこちょこ作っていた小物のツール類が全滅してしまったわけですよ。昨日なんかモジュールをつなぐだけで4時間ぐらいかかってしまい、涙目になってしまいました。

前向きに捉えれば、作ったツール類が生産性向上に役立っていることが分かって良かったのですが、全体的には困ったなと。たいしたことやっていないのでVerilog2001用に書き換えるくらいはできるのですが、次に直すときが来たらちゃんとパースしようと思っていたので、そのタイミングが来てしまいました。

パースしてAST作れれば良いので、ドラゴンブックを全部読む必要はなく、前半を読んでいるうちにタイガーブックとParsing Techniquesが届く予定。

パタヘネは一週間にこれだけと時間決めて勉強していくしかないな。[生]タグつけてくれた人、本当にごめんなさい。

| | Comments (6) | TrackBack (0)

2008.04.02

パタヘネを一緒に勉強する人募集中、めざせバイナリアン!

春ですね。パタヘネを勉強しませんか?

パーサの本で注文した、Compiler Implementation In CとParsing Techniquesがアマゾンから、一緒に頼んだ本のせいで全然届かない。ドラゴンブックでも読もうかと思ったのだが、ふとパタヘネを手にとって読んでみる。以前読んだのが新人の頃なので、約10年くらい前になるんだ。

ぱらぱら眺めて気がついたこと。CDROMのIn More Depth とFor More Practiceって面白くない?例えば、2.10-2.12はジャンプテーブルの最適化、2.16-2-18は末尾再帰の最適化の話がCDROMに入っています。ジャンプテーブルの最適化てのは、Cのcase文がテーブルジャンプに置き換わる話。http://alohakun.blog7.fc2.com/blog-entry-878.html、とかhttp://shinh.skr.jp/m/?date=20071121#p01とか。末尾再帰の最適化ってのはhttp://alohakun.blog7.fc2.com/blog-entry-813.htmlとか。

こういうトピックが載っている本て意外に無いんですよね。それこそ、コンパイラの本読まないと出てこない。パタヘネに比べると上のリンクの方がよっぽど突っ込んだ話になっているのですが、そこにいくステップとしてパタヘネは悪くない。

ちょっと面白くなって、付属のCDに入っているMIPSの開発環境を動かしてみるとこれがそのままでは動かない。
YUKI.N>sde-make SBD=GSIM32L
sde-gcc -g -mcpu=4kc -mips32 -EL -mno-float -DGNUSIM -D__SIM '-Afloat(no)' -I../../kit/GSIM32L/../gnusim -c hello.c -o hello.o
sde-make: *** [hello.o] Error 53

この辺りの情報もまとまっているとうれしいよね。

とここまでが前振り。

やること

目標としているのは、ひげぽんさんのSICP関数型言語の勉強に「計算機プログラムの構造と解釈」を読もうのような構成。ただ自分の勉強した結果を残していくだけ。一緒に勉強すると言っても、ただ各自のブログなり、なんなりにお互いの勉強の成果を記録するだけ。途中参加、一章だけ参加も大歓迎。SICPに比べたら、途中参加は全然楽ですよ。


僕向けルール

・主に章末の練習問題と、CDROMを中心に勉強する。
 練習問題は基本的には解いていきたいけど、初版のやつは「CPUをHDLで書け」とか無茶な練習問題もあったので、ボリューム次第。
・プロセッサ周辺は、たとえ少しでもVerilogとかSystemCで動かしてみる
・勉強していく課程で、勉強の為のノウハウを共有したい
 こういうの関数型言語の勉強にSICPを読もう - (6) 1章 - 小休止 traceを使えるようにする。SICP勉強したときに先人に助けられたので、同じ事をしたい。
・原書で進めていくけど、盛り上がったら邦訳も買う。
・記録の場所は、こことは別にしたい。
 http://d.hatena.ne.jp/natsutan/ が第一候補。ただ、はてなダイアリーはAirHでアクセスするとき、ココログに比べて明らかに遅いので悩み中。そっちには長門とか書かない。長門プロンプトはぎりぎり可。
・マイペースでする。
 仕事が混めば2~3ヶ月の放置もある。途中で飽きたら終わり。(今までの勉強の実績から行くと、飽きても飽きたなりに飛ばしもって最後までするとは思う。)
・まずは隗よりメソッド
 無知をさらすことになるが気にしない。


余裕があったらしたいこと

・MIPS以外のプロセッサとの比較。主にx86+gccとか。
・Veritakとの連携
 ここの後半のような事をテキストに沿った形でやりたい。ついでに、Veritakの技も覚える。
・OpenSparcハック。キャッシュやMMU等、CPUから一歩出たところは、OpenSparcから該当するソースを探して見てみたい
・パタヘネ初版、コンピュータ・アーキテクチャ(ヘネパタ)との内容比較

数日放置しますので、興味がある人は、コメント、トラバ、はてぶ等で教えてください。特に、生暖かく見守っていただける人は、はてぶで「生」とだけ書いていただければ伝わります。難しそうだって人はハッカー養成塾:ハッカーへの遠回りを読めば良いと思うよ。

| | Comments (0) | TrackBack (2)

IT技術者として生き抜くための十ヶ条

IT技術者として生き抜くための十ヶ条

ときどきの雑記帖 i戦士篇で紹介されていたので購入。

一日一回C++ソースコードをビルドすること
一日一回アセンブラコードを眺めること
C++知らずはITを語れず

等、心を揺さぶる出だしですが、ほとんど出落ちでした。十ヶ条ってほとんど出てこないじゃん。

途中にアルテラが出てきて、おっと思ったくらいで後半は読む物が無い。アルテラのデータシートが原文を確認してね、になっているのは、あそこのデータシートはころころ変わるから。データシート通りに回路書いて、実装あがってきたら該当部分のデータシートが変わっていたとか良くあること。デバイスリリースしているはずなのに、そこがTPDの訳無いだろ、デバイス作ってから埋める気だろ、な所がいっぱいある。あと、1700ピンクラスだとデータシートにあるんだけど、実物を一回も見たことないデバイスもある。

Stroustrupとのやりとりは素晴らしい。原文と訳の両方が読めるのは、何気ない事だけどすごく大事。後半のインタビューいらないから、前半の勢いで10ヶ条について詳しい説明を入れた方が良かったと思う。(インタビューが悪いんじゃなくて、この構成だと本全体が何を言いたいのか分からない)

Stroustrupのインタビューだけで、2000円分の価値を見いだせる人は買おう。

| | Comments (0) | TrackBack (0)

2008.04.01

Python でSICP4.3 Nondeterministic Computing

あれ、思ったより綺麗に書けたぞ。

# Amb evaluator
# See http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3

# Global variable for amb evaluator
amb_variable_name = []
amb_possible = []

def comb(lol):
  """
  make all combination from a list of lists
  """

  if not lol:
    yield []
  else:
    for x in lol[0]:
      for y in comb(lol[1:]):
        yield [x] + y


def amb(v, l):
  """
  set global variable for amb evaluator
  """

  amb_variable_name.append(v)
  amb_possible.append(l)
  return

def ambeval():
  """
  amb evaluator
  """

  for tp in comb(amb_possible):
    # set variables
    # ex: exec("baker = 0")
    for i in range(len(amb_variable_name)):
      s = amb_variable_name[i] + "= " + str(tp[i])
      exec(s)

    # check requirements
    # ex: eval("baker != 5")
    met = True
    for f in require:
      if not eval(f):
        met = False
        break
      
    # all requiements met
    if met:
      yield tp


### USER FUNCTION ###
def make_distinct(list):
  """
  make string like distinct?
  (See http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#call_footnote_Temp_609 )
  """

  s = ""
  for i in range(len(list)):
    for j in range(len(list)):
      if i <= j:
        continue
      s += list[i] + " != " + list[j] + " and "
  s += "True"
  return s


### main
amb('baker', (1,2,3,4,5))
amb('cooper', (1,2,3,4,5))
amb('fletcher',(1,2,3,4,5))
amb('miller', (1,2,3,4,5))
amb('smith', (1,2,3,4,5))

require = ["baker != 5",
      "cooper != 1",
      "fletcher != 5",
      "fletcher != 1",
      "miller > cooper",
      "abs(smith - fletcher) != 1",
      "abs(fletcher - cooper) != 1",
      ]

# make_distinct resturns the string
# cooper != baker and fletcher != baker and fletcher != cooper and miller != baker and miller != cooper and miller != fletcher and smith != baker and smith != cooper and smith != fletcher and smith != miller and True

distinct = make_distinct(('baker','cooper','fletcher','miller','smith'),)
require.append(distinct)

# solve the problem!
for result in ambeval():
  print "baker = %d, " % int(result[0]),
  print "copper = %d, " % int(result[1]),
  print "fletcher = %d, " % int(result[2]),
  print "miller = %d, " % int(result[3]),
  print "smith = %d" % int (result[4]) 


実行結果がこれ

YUKI.N>python dwelling.py
baker = 3, copper = 2, fletcher = 4, miller = 5, smith = 1

実際にかかった時間が2時間くらい。大半がgeneratorの勘違いで時間を食った。再帰呼び出しをしている中でyieldすると、再帰を一個戻るだけなんだ。ツリーの一番下でyieldしたら、一気に値を返してくれると思って、すごく悩んだ。分かってしまえば当たり前の話。

いらいらしていたら、回答を教えてくれた@kana1さんに感謝。

対話的環境は無いが、SICPのあのごちゃごちゃしたソースが、組み合わせを作るcomb、amb評価器を生成するamb、条件から解を求めるambevalの3つの関数だけでできるんだからたいした物だ。条件も、そのままPythonの文字列書けば良いんだし。Python恐るべし。

言語占いの問い1はYesで確定。

| | Comments (0) | TrackBack (0)

« March 2008 | Main | May 2008 »