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

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

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

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

表題のとおり、Shibuya.lisp Technical Talk #4 に行ってきました。
メモ書きを……と思ったら猛烈に長くなったので二部構成でお届けします。

ぶっちゃけ普段の私の言動をご存知の方は、「お前 Lisp 嫌いなんじゃないの? なんで行くの?」と思われるかもしれません。実際私も悩みました。
でも私は実は Lisp 自身は嫌いじゃなくて (むしろ Scheme は積極的に好きだし、λ算法ステキだし、構文ががS式しかないってのはむちゃ強力かつエレガントで、そういうところは好きだったりする)、単に:

  • 関数型言語の文脈で Lisp を語るのが嫌い。(progn と set がある限り関数型とは俺は認めん)
  • Lisper はある種「信者」が多くて嫌っつかキモチワルイ。まあ、竹内さんぐらいになると「Lisp 以外に言語はいらない」って言っても許せるけどさあ、そうじゃない人が言っても……。
  • マクロが強力過ぎて嫌。強力過ぎる言語は人を選ぶから、企業で多人数開発することを考えるとおっかない。
  • Lisp はこんなにもてはやされてるのに Prolog が忘れられてるのが悲しい。ジェラシー。

ってだけなんすよね。最後のは冗談に見えて一番真実に近い理由かも。

でも今回は、「あの」竹内さん*1 がいらっしゃるというではありませんか!
もちろん Lisper として著名なわけですが、なんといいますか、文武両道というか、ソフトもハードも軽やかにこなすスーパーハッカー、そして書く文章にユーモアが溢れている、そういう、もー、なんちゅーか、憧れの人ですよ。
コンピュータエンジニアやっててよかったなと思うのは、草野球の人が王貞治イチローに会うのは大変だけど、オイラが Linus や竹内さんにはちょっとのチャンスを逃さなければ会える! ってことかな。
ということで、いそいそと参加してきたっす。

結論

大事なことは先に言おうキャンペーン。

Shibuya Lisp Users Group の皆さん、講演者の吉田さん、近山先生、Alex Fukunaga さん、竹内さん、そして LT 発表者のみなさま、会場ご提供いただいたECナビさま、休憩所のお茶とお菓子を寄贈してくださった EY-Office さま、そして Lisper でもない私とお話付き合ってもらった皆さんに感謝です!

第一部の Gauche チュートリアル、第二部の近山先生、Alex Fukunaga さん、竹内さんのお話、ライトニングトークと、non-Lisper である私にもどれもとても面白かったです。

ガリガリに Lisp したイベントでは(少なくとも今回は)なかったので、ちょっと Lisp をかじってみたい人にもおすすめのイベントなんだけど、いかんせん埋まるのが早すぎ……運営真面目にやりすぎなんじゃないかなあ。もっと手を抜いて毎月やるとかすればこんなに人数が集中しないような気がするんだけど……ま、外野の戯言です。すみません。

第一部:Gauche チュートリアル

GNUScheme 処理系 (というと怒られるのかも) Gauche *2 を使ったチュートリアルっつかハンズオンっつか。

講師は EY-Office 代表、かつ Gauche ファンクラブ会長、吉田裕美さん。ちなみに EY-Office さんは RoR などによる Web サイト構築や教育などを行っているそうですが、Gauche での案件は「残念ながらまだありません」とのこと。

あー内容に入る前に一言。吉田さん、「質問は随時で構いません。話してる人の邪魔になるとか思わないでください。質問はとてもよいことです」、ちょういいことだ!

内容はホントの入門で、オイラのレベルでも全然問題なかった。いちおー大学時代に中西先生の教科書*3 で中西先生から直々に Lisp 習ってるしね。

中村正三郎さんの影響で湯浅先生の Scheme の本も読んだしね。
Scheme入門 (岩波コンピュータサイエンス)

Scheme入門 (岩波コンピュータサイエンス)

ま、10年前の話ですけど……。

オイラと Mizo さんという口うるさいコンビが並んで座っていたため、
「あのー変数の define と関数の define って何が違うわけ?」
「えーとですね、基本的には違いません。つまり……」

(define (func n) ...)

「……は、こう書くのと実質一緒です」

(define func (lambda (n) ...))

「ということは、func という変数に lambda を binding するということの syntax sugar という理解でいいですか?」
「そうですね」
という、とても微妙な展開になってしまいました。あれ? 俺、Lisper じゃないはずなのに。

でもつまらなかったというわけではもちろんなく、久しぶりに手を動かしてコード書いてみるとやっぱ Lisp も面白いなと。んで、Ruby とかやってる人なら楽勝のレベルなので、この手のハンズオンはぜひ参加した方がいいです(前述の理由で参加しにくいのが欠点ですが)。

ちゃんと GC とか、tail-recursive な場合はループに最適化されるとか、変な人なら気にする内容にも触れてたから安心だよ!

あとこの日の収穫なんですが、みなさんには当たり前のことなんでしょうけどね、

  • 例えば if のような構文 (special form) をマクロでしか定義できないのは、関数の引数は関数実行前に全部評価されてしまうから
  • したがってある機能を関数で実装するかマクロで実装するかは、次のガイドラインが適用できる
    • 引数の評価を内部の処理が動くまで遅延したい (言い換えれば、special form が書きたい) のであればマクロ
    • 引数の評価が呼び出し時に全部されちゃってよければ関数
  • なおマクロと関数の実効速度はほとんど差がない

ということが確認できたことです。
これでマクロ大嫌いなオイラも、マクロをいつ使うべきかの俺内ガイドラインができたのでちょっと安心した。

第二部:テクニカルセッション (1) 1980年前後の Lisp 事情と UtiLisp (近山隆/東京大学)

東大和田研出身の近山先生が、学生時代に作った UtiLisp についての思い出話というかその他あれこれ。
つか当時の計算機パワーで海外の論文見ながら処理系実装しちゃうわけだからパワーがあるよなあ。今そういうタイプ少なくなってるもんなぁ。オイラなんか実装力のない能書き野郎だし。

とかいう愚痴はさておきむちゃくちゃ面白いプレゼンでしたよー。

はじめての Lisp
  • なんか Lisp って言語があるらしい
  • ということで卒研のテーマに
  • しかしテキは IBM 704、こちらは 8080
    • ちっちゃい処理系なので名づけて MicroLisp
    • 目標1KB
    • 処理系書いてみると分かるけど read - eval - print ループのなかで eval は一番簡単
    • 大変なのはシンボル (アトム) の処理
    • じゃあアトムを全部一文字にしちゃえ!
      • なんだか APL みたいな Lisp が完成 (笑)
  • Lisp はポインタ演算の嵐
    • 8080 は HL レジスタペアでのみアドレス参照ができる
    • リスト処理する度に HL を push/pop なんかやってたら戦争が終わっちまうぞ!
      • サブルーチン PDXA: Push, cDr, eXchange, cAr
      • Lisp のプログラムの多くは「car を処理して、cdr で再帰
      • だから「先に cdr をとってやって、それを push しといて car を取って HL に入れておく」というサブルーチンを作っておけば、読んだだけで HL に car が入っているし、処理が終わったら pop すれば cdr が入る。非常に多用する処理なのでサブルーチンにくくり出すと効果絶大。
  • 結果、860byte で Lisp の処理系が完成!
Lisp コンテストの思い出
  • FACOM 230/38 で Lisp を作ってみたい
    • FACOM の上で動くまともな言語といえば FortranPascal
    • Pascal を使いたかったが Pascal のポインタには強い制限が*4
    • でも Pascal のメンテナも自分なんだよね。
    • 文法拡張しちゃえ! これで GC が書ける! 勝つる!
  • なんで作ったかというと IPSJ で竹内さんが呼びかけた「Lisp コンテスト」にエントリーしたかったから。
    • でもギリギリ間に合わず
    • しかし同じマシンの Fortran で実装された処理系よりはるかに早く、「情報処理」の記事では言及してもらえた。うれしかった!
  • これが修士のときだっていうんだからすごいよね〜。
HLISP と Ada
  • ご存知のとおり米国防総省の呼びかけで Ada という言語が提案された*5
  • 研究室で仕様の輪講
  • 和田先生曰く「仕様書なんか読んでたって言語は分からん。まずは作ってみろ」
  • どうせ作るなら Lisp で作りたいなー。
  • HLISP で作る
    • HLISP は Hitach の HITAC で動く Lisp だったが、H は Hitachi ではなく Hash の意味。シンボルテーブルの解決にハッシュを使ってたので。
    • いろいろ不満がたまる
    • よし! オレ Lisp 作ろう!
UtiLisp
  • HLISP へのアンチテーゼ
  • S360 系はレジスタ構成は 32bit だがアドレス線は24本しか出てない*6
    • だから上の 8bit は自由に使える
    • ここにデータタイプ (タグ値) を格納しよう
      • int (24bit のみ。欲しければ bignum 書けばいい)
      • float
      • string (バイト列として表現。cons セルとして扱うと遅くなるし、大型命令*7 が使えない。)
      • I/O stream
      • built in function
      • array (あったほうが計算量が下がるので用意した。ただし1次元。多次元は書きやすさが変わるだけで計算量は変わらない (なら欲しい人がマクロで書け))
    • これらの type 判定は bit 判定で用意にできるようにした
      • 例えば atomic かどうかは signed とみて正負判定で
      • その他もビットマスクかけて簡単に判断できるように工夫した
  • 実装はフルアセンブラ
    • S360 のマクロアセンブラはなかなか強力で、関数にするまでもない処理をマクロで記述できたのでありがたい
  • GC は Copy 式
    • 作業エリアを多く食うのが欠点だが、有り余る利点
    • 実装簡単
    • GC と一緒に compaction もできる
    • スタックも一本で実装
      • これだとスタックから参照されているオブジェクトも探さないと
      • しかしスタックにはサブルーチンへの return address がかかれているのでこいつは除外が必要
      • トリック:return address のタグ値を「0」とする
      • つまり普通に call すれば他のオブジェクトと区別がつくというわけ
  • 変数値管理は shallow binding
    • deep binding はパワフルだが遅い
    • 大抵の場合は shallow binding でも結果は同じ
      • Dynamic scope がない Scheme だと関係ないんだけどねー。-
  • オプショナル引数
    • C++ のそれと同じ感じ
    • 引数の最小値と最大値、最大値より少ない場合のデフォルト値が指定可能。
    • ただし LispC++ とちがって動的言語なので、caller / callee がお互い知り合ってるとは限らない
    • caller は自分が何個引数を渡したか知っているので、call する番地を引数の数に応じてずらして呼ぶ
    • callee はどこの番地で呼ばれたかでスタックから値をいくつ取り出すか決める
    • ただし max を越えると不正な参照が起きちゃうのでそこだけチェック
      • この方法で動的言語としては高速なオプショナル変数を実現!
ところで
  • Lisp の魅力ってなに?
    • λ算法?
    • 強力なリスト演算?
    • マクロ?
  • でも最大のポイントは、自分自身を eval ること!
    • すなわち、データとプログラムが同じに扱えること!!
    • すなわち、von Neumann アーキテクチャを体現していること!!!*8
  • では von Neumann はどこからその発想にたどり着いたのか?
    • 実装は EDVAC
    • アイディアの発露は Universal Turing Machine だと言われているが?
    • もっと前に偉大な先達がいたではないか?
  • Kurt Gödel の「不完全性定理
    • ゲーデル数」という考えですべての命題を自然数に「繰り込む」ことで「不完全性定理」を証明
    • これって「プログラム(命題)」と「データ(自然数)」の同一視じゃないか?
    • von Neumann は数論の完全な論理体系の構築を目指す Hilbelt の下で学んでいた
      • 当然、「不完全性定理」についてはショックを受けたに違いない!

もしかしたら von Neumann architecture は

Gödel architecture と呼ばれるべきなのかもしれない!

話戻って再び UtiLisp
  • 書き忘れたけど UtiLisp の語源は「Utile な Lisp
  • 使いやすさの追求
    • 一度 Lisp 環境に入ったら出てこない
    • OS の機能はすべて Lispp からコントロールできるべきだ
      • OS の機能を大抵実現する関数
    • 構造エディタ*9
      • 当時のテレタイプではスクリーンエディタは無理
      • S式を登ったり降りたり右左に動いたり削除したり挿入したり
      • そして Backquote をサポートした pretty print
      • 使えるところには Backquote をつかって表現するので、人間が気づかない表現方法を提示することもあり。
  • Match
    • 当時 UtiLisp のヘビーユーザに中島秀之さん*10 がいた
    • UtiLisp の上で Prolog を実装してた
    • ついでに "Match" という関数も実装した
(match expr
  ((match1)  action1)
  ((match2)  action2)
  ..))
    • match(n) には式、文字列、関数がかける
    • expr が match(n) と一致したら action(n) の結果を返す
    • 関数が変数を持っていた場合その変数には式が成立するような値が束縛される
      • ただしバックトラックはしない*11
UtiLisp を振り返って
  • ハードウェアベタベタの最適化をするような実装は今となっては古いが、当時としてはベストエフォートだったと思う。
  • 実際そのあと、和田研では UtiLisp はしばらく使われていた
    • S360 のアセンブラから 68000 のアセンブラへ変換するフィルタを作って無理やり移植 to SUN1
    • SUN2, SUN3 では仕様のみ踏襲して一から書き直した
  • 和田研フォント
    • 実はあれは日本語版 METAFONT*12 を目指していた
    • つまり同じ「字」という抽象概念から、セリフなしフォント (ゴシック) とセリフありフォント (明朝) を生成するのが目標
    • そのロジックを SUN3 版 UtiLisp で記述
      • しかし残念ながらいろいろな限界があって、フォントを生成するところまではできたが、「美しく生成する」ところまではいかなかった
      • その志半ばのフォントがフリーフォントとして流通してしまい、本人はちょっと不本意らしい。
  • 実装にかかったのはほぼ1.5人年。一人でほとんどの時間をつかって作業していた。
  • 最後の半年はずっとマニュアルを書いていた。

最低でも言えることは、

UtiLisp を作っている間、私は幸せでした。
そして30年ぶりに UtiLisp の話をしている今、私は幸せです。


その話を聞ける我々も幸せでした。
近山先生ありがとうございました!


……あまりにも長くなったので二部構成にします〜。

*1:現在の所属は大学なので「先生」なのだけど、やっぱり電電公社/NTT 研究所時代の印象が強いので「さん」と呼ばせていただきたいので、「さん」で失礼します。

*2:このエントリ読んでる人には今更だけど、「ゴーシュ」と呼びます。「ガウチェ」とか呼んだら多分グーパンチで殴られるので気をつけましょう。

*3:記憶が正しければこの教科書、たしか M 式でかかれてるんだよな……。

*4:過去のブログにも書いたけど、Pascal のポインタはあくまでも Pascal の内部オブジェクトを指すためのもので、C のようにメモリをゴリゴリとはいじれないのです。

*5:知らない人も多いと思いますが、Ada ってものすごい先進的な言語なんですよ。オブジェクト指向が流行る前から抽象データ型サポートしてたりとか。

*6:これって S370 / S390 / z シリーズと続いた歴史のつい最近までそうで、だから z シリーズ用の Suse Enterprise Linux Server は「24bit 版/64bit版」という区分けなんですよね。

*7:S360 独自の、一命令で一気にバイト列を舐めて処理する命令。

*8:フォン・ノイマンアーキテクチャについては Wikipedia でも見てください。要は同じ記憶領域にデータとプログラムを格納するアーキテクチャのことです。

*9:ワタシ、これって Lisper では当たり前なものだと思ってたら、休憩時間に「構造エディタってどういうものなんですか?」と聞いていた若い人がいたから、若い Lisper は知らないんだなぁ。

*10:Prolog 界では超がつく有名人。私この人のテキストで Prolog 勉強しましたです。

*11:Prolog っていうより Erlang っぽいね。

*12:というか Computer Modern Typeface