次回のテクニカルトークは、いつもの間隔でいうと2010年3月で、みなさんもぜひTalkerに応募してください、との話でした。隆)Lispが「実用的な言語」とあまりみなされていなかった時代に、当時としては爆速の処理系UtiLispを作った話を、ご自身のLisp歴や当時の状況をまじえて解説しました。実装の細かい工夫をうれしそうに話しているのを見て、ああハッカーだなと思いました。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が「>」という具合で、そのままはともかくこのセンスは使えるかも。cAr」というコンビ技で、レジスタにcarが、スタックトップにcdrが入る、というのも紹介しました。ちなみに、Lispの処理系はcdrをcarより先に置く実装が多くて、これは昔の処理系で、リストを順にたどるのにcdrを読むことが多いからオフセット0に置いたのが由来、というトリビアもありました。次に紹介したのが、修論で作ったPascal上のLispです。230/38で、竹内郁雄さんが委員長をやったLispコンテストを目指して作ったそうです。このコンテストは1974年に中西正和さんが委員長をつとめたのに続く第2回で、基準は「ベンチマーク」というわかりやすいものだったそうです。実装で問題になったのは、Pascalのポインタは自由に操作できないこと。そこで、実はPascalコンパイラをいじってヒープ中を指すポインタの機能をこっそり追加してLisp処理系を作ったそうです。230/38上でFORTRANで実装した処理系より少し速かったため、竹内さんに言及されて、うれしかったとの話でした。博士課程では、まず、Adaの仕様を勉強するなかで、「作って理解」という和田流によりHLISPでAdaの処理系を開発したそうです。HLISPを使ったのは、GCがあり、Lispコードを生成すれば楽で、大規模な処理に使えるという理由からとのこと。HLISPはもともと数式処理システムReduceの実装のために作られたLispだそうです。Lispの略で、Hashというのは、carとcdrが同じならユニーク(eq)になるという仕様からとられているそうです。この仕様のおかげで、どんな大きな構造でも一定の手間で同一性判定ができるのが特徴とのことでした。360/370互換のHITAC上でUtiLispを作ったそうです。Lisp(ユーティリティ的なLisp)だとか。コンセプトは、機能はなるべく一般化して、ユーザー定義可能にすること。throwなどを加えたそうです。実装の戦略としては、インタプリタの基本部をアセンブラで書き、そのLispでコンパイラを開発し、そこからさらに豊富な機能をLispで記述してコンパイルして組み込む、という方法をとったそうです。1人で1年半ぐらいで全部作ったとか。ちなみに、近山さんに言わせると、System/360系のアセンブラは使いやすくてCとそれほど変わらない感じで書けるそうですが、本当なんでしょうか。仕様面では、当時としては珍しく豊富なデータ型をサポート。バイト列の文字列、入出力ストリームがあったそうです。文字列は当時セルと同じサイズの構造に文字を詰め込む実装が多かったのを、汎用言語としてテキスト処理にも使いたかったのでバイト列にしたそうです。これにより、バイト列データを扱う(バイト列のコピーや比較など)CPUの大型命令の恩恵を受けたとか。Lispではプログラムもデータという考えから、コンパイルした関数もデータ型にしたそうです(操作はできない)。必要ならbignumは作ればいいやと思っていたら、とうとう自分では作らずじまいだったそうです。データ型の表現は、ポインタにタグ情報を持たせるポインタタグ方式。これは、アドレスの上位8bitは無視されるアーキテクチャで都合がよかったそうです。タグの値も、頻繁な型判定が高速になるように選定。負はセル、アトム(シンボル)は最大値、数値は小さい正値など。ちなみに、nilはnilというシンボルとする実装とのことでした(emasaka注:nilの実装には、タグ値、シンボル、自己参照ポインタ、などの実装方法がある)。実装では、レジスタrがconsならcdrに飛ぶ、などのイディオムをどんどんアセンブラマクロにして記述したそうです。これは、コード量より、なにをやっているかを示す意味が強かったそうで、あとでほかのアーキテクチャに移植した人が助かったと言っていたという話でした。GCは単純なコピー方式で、コンパクションがなされることから可変長オブジェクトも同じヒープに置いたとのこと。スタックからのGCの処理のために、帰り番地はタグを0にして(つまり、実は何もしてない(笑))GC対応したそうです。変数束縛は、速度優先でシャローバインディング。いわく、当時のダイナミックスコープのLispではシャローバインディングはFunarg問題などで面倒があったのだけど、レアケースということで放っておいたとのことでした。束縛関連の特徴的な機能としては、オプショナル引数も紹介されました。...」とか書けて、前の引数の値を参照できるという、いまでいうlet*っぽい感じだったそうです。オプション引数で問題になるのがコンパイル時のリンク方法。UtiLispでは関数はそれぞれ独立してコンパイルしてリンクし、再定義できるようになっているため、呼び出し側にはオプショナル引数の情報はわからない。そこでとったのが、関数側の入り口に、引数の最大数だけのエントリポイントを設けてそこをジャンプテーブルにし、呼び出し側が引数の数で飛び先を変える、という大技。ちなみに、System/360は、システムコールの結果ごとに戻り番地が違う、という仕様を参考にしたそうです。当時の計算機利用環境が、TSSではあるけど、タイプライタ型でシングルタスク、使いやすいエディタもない、コマンドシェル相当のものも使いにくい、ということで、Lispの中にOSを操作する環境を作ったという話も紹介されました。Lispの中からOSのほとんどの機能を使えるようにしたほか、InterLispを参考に構造エディタUSEを作ったそうです。いまならEmacsでいいだろうけど、と語って笑いをとってました。バッククォートも実装し、readmacroでreadtableから展開するように。ここで問題なのが構造化エディタUSEでは展開されたS式を扱うことになること。Printerを作ったそうです。Printerに教えてもらったということでした。当時のUtiLispヘビーユーザーにProlog/KRの中島秀之さんがいて、それを見てPrologを参考にパターンマッチ機能をmatch式として実装したという話も紹介されました。4に移植されたそうです。4版UtiLispは、和田研フォントのシステムにも使われたけど、メタフォントシステムの部分はさておき、できあがったフォントだけが広がっちゃった、とのことでした。余談ぎみの話では、Lispのいちばん面白いのは「Lispはフォン=ノイマン型言語」であること、つまり、プログラムとデータを同じメモリに格納して、evalできることだと語りました。Machineの影響というのが定説だが、むしろノイマンも研究しているゲーデルの不完全性定理(具体的には、論理式を自然数にエンコードしたゲーデル数)じゃないか、という説を語りました。余談としては、Prologもプログラムとデータが同じ形式だが、この特徴があまり活用されていないので、ESPではマクロ機能を付加した、というエピソードも語られました。Lispの面白さとしては、GCにより気軽に構造を作って捨てられることも挙げられました。GCを持っているという意味ではJavaなどもLispのうち、だそうです。最後に、UtiLisp/360をいま振り返ると、機能は適切だったけど、データ型などの工夫は徒花で、今だったらもっと効率よりポータビリティを意識したものにするだろう、と語りました。UtiLispの開発は、なにより幸せだった、と語りました。Lispで疎結合の並列プログラミングをサポートするライブラリCL-MPIの解説でした。ちなみに、Fukunaga(福永)さんは、アメリカ生まれでアメリカ育ちのアメリカ人だそうです。Fukunagaさんの本業はAIで、SAT問題(充足可能性問題)に対するソルバーを遺伝的アルゴリズムで自動作成する研究で圧倒的な計算能力が必要になって、CL-MPIを開発したそうです。1コアのCPU1つだと5年かかる計算だとか。Lispのスレッドについて紹介しました。スレッドはANSIの標準に入ってなくて実装依存で、移植性が低いというのが問題として挙げられました。Lisp処理系をターゲットにある程度ポータブルに書けるそうです。実際のスレッドの例として、マンデルブロ集合の計算をまず逐次処理で書き、それをスレッドに対応させるという例を見せました。Lispがスレッドセーフじゃない?)とかに自分が遭遇した体験を語りました。Passing方式が紹介されました。Interfaceの略で、標準化されたライブラリ規格(フリーの実装や商用実装がある)とのことです。Lisp処理系で使えると紹介されました。起動には、mpirunというラッパースクリプトもあり、プロセス数などをコマンドラインから指定できるそうです。passingは、mpi:send-autoで送信、mpi:receive-autoで受信するだけでよいとのこと。実装も、Lispなので内部でprint1-to-stringとreadでデータのシリアライズができて楽だった、との話でした。同期メッセージのほかに非同期メッセージもあるそうです。APIの一部を実装したところで、教科書に出てくるようなAPIは実装済み。2対応とかが挙げられました。最後に、CL-MPIはスケーラブルで移植性が高い、危ないメモリ対応がないのでスレッドより簡単なプログラミングモデル(と自分は思う)、ということでまとめました。Lispの心(竹内郁雄)とても面白い(interesting)話を、とても面白い(fun)語り口で聞かせてくれました。Ustream中継も動画保存もNGとのことですので、内容は詳しく書かないほうがいいかな。(1956-1959)」論文を元にしたという「Lisp誕生秘話」から、特に面白かった部分をかいつまんで。なんとなく、LispはMcCarthyがキレイな理論として考えたアイデアが実装された、というイメージだったのですが、実はすごく泥臭い試行錯誤のすえに作られたのだとわかりました。McCarthyはFORTRANに感激していたが、文が好きじゃなくて式にしたかったリスト処理を追加しようとしたが、関数の結果がアドレスになるのが許せなかった。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はちょっと微妙だけど...まあ自由に考えよう」という答えでした。]を微妙に区別するとかそういうのが頭にあったのですが、まさに「自分の作った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でバインディングしているとのこと。Lispでそれぞれページを表示してみせていました。Talkを聞いて、俺もLispがんばる!(イマココ)、という人が、週が明けるとRubyのコードを書いていたりする、というありがちなパターンを紹介して笑いをとったあと、「まずLispを使ってみましょう」と呼びかけました。「まずは自分で使う小さいツールから始めるとよい」と薦め、Lispの良さを生かしたものいうことで、higeponさんがちょこっと作ったという小物をいくつか紹介しました。英単語復習プログラム。データをS式にしているので「人間に読みやすい」と(笑)。Webの検索履歴を記録するツール(リダイレクタになるCGI)で、データをS式に(ry。最後が自分のPCが積んでいるCPUの型番を調べるツールで、S式でアセンブラが書ける(笑)ということでした。Night」を紹介していました。11月20日にお台場で開催されるそうです。LTも募集中との話でした。詳細を見る一般の「文系」の人向けに、待ち行列理論、ダイクストラ法、ゲーム理論、ベイズ理論、モンテカルロ法、遺伝的アルゴリズムなどを、ユーモラスに解説する新書。それらの理論という「知識」ではなく、モデルをどう適用するか、適用するときに丸めている部分はどこか、などの「考え方の基礎」のほうに主眼を置いて解説しているのが特徴。きたはてダコメントしたので、改めてメモ。シェルのパイプラインでは、終了ステータスは最後(右端)のコマンドのものになる。3.0以降であれば、pipefailオプションをオンにすると、エラー(0以外の終了ステータス)を返した最後(右端)のコマンドの終了ステータスになる。$?1ただし、たとえばUbuntuでは/bin/shが標準でdashだし、FreeBSDも/bin/shがbashではないので、注意。Byb0nerAppendixemasakaフリーター。