「Software Design」2009年12月号
技術評論社
特集「Linuxカーネルのしくみ」がよかった。Linuxカーネルまわりのポイントになる部分を50ページちょっとで広く浅く概観できて、Linuxカーネルに入門する人とか、昔学んだけど最近のカーネルの概要を改めて押さえたいとかの人にぴったりじゃないかな。ネタは、Linuxカーネルの歴史やモジュール構造にはじまり、起動プロセス(含upstart)、プロセス管理、メモリ管理、ファイルシステム、udevとuevent。
ChromiumOSのローカルアカウント
コメントもしたんですが、改めて。
しかし、 Google Account なしに Chrome OS は使えないようなのです。
いやー、ビルドした人にはわかるんですが、(今の)ChromiumOSは、ビルド時にローカルアカウントを作れるようになっています。
Enable a local user account
まぁ、pam_googleのそのへんのソースを見ると、ちょっとやっつけっぽい気もしますが。
あと、日本語入力は、リポジトリを見るとiBus-Anthyが予定されているっぽいです。
追記2009.11.21:
Googleのサーバーが停止したらログオンすらできなくなるんじゃ・・・
pam_googleのソースを見ると、いちどログインに成功したアカウントは、ローカルに情報を保存して、バックアップ的に認証できるようになっています。
…いや、一般ユーザーならともかく、/.Jなオープンソース技術者なら、ChromiuimOSはソースを見たほうが楽しいと思うんですよね。使うより(笑)
「CB感。REBORN」008
なぜか途中までしか読んでなかったので購入。最後はバイク2台+クルマで追いかけっこするキリン展開になって、やっぱりいいねぇ。改めて、ライディングフォームがリアルだなぁと思った。
第58回東京エリアDebian勉強会に参加
第58回東京エリアDebian勉強会に参加しました。前田さんがGnuplotやGNU R、OctaveとそのDebianでのパッケージングについて説明。岩松さんがauto-builderについて解説しました。
本題はさておき(えっ)、複数のパッケージのBuild-Dependsが循環している場合の解決方法が、へぇでした。パッケージAのBuild-DependsにパッケージBがあるけど、パッケージBのBuild-DependsにパッケージAがあるような場合です。builddとかでは、まっさらな環境にBuild-Dependsだけ入れてビルドするので、これではビルドできません。テストフェーズでそうなったりするのだけど、公式パッケージでテストを飛ばすのはけしからん、と。というわけで、ざっくりいうとこう(↓)やるんだとか。
- パッケージAのBuild-DependsからパッケージBをはずして仮のパッケージAをビルド
- できた仮のパッケージAを、それ用のディストリビューションunreleasedにアップロード
- ビルド環境のapt-lineにunreleasedを追加してパッケージBをビルド
- unreleasedから仮のパッケージAを削除して、本物のパッケージAをビルド
うろ覚えでKanzenの辞書データ構造をまねてみる
発端
twitterでつぶやいてみました。
…じゃなかった、こっちこっち(↓)。
KanzenはLispマシンのTAO/ELIS上で動く漢字入力システムで、SKKの原型です(実装はまったく別)。とりあえず、うろ覚えで、Emacs Lispを使ってデータ構造を再現してみます(うろおぼえ選手権的な意味で)。
データ構造
こんな構造にしてみます。
("k" (("a" (("o" . "顔") ("n" (("j" "i" . "漢字") ("z" "e" "n" . "完全"))))) ("u" "r" "u" "m" "a" . "車")))
- 1文字ごとのTRIE構造
- 文字列はcdr方向に伸びる
- 各セルのcdrは:
- 候補が1つなら、その文字
- 候補が複数なら、候補ごとのTRIE構造のリスト
- 各セルのcdrは:
- 最後のセルのcdrに変換後の文字列
実は、実装よりデータ構造を考えるほうが悩みました。
やってみる
というわけでサンプル実装。これを評価してから、*scratch*で以下のようにやってみます。
(setq r (trie-add nil "kao" "顔")) (setq r (trie-add r "kanji" "漢字")) (setq r (trie-add r "kuruma" "車")) (setq r (trie-add r "kanzen" "完全"))
これでrに上記のデータ構造が作られました。
作ってみてから
ふと思い返してみれば、Kanzenの辞書はローマ字じゃなくてカナのTRIEだったような気がしてきました。
「Shibuya.lispテクニカルトーク #4」観覧
Lispコミュニティ「Shibuya.lisp」のテクニカルセミナーイベント「Shibuya.lispテクニカルトーク#4」が開催されました。
今回は、近山隆さんと竹内郁雄さんが目玉で、単なる昔話に終わらず、濃くて面白い話を聞けました。もちろん、ほかの方々も興味深い話を披露してくれました。発表者の皆さん、スタッフの皆さん、ありがとうございました。
以下、観覧メモ。間違いがあったらご指摘ください。
開会の挨拶(garaemon)
Shibuya.lisp Technical Talk 1周年だそうです。ぱちぱち。
次回のテクニカルトークは、いつもの間隔でいうと2010年3月で、みなさんもぜひTalkerに応募してください、との話でした。
1980年前後のLisp事情とUtiLisp(近山 隆)
Lispが「実用的な言語」とあまりみなされていなかった時代に、当時としては爆速の処理系UtiLispを作った話を、ご自身のLisp歴や当時の状況をまじえて解説しました。実装の細かい工夫をうれしそうに話しているのを見て、ああハッカーだなと思いました。ちなみに、会場からの質問で「Common Lispをどう思うか」と聞かれて、仕様を見たときに「俺ならこの仕様を効率よく実装できるぜ」と制定した人が誇示しているように思った、という答えが面白いと思いました。
なお、今回の内容は、和田英一さんの論文と、それを見て思い出した自分の論文、Lispコンテストの解説記事、そしてWikipediaを参考にして(笑)、思い出したとか。
Lispの出会いは、学部生時代に東芝の研究所に実習に行って、あの黒川利明さんに会ったときだそうです。そこから森口繁一・和田英一研究室というLispの王道の研究室へ入り、卒論はDijkstraアルゴリズムの並列GCだったそうです。ちなみに、実は実際に並列GCを動かせるハードウェアが手元になかったというエピソードも語られました。
大学院では和田英一研究室に入り、修論ではPascalでLispを実装、博士過程ではHLISPでAdaを実装したあと、博士論文としてUtiLispを設計し実装したそうです。
実装したLispの歴史としては、1976年にi8080上で動かしたMicroLispから紹介しました。主記憶が4KBなので処理系は1KB程度(実際は860B)にするという、今では信じられない要求使用です。
このときの工夫として、パースはコードが長くなるのでアトムをすべて1文字にした、というのがびっくりでした。基本関数関係でいうと、setが「=」、quoteが「'」、lambdaが「#」、condが「?」、atomが「@」、consが「+」、carが「<」、cdrが「>」という具合で、そのままはともかくこのセンスは使えるかも。
あと、16bitで使えるレジスタが1つしかないアーキテクチャで短いコードでスタックを使って遣り繰りする工夫として、「Push, cDr, eXchange, cAr」というコンビ技で、レジスタにcarが、スタックトップにcdrが入る、というのも紹介しました。ちなみに、Lispの処理系はcdrをcarより先に置く実装が多くて、これは昔の処理系で、リストを順にたどるのにcdrを読むことが多いからオフセット0に置いたのが由来、というトリビアもありました。
次に紹介したのが、修論で作ったPascal上のLispです。ターゲットマシンはFacom 230/38で、竹内郁雄さんが委員長をやったLispコンテストを目指して作ったそうです。このコンテストは1974年に中西正和さんが委員長をつとめたのに続く第2回で、基準は「ベンチマーク」というわかりやすいものだったそうです。
実装で問題になったのは、Pascalのポインタは自由に操作できないこと。そこで、実はPascalコンパイラをいじってヒープ中を指すポインタの機能をこっそり追加してLisp処理系を作ったそうです。Lispコンテストのエントリにちょっと遅れたそうですが、同じFacom 230/38上でFORTRANで実装した処理系より少し速かったため、竹内さんに言及されて、うれしかったとの話でした。
博士課程では、まず、Adaの仕様を勉強するなかで、「作って理解」という和田流によりHLISPでAdaの処理系を開発したそうです。HLISPを使ったのは、GCがあり、Lispコードを生成すれば楽で、大規模な処理に使えるという理由からとのこと。HLISPはもともと数式処理システムReduceの実装のために作られたLispだそうです。名前はHash Lispの略で、Hashというのは、carとcdrが同じならユニーク(eq)になるという仕様からとられているそうです。この仕様のおかげで、どんな大きな構造でも一定の手間で同一性判定ができるのが特徴とのことでした。
ただ、近山さんとしては、HLISPはいろいろ趣味にあわなかったそうで、その経験を元に、自分の好きな仕様のLispシステムとしてSystem 360/370互換のHITAC上でUtiLispを作ったそうです。UtiLispは表向きにはU-Tokyo Interactive Lispの略ですが、本当はUtile Lisp(ユーティリティ的なLisp)だとか。
コンセプトは、機能はなるべく一般化して、ユーザー定義可能にすること。仕様はMacLispを元に拡張し、暗黙のprognや、オプショナル引数、マクロ、catch - throwなどを加えたそうです。
実装の戦略としては、インタプリタの基本部をアセンブラで書き、そのLispでコンパイラを開発し、そこからさらに豊富な機能をLispで記述してコンパイルして組み込む、という方法をとったそうです。1人で1年半ぐらいで全部作ったとか。ちなみに、近山さんに言わせると、System/360系のアセンブラは使いやすくてCとそれほど変わらない感じで書けるそうですが、本当なんでしょうか。
仕様面では、当時としては珍しく豊富なデータ型をサポート。セルとアトム(シンボル)のほか、24bit整数、浮動小数点数、一次元配列、バイト列の文字列、入出力ストリームがあったそうです。文字列は当時セルと同じサイズの構造に文字を詰め込む実装が多かったのを、汎用言語としてテキスト処理にも使いたかったのでバイト列にしたそうです。これにより、バイト列データを扱う(バイト列のコピーや比較など)CPUの大型命令の恩恵を受けたとか。また、Lispではプログラムもデータという考えから、コンパイルした関数もデータ型にしたそうです(操作はできない)。なお、必要ならbignumは作ればいいやと思っていたら、とうとう自分では作らずじまいだったそうです。
データ型の表現は、ポインタにタグ情報を持たせるポインタタグ方式。これは、アドレスの上位8bitは無視されるアーキテクチャで都合がよかったそうです。タグの値も、頻繁な型判定が高速になるように選定。たとえば、負はセル、アトム(シンボル)は最大値、数値は小さい正値など。ちなみに、nilはnilというシンボルとする実装とのことでした(emasaka注:nilの実装には、タグ値、シンボル、自己参照ポインタ、などの実装方法がある)。
実装では、レジスタrがconsならcdrに飛ぶ、などのイディオムをどんどんアセンブラマクロにして記述したそうです。これは、コード量より、なにをやっているかを示す意味が強かったそうで、あとでほかのアーキテクチャに移植した人が助かったと言っていたという話でした。
GCは単純なコピー方式で、コンパクションがなされることから可変長オブジェクトも同じヒープに置いたとのこと。スタックからのGCの処理のために、帰り番地はタグを0にして(つまり、実は何もしてない(笑))GC対応したそうです。
変数束縛は、速度優先でシャローバインディング。いわく、当時のダイナミックスコープのLispではシャローバインディングはFunarg問題などで面倒があったのだけど、レアケースということで放っておいたとのことでした。
束縛関連の特徴的な機能としては、オプショナル引数も紹介されました。「(defun fn (x y (x 'a) (w (car x)) ...」とか書けて、前の引数の値を参照できるという、いまでいうlet*っぽい感じだったそうです。
オプション引数で問題になるのがコンパイル時のリンク方法。UtiLispでは関数はそれぞれ独立してコンパイルしてリンクし、再定義できるようになっているため、呼び出し側にはオプショナル引数の情報はわからない。そこでとったのが、関数側の入り口に、引数の最大数だけのエントリポイントを設けてそこをジャンプテーブルにし、呼び出し側が引数の数で飛び先を変える、という大技。ちなみに、System/360は、システムコールの結果ごとに戻り番地が違う、という仕様を参考にしたそうです。
また、当時の計算機利用環境が、TSSではあるけど、タイプライタ型でシングルタスク、使いやすいエディタもない、コマンドシェル相当のものも使いにくい、ということで、Lispの中にOSを操作する環境を作ったという話も紹介されました。Lispの中からOSのほとんどの機能を使えるようにしたほか、InterLispを参考に構造エディタUSEを作ったそうです。もっとも、いまならEmacsでいいだろうけど、と語って笑いをとってました。
バッククォートも実装し、readmacroでreadtableから展開するように。ここで問題なのが構造化エディタUSEでは展開されたS式を扱うことになること。そこで、readmacroの逆変換をするPretty Printerを作ったそうです。その結果、思わぬlist式がバッククォートに変換されて、いわく、バッククォートのうまい使い方をPretty Printerに教えてもらったということでした。
また、当時のUtiLispヘビーユーザーにProlog/KRの中島秀之さんがいて、それを見てPrologを参考にパターンマッチ機能をmatch式として実装したという話も紹介されました。
UtiLispはその後、1983年にSun 1に移植、1985年にMacintoshに移植、1986年にSun 2/3に移植(まったく新しい実装)、1988年にSparcのSun 4に移植されたそうです。Sun 4版UtiLispは、和田研フォントのシステムにも使われたけど、メタフォントシステムの部分はさておき、できあがったフォントだけが広がっちゃった、とのことでした。
やや余談ぎみの話では、Lispのいちばん面白いのは「Lispはフォン=ノイマン型言語」であること、つまり、プログラムとデータを同じメモリに格納して、evalできることだと語りました。で、フォン=ノイマンの考えの元としては、EDVACやUniversal Turing Machineの影響というのが定説だが、むしろノイマンも研究しているゲーデルの不完全性定理(具体的には、論理式を自然数にエンコードしたゲーデル数)じゃないか、という説を語りました。
さらに余談としては、Prologもプログラムとデータが同じ形式だが、この特徴があまり活用されていないので、ESPではマクロ機能を付加した、というエピソードも語られました。
なお、Lispの面白さとしては、GCにより気軽に構造を作って捨てられることも挙げられました。GCを持っているという意味ではJavaなどもLispのうち、だそうです。
最後に、UtiLisp/360をいま振り返ると、機能は適切だったけど、データ型などの工夫は徒花で、今だったらもっと効率よりポータビリティを意識したものにするだろう、と語りました。そして、UtiLispの開発は、なにより幸せだった、と語りました。
CL-MPIによる大規模並列プログラミング(Fukunaga Alex)
Common Lispで疎結合の並列プログラミングをサポートするライブラリCL-MPIの解説でした。ちなみに、Fukunaga(福永)さんは、アメリカ生まれでアメリカ育ちのアメリカ人だそうです。
Fukunagaさんの本業はAIで、SAT問題(充足可能性問題)に対するソルバーを遺伝的アルゴリズムで自動作成する研究で圧倒的な計算能力が必要になって、CL-MPIを開発したそうです。なにしろ、1コアのCPU1つだと5年かかる計算だとか。
まず、CL-MPIと対比する意味で、Common Lispのスレッドについて紹介しました。スレッドはANSIの標準に入ってなくて実装依存で、移植性が低いというのが問題として挙げられました。ただ、Bordeaux-ThreadsというポータブルなAPIがあって、だいたいのCommon Lisp処理系をターゲットにある程度ポータブルに書けるそうです。
実際のスレッドの例として、マンデルブロ集合の計算をまず逐次処理で書き、それをスレッドに対応させるという例を見せました。で、実際に、ループ変数をスレッド内で参照できないのにハマったとか、なんだか関数を呼ぶと途中から値があわなくなる(Common Lispがスレッドセーフじゃない?)とかに自分が遭遇した体験を語りました。
それをふまえ、スレッドはデータを共用するのでスレッドセーフティに気をつける必要があって大変、ということから、スレッドじゃないMessage Passing方式が紹介されました。本題のCL-MPIのMPIも、Message Passing Interfaceの略で、標準化されたライブラリ規格(フリーの実装や商用実装がある)とのことです。
CL-MPIは、このMPIのFFIライブラリであるCFIのCLバインディングで、ほとんどのCommon Lisp処理系で使えると紹介されました。起動には、mpirunというラッパースクリプトもあり、プロセス数などをコマンドラインから指定できるそうです。実際のMessage passingは、mpi:send-autoで送信、mpi:receive-autoで受信するだけでよいとのこと。実装も、Lispなので内部でprint1-to-stringとreadでデータのシリアライズができて楽だった、との話でした。同期メッセージのほかに非同期メッセージもあるそうです。
現状は、MPI 1.1 APIの一部を実装したところで、教科書に出てくるようなAPIは実装済み。実装していない部分としては、Derived type対応とか、MPI 2対応とかが挙げられました。
最後に、CL-MPIはスケーラブルで移植性が高い、危ないメモリ対応がないのでスレッドより簡単なプログラミングモデル(と自分は思う)、ということでまとめました。
Lispの心(竹内郁雄)
とても面白い(interesting)話を、とても面白い(fun)語り口で聞かせてくれました。ただ、Ustream中継も動画保存もNGとのことですので、内容は詳しく書かないほうがいいかな。
いろいろな話があったうち、とりあえず、H.Stoyanの「Early LISP History (1956-1959)」論文を元にしたという「Lisp誕生秘話」から、特に面白かった部分をかいつまんで。なんとなく、LispはMcCarthyがキレイな理論として考えたアイデアが実装された、というイメージだったのですが、実はすごく泥臭い試行錯誤のすえに作られたのだとわかりました。
- McCarthyはFORTRANに感激していた
- が、文が好きじゃなくて式にしたかった
- リスト処理を追加しようとした
- が、関数の結果がアドレスになるのが許せなかった。McCarthyの頭でもコンスセルという抽象化ができていなかった
- Lispの原型の最初の案(AIラボ)
- Church Lambda
- lambdaを使わないfunction argument
- リストを使わないデータ構造
- レジスタのフィールドの選択関数(のちにcar/cdrのコンスセルに)
- IBM704/709のワード構成は、address partとdecrement partだけじゃなくて、sign、prefix、index、decrement、tag、addressの6パートある。初期の案では、それぞれのフィールドがあった
- McCarthyがcarとcdrという用語を嫌ったらしく、この用語が消えたり復活したり
- applyは最初、式の置き換えしかやらないものだった
- 「計算はすべて置き換え」というChurch方式からMcCarthyは抜けていなかった
- 無差別に置き換えるので、引数リストやquoteされた中も置き換えちゃう、という乱暴なものだった
- McCarthyは実装はapplyベースで考え、evalは論文だけのものだと考えていた。でもRusselがevalを実装しちゃった
- (emasaka注:「MaCarthyはLispを論文だけのものと考えていたが、Russelが実装しちゃった」という巷説とは、ちょっと違うらしい)
ほかにも、これからの言語はGCが必須とか、GCはOSやマシンアーキテクチャでサポートすべき(ELISでは、スタックにダーティーフラグがあったり、GC中かどうかを1発でとれたりした)とか、Lispをデモする環境がWindows上の仮想マシン上のFreeBSD上の仮想ELISのTAOだった(天海さんが移植したやつ?)とか、いろいろありました。
メッセージとしては、「Lispの心とは自由なり」「万物はS式から生じる」、と。そこで質疑応答で、「どこまでS式か。XMLなどもS式か」とちょっとツッコんでみたところ、やはり「XMLはちょっと微妙だけど…まあ自由に考えよう」という答えでした。で、質問の背景として、バッククォートあたりはリーダーマクロとか、TAOでは'xと(quote x)・nilと()・( )と[ ]を微妙に区別するとかそういうのが頭にあったのですが、まさに「自分の作ったLispでは、バッククォートもそのままの形で内部構造にしている」と続けていただき、ちょっとうれしく思いました。
LT:あなたがSchemeを使うべき10の理由(yadokarielectric)
ここからLTです。1番手は、yadokarielectricさん。
Schemeを使うべき理由として、Lispは()が圧倒的に少なくてすむ(ただしCやJavaとくらべて(笑))というのと、構文が少なくてすむというのが紹介されました。後者としては、Schemeの構文はlambdaだけ、と言って、条件分岐をチャーチ真理値で、繰り返しをYコンビネータでやって見せて、笑いを取りました。
ちなみに、タイトルの「10」は2進数だそうです(笑)。
LT:弾幕記述言語BulletSMLのご紹介(mokehehe)
まず、2Dシューティングゲームの弾のパターンを記述するBulletMLを紹介しました。XMLでプログラム的に記述されていて、Javaアプレットで解釈・実行されるそうです。
これをS式にしてLispで解釈・実行する「BulletSML」が発表でした。S式をDSLとしてマクロで処理し、Lispの式として評価するそうです。普通ののLispの式もまぜられちゃうそうです。
デモは、Gauche+SDLで、キレイに動いてました。ただし、弾1つに継続1つなので、重くて無謀な仕様、という話でした。
LT:三次元幾何モデルライブラリkomainu(garaemon)
Lispのインタプリタで対話的に3D幾何図形を作りたいとき、GLUTやGTK、Qtを使うと処理をそっちに取られてREPLで対話的に使えない、そこで自分でライブラリのkomainuを作った、という発表でした。EusLispを参考にしたそうで、GUIライブラリや数学処理など、いくつかのモジュールから構成されているようです。
デモでは、キューブや3Dの物体などを表示して、回転させたりというのをキメてました。
LT:Schemeではじめる音声認識(前編)(naoya_t)
しゃべっている音声ファイルの言葉を認識してテキスト化する試みの、中間報告でした。
AIFFファイルを読み込むライブラリを自分で作って、高域強調などフィルタリングして、0.02秒で区切ったフーリエ変換でスペクトルを抽出して、人間の聴覚が周波数でリニアじゃないのに応じた変換をかけて、DCTで尺度の高さごとのパワーを求めて、声紋のグラフを求めるところまでは行きました、とのことでした。引き続き、隠れマルコフモデルで音素を特定、とかに取り組むそうです。
LT:他言語で作ったWebページをLispでも(making)
「Lisp入門者に、とりあえずWebから、という建前で」ということで、いろいろな言語でテンプレートを共有できるテンプレートエンジンを紹介しました。一部だけLispとかできるそうです。
テンプレートエンジンは、C++で書いて、SWIGでバインディングしているとのこと。形式はSmarty風ということで、デモでは同じテンプレートからPHPとCommon Lispでそれぞれページを表示してみせていました。
LT:さあ家に帰ったらSchemeのコードを書いてみよう(higepon)
Lispの本を読んで、Shibuya.lisp Technical Talkを聞いて、俺もLispがんばる!(イマココ)、という人が、週が明けるとRubyのコードを書いていたりする、というありがちなパターンを紹介して笑いをとったあと、「まずLispを使ってみましょう」と呼びかけました。
そして、「まずは自分で使う小さいツールから始めるとよい」と薦め、Lispの良さを生かしたものいうことで、higeponさんがちょこっと作ったという小物をいくつか紹介しました。
まず、英単語復習プログラム。データをS式にしているので「人間に読みやすい」と(笑)。次に、英辞郎 on the Webの検索履歴を記録するツール(リダイレクタになるCGI)で、データをS式に(ry。最後が自分のPCが積んでいるCPUの型番を調べるツールで、S式でアセンブラが書ける(笑)ということでした。
LT:Haskell Nightについて(nobsun)
飛び入りで、Haskellのイベント「Haskell Night」を紹介していました。11月20日にお台場で開催されるそうです。LTも募集中との話でした。
「理系思考術」
ソフトバンククリエイティブ
売り上げランキング: 156512
一般の「文系」の人向けに、待ち行列理論、ダイクストラ法、ゲーム理論、ベイズ理論、モンテカルロ法、遺伝的アルゴリズムなどを、ユーモラスに解説する新書。ただし、それらの理論という「知識」ではなく、モデルをどう適用するか、適用するときに丸めている部分はどこか、などの「考え方の基礎」のほうに主眼を置いて解説しているのが特徴。
シェルのパイプラインで、コマンドのエラーを反映する
コメントしたので、改めてメモ。
シェルのパイプラインでは、終了ステータスは最後(右端)のコマンドのものになる。
$ (exit 1); echo $? 1 $ (exit 1 | tee /dev/null); echo $? 0
bash 3.0以降であれば、pipefailオプションをオンにすると、エラー(0以外の終了ステータス)を返した最後(右端)のコマンドの終了ステータスになる。
$ (set -o pipefail; exit 1 | tee /dev/null); echo $? 1
ただし、たとえばUbuntuでは/bin/shが標準でdashだし、FreeBSDも/bin/shがbashではないので、注意。