北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

第一部 Scheme、Common Lisp、俺Lisp

いつもの実況メモです。

開会の言葉 / ひげぽんさん

  • Lispは今年50周年
  • 本やチャットが活発
  • Sheme実装者が多い(利用者より多いかも?)
  • Enjoy λ

50万行オーダーのプロジェクトを俺Lispで書く / mitamex4uさん

L4uLispを元にした独自の構文を持つスクリプト言語です。

  • 10年でプロジェクトが巨大になって来た → 楽をするのにLispを使う
  • なんでLisp
    • 小さい
    • REPL(Read Eval Print Loop)できる
  • L4u (Lisp for you!)*1
    • Lispが好きじゃなく、必要で産まれた
    • ほんとはErlangを動かしたかった → Lisp → なので超並列型
    • 読みやすいLisp
    • 2バージョンを同時に実行することで、プロトタイプから物を作る時にデグレしない
    • S式に統一し、XMLを利用しない → コードサイズ低
  • L4uは、DojaからServlet環境、.NETでも動く
  • エディタもツクッタ (Eclipseプラグイン誰か作って → Eclispとか言う名前がいいw)
  • サーバ側
    • まずはS式の代わりにJSONで作ってもらう→JSONからS式に置き換え
    • JSONならみんな作ってくれるから
  • REPLが可能→Doja - サーバ - PC 間で可能
  • サーバサイドのL4u → サーバで動いてた物をケータイに移せる
  • ホスト言語との連携前提。グルー的に使う。
  • call/ccの代わりのdelegate/cc
    • スタックをコピーせず、そのまま停止してホスト言語に処理を渡す
    • ホスト言語から継続を呼べば、動作再開
  • プリプロセッサ搭載 → ケータイ端末ごとにいろいろ変えなきゃならないから
  • すべて糖衣構文で、S式になる
  • 超並列的指向
  • 人に優しい構文
    • (if a b c)は if then else end の方が人にわかりやすい
    • breakとかcontinueを用意(継続で、とか言われても人はきつい)
    • loopやwhileも用意
    • かっこを減らす
      • 直前の評価結果を示すitの導入(なでしこの「それ」)
      • -> を導入
    • 第一引数を多体勢のために特別扱い
    • 高階関数の引数の順を逆(リストの方が重要だから)
    • CLOSは使わない → ホストがJavaなので、Javaと親和性を高めた
  • 質疑応答
    • Q. もっと軽量なRubyの処理系が出たらどうする?
    • A. Lispがいい
    • Q. どうやって説得する?
    • A. Lispとは言わない。S式とは言わない

HyperSpecひとめぐり〜こんなことまで決まっていますよ、Common Lispでは〜 / NANRIさん

Common Lispの仕様から、独特な物を紹介していただけました。

  • HyperSpecANSI Common Lispの仕様で、1300ページ以上
  • CLtL2 → 途中経過。日本語訳がある
  • 自然な型変換とは逆の変換がされるもの
    • 有理数の正準化 → 2/1 => 2
    • 複素数の正準化 → #C(1 0) => 1 (非正確数0.0だと、正準化は行われない)
  • コンパイラ compile関数
  • アセンブル disassemble関数
  • デバッガ invoke-debugger
    • エラーがあると普通デバッガに移行するので、普段は使わない
  • エディタ ed → どんなエディタが上がるかは処理系依存
    • 引数が関数名の時は、その関数定義を開くと言う"仕様"
  • デモ
    • edの使用 → SLIMEの機能で十分
    • disassemble → アセンブリが表示される
  • Q. SLIMEの自慢は??
  • A. HyperSpecを引ける
  • A. 下部に引数リストが出るのが便利。ユーザ定義関数も
  • Q. 正準化は数学よりもパフォーマンス要件では?
  • A. それもあると思われる
  • A. 虚数のルーチンを呼ばなくて済む

scheme on PINBALL / fujita-yさん

Ypsilonの実装に関する話です。VMの実装者ってすごいですね*2。でも、楽しそう。

  • ピンボール: FPSは200程度。経験的に140以下ではギザギザ。*3
  • フレーム間が5msec
  • SchemeはConcurrent GCを実装しやすい
  • Ypsilon
    • ピンボール用のR6RS。ほぼ全てに準拠 ← 広く使ってもらって、バグを見つけたい
    • デバグのため、セルフコンパイルは良い
    • マルチコアに最適化したコンカレントGC
    • レスポンス・信頼性重視
    • VM並列化とネイティブコード生成はまだ開発中
  • 基本的な最適化
    • 資料も実装も豊富*4
    • Direct Threading → ジャンプの最適化
      • 直接アドレスを保持。必ず下位3ビットが100となるアドレスを使うことで、他のオブジェクトと識別*5
      • ud2命令により、プリフェッチしないようにする ← VMは、上から下には実行されないため
    • Super Instruction → VM命令数を減らす
      • 93個のVM命令、全てコンパイラ最適化を考えて手書き
      • コンパイラが初めから合体された命令を出す
      • 相当使われる命令のみに適応する。そうでなければ逆効果
    • Operand Fusion → タイプチェックを不要にする
      • Super Instructionとあわせると、命令数が増え過ぎるので注意
    • Cache Access → メモリアクセスが一番影響が高い
      • 見極めが難しい→ベンチマークで、広範に影響を与えるものが対象
      • VMではPrefetchが効きにくく、I-Cacheが重要
  • Scheme専用の最適化
    • 最適化コンセプト → ポータブル、メンテナンス、デバッグ、万能、GC、高速
    • Stack GC
      • デバグでBacktraceに対応させたい ← Schemeでは、末尾呼出でBacktraceが失われる
      • スライドによってフレームを潰す ← StackのOverflow時にStack GCで改修
      • ただし、末尾再帰でもGCが発生
      • 末尾呼び出し以外が多いと、GC効果が薄い → 効果が薄い → Stack Closureとの組み合わせ
    • Stack Closure
      • 自由変数を持つクロージャでも、ヒープを使わなくても済む場合がある → Stackですませる*6
      • 生存期間の解析による(自由変数とクロージャ) → 末尾再帰じゃなくても破壊的でも利用可能
  • Coucurrent GCとは??
    • VM(Mutator)とGC(Collecotr)が並列で動く。マーク開始時にだけVMを止める。
  • 簡単に実装できた → 超遅い
    • Mark Phaseが遅い → アロケーションが大量に起こってるとき
    • Snapshot at beginning をやめ、Incremental Update に鞍替え
    • 次はスタベーションが発生(Sweep Phaseで競合)
    • なぜ?? → Concurrent Sweepなので。Sweep開始時にないものをアロケートする場合にMarkをたてるため。
    • 対策 → Sweep 領域にはアロケートしなければ、競合しない
    • またスタベーション
    • GCではなくVM側でアロケーション量を減らす対策→スタベーション
    • 結局いたちごっこ
  • Q. Ypsilonでピンボールは動いているの??
  • A. 動いていません。GCの致命的な不具合があり、延期
  • Q. Ypsilonで 5msec って出るの??
  • A. 今は、1msec以下の速度。50usec×3程度。
  • Q. スタベーションが起こるとどうなる??
  • A. スレッド優先順位を変更してコレクタ優先(ポータブルじゃない)。YpsilonではMutatorを止める。10msec止まるが、Overflowで死ぬよりいい
  • Q. 全てYpsilonにする?
  • A. ルール記述、カスタマイズ、プロトタイプ等に使いたい
  • Q. GCと局所性などは矛盾する。どうする?
  • A. Sweep GCと局所化は相性が悪い。スラバーロケーター??を使っている。コピーGCやコンパクションなどで、局所性が崩れて遅くなることがある。

*1:!は破壊的w

*2:Ypsilonは特にリアルタイム系だからかな

*3:ブラウン管は60にすればよかったが、液晶は違うとのこと

*4:古い資料は現在の石にあってないかもしれないので注意

*5:タグを打つと、タグを分離する分だけ遅くなるとのこと。面白い。

*6:自由変数がなければ、クロージャではなくトップレベル関数になる