自分はFLOPSには行ってないけど （すみません(^^;）それのために来日した人と会いまくる 日でした。具体的には shelarcy さんに誘われて、Oleg Kiselyov 氏 と Andrew Pimlott 氏 と語る会 →→ Guy Steele 氏と鍋をつつく会、のコンボ。 Oleg (SXMLの人でMetaOCamlの人でZipperFSの人でetc.etc.)もGuy(CommonLisp本の人でSchemeの 人でJavaの人でetc.etc.)も自分から見れば雲の遙か上の人で。このような機会をくれた方々に 本当に本当に感謝です。
Olegさん達とは、FLOPSで発表されてた Soutei というシステムの話。
なぜだか最後の方はひたすら
cut-sea
さんマシンのGaucheでUnificationとSLD Resolutionを実装するぞ大会に。
時間が無くて append(?x,'(4,5,6),'(1,2,3,4,5,6)). が無限ループするバグが
とれてなかったんですけど、後ろで見てても問題がどこにあるのかわかりませんでした…不覚。
昼食中にcut-seaさんが「Scheme と Haskell を比較してみるとどうですか？」という質問を
していらして、型安全性云々とか遅延評価のいいところと悪いところ（…なかなか評価され
ない値がthunkの形でメモリに残ってしかも結局評価してみれば消えるreferenceがthunkに
残ってるとGCにも良くなくて大変…）とか、そこで正格性解析とか、でもそういうメモリの
問題が大問題なことは認識されているからghc周りにはメモリ使用状況を解析する強力な
プロファイラが作られててとか、schemeのdefine-macro=camlp4 で
schemeのdefine-syntax=MetaOCaml みたいなもので両方使うとOCamlのマクロもいい感じとか。
他にも色々…あああ全部は思い出せない…。あ、Soutei（アクセス権管理システム的なもの）の
つながりで E言語 によく言及されてました。
調べねば。
しかしとりあえず、 Xanadu （有名
らしいけど知らなかった…）について話すときに引くだけならまだしも 「サイゼリアって、
lainに出てくるサイベリアに似てるね」 とか言い出すOlegさんは相当に
lain
好きの強者だと思た。
そしてそのメンバー全員で "Guy(GLS)としゃべろう会" (mixi) へ合流。Guy本人の発案で、自己紹介では「自分の一番好きな言語とその理由を一言で語る」 ことになったのですけど、そのご本人の好きな言語は（…ご自身の設計した言語は 除いた上でだと思いますけど…）「その一貫した言語デザインの美しさ」という理由で APL ということでした。 おお。
ちなみに自分はJavaScriptですと答えて横にいた向井さんに驚かれたりしつつ、「Script言語をあげたのは君が最初なので逆に質問、 RubyやPythonについてはどう思う？」と逆に訊いてもらえたのにまともに答えられなくて もったいなかったー！うぎゃー！！なんてことだ。実は Ruby も Python も ほっとんど使えない自分が大問題だとこれほど思ったのは今日が初めてです。 ちなみに他にあがった好きな言語はCommonLispとSchemeとHaskellとCleanで、こう、 あの、"Lisp in C's clothing" って言えばよかった…(違。 いや、もう、とにかく楽しかったです。わーい。
大学であった Guy Steele 氏の講演を聴いてきました。お題は、Sun で今研究開発中の "Fortress" という新しい言語に ついて。キャッチフレーズは "To Do for Fortran What Java Did for C" だそうで、 基本は、大規模な科学技術計算・並列計算のための（つまり、Fortranがこれまで担ってきた 作業をするための）言語です。ただ、それを実現する枠組みはもっとgeneralな何かになって いるよ、と。
並列計算特有の話はほとんどなくて、「言語設計のやり方」 的な内容をお話しされていて、 まさにそれが聴きたかったのでとても面白かったです。以下雑メモ。
この問題提起に対する答えは当然
ライブラリでやる、というアプローチに対する批判も当然ご想像の通りのがあるわけで
プロジェクト的に一つの年限が2010年らしく、まあ2010年を待っててくれよ的スタンス。
私(k.inaba)は、この徹底してライブラリでやるというスタイルがとても好きなのですが、 同時にそのスタイルを批判している言語をメインで使っている人でもあって、なかなか考えさせられます。 リンク先の批判の 「5: 結局"標準"ライブラリとなってしまえばエンドユーザにとって 柔軟性は何も変わらない」 については同じ懸案事項ではあるようで、「Fortressで はMonolithicな標準ライブラリは持たずに、常にライブラリの各部分をいろんな実装に 取っかえひっかえすることをむしろ推奨すらする」いう方針を明確にしていました。 「1,3,4,6 ... 効率や使い勝手を真に組み込みの機能に並べることは難しい」という点は、 「それを実現するのだ」というのがまさにFortressのチャレンジングなところであって、 「それが実現できる」という言葉に期待ですね。「2: ライブラリで実装した機能を間違って 使ったときに、コンパイラ組み込みの実装並のわかりやすいエラーメッセージが出せますか？」 というのが一番面白い問いだと思うけれど、どうなんだろう。閑話休題。
他に、ライブラリで実現された機能って言語組み込みの機能より読みにくいし 使いにくいよね、的な話もありまして。
x.multiply(y) って、もうやってられませんよね。x*y と書く必要すらない。
x y です。Generalized Overloading ｷﾀｺﾚ!! …っていうか、並置の意味の オーバーロードはマジメな話本気でやりたいのでこれは個人的には嬉しい方向。
「スタンダードな数式っぽい書き方というと単に記号の問題だけでなくて、例えば
0 < x < 1 みたいな表記の問題もあると思うけど、そういうのは
どうするんでしょう？」 って質問したら 「その書き方は既にFortressでサポートされてます」
って返されました。うへ。そういうのは演算子オーバーロードの枠組みは越えるけれど、
数式の書き方としてよく使われているものだし、これは個別にサポート、とのこと。
他に、内包表記 {f(x,y) | x←S, y←A, x≠y} なんかも、それが数式としてスタンダードな
表記なのでこれはこれで対応。A^2と書くと行列Aの2乗だけれど、A^Tと書くと行列Aの転置に
なるようになっていたりする、と。（最後の例は識別子Tに特別な意味を持たせれば普通に
演算子オーバーロードの範囲内だと思うけど、そういうのは嫌ったのかな…？）
他の人からの質問で、「我々にはこの10本の指しかないわけですが(^^;、それでASCIIの範囲で プログラムは書けてもUnicodeをフルに使ってプログラム組むのは、それは本当に生産性 あがるのでしょうか？」 というのもありました。「一度その記号を打ったらあとはコピペ」 で割と困らないよ、というのが回答の一つ、あとはスタンダードに、「代替記法」を用意。 α でも alpha でも同じ意味になるようにする。各種括弧については、ASCIIで書けるような 記法を用意しておく、etc。打ち込むのはASCIIな方で、開発環境がpretty printしてくれる とか…Wikiっぽいイメージ？とかそんなこんな。
プログラミング言語ではないけど、MathML がUnicodeで記号を入れることを許す
言語なんですが、自分の経験ではあれは割とややこしい気がしていました。
ギリシャ文字のΣと数学記号の∑(∑)は素敵なことに別の文字で、
（実装によるのかもしれないんですが）後者は総和演算子扱いされて添え字が∑の真上と
真下につくんですが、うっかりそのつもりでギリシャ文字のΣを使うと悲惨なことに
なっちゃったり。"代替文字"をちゃんとunifyしてくれれば無事なんでしょうが、さてさて。
それでなんだっけ、一晩寝たらほとんど忘れたよ。 「コンパイラは簡潔に、アプリケーションコードも簡潔に、全てのノウハウ的なものは ライブラリ部分に突っ込む」のだという話でした。 他にはFortress言語自体のもうちょい詳しい話。
並列計算の扱い方はどんな風になるのか。
for i←1:m, j←1:n do a[i,j] := b[i] c[j] end
for i←seq(1:m), j←seq(1:n) do a[i,j] := b[i] c[j] end
seqのようなものは、各iterationが始まる前に直前のiterationが完了していることを ちゃんと保証しておかないといけないわけだけど？という質問があって、そう、そういう ことをライブラリでseq関数としてきちんと全部記述してやるのだ、という回答、だったと 思う（ちゃんと聞き取れてなかったかも）。
並列処理というと同期とかロック処理とかの話は…
そんなところで。
あー思い出した。昨日の続き。
S -> X | Y X -> "a" X "b" | "1" Y -> "a" Y "bb" | "2"
がなんで嫌だったかというと、S の下を構文解析しようと思ったときに、X を調べればいいのか Y を調べればいいのか、その場ではわからないから。こういう感じにどっちに行けばいいか わからない X と Y みたいなのがあるときに、こいつらをとりあえず一纏めにした記号 Z (XかY) と、X? (Xだったんですけど？) と X! (Xだったんですか！) と Y? (Yだったんですけど？) と Y! (Yだったんですか！) を導入して書き換えてやる。
S -> Z X! | Z Y! // 右辺の X は Z X! に、Y は Z Y! に全部置換。
Z -> "a" Z X! "b" X? | "1" X? // Xの定義とYの定義は全部 | でZの定義として
| "a" Z Y! "bb" Y? | "2" Y? // 繋げてしまう。ただし、後ろにX?とY?をくっつける。
この文法なら、以下のような雰囲気でトップダウンに解析ができますバンザイ。
function S()
{
Z();
switch( getc() ) {
case 'X!': break;
case 'Y!': break;
default: assert( false );
}
}
function Z()
{
switch( getc() ) {
case '1':
ungetc('X!');
break;
case '2':
ungetc('Y!');
break;
case 'a':
Z();
switch( getc() ) {
case 'X!': assert( getc()=='b' ); ungetc('X!'); break;
case 'Y!': assert( getc()=='b' ); assert( getc()=='b' ); ungetc('Y!'); break;
default: assert( false );
}
break;
default:
assert( false );
}
}
X? のところでは ungetc('X!') してやるのがポイントで、X?の直後にはX!が来ないとダメと いう条件を表現してやるわけです。もちろん本物のungetcにX!なんていう謎の記号は戻せません ので、そこは実際にparserを書くときには自前のungetバッファを用意してやることになるの ですが、まあたいした手間じゃない。
そして書きながら思ったんですけど、X? は直後に必ず X! で喰われるわけで、 実装上は、X|Yを同時にparseしながら実際にどっちとしてparseできたかを返すような 関数で実装してやれば十分ですかね。
function S()
{
switch( XorY() ) {
case 'X': break;
case 'Y': break;
default: assert( false );
}
}
function XorY()
{
switch( getc() ) {
case '1': return 'X';
case '2': return 'Y';
case 'a':
switch( XorY() ) {
case 'X': assert( getc()=='b' ); return 'X';
case 'Y': assert( getc()=='b' ); assert( getc()=='b' ); return 'Y';
default: assert( false );
}
default: assert( false );
}
}
なんだかだいぶ当たり前に見えてきたけど、あの手の文法をバックトラックなし 任意先読みなしでトップダウンに解析してやろうという発想はなかったのでこれは やっぱり面白いと思う。
Martika をヘビーローテ中です。 『Toy Soldiers』 を聴いて即買いしたわけなのですが、他にも 『See If I Care』 なんかも 割といい。
DIKU-IST に行ってました。
面白かったのが Pair-Matching Grammar という話で、LL 構文解析はトップダウンに再帰で 書けて楽でいいのだが LR と比べて表現力に劣る。でも LR 系の解析は手書きはとても 大変だし機械的に実装するのもLALRより上になるとなかなかしんどいしで困る。ということで、 Pair-Matching Grammar というのを導入して、「LL(k)のようにトップダウンの楽な構文解析が 可能で、表現力はLR(k)と同等なもの」を目指しているというお話。 証明はこれからだけど 「PMLL(k) = LR(k)」 だといいなあ、らしい。
で、どんな有限のkをとっても LL(k) に入らないけど LR(0) な言語として
S -> X | Y X -> "a" X "b" | "1" Y -> "a" Y "bb" | "2"
という例を挙げて Pair-Matching Grammar に変換して云々…という流れでほほーと 思ったはずなんですけど、今自分でやろうとしたらやり方思い出せない…。あれ？ なんかこんな感じに
S -> X X! | Y Y! X -> "a" X X! "b" X? | "1" X? Y -> "a" Y Y! "bb" Y? | "2" Y?
X? と X! のような対となる幽霊記号を導入して、最終的な生成結果には *? *!
の形に並ぶ物だけを許すようにして、そのペアを対消滅させた残りを文法が生成する言語と
定義するのが Pair-Matching Grammar で、普通の文脈自由文法の必要なところにこのペアを
入れてやってからちょいと式変形して見直すとトップダウンで行けそうな感じになってる、
という流れだったはずなんだけど。むむむのむ。忘れた。
f(x) = s*(a+1) … ceil(a)が奇数のとき
-s*(a-1) … ceil(a)が偶数のとき
where s = +1 (if x>0), 0 (if x=0), -1 (if x<0)
a = |x|
解は機械的に何個でもつくれるけど（↑例えばこれ）、美しいのが全然思いつかない。むぅ。
PHP6の話。 「ラベル付きbreak文」として拡張。ifやforなどの「外に」抜けるジャンプ、しかも 「下に」抜けるジャンプのみに制限して導入することを考えている…らしい。 PHPの中の人もDijkstra以来のgotoに関する議論は百も承知しているだろうから、 ここであえて新しく入れるということは、よほどこの機能がないと書くのがしんどいと 感じる実例が見つかったのかなぁ、と思うのですが。気になる。 開発者MLのログでも漁ってみればよいのだろうか。
唐突にまわしてみました。参考文献。
import std.cstream;
import lazy;
class tarai {
Lazy!(int) x, y, z; // 引数
Lazy!(int) run() { // 処理内容
if( x <= y )
return y;
else
return tarai(tarai(x-1,y,z),
tarai(y-1,z,x),
tarai(z-1,x,y));
}
mixin LazyFun!(x,y,z); // おまじない
}
void main() {
dout.writefln( tarai(768,340,0) );
}関数のbodyには一切手を加えないという方針はなんとか死守。 でもあんまり綺麗にできませんでした。 マクロのある言語でやればよかったと今は反省している。
> dmd -O -release -inline tarai lazy > time tarai 768 0.00user 0.01system 0:00.95elapsed
経験上、こういうことをやると時間の半分はGCが食ってるので、 超絶いい加減アロケータで手抜きしてみる。
> dmd -O -release -inline tarai lazy -version=Hansoku > time tarai 768 0.01user 0.00system 0:00.11elapsed
しかし流石に
> ghc -O3 tarai.hs > time main 768 0.01user 0.00system 0:00.04elapsed
GHC速ぇ。一部まじめに遅延してない分と、正格性解析してない分と、 あと何の差だろう。
中身まで変えてしまうと、例えば、まず元の定義の末尾再帰をループに変換。
int tarai(int x, int y, int z)
{
for(;;) {
if( x<=y )
return y;
int px=x, py=y;
x = tarai(px-1,py,z);
y = tarai(py-1,z,px);
z = tarai(z-1,px,py); // ←
}
}
(x<=y) が成立していて次の周で return できるような場合、
「←」の箇所で z を計算するのは無駄。なので、「←」の直前にも
if～return を入れてやることにする。そうすると、元々のif～returnは
ループの外に出せる。
int tarai(int x, int y, int z)
{
if( x<=y )
return y;
for(;;) {
int px=x, py=y;
x = tarai(px-1,py,z);
y = tarai(py-1,z,px);
if( x<=y )
return y;
z = tarai(z-1,px,py); // ←
}
}
これでもうGHCで定義通りに書いた版よりは速くなってしまうので面白くないかもしれず。
だけれど何も変わらない気分。
MetaOCaml等 については この頃 の自分が 「型宣言を生成できない」のと「型情報を使った分岐ができない」のが困ったなー、 などと言っていました。今考えると後者はマルチステージなこととあまり関係なくて、 何かしらのad-hoc多相が入れば十分ですね。前者も、多相型の範囲でできる機能で だいたいの場合は足りてるのかな。
"人間～～" はもちろん Revenge of the Nerds の後ろから２個目の段落のもじりですが、今現在 "人間～" で Gg ってもネタ元を差し置いて ここがトップに来るようになってしまいました。これはいかん。
3-Lisp というのは知りませんでした！