本を読む

　Lispコミュニティ「Shibuya.lisp」のテクニカルセミナーイベント「Shibuya.lispテクニカルトーク#1」が、2008年10月18日に開催された。参加したのでメモ。間違いがあったらご指摘ください。

　全体の感想として、アプリケーションにLisp処理系を組み込んで自由度の高い開発をする、といったような話がいくつかあり、Lispは研究言語ではなく実用言語なのだなと改めて思った。あと（自分も含めて）Emacsだらけ（笑）

Why Lisp（higepon）

　司会のharupiyoさんのあいさつのあと、higeponさんのオープニングスピーチ。まず「50って何でしょう」という質問に、客席のえんどうやすゆきさんから「Lisp生誕50周年」という答えが出た。そこからRubyやJavaとは年季が違うというジョークに。

　で、最近の日本ではLispの本やチャットなどがけっこう活発。しかも、日本にはなぜかScheme実装者がたくさんいる（会場笑）。へたするとユーザーより多いかも（笑）。

　最後に、「Lisp is hot now!」「Enjoy λ」ということで、会をスタートした。

50万行orderのプロジェクトを俺Lispで書く（mitamex4u）

　元々、ゼンリンの電子地図ソフトを開発した人だそうな。で、10年前と今の同様のソフトを比べると、ソフトの規模も大きくなり、2人で開発していたのがチーム開発になり、デスクトップアプリがサーバークライアントになり、といろいろ大変になっている。

　で、携帯向けの地図アプリを開発するにあたり、「楽をしたいから」Lisp処理系を作ってその上でアプリを動かしたというのが今回の発表。「Lispを目的としたものではない」と語っていた。どうしてLispなのかというと、携帯上でコンパイルができてREPL（read-eval-print loop）も動く動的言語はLispしかなかったから。Java VM上で動作し、必要があればホスト言語のJavaと書き分けられるようになっている。

　名前はL4uで、「Lisp for you!」の略。「最後の"!"は、現状に破壊的操作をするという意味です」というのはジョークか本気か。Lispになじみのないチーム全員に拒否反応なしで使ってもらえるように、Algol系ふう（というかちょっとRubyふう）の構文で書けるようになっている。これはプリプロセッサで変換しているので、S式で書いてもよい。実態はScheme。S式のパワーを活かして、XMLのかわりにS式で通信するので、XMlパーサーが不要でコードサイズが小さくなった。開発メンバーには、まずJSONでデータを返すように開発してもらって、それをS式に変換する関数をかぶせた（開場笑）。

　細かい仕様では、リストに似たタプルというデータ構造を取り入れた。「{a b}」のように波カッコで書き、評価すると自分自身を返すのがリストと違うところ。これによりSXMLで「(body {bgcolor #ffffff})」のように単純に書ける。

　また、携帯アプリはI/Oや描画、GPSなど非同期だらけということで、Erlangを目指してアクターモデルによる超並列を実装。共有メモリなしですべてメッセージパッシング。メモリがゆるすならスレッド100万個でもOK。「(parallel 式1 式2 ...)」で並行実行し、「target.send」でメッセージを送信、「(receive)」でメッセージをタプルとして受信する。アクターモデルには開発を切り分けられるメリットもあるとか。

　携帯からサーバーまで複数のプラットフォームで動作する。携帯ではDojaやMIDP。サーバーではLinuxやWindowsのJava VM。なんと.NET FrameworkのManaged C++／C#にも対応した。ホスト言語との連係が前提。実行するだけでプロファイリングして、遅い部分はJavaで書き換えるようになっている。オブジェクトのメソッド呼び出しはJavaふうにもCLOSふうにもObjective-Cふうにも書けるようになっているが、Javaに書きかえる前提だとJavaふうに書くのがよい。また、サーバーとクライアントの切り分けは、スループット重視の処理はサーバー側、レスポンス重視の処理は携帯側というところ。

　Lispにした理由のひとつが、携帯上でREPLが動くこと。実機デバッグできれば原因がすぐわかるのにとか、デザイナから細かい修正が来たときにアップロードが面倒とかいうときに便利。また、リモートデバッグも用意した。携帯からリモートデバッグのサーバーにHTTPでポーリングしてコマンドを受け取るという力技。

　へぇと思ったのが、Algol系ふう文法で関数呼び出しチェーンを見易くする工夫。ある式の後に続く式では、「it」という変数に前の式の値が束縛されている（なでしこの「それ」相当）。また、「式1 -> 式2」と書くと、左の式の値が右の式の第1引数になる（それにあわせてmapの引数の順番も逆にした）とか。

　そのほか、テンプレートシステムとか、同期動作版call/ccであるdelegate/cc（IME入力待ちなどで使用）とか、Cの「#define」や「#if」のような構文（携帯端末ごとにコードを切り分けるのに利用）とかいうのもあった。

　2009年オープンソースで公開予定、大人の事情でもうちょっと待ってね、とのことだった。

• Q: Rubyみたいな軽量処理系が携帯上で動くとしたらそちらを使う？
  • A: もう開発してしまったので乗りかえない。私はLisp面に落ちてしまったし（笑）
• Q: マクロは？
  • A: 未実装
• Q: どうやってまわりを説得したか
  • A: Lispといわずに「新しいスクリプト言語を作った」と（会場笑）

HyperSpecひとめぐり（NANRI）

　xyzzy lispのリファレンスの世話をしていた人。「HyperSpec」はANSI Common Lispの正式な仕様で、会場に多いであろうSchemeの人を対象に想定して、Common Lispの仕様のすごい部分を紹介した。

　Hyper SpecはLispwork社のサイトで公開されている。印刷すると1,300ページ超。ちなみに、CLtL2は途中の仕様で、これでも日本語訳で900ページ。

　NANRIさんが感心したところとしては、数の体系がある。整数、有理数、実数、複素数と、正確数と非正確数の区別がある。ふつうの言語では違う型の数値を演算すると結果は大きいほうの型になるが、CLでは逆の変換をする場合があるとして、有理数の正準化（分母が1なら整数に）と複素数の正準化（虚部が0なら整数に）を紹介した。さらに、複素数の虚部が0.0だと正準化されない（実数は非正確数）という仕様があり、これはSchemeではR6RSではじめて登場した仕様だとか。

　数の体系については、数学的な整合性が目的か、パフォーマンスのためか（虚数でないことがわかれば虚数演算ルーチンが不要になる）、といった話が質疑応答で話題に出ていた。

　また、ほかの言語になさそうな仕様としては、コンパイラが仕様に含まれること。disassemble関数もあり、デバッガも仕様に含まれる。エディタも仕様に含まれていて、「(ed x)」とするとエディタでxを開き、xが関数名なら関数定義を開く。どんなエディタが起動するかは処理系依存で、SBCLの場合は変数*ED-FUNCITONS*にエディタを開く関数を入れておく。

　後半は、Emacs上の開発環境SLIMEからSBCLをデモした。

Scheme on Pinball（fujita-y）

　Scheme処理系Ypsilonの実装の話。CPUアーキテクチャとからんだ高速化の話がばんばん出てきて、すごく面白かった。

　仕事でピンボールゲームを作っていて、Windows・Macのパソコンから、PS、ドリキャス、アーケード機などいろいろなアーキテクチャーに対応している。実装はC++。役物にバリエーションを持たせる必要があり、ピンボールコンストラクションキットを作りたい。GUIは簡単だが、ルールをコーディングするのが大変。そこで、Ypsilonを実装した。

　要求として、描画がフレーム間5msec以内。このスピードに対応してGCがある処理系ということで、Schemeを採用した。YpsilonはR6RS準拠のSchemeインタプリタでセルフコンパイル。マルチコア対応（ゲーム機はマルチコア）のコンカレントGCを使って極めて短いGC停止時間を実現。あと、アーケード機では電源を入れっぱなしにして動き続ける必要がある。コンセプトは、ポータブル（pthreadがあればいい）、メンテナンス性（OSが変更されてもちょっとコードをいじって対応）、デバッグ機能、不得意とするコードがない（下手なコードでもそこそこの性能）、そのうえで速く。

　で、最適化の話に。まず基本的な最適化として、Direct Threading、Super Instruction、Operand Fusion、Cache Accessを利用している。

　Direct Threadingは、間接分岐の分散により分岐予測のヒット率を上げ、Instruction Cacheの効率を上げる。そのために、AST（抽象構文木）にVM命令処理コードのアドレスを直接書き込む。ただし、GCに注意しなくてはならないため、アドレスのアラインメントをそろえて下位3bitで判別する（タグ不要）。さらにud2命令（未定義命令例外）でprefetchを抑制し、Bus TrafficとInstruction Cacheの使用を抑制した。これにより、takで7.8%、taklで11.8%の高速化を実現した。

　Super Instructionは、VM命令数を少なくして、Dispatchの回数を少なくする。これにより、Data Cacheの利用効率が上がる。コンパイラが命令を結合することで、VM命令の処理コードが長くなり、C/C++コンパイラによる最適化を期待できる。ただし、コードの局所性が失われる、使われないコードが局所的に集めたはずのメモリエリアを使うというトレードオフがあり、よほど頻繁に仕様されるコートでなければ逆効果になる。

　Operand Fusionは、Operandの固定された特化命令。動的言語ではOperandのタイプチェックが不要になる。ただし、Super Instructionと同じような効果とトレードオフがあり、Super Instructionと同時に使うと命令数が爆発するという問題もある。

　Cache Accessは、CPUの一番のボトルネックであるメモリアクセスをできるだけ少なくするもの。たとえば、構造体の中でメンバの順番を変えただけで速度が大幅に変わったりする。とくに、Intel Coreなどは、InstructionとDataでL2 Cacheが共通なので、Cahce Lineコンフリクトに注意する。VMではInstruction Cacheが一般プログラム以上に重要で、間接分岐が多いため投機的Prefetchも有効に働かない。Cacheのチューニングは、とにかくベンチマークで特定する。広範囲に発生する場合は優先的に解消。このときはvtuneはあてにならず、経験と勘と根性（笑）。特定の箇所で発生する場合は、CPUやコンパイラで変わったりするので気にしない（笑）。

　さらに、Scheme専用の最適化として、Stack GCとStack Closureを上げた。前置きとして、Schemeのスタックトレース表示では、末尾再起が最適化されるのでそこの呼び出し情報が消えてしまうが、Ypsilonではソースまで含めて表示できる、という話。これは、一般的なSchemeでは末尾呼び出しでスタックフレームをスライドさせて縮めるが、Ypsilonでは呼び出し時にスタックフレームを縮めずGCのフェーズで縮めるという方式（Stack GC）を採用したことによるもの。これにより、フレームのコピーを省略できることが、いまのCPUでは性能的に有利になる。いっぽう、末尾再起するだけでもGCが発生するのは弱点。そのほか、末尾呼び出しの呼び出しがスタックに残っているとGCによって回収できるフレームが少なくなるので、そんなコードを避ける。

　また、Schemeでは、Closureを作るたびにClosureをヒープに作成する実装が多い。しかし、自由変数がスタックの上側からしか参照されないClosureを検出できれば、スタックフレームのままでよい（Stack Clusure）。これにより、コピーのコストが不要になることや、ヒープのあちこちを参照しなくてよい局所化のメリットがある。ただし効率のよい実装にはStack Closureの併用が必要になる。

　さて、Ypsilonの売りであり、同時にいまでも苦労しているところがConcurrent GCだ。Mark&Sweep方式を利用。基本は簡単で、まずMutator（VM）を止めてMarkのルートになる要素を取る。そうしたらMutatorを再開してしまって並行してCollectorがMarkをする。VMはゴミにアクセスすることはないので、Sweepは並行してできる。Schemeは破壊的操作が少ないので、やりやすい。

　…と思ったが、そんな簡単に終わらなかった。試したところ、2コアのマシンでは普通のGCよりかなり遅く、1コアのマシンで普通のGCよりちょっと遅いという結果になった。これは、MutatorとCollectorが激しい競合をしていたため。アロケーション時にMarkビットを立てているのが、GCと競合していた。

　そこで、Incremental Updateにあっさり変更した。新規アロケーションに特別の処理が不要で、Mutatorの動作が速くなった。で、Mutatorが速くなったため、時間あたりのアロケーションも増え、メモリスタベーション（メモリ飢餓）になるという問題となった。Sweepで競合が起きていて、本来Sweepは競合しないはずだが、Collectorが巡回していない場所からメモリを確保する場合はMarkビットを立ててやる必要があり、その部分が競合していた。

　そこで、CollectorがSweepをすませたところからアロケーションするように変更した。で、Mutatorが速く（略）メモリスタベーションになるという問題となった。しかたがないので、VM自体を変更してアロケーションを減らす（Stack Closureもそう）ように変更したら、Mutatorが速く（略）メモリスタベーションになるという問題となった（会場笑）。で、どうしようと。

　最後に次回予告「スピンロックに失望」ということでまとめた。

• Q：もうピンボールに組み込んだか
  • A：バグがあって見送った。次から
• Q：スピード要件は
  • A：GCタイムが0.5msecぐらい（会場驚）
• Q：ピンボール全体をYpsilon化する計画は
  • A：力学パラメータの変更などを試せるようにしたい
• Q：Mark & SweepのGCの動作と、キャッシュや局所化は、反対の性質があるが、工夫はあるか
  • A：スラブアロケータでコンパクション。密にするコンパクションと、先頭に集めるコンパクションの2段階。が、実はヒープをコンパクションすると遅くなることも多い。これは、最初にリストを作るときにはセルが隣りに連続してくれることが多く（cdrコーディングのように？）性能がよいが、コンパクションしたときに並びがかきまわされてしまう

LT：世界のナベアツにGaucheで挑戦する（yshigeru）

　ここからLightning Talk。一番手はFizzBuzz問題ならぬナベアツ問題。なんと、問題をS式で表わし、「アホになる」というシンボルを動作登録の関数に、「3 の倍数なら」というシンボルを条件登録の関数にして、言語内DSLにしていた。で、そのS式をGaucheに与えて、みごとナベアツに。

　なお、ハイテンションでウケた発表に対し、司会がクールにまとめていたのがさらにウケていた。

LT：はじめてのScheme（masa.edw）

　「5分でわかるquine」ということで、quine（自分自身を表示するプログラム）をライブコーディング方式で作ってみせた。使ったのは、formatとlet1。formatに"format"を食わせると表示されるけど、増えたformatを表示するために"format"を追加するとまた…とイタチごっこ。そこでlet1を使ってみて、ここが同じだぞ、ではlet1した変数を使って、できた！ という発表だった。

LT：マイナーRPGはlispで（odaさん）

　2000年ごろに仕事で起きた体験談。ゲーム会社ではないのに、いきなりRPGを作ることになった。しかも、壮大すぎるストーリーに自由度の高すぎるゲームシステム。おまけに、2人で半年というムチャな要件。

　これをクリアするには、自在なデータ構造、インタラクティブ開発、メモリ管理、マクロが欲しい。これはつまり、「毎日使っているエディタに入っているアレだ」ということで、USIというLisp処理系を作った。部下

や手伝いが「Lispわかんない」というので、JavaScriptふう（一部Perlふう）のシンタックスシュガーも作った。

　という苦労をして、RPGを1年間で開発して出荷。とりあえず大きなバグは出なかった。オチは「売れなかったけどな（笑）」。

LT：ケーゾク小説（oskimura）

　暗黒通信団というサークルで、中身のない本とか、eの本とかを作ってコミケに出している。ISBNも取得済みで、Amazonでプレミア（笑）。

　次はSchemeで「継続小説」。AMB評価器を作ってマルコフチェーンとランダムウォークで文章を生成し、その場でプリントアウト、というネタだった（笑）

　最後に、実況板のテキストを元に生成済みのテキストをデモした。

LT：Gaucheのプログラムをもっと速くする方法（小黒直樹）

　マンデルブロの表示とプログラミング過程の自動表示（ttyrecか？）を使って洗練された感じのプレゼン。Gaucheだけでやると遅い局面があるので、Cで拡張モジュールを書いたりする。が、Windowsでは動かない拡張モジュールも多い、S式じゃない、インタラクティブじゃない。

　そこで開発したのがdyncomp。S式でCを表現して、組み込みのTCCでコンパイル、その場でインタラクティブに実行する。Gauche中にインライン化可能。Unix & Win対応。

　デモでは、マンデルブロ表示のSchemeコードをエディタで書いて実行し、それをその場でdyncompな関数で置きかえて高速化してみせた。

LT：CL/SCchemeの組み込み利用（mokehehe）

　Lispをリアルタイムアプリケーション（ゲーム）に組み込みたいので、いくつかためした体験談。

　まず試したのがECL (Embeddable Common Lisp)。バイトコードにコンパイルして実行したり、Cへトランスレートしたりできる。が、cygwinでmakeできず、ソース構成も難解だったのであきらめた。

　そこで、Gaucheをライブラリ化してみた。不必要なソースを除外し、必要な共有ライブラリや.scmファイルだけを配備して、呼び出し側のCコードを書いた。

　ここでDirect Xでデモ。Luaより速いが、ライブラリのサイズはLuaの9倍（笑）。ただ、GCがBohemで不安、例外がわからない、などの部分は未解決。で、Ypsilonはさらに倍の速度が、というところで時間切れ。

LT：初心者がgaucheでロボット制御（momo_dev）

　バンダイロボット研究所所属。自分が開発に参加している探査ロボット「NetTansor」をGaucheで操作してみせた。NetTansorにはLinuxが載っていて、カメラや障害物の距離を測るセンサーなどがついている。センサーの値はポート8081番、カメラ画像はポート80番のHTTPでとれる。

　ということで、gauche-gtkなアプリから会場でNetTansorをコントロールしてみせてデモしていた。Gaucheはスレッドとかも簡単に使えて実装しやすかったとか。

　面白そうなんだけど、価格は5万円。なお、今度出るニューモデルではなんと写真をとって文章を生成してブログに投稿する機能も追加されるとか。すごい。

LT：Reading Gaucheしてみませんか（ココサブ）

　すみません、最後の最後でノートPCのバッテリーが尽きてしまいました。以下、記憶で。

　Reading GaucheプロジェクトでGaucheのソースを読みすすめている。ひらメソッドを使う。トップダウンでWikiのページを作り、末端まで行ったらボトムアップで読む。これで、Gaucheの実装がわかった、ファイル分けなどのコツがわかった、LTに出られた（笑）

　Wikiでやっているので参加者募集中。終わったら、次はStalinかYpsilonか、それともcompile.scmか、あるいはGCCか。