« May 2005 | Main | July 2005 »

June 28, 2005

型推論C++

C++の問題は挙げればきりがないが、その中の一つに「型名を打つのがめんどう」というのがある。変数宣言の際に型名が必要になるのはCから受け継いだ属性であるが、Cの型名はintとかcharとか、せいぜいstruct hogehoge程度であった。が、C++になると途端に化け物じみた型名が出現する。例えば

std::vector<int>::const_iterator it = v.begin();
という具合に、イテレータを使おうとするとものすごい量をタイプしないといけない。OCamlに一度慣れてしまった人間にとっては「このくらい型推論してくれないのー?C++の処理系はテンプレート関数の解決のために型推論機構持ってるだから活用してくれよ」という感じである。本当はUnno氏が米澤研の演習3で「The design and implementation of C++ with type inference」を作ってくれるはずだったのだが、残念なことに彼はSPINなる謎のモデル検査器へと逃避してしまった。

C++には型推論の未来はないのか?と希望をなくしかけた我々のもとに、福音がもたらされた。

[cppll:12064]によれば、

vector<int>::iterator i = find(v.begin(), v.end(), 2);
auto i = find(v, 2);
と書けるようになる(かもしれない)、とのこと。うひょひょ。OCamlのlet i = ...の感覚で変数宣言ができることになる。

記事の最後でStroustrup先生も"significant improvement"と述べているが、これらの機能が実現されればそれは間違いなくsignificant improvementと言えるだろう。

問題は処理系が入手可能になる時期だが……標準が2008くらいにできあがったとすると、処理系が広く出回るのは2013年以降!?その頃もC++ってあるんでしょうかね?

| | Comments (3) | TrackBack (0)

June 27, 2005

alpha-betaの歴史

おもしろいスライドを見つけたので貼っておく。

Die Entwicklung der Spielprogrammierung: Von John von Neumann bis zu den hochparallelen Schachmaschinen
タイトルと2ページ目だけドイツ語だけどあとは英語なので安心されたい。NegaScoutのAlexander Reinefeld氏によるものだが、Minimaxアルゴリズム及びAlpha-Betaやその亜種について紹介している。興味深いのはAlpha-Betaの歴史や、関連する古い文献の抜粋が載っていること。MinimaxってTuringとShannonが考案したと思っていたけど、実はvon Neumannだったの?「同時発見」ってやつかもしれないけど。

| | Comments (0) | TrackBack (0)

June 25, 2005

WindowsからCUPSのジョブ管理

朝起きてくると母親が騒いでいる。プリンタに間違って大量のジョブを投入してしまったらしい。いつもならまたやらかしたか…という感じで後始末するのだが、これはどちらかというと俺の設定の問題である。

現在、我が家の印刷環境は、Linuxサーバーにcupsを立てて、そこにプリンタを接続しておき、クライアントのWindowsからはIPP(Internet Printing Protocol)を使って印刷するようになっている。これまで、設定方法がわからなかったがためにクライアントからjob管理が一切できないという状態になっており、例え大量のジョブを間違って入れてしまってキャンセルしようとしても「アクセスが拒否されました」となってしまうようになっていた。ジョブを取り消すにはrootでLinuxにログインしてlprmするしかなかったのである。

それではあまりにもありえないので、クライアントのWindowsマシンからジョブを管理できる方法はないかどうか調べてみたところ、有用なページを発見。

CUPSでLinuxのプリンタ(PIXUS)を共有する
ちょうど、我が家と同じくCUPSに対してIPP経由でWindowsから印刷するという状況について解説しているページである。この通りに設定したら、確かにジョブ管理ができるようになった。すばらしい。

| | Comments (0) | TrackBack (0)

sudo Winny2.exe

相次ぐWinnyでのデータ流出事件に開いた口もふさがらないが、「chrootしてその中でWinnyを動かせばいいんじゃないの?」という話になった。一理あるな。言われて気づいたが、Windowsにはchrootに相当する機能がない。全てをファイルシステムに結びつけるUNIXとそうでないWindowsの文化の違いだろうか。とりあえず考え得る対策として、VM上でWinnyを動かす、とか、権限の低いWinny専用アカウントを作っておいてWinnyはその権限でrunasして(UNIX風に言うならsudoして)動かす、とかだろうか。

とここまで書いて、そんなことができる/思いつくことのできるスキルのあるユーザーなら、Winnyでデータを流出させたりしないような気もしてきた。思わぬところで振り出しに戻ってしまった格好だ。

それにしても、これだけ流出事件が相次ぐということは、すなわちWinnyの普及率の高さを示していると考えられる。データを流出させた全員が違法なファイル交換(というか、入手?)目的でWinnyを使っていた、と断じるのは早計かもしれないが、普通Fedoraのisoイメージが欲しいのならWinnyではなくBitTorrentを使うだろう。

今更言うことではないかも知れないが、開発者のみが逮捕され、「Winnyであんなファイルやこんなファイルも手に入る!」とあおり立てる雑誌類は何もお咎めなしという現状に、たまらない違和感を感じる。

| | Comments (2) | TrackBack (0)

Win32デバッグAPI

常駐プログラム隠蔽テクニック
Windowsにおいて、IEのプロセス空間にスレッドを作成してその中でDLLをロードさせることで、タスクマネージャ上にプロセスIDを出さず、望みのコードを常駐させられるというもの。
そんなことできちゃっていいんかい!と思ったけどこれはデバッグAPIの一種なのだろうか。試した訳じゃないけど、当然、(adminでもない限り)他のユーザーのプロセスに対してそんなことはできないだろう。さらに、プロセスのデバッグ権限(ローカルセキュリティポリシーで設定するやつ)も必要かもしれない。要は、日常のオペレーションは低い権限で行う、怪しい実行ファイルは絶対に実行しちゃいけません、というあたりまえの結論を再確認するだけのことか。悪意のあるコードに実行を許した時点で、もう全ての望みは絶たれるのだ。

| | Comments (0) | TrackBack (0)

June 24, 2005

京ぽん購入

以前から騙し騙し使ってきたKX-HV210であるが、ついに今日、何をしても画面が映らなくなった。ボタンの操作は効くしバックライトのON/OFFはOKなので、液晶部分がおかしいということか。何度か画面を開閉したり、電源を入れ直したりしてもだめ。そこで、ようやく京ぽんへの乗り換えを決心したのであった。

いわゆる「京ぽん2」、AH-K3002Vの発表も間近と見られており、これを待つつもりでいたのだが、さすがに携帯が壊れているのはどうよということ、どうせ京ぽんは発売後しばらくは品薄になりそうということで、京ぽんをとりあえず買ってしまうことにした。

ポイントが溜まっていたので購入は柏のビックカメラで。お約束通り、柏駅に着いた途端KX-HV210が息を吹き返すという事象が発生したが、今日の俺はもう意を決していたので、そんな小手先の罠にひっかかりはしない。どうせ家に着いたあたりでまたダメになるに決まってる。

そんなこんなで、京ぽん[ネイビー]を購入。学科には同じ色の京ぽんを使ってる人はいなかった気がするので大丈夫かと。

いわゆる携帯端末はこれが2台目になるが、大分メニューや操作感が違うので戸惑い中。キー操作に対するレスポンスは確かにKX-HV210よりはよいが、きびきびしているとも言えず、ちょっと残念。バッテリ持ちは大分悪いとの評判なので充電には気をつけないとな。

目下最大の問題は、店の中の人がなぜかアドレス帳を移してくれなかったので京ぽんのアドレス帳は空になっているということである。以前自分でH"問屋を使ってアドレス帳のバックアップを取ろうとしたときは途中でエラーで終了してしまったし、どうしたものか。

| | Comments (0) | TrackBack (0)

June 20, 2005

演習3: 石川研

演習3が終わるたびにまとめをするのが流行っているようなので、第2期のまとめ。

第2期の石川研では、Linuxにおけるプロセスのマイグレーションに取り組んだ。プロセスマイグレーションとは、あるマシンで実行中のプロセスを一時中断して別のマシンに持って行き、中断したところから実行を再開する機能である。実は第1期の米澤研でも、プロセスマイグレーションという話のはずがいつの間にかsnapshot機能の実装になっていたという経緯がある。2期続けて同じテーマになったのは、まあ偶然であるが。

最初の1週間はBerkeley Lab's Checkpoint/Restart(BLCR)というcheckpointライブラリの調査をした。大変よくできたライブラリで、これを使えば俺は何もコードを書かずにプロセスマイグレーションを実現できそうに思えたが、カーネル2.4では完璧に動くものの、まだカーネル2.6へはまともに対応していない状況であった。blcrのカーネル2.6対応作業はいずれ本家が行うだろうし、どうせだから何か別のことをしようということで、blcrとはちょっと違った切り口でプロセスマイグレーションを実装してみることにした。

なにしろLinuxカーネルを本格的にいじるなどこれまでやったことがないので、関連するソースを読むことに大半の時間を費やした。実装を開始したのは最終発表3日前というきわめて泥沼的状況で、案の定最終発表までにはきちんと動作させることはできなかった。第3期の開始までにはまだ時間があったので、その後デバッグを進めていき、今日ついにプロセスのマイグレーションに成功したのである。何はともあれ、動いてよかった。

カーネルソースをいじっていて思ったのは、「OSの安定性は超人的努力によって支えられている」ということ。例えば、様々なリソースはカーネル内で構造体として表現されている。それらのメンバを操作する際にはセマフォをロックし、操作が終了したらアンロックする。もう、ちょっと間違っただけですぐにデッドロックや競合条件の嵐に見舞われそうである。カーネルソースをいじり慣れている人にとってはまた違って見えるのかも知れないが、少なくとも俺にはカーネルの安全性がきわめて脆いバランスの上に成り立っているように思えた。個人的には、あのような複雑なプログラムにこそC++を使うべきではないかと思う。例えば重要なデータ構造をクラス内に隠蔽して、インターフェースを通してのみアクセスさせ、それによってロック/アンロックを保証するとか。

さらに進んだ取り組み、例えば型安全な高級言語やアセンブリでOSを書けるようにするという試みや、様々な検証技術は決して未来の技術ではなく、今まさに必要とされている技術といえる。

| | Comments (2) | TrackBack (0)

June 19, 2005

Team U/Ox

今日はICPC OB/OGの会の方々による練習会だった。今日はおーくらが用事があるというので二人での参戦。彼によれば「1人が6問解けば2人で12問解けるので大丈夫」とのこと。なるほど。

なんか12時過ぎに集まってあれこれしていたら気づいたらrehearsal is overとかなっていて練習セッション参加できずとか、早くも微妙な感じ。まあ、去年も参加したし大丈夫だろう。14:00の開始まで、メール本文書式作成用のプログラムを書いたりなどして過ごす。

14:00に問題が公開。UnnoがAを早速解き始める。俺はお約束通りBを見る……なんじゃこりゃ。DP?しかし書き方がわからない。いっそ、全探索+枝刈りで行けるか!?いやまさか…いくらなんでも…横で問題を解いてるUnnoに聞いてみよう。「全探索+枝刈りってどうよ」「むりむり」「だよねー」ということで放置。後ほど、全探索+超手抜き枝刈りで余裕で終了することが判明orz

で、なんとなく簡単そうなFに手を出して書き始めるも……reject。いくつかバグを直すもやはりだめ。ぉーん。結局3時間まるまるFに費やして、結論としては「考え方が間違ってた」。OTL

そういうわけで今回は結局、Unnoが3問、俺が0問解いて終わりましたとさ。あー自己嫌悪……これが本番だったらと思うとぞっとする。立ち直れないだろうな…。はまったら潔く諦めて他の人にまわすという勇気も必要だと知った日のこと。アルゴリズムについて他の人に説明してレビューして貰うというのも重要だと思うが、他の人がヒマなことはそう多くなさそうだし、なかなか難しいな。

とりあえずUnno乙。俺にはものすごい勢いで猛省を要求する。

| | Comments (1) | TrackBack (0)

pasteコマンド

ICPCが近づいてきたので、あわててツール作成。去年clipだけ持っていったところpasteも必要だということを痛感したため、作ってみる。要するに、クリップボード上のテキストデータを標準出力に垂れ流すためのツールである。

「paste.lzh」をダウンロード

ところで、clipって全く同じモノをMicrosoft自らが提供していた……まあ、誰しも考えることは同じってことか。

| | Comments (0) | TrackBack (1)

June 13, 2005

ICPC練習会

7号館地下室でACM ICPC国内予選に向けた練習会。詳しくはunno氏の日記を参照されたい。TLE(Time Limit Exceeded)ってなんか業界人な感じですね。TLBみたい。

「俺が一人でM&Mをぱくぱく食べてる間に難しいのを両方解かれてしまいました。 」

というのはおいといて、6問中4問と、まあひどい成績ではなかったが、反省点は山積み。同じ正解数4問でも、例えばExtreme GNCの成績を見てみるとwrong answer等によるペナルティがほとんどない。対して俺などはsubmitした直後にフォーマット指定の考慮忘れに気づいたりする有様で、話になっていない。この辺が強さの違いか。

そしてもうちょっとで5問正解できるところだったのが実に悔しい。去年の本番と全く同じ感覚。今度の原因は俺だし。原因にまで気づいていながら、他のことに気を取られてすっかり対処を忘れていたのは本当にいただけない。ラスト30分をいかに有効に使うかといったメンタル面での強さも要求されるな…。

しかし東大勢多すぎ……GNC、IHI、qoo_など強豪揃いで全くどうしたものか。

| | Comments (0) | TrackBack (0)

Safariか?

cocologのテーマ一覧をみていたら…

メタル

これって……Safari?でも、ちょっと惹かれたかも。

| | Comments (0) | TrackBack (0)

June 09, 2005

れのぼ

X41 Tabletか。実は少し前から情報がでていた?

個人的にはTablet PCは便利そうだと思うので期待はしている。が、現行のTablet PCは重く、高いのが難点だ。今回の製品はこれまでのTablet PCに比べると安いかなという気はするが、それでも通常のX41と比べると高い。重さも1.8kgとちょっと躊躇する重さだ。通常のノートパソコンと同じ価格、同じ重量のTablet PCがほしいというのは欲張りすぎだろうか?むしろ、ノートPCは全てTablet PC化してくれればいいのに。

ところでレノボのスライドはどうにも格好悪くないか?() IBMの共通フォーマット(?)が格好よかった()だけに余計にそう感じるのかもしれないが、なんとも先が思いやられる……。と思ったけど、IBMでもこれなんかは格好悪いな。要は作る人次第?

| | Comments (0) | TrackBack (0)

June 08, 2005

Linkers & Loaders

カーネル輪講に参加した後、IS4年生と一緒にアキバへ。今回は決して怪しい目的ではなく、書籍を購入するためである。

というわけでこのところ必要性を感じていたLinkers & Loadersを購入。様々なオブジェクトコードおよび実行可能ファイルのフォーマットや、リンカとローダの動作について解説した本である。

本書の冒頭に書かれているとおり、リンカってそれなりに複雑な仕事してるはずなのに、コンパイラに比べると全く取り上げられていない。CPU実験では実に単純なモデルを仮定していたのでリンクはそもそもなかったし、ロードもアドレス0に持ってくればいいだけだったしな。一応気分的にはtextセクションとdataセクションにあたる部分を分けた感じだが、明示的にセクションに分かれていたわけではなかったし、そもももアドレス決定はコンパイラではなくアセンブラの仕事だったから俺の仕事ではなかったわけだ。

ところで、リンカはオブジェクトコード中のバイナリコードを解釈してアドレスにあたる数値の部分を書き換える、と書いてあったけが、そうするとリンカは対象アーキテクチャのオペコードを全て知っていないといけないということ?となると何のために一旦オブジェクトコードにアセンブルするのかわからんな。アセンブリコードの集合を最後にアセンブルしつつ同時にリンクを行う方が効率がよい気がしたが、何か別の理由があるのだろうか。

ところでアキバ巡検であるが、Schemer氏がX40 2371-GDJを購入。価格はさらに下がって137,800円だった。これで6人目。

| | Comments (0) | TrackBack (0)

June 07, 2005

オープンソースを導入すべき理由

オープンソースなソフトウェアを使うべき理由として、「マシンのベンダの気まぐれでCPUアーキテクチャががらっと変わっても平気!」というのが挙げられる。

というわけで、Macユーザーはなるべくオープンソース製品を使うべきかも知れない(笑)

ほら、「2度あることは3度ある」というではないか……。

| | Comments (0) | TrackBack (0)

PentiuMac

Apple to Use Intel Microprocessors Beginning in 2006

本当だった。なんというか、あまりに事前情報通りの発表だったので正直どうしたものか。

・2006年からIntel x86へ移行
・FATバイナリ(universal binary)を提供
・Cocoaアプリはそのまま再コンパイルするだけでOKとの大風呂敷 Mathematicaは2時間の修正で動いたとか?
・PPC→x86のdynamic translator(Rosetta)も搭載

詳細は追って各種メディアで報じられるだろう。詳しくは基調講演のスクリプトを参照されたい。

基調講演中で多分触れられていない事として、
・PC/AT互換機なのか、CPU以外は全くのApple独自アーキテクチャか
・64bit OSなのか(Pentium Mは当面64bit化しなかったはず…)
の2点が気になる。

アプリケーションの移行に関しては、AltiVecのインラインアセンブリをごりごり書いているようなところ以外はそれこそ再コンパイル程度でなんとかなるだろう。問題はエンディアンの扱いとデバイスドライバということになるが…。

それにしても、Appleはやることが違う。

さて、俺のMac mini……。

| | Comments (1) | TrackBack (2)

June 05, 2005

AppleがIntelのチップを採用へ!?

合宿で1晩IP unreachableだった間にとんでもないニュースが入っていた。

[WSJ]Apple、WWDC基調講演でIntelプロセッサ採用発表へ

ほんとかよ。以前からウワサにはなっていたものであるが、「どうせまたガセネタだろ」と思っていたのだが、こうも続けてニュースが出てくるということはやはり何かあるのだろうか。

/.日本語版の記事本家の記事を適当に斜め読みしてみた結果、いろいろな予想が上がっている。

1.x86プロセッサを採用
特に低消費電力で高性能をたたき出すPentium Mを利用できることでより軽く、高性能なPowerBookを実現できる。AT互換機にするとさすがにまずいのでCPU以外の部分のアーキテクチャは独自?既存アプリへの対応はやはりOS内蔵エミュレータか

2.IntelにPowerPCアーキテクチャをライセンス
PC向けチップそっちのけでゲーム業界に夢中なIBMに見切りをつけ、PowerPCと互換性のあるチップをIntelに製造させる。ただ、たしかにAppleはPowerPC陣営の一翼であるが、そこまでの権利があるのかどうか不明。しかし、アプリケーションの互換性の問題を考えずに済むなど、実現できるとしたらメリットも多い。

3.Intelに全く新しいアーキテクチャのチップを作らせる
これはどうだろう?しかしAppleならなんでもやりかねない。

4.XserveにXeonもしくはItaniumを採用
とてもありえそうで現実的な話だと思うが、元記事ではMac miniやPower Macについて明言しているのでこれだけにとどまらないと言うことか。

5.IBMへの圧力のため意図的に流されたネタ
うーん。これもありそう。


どの案でも、現在のIBMとMotorola(Freescale)によるチップ製造体制における供給量不足問題の解決、及びPowerMacやPowerBookにおける性能向上という前提があるようだ。個人的にはPowerPCアーキテクチャは好きだし、世の中がさらにx86に収斂してしまうのもおもしろみがないので、2.あたりが実現したらおもしろいかなぁなどと夢想している。

まあどれもまだ噂の範囲で、ふたを開けてみたら「やっぱりネタでした!」ということも十分あり得そうだが、こういうよくわからない状況であれこれ噂する段階が一番楽しいものだ。

| | Comments (0) | TrackBack (1)

June 02, 2005

コンテキストスイッチ

UNIX USERでやっているというLinux 2.6の連載はこれか。例によってVA Linuxの高橋さん(*)である。この連載、終わったらぜひ全てまとめてWebに公開するか、書籍化して欲しいものだ。

2.6でのスケジューラの改良はまあよさそうだが、俺はむしろもっと下層のコンテキストスイッチの実装に興味があった。以前スケジューラ関連のコードからswitch_toという関数にたどり着いたのだが、どうもそこから呼ばれる__switch_toを見ても一体何処でレジスタの保存をやってるのか不明であった。その謎がこの記事を読んでようやく解けた。

ここまで見てきて気が付いた人もいると思いますが、汎用レジスタはいつ切り替えたのでしょうか?実は、Intel x86ではこのタイミングで切り替えることは不要です。必要な情報はすでにスタック上に退避されています。
はっと思ってentry.Sを見ると確かにENTRY(system_call)以下でSAVE_ALLしているではないか。そしてこれが、pt_regsの順番でもあるわけか。OK。この値はシステムコールを実装している関数(sys_hogehoge)の側ではstruct pt_regsの値渡しで取ることができる

もちろんこれはCPUアーキテクチャ依存(もちろん、コンパイラにも依存)です。
というので、試しにPowerPCを調べてみると、entry.S内の_switchでレジスタの保存をしている。SAVE_NVGPRS(r1)というのがそれだ。NVGPRSとはnon-volatile GPRsのことだと思われる。r1はスタックポインタだったかな?CPU実験の頃調べたけど忘れてしまった。ところでSAVE_NVGPRSの実装を見ると、stmw(store multiple words)命令は使っていないようだ。これは複数レジスタの値を一気にストアする命令で、コンテキストスイッチに便利かな?と思ったのだが。

はぁ…しかしこんなペースで調べていて実装間に合うのかね?

(*)高橋メソッドの高橋さんとは違う。

| | Comments (0) | TrackBack (0)

June 01, 2005

かけ算のできない大学生

某研究室では、「かけ算九九」ならぬ「かけ算FF」が必須科目らしい。

「4×8は?」
「20(にーぜろ)」

「ff = e1」

一旦10進を通って答えてるようでは先が思いやられるらしい。

| | Comments (0) | TrackBack (0)

月のひつじ

BSで月のひつじをやっていたので丸々見た。

オーストラリア映画ってのはなかなか聞かないのでちょっと新鮮。まあ基本的にはどたばたコメディで最後に感動というオチなわけだが、俺はどうも「科学者、技術者の見えない苦労」みたいな話に弱いのでついつい見入ってしまった。

UNIXすらまだなかった時代に人間を月に送っていたなんて信じがたい気分だ。改めて情報科学という分野の若さを実感させられる。しかしながらこの時代に既にパイプラインや仮想化技術はあったのかと思うとそれも不思議な感じ。

アポロの月着陸のような、人類の大きな進歩を感じさせるような出来事はこのところないような気がする。しかし人類の進歩は止まってしまったかというというとそうではなく、気づかない間に進行しているものこそ真の進歩ではないかと思う。数人の人間を国家の総力を挙げて月に送ることと、何十億もの人たちがインターネットを通じて情報のやりとりができること、もしかしたら後者の方がよりすごいことなのかもしれない。

| | Comments (0) | TrackBack (1)

« May 2005 | Main | July 2005 »