おがさわらなるひこのオープンソースとかプログラミングとか印刷技術とか

おがさわらなるひこ @naru0ga が技術系で興味を持ったりなんだりしたことをたまーに書くブログです。最近はてなダイアリー放置しすぎて記事書くたびにはてな記法忘れるのではてなブログに移行しました。

クリエイティブ・コモンズ・ライセンス
特に断りがない場合は、本ブログの筆者によるコンテンツは クリエイティブ・コモンズ 表示 - 継承 4.0 国際 ライセンスの下に提供されています。

2009.11.7 Shibuya.lisp TT #4 (その２)

Event ProgrammingLanguage

d:id:naruoga:20091108:1257683473 の続き。

第二部：テクニカルセッション (2) CL-MPI による大規模並列プログラミング (Alex Fukunaga/東京工業大学)

イントロダクション
  • 先攻はAI
  • SAT問題の解決がテーマ
    • 論理充足性の確認 (Wikipedia の定義 も参照)
    • SUSE のパッケージ解決にも用いられている
  • 計算量膨大
    • でも並列度あげれば行けそう
    • こういう処理はやっぱ Lisp でやりたい
      • CL での並列プログラミングの探求
まずはスレッド
  • CL のスペックにはスレッドは存在しない
  • Implementation Dependent
    • 実装されてないやつもある
    • あるいは実装されてても Native スレッド使えないとか
  • 救世主「Bordeaux Thread」！
    • CL のスレッドの Implementation Dependency を丸めてくれる*1
    • Binding は Global binding と Thread Binding と両方ある
  • しかし罠が
    • マルチスレッドプログラミングだと「引数で渡されたパラメータの数だけスレッドを生成して実行」とかやりたくなるが、binding の文法としてできない
      • let 一個入れればいいが割とハマりやすいので注意
    • スレッド生成のときに処理の記述に関数呼び出しを入れると結果が狂う
      • lambda で直書きしてやれば問題ないが……わかんないってば。
    • 結論：CL でスレッドはイケてない
      • そもそもスレッドはスケールアウトしないしね……*2。
そこで MPI
  • MPI とは Message Passing Interface
  • 並列計算機同士の規格を統合するもの
    • Single Process Multiple Data (SPMD) が基本
      • 同じプロセスががーっと走ってそれぞれ違うデータを処理するモデル
  • こいつを CL から呼べれば大規模クラスタ計算機とかサクッと使えて勝つる！
  • CLI-MPI
    • CL が持ってる FFI*3 のライブラリ CFFI を用いた MPI ライブラリ
    • 当たり前だが CFFI を実装してない処理系はダメ
    • 逆に言えば CFFI さえ動けば MPI は使える！

おうちの ATOM から Grid Computing まで
移植性抜群な CLI-MPI をぜひどうぞ！

おまけ。

個人的に一番驚いたのは GNU Common Lisp って懐かしの KCL の末裔なんだ！　ということ。Lisper には常識かもしれませんがね。

第二部：テクニカルセッション (3) Lisp の心 (竹内郁雄/東京大学)

コンピュータと Lisp の出会い
  • 大学では TOSBAC 3400 + フレキソライタ*4
  • リバーシを書いてた
  • 教授から McCarthy の Lisp 1.5 Programming Manual を渡されたが、なんだか分からないので投げ出してしまった。
Lisp との再会
  • 大学を出て旧電電公社の研究所に入所
  • 文字列処理を根幹にした Formal-2 という処理系を書いてた
  • 1970年、T. Winograd の SHRDLU の論文を読む
    • すげー！
    • Winograd の環境は PDP-6 + MacLisp *5。
    • 計算機資源は大きく違うが、よく見るとほとんどが辞書とかそういうスタティックデータで、ワークエリアは案外小さい
      • Lisp 使えば面白いことできるかも！
      • PDP 11/30 を購入してもらい実装を始める
LISQ (りっぷく*6 )
  • Q は四次元の Q
car cbr ccr cdr
  • 4セルあった方が自然言語処理には色々便利*7
  • Bulk
    • (半)仮想記憶のようなもの
    • メモリが足りなくなると今使ってないリストごとずるずるっとファイルに書き出す
    • もちろん必要なときにはまた読み込む
LISX (りっぺけ)
  • PDP11/55 に入れ替えたときに最適化
    • 仮想記憶が追加されたけどマシンスペックはさほど変わらず
    • とにかくうるさいマシンだった
TAO → DAO/60
  • PDP 11/60
    • マイクロコードがいじれた！
    • 最適化のためにマイクロコードのレベルでガリガリ書いた
    • でもそれだけじゃ足りなくて、ロジックボードもいじっちゃった！
たらい回し関数

{\rm Tak}(x,y,z) = \left \{ \begin{array}{ll} y & {\rm if} x \leq y \\ {\rm Tak}({\rm Tak}(x - 1,y,z),{\rm Tak}(y - 1,x,z),{\rm Tak}(z-1,x,y)) & {\rm otherwise} \end{array}

  • MaCathy に紹介したらアメリカで紹介されたが、y を返すべきところを z を返すように間違えられてしまった！
    • z を返しちゃうと問題が簡単になってしまうのに。つまらん。
    • なおこの関数にあるパラメータを与えたときの計算量を計算したのは Knuth の研究室だそうな。*8
McCarthy と Lisp ｰ 先入観を持った天才が迷走した話 (1) -
  • 1984 年の ACM の Conference on LISP and Functional Programming で発表された一つの論文
  • 東ドイツの Herbert Stoyan が書いた "Early History of Lisp"
    • HTML 版はこのページからこちら。
    • PDF 版はこのページからたぐれます。ただし ACM 会員じゃないとダウンロードできないっぽい。
    • 手動式タイプライタ（キーを押すとガチャンとタイプされてキャリッジリターンするとチーンとなる懐かしいアレね) で書かれてて、時々字が抜けたりして非常に貧乏くさい論文だった
    • しかし非常にエキサイティング！
  • なにが面白いか
    • McCarthy といえば Lisp の開発者として有名
    • だが彼も一直線に今の Lisp にたどり着いたわけではなかった
    • 彼曰く「私が Lisp にした貢献は cond の発明だけ」
    • そういう迷いが全部書いてある！

ということで話が面白すぎてメモれなかった私のブログなんかより上の論文を読んだ方がいいと思います。

McCarthy と Lisp ｰ 先入観を持った天才が迷走した話 (2) -
  • MaCarthy: MIT の大学教授
    • 元々数学者で論理が専門
    • 多くのハッカーを生んだ Project Mac の牽引役
    • 世界ではじめてチェスをするコンピュータプログラミングをした人
    • 始めて Artificial Intelligence (人工知能) という言葉を作った一人
  • あるとき IBM の研究所で Fortran を始めてみる
    • これはすごい！　式から機械語に翻訳できる！
    • Logical-Mathematical への野望 (妄想)
    • AI Memo 1 からその野望への萌芽が
  • AI Memo 2 でほぼ方向付けはされたが……大分未整理。
    • car と cdr と cons だけでいくつあるんだよ！
  • AI Memo 3
    • 当時 Fortran のコンパイラ開発が30人年と言われていた時代 *9
    • S式の登場
      • McCarthy は別に "()" にこだわりがあったわけではない
      • 単に当時使っていたタイプライタに他の文字がなかっただけ
    • McCarthy はラムダ算法による計算理論に非常に思い入れが強かったので、計算 = 関数の適用 (による置き換え) だった。
  • Sequential Program の導入
    • 副作用があるが、実用的なプログラムを書くには必須
    • progn の発明
      • それまではみんな cond で Sequential Programming してた
      • print とかが nil を返すのはその名残り
      • いい加減直したらいいのに……
Lisp の魅力
  • APL はガラス玉のようだ
    • 美しいが、なにかいじろうとするとすぐ壊れてしまう
  • Lisp は泥の玉のようだ
    • 新しいパラダイムをどんどん取り込んで行っても Lisp であることは変わらない
      • 論理型とか
      • オブジェクト指向とか
      • ひょっとしたら遅延評価なんかもあるかな？
      • この懐の広さこそが Lisp
  • GC
    • 多分 Lisp が多言語に与えたもっとも大きな影響
    • 今や GC をサポートしていない言語は少数派
    • それなのに OS や CPU アーキテクチャレベルで GC をサポートしないのはなぜだ？
  • なぜか Algol 68 のマニュアルの最初に道教からの引用がある
    • それまんま Lisp ですから。
    • 道教の言葉「道を極めたと思ったならば、その道は真の道ではない」
    • いかようにも変化していける Lisp は TAO にもっとも近い存在
話とんでプロシンのカレンダーのお話
  • IPSJ の古くからやっている行事「プログラミングシンポジウム」
  • そのオープニングセッションでお題が出て、それを好きなプログラミング言語で作り、応援演説をする
    • 作ってこない人もいるけど (なんじゃそりゃ)
    • 今年のお題はカレンダー
      • 普通のカレンダーじゃつまらない
      • 面白いカレンダーをつくろう！
      • 調べごとに熱中しすぎて遅刻 (笑)
  • どんなカレンダー？
    • 作るからには世界だけではなく地球外（宇宙）を相手に
    • いろんな星で年月日・週の概念はどうなっているのか？
      • 年は公転周期、日は自転周期
      • 月は衛星？　でも衛星がない星、複数ある星は？　自転傾斜角があるなら四季はあるから４の倍数が望ましい
      • 週は多分 Social なもの。
Q&A
Q
竹内先生はS式への愛を語っていらっしゃいましたが、どこまでS式といえるのでしょうか。例えばXMLはS式のような表現能力を持っていますが。
A
XMLはちょっとS式といいたくないですね(笑)。でも僕の作った Lisp では backquote もS式です。
Q
先ほどお見せいただいた Elis/TAO の実行環境は配布されてるのでしょうか。あるいはいただけたりするでしょうか。
A
(事情により省略) でもいろんな恥をさらしてるのであんまりあげたくないなぁ〜。老後の楽しみで色々直そうと思ってるんですよ。

いやー面白かった。竹内さん、ありがとうございました！

第三部：Lightning Talks

ビデオ撮影のためか照明が落とされていてメモ取れなかったので、一言コメント。

発表テーマ* お名前 (所属)
yadokarielectric あなたがSchemeを使うべき10の理由 とりあえず チャーチ数じゃないと答えが出ない lambda だけの階乗わらた。
mokehehe 弾幕記述言語BulletSMLのご紹介 (cadrグループ) タイトル見た瞬間にBulletMLをS式で書くんだなってのは分かったけどやっぱマクロで実行しちゃうのね。しかし wait で (yield 1) は強引だな (^^;)
garaemon 3次元幾何モデルライブラリkomainu on CL なかなか面白い。こういうインタラクティブ性があるのは教材にもいいんじゃね？
naoya_t Schemeではじめる音声認識(前編) 専門用語でまくりでかなりのハイペースだったのでついていけませんでした (^^;)
making (まきんぐ) LL他言語で作ったWEBページをLispでも！ Web 系 LL な人に Lisp 使ってもらうために SWIG でバインディングってのはいいアイディアだと思う。
ひげぽん さあ家に帰ったらSchemeのコード書いてみよう (サイボウズ・ラボ) ちょっとしたもので思いついたものをすぐ実装してみるの大事。でも例1、2と3のギャップが激しすぎで笑った。

的を外したコメントもあるかもしれませんが私が Lisper でないせいです。リンク先のビデオをぜひご覧になってくださいませ。

懇親会

幸運にも竹内さんの一つおいて隣の席に座らせていただいていろんなお話を聞かせていただいたので、それだけ記憶が発散する前にメモった内容。

  • TAO は ELIS のアーキテクチャから Lisp に最適化してたので、GC のためにメモリにダーティかどうかをハードウェアで判定してた*11。
    • で、この ELIS のチップ作ってたのが ylug つながりの方 (関数型言語ラブラブ) のお父様というところが世の中面白い。
  • 「Lisp 以外に気になる言語はなにかありますか？」という質問に対して即答。「アセンブラとマイクロコード」。さすが電電公社時代 LISQ という処理系を作ったときに PDP-11/30 (だっけ) のマイクロコードを書き換えたうえ、こっそり論理基板まで変えちゃった人は違う。
  • GC は遅い、遅いというが、マイクロコードレベルで詰めていったら１サイクルが100μsec.を切れるところまでいけた。そうするとGC自身をコンカレントな処理の一つとして扱うことができて、60000プロセスを同時に走らせても問題なく動くような実装にできた。
    • 寝ながらマイクロコードレベルであそこをどうつめるかとか考えていると、ぱっと3クロックが2クロックになるロジックが浮かんだりする。最適化はそういうレベルで考えていかないと。Cコンパイラのコードに勝てるような最適化をする自信がないなんてまだまだ甘い*12。
    • それを考えると今の組み込みとかオーダー間違えてるとしか思えない。なんで ms 単位の話なんかしてるの。おかしいでしょ。
  • 「竹内先生としては CL とかどうですか？」「自分の作った Lisp 以外はよく知らないんだよねえ。でも Scheme はなんか今ひとつだなー。整理され過ぎちゃってる感じがして」「講演でおっしゃってた、どんどんいろんな特徴を取りこめる自由さがないというか、APL ほどじゃないけどなんか変なの入れると壊れちゃうとか、そういうことですか？」「うーん、そうだねー」

あとシルクハットガイ、「そーり」さんのことをいたく気に入って、「君、ぜひ通天閣行くといいよ。絶対おすすめ。腹巻してさ、できれば上は燕尾服で、下はそのジーパンでいいよ。いやー絶対似合うよ、通天閣」とおっしゃってました。そんなにそーりとマッチするのか、通天閣よ (笑)。


近山先生ともお話ししたくていったらちょうど時間切れになってしまい残念。ESP の話とか聞きたかったのに。
自分の好きなプログラミング言語を列挙した名刺を渡したら「Erlang 好きなの？」「いや元々は Prolog が大好きで、似た言語ないかって聞いたら Erlang を薦められて、でもバックトラックもないし全然 Prolog じゃないじゃんって思ったんですが」「そうだねー、Erlang は Prolog の癖のある面白いところはなくなっちゃってるからねー」「でも、まてよこれ、ヒューイットの Actor じゃんって思いまして」「なるほど」「でさっきの UtiLisp のときに、中島さんが Match って構文作ったっておっしゃってたけど、関数型にバックトラックのないパターンマッチングを導入するのってなんか Erlang っぽいなーと思ったんです」「あれはね、その後に作ったｘｘって処理系*13 があって、Erlang 作った Joe Armstrong だっけ？　彼が来日したときそれについていろいろ話したんだよ。そしたら Erlang がそれにそっくりでね」「へー、そんなことあったんですか」とかなんとか。
近山先生、一度研究室に遊びに行っていいですか？　と思わず言いたくなった。マジでメール出してみようかなー。


ということでながーいながーい（割には内容の薄い）エントリをみていただいた皆様には感謝！

*1:さすがにない奴はムリだし、non-Native スレッドを Native にできるわけじゃないですが。

*2:一説によると、Lisp に限らず、人間がちまちま排他処理書いてスレッドでスケールするのは４プロセッサまでなんだそうです。やっぱり SMP には無理がある。

*3:Foreign Function Interface の略だそうです。リンクさがすのめんどくなった。

*4:スティーブン・レビーの「ハッカーズ」で、リチャード・グリーンブラッドやらアラン・コウトクなどの初期の MIT ハッカーがこいつでハックしてたって書いてたなぁ。

*5:Wikipedia によると Planner も使ってたみたいですね。世界初の論理記述言語。

*6:下のりっぺけ共々覚え間違えてたら Twitter で emasaka さんに教えてもらいました。ありがとです。

*7:とおっしゃってた気がするけどメモってないので怪しい……。

*8:オイラは Knuth 大好きっ子なので、この話を聞いたときにニヤリとしたことを否めない。

*9:メモに残ってるんですがどんな文脈で出てきた話か覚えてません (^^;)。

*10:ここは文法がS式しかないLispの強みで、例えば Ruby なんかにも eval あるけど、syntax break しないようにプログラムを作ることその物が猛烈に大変なので、こういうやり方は Lisp ならではだと思う。

*11:今の言語も多くは GC を備えているのだから、OS や CPU アーキテクチャが標準で GC を備えてもよいのではないか、というのは講演でもおっしゃっていました。

*12:「Cコンパイラの……」というのはその前にされた UtiLisp の近山先生の講演で出てきたセリフ。まあ近山先生はポータビリティを考えての話だし、竹内さんは環境を限定した最適化を意識されてる差なのかなぁと。

*13:忘れてしまったんですが、もしかしたら KL/I かも。