22:12 08/03/23
観光
もっと早くから連休に気づいてたら遠出したんだけどなー、と思いながら
ブルーマウンテンズ
に行ってきました。
シドニーの街から電車で西に２時間くらい。
東京で言うと 青山 高尾山みたいな感覚です、たぶん。
ここんとこ雨続きだったので山道がデロデロで難儀しましたが、 そのデロデロの土が赤茶くなくて白っぽいというか灰色っぽいのがなんだか新鮮な風景でした。
Twitter: @kinaba
0.30 リリース しました。 具体的には、ヘッダの格納ファイル数フィールドに実際より大きい値が入ってると変なとこ読もうとして落ちるバグ修正。 GreenPad の修正は来週くらいには…。
Boost 1.35.0 来てました。 Asio と Fusion と GIL の三枚看板がでかいですが、Bimap が地味に便利だ。
あと、mbさんのEgg のレビューが明日からでしょうか。（また スケジュール から消えてますが…Protoが入る前までロールバックしてる？） 他人事ながらドキドキ。
十年来の疑問なんですが、"case" に単独で対応する日本語ってなんになるんですかね。 "case-insensitive" や "lowercase" の "case"。単に "case-insensitive" だけなら「大文字小文字を区別しない」 みたいに訳せばいいんですけど、"You must use the same case as it was declared." とかそんなんだと、 文全体の構造をグローバルに書き換えるしか思いつかなくて。
「百万ゴールドの男」を読んで面白いと思った人は、 過去作品 一気読みに走るといいよ！ 「創作テキストサイト過去ログ」あたり！ …などと信者の俺が述べております。
The road coloring problem を読んでました。 問題自体知らなかったのですけど、abstract にオートマトンと書いてあったので、ついふらふらと。
この記事 の説明はちょっと変だな。スタート地点がどこであっても「青赤赤青赤赤青赤赤」のぴったり９歩 動くと必ず黄色の地点にいる、というのがこの色分けのポイント。 今どこにいるのか、どこで止まればいいのかすらわからなくても目的地に到着できるのです。 記事にあるような「目的地をいつかは通りがかるような色の列」なら40マイクロ秒くらいで 解かれてると思う。
論文に乗ってた具体的な構成法は、(1) "Spanning Subgraph" を適当に１個作る。 Spanning Subgraph とは、"元のグラフの頂点を全部含む" && "それぞれの頂点について、 それを始点とする辺を１個だけ含む" グラフ。Spanning Subgraph は必ず、「ループとループにぶら下がったツリー」 が何個か並んだ形をしていることに注意。 (2) 作った Spanning Subgraph の「ぶら下がったツリー」部分の高さに注目。 一番高いツリーが１個だけだったらOK、3に進む。同じ高さのツリーが２個以上あったら、 この問題の前提とするグラフでは、どっちかのツリーを変形して「もっと高く」できるのでそうする。 (3) そうしてできた Spanning Subgraph に属する辺を全て同じ色（例えば 赤）で塗る。 残りの辺は他の色で適当に塗る。
…という感じ。これが求める色塗りになってることの証明は背理法なので、 具体的にどう色をたどれば一カ所に集合できるのかは、証明からは直接読み切れてないですが、 直感的には、「赤をたどりまくってループの上に合流して、時々別の色で別のツリーにジャンプ」 を何回か繰り返したら一カ所に集まる感じかな？
"The solution is not that complicated. It's hard, but it is not that complicated," Trahtman said in heavily accented Hebrew. "Some people think they need to be complicated. I think they need to be nice and simple."
After 38 Years, Israeli Solves Math Code
当然 トーハム・セリ・サロス・アンダース なんですけど相変わらず４人パーティきついな…。
もっと早くから連休に気づいてたら遠出したんだけどなー、と思いながら
ブルーマウンテンズ
に行ってきました。
シドニーの街から電車で西に２時間くらい。
東京で言うと 青山 高尾山みたいな感覚です、たぶん。
ここんとこ雨続きだったので山道がデロデロで難儀しましたが、 そのデロデロの土が赤茶くなくて白っぽいというか灰色っぽいのがなんだか新鮮な風景でした。
| 言語名 | Lang | Lib |
|---|---|---|
| Smalltalk | 49 | 255 |
| Scheme | 50 | - |
| Clean | 128 | - |
| Standard ML | 128 | - |
| Haskell | 177 | 100 |
| ECMAScript | 188 | - |
| Eiffel | 194 | - |
| C | 316 | 238 |
| C++ | 428 | 358 |
| Ada | 461 | 330 |
| C# | 553 | - |
| Fortran | 585 | - |
| Java | 684 | - |
| Common Lisp | 1358 | - |
PDFのページ数で数えました。 Smalltalk と CommonLisp は正式な規格書を持っていないのでドラフトで数えています。 仕様でライブラリまで定義されている場合、その部分のページ数を「Lib」、 残りを「Lang」と分けています。 Common Lisp と ECMAScript 辺りは、他の言語でなら「ライブラリ」と呼ばれそうな機能まで 「Lang」に入ってるような感じがして微妙ですが、その他の「Lib」のない言語については、 上記の仕様では文字通りライブラリが定義されていない感じです。
もちろんページ数なんてものはレイアウトにも、どのくらい詳細に書くかにも、 どんな表記法を用いるかにも思いっきり依存するわけなので、この表が何か直ちに 意味を持つと言うことはありません。 が、自分の実感にはわりと合っているような気がしたので、その。
つまり、C++ の言語仕様は、 （Java とか C# とかと比べたら）だいぶ個人の手に負える範囲 にあるのではないかと思ったのでした （コンパイラ を 作る 時 的な意味 で）。今コンパイラ間のポータビリティが怪しいのは、仕様が
などの理由でアレなせいで、これは別に実装にマンパワーがいるとか凄いアルゴリズムが 必須とか言う類の難しさではないですし… あ、export は見なかったことに… まさか C++0xに残る とは。 でも実際、「分割コンパイルはサポートしない」くらいの制限で現実的な目標にならないかな。
まあ、俺はここでgdgd言ってないで作ってみればいいんだよねぇ。ううむ。
なんか今日から 四連休 らしい ということを昨日知りました。どっか出かけようかと思ったらいきなり天気が最悪。
とりあえずロードカオスが鬼だった。
C++の勉強ですが っていう話題。
私はいつも 「Exceptional C++ は全プログラマ（C++を一切使わない人でも）が読むべき本。 あとはどうでもいい」 などと言ってますが、どうなんでしょうね。 cf. ”技術者”の解放
「C++ 再考」は面白そうなんだけど、噂のほしい物リストに積んだまま全然読んでないや。「Effective C++」の第２版は…17年前なら違ったのだろうけれど、 正直、今では "読むべきでない" 部分すらいくつかあるように思ってしまう。例えば 「コンストラクタでの例外は禁じ手」 なんていう迷信の遠因は Effective C++ の「デストラクタでポインタメンバにdelete を使うのを 忘れないようにしよう」じゃなかろうか、など。 第３版はしっかり改訂されているので （違いをまとめてる方がいらした）、 読むなら絶対に第３版です。ただ、Exceptional C++ 読めば既にほとんどカバーできてるんじゃないかなーとか。
自分がC++を最初に勉強したのは… 「Visual C++ 4.0 のアカデミック版についてきたC++の解説冊子」 だなぁ。同じ頃 Windows プログラミング始めた人には同じ境遇の人がいたりするかも。 こういうの最近の Visual Stduio には無いよね。ちょっと残念。
なんと…。自分がはじめて読んだハードSFはクラークの作品だったように思う。 ついでによく考えたら、一番最近読んだSFも「イルカの島」だ。 確か「2010年」だったと思うけど、高度に発達した生命がどのような形に"進化"しうるかの描写、 And now, out among the stars... 以下の数段落はずっと記憶に残っています。凍てついた光の格子の中で。
MegaTokyo にハマっている今日この頃です。
なんか英語でマンガ読むぞーと思ってコミック買ってみたのだけど、これウェブマンガだったのか。 でも作者コメントが面白いので買って良かった。 62 の辺りで４コママンガがギャグばかりだと思うなよ的論争があったらしく、 そこから今の方向にじわじわスイッチしていく流れとかが。 要するに大変ベタベタなラブコメなんだけど、まあそういうのは好きなので仕方ない。 といってもまだ２巻までしか読んでないのでこの先どうなるのかな。はてさて。
チュートリアル日本語版！ おおお！
SIGGRAPH に対する SBR
『採択論文が公開されると同時にスタートし、
ゴールをその実装とする人類史上初の公開論文実装レースであるッ!!!
』
みたいなのすっごい楽しそうだなーと思うのですよ。
プログラミング言語系でも同じようなイベントは可能だろうか。…てなことを
という過程をたどった結果考えました。 あまりに理論的だったり、大規模な実装や事例紹介的な研究は対象とするのが難しいと思う。 OOPSLAとその併設イベント、とか、ICFPとその併設イベント、とかで結構何とかなったりしないかな。 しかしそれ以前に、 自分が実装したいと思うのは大抵プログラミング言語系というよりデータ構造／アルゴリズム系の話な気がする。 「Haskellを新しい型システムで拡張しました！」とか実装する気にならないし。うーむむむ。
DWT 使いたいんだけど Tango とか D 1.x とか使う気にならない人の数→ (1)
すごいダメダメな完成度ですが一応晒しておきます。
えーとあれです、要するに var x = mouseX + mouseY って書くとマウスの動きに合わせて勝手に x の値が変化する感じの言語です。document.createTextNode("ねずみ ＠ "+mouseX+","+mouseY") とか書くと勝手に値が変わるテキストノードができます。 この方向性でちゃんとした言語としては FrTime や Flapjax などなど。 追記： Mathematicaすげー！
再計算する範囲を最小限にする実装のなかで一番単純なもの（一つ一つの演算子単位でバラバラに 値を変えられるようなノードにしてそれを繋ぐ実装）から始めて定数畳み込み＋α的に最適化しようと 思っていたんですが全然そんなとこまで行っていないのであった。これなら、上の実験ページの見た目を 再現するくらいなら普通に埋め込みテンプレート単位で再計算した方が1000倍マシだ。 実装もきっと1000倍くらい楽だし。まあ、でも
var x = 10;
var y = x + 100;
x = 20;
x = 30;
print( y );これが 130 になる言語ができたので満足です！ Functional Reactive Programming 的にこうなる物なのかどうかは知らないけど、 絶対こんな風になった方が面白くていいと思う。y は x に 100 を足したもので x は 30 なんだから、 y は 130 に決まってるではないか。 いや、わりとマジメにこれ便利だと思うのだ。
で、破壊的代入という副作用はそれでいいとして、環境の操作の方の副作用はいかんともし難くて、 何も手をつけられませんでした。今の実装だと（たぶん）
document.getElementById("hoge").appendChild( document.createTextNode(mouseX) )
って書くとマウスを動かすたびにノードが増えて行くんですけど、これは果たして正しいのだろうか、と。 この例くらいなら「hogeの末尾に、値がマウス座標に合わせて変わるテキストノードを１つだけ挿入」という 動作をさせる実装もすぐにできるんですが、もっときわどい例として
(mouseX%2 == 1
? document.getElementById("foo")
: document.getElementById("bar")).appendChild( document.createTextNode(mouseX) )
を、どうしたものか。制御フローが変わる時に影響範囲全体にundoかけるしかないのかな。 実装していざ突き当たってみるまで全然この辺考えたことなかったや。 Flapjax はこの辺りどうしてるんだろう。
あとそういえば、JavaScript パーザは Top Down Operator Precedence のを使わせてもらいました via h_sakuraiさん。 デモ用に用意されてる構文定義が色々自分の趣味に合わなかったりしたのですが、そういうときでも 確かにこれは読みやすい＆＆手で弄りやすくていいですね。
Wizard Eye が強すぎて笑えてきた。視認できない距離から遠距離魔法飛ばしてきて 二発当たると確実にパーティー全滅級のダメージとかもうね。素晴らしいですね。 おかげでPhobosの翻訳もGreenPadの修正もProject Eulerの新問題もEarley Parser実装祭も １ミリたりとも進まないのが問題ですね。
新山さんメモ で Flapjax の話が出てたのを見て、ふと、これの真似っ子実装してみようと思い立ちました。 「世の中に色々なパラダイムはあるけれど、その中で Reactive Programming だけが世界を変える可能性がある」 などと、実装したことすらないのに思っている自分は滑稽であるので一度作ってみないといけない。 てなわけで明日やる。12時間勝負。
唐突に ダンジョンマスターRTC を始めてみました。
ゲームは一度もやったことなかったんだけど 小説 は昔すごい好きだったので ヒッサー、ゴスモグ、ウーツェ、シラ のパーティでGo。 操作方法よくわからずに手探りでやってるせいもあって今のところ 戦士、松明、薬草、薬草 みたいな、 ヒッサー以外存在意義がわからん状態なんですけど、こんなもんなんだろうか。 今地下３階（２階？２回階段降りたとこ）。
この辺のvar/autoに関する議論 を読んでて。
感覚的に、変数には「オブジェクトに名前を付けるもの」として使う場面と「式に名前を付けるもの」として 使う場面があって、 要するに 箱モデル と 名札モデル ね。 ちょっと違うかな。まあいいや。 で、（言語の実行モデルがどうであるかとは関係なく、）前者の感覚で使う変数もあれば 後者の感覚で使う変数もあって、みんな、基本的には前者なら型を書くし後者なら auto/var で省ける、 というところまでは一致していると思うのだ。
違いはどっちの感覚で使う変数の割合がどのくらいか、という個人差。要するにNyaRuRuさんのおっしゃっている
"仮名漢字変換を単文節でぶつ切り変換するのが好きか，長文で一気に変換するのが好きかみたいなもので，
もはや好みの問題かなぁという気もします．"
という話で、
「なんでもvarにすると変数に込めた意図が失われる」人とそうでない人とでは、そもそも「意図」の時点で
違うっていう、ただそれだけの話なのではないかと。
で、そういう意図の持ち方は良い/悪いの議論は大いに盛り上がると楽しいと思うんだけど、
ただこれは、純粋に個人の好みの差違であって言語の差違ではないと思うのだよね。つまりどうも自分には
"C++畑の人は"
、
"C++プログラマ達にとっては"
、"C#とC++は違う言語だから"
みたいな一般化が納得いかない。確かにC++の変数は箱モデルかもしれないけれど、それは関係ない。
あれは必要ならいくらでも名札的に振る舞わせることができるし、実際、モダンなライブラリには
名札的なものが多い（と自分は感じる）。
型名を公開したら負け
みたいな作りを見ると（自分の場合は）そう思う。
おわた！
"最もタメになる「初心者用言語」はR" を読んでマジメに R 格好いい！！ と思ったりして最近 R で遊んでます。 example いいね example。しかしひととおり触ってから思うに、特に分析したいデータもないので なかなかそういうRっぽいところに慣れる機会がないな。しばらく分析したいビューで世の中を見ることにしよう。
Uniqueness Typing Simplified
の中で引用されてた説明
in linear logic, "linear" means "will not be duplicated" whereas in uniqueness typing,
"unique" means "has not been duplicated
というのがなるほどなーと思った。
今日から ^Z 才です。うわー。
LL(1) とか LALR(1) って要するに何？ っていうのを、思いっきり大ざっぱに紹介してみたいと思います。 細かい具体的な実装方法は本なりWebなり探せばいくらでも見つかると思いますので、全部省きます。
単語の列を、文法と照らし合わせて解釈する作業のことです。 プログラミング言語の場合、要するに、ソースのこっからここまでがif文で、こっからここまでが １個の関数定義で、この部分はクラス定義で、ここからここは足し算してる式で…みたいな、 ソースコードの構造を完全に判定する作業です。
プログラミング言語的には「単語」のことを「トークン」といいます。「if」とか「else」とか 「+」とか「<=」とかがトークン。
プログラミング言語の構文解析には、"directional" で "deterministic" な手法が好まれます。 "directional" というのは左から右に順番にトークンを読みながら順番に構造を判定する、ということ。 「ちょっと突然一番最後のトークンが知りたくなった」とか言ってジャンプしたりしない。 "deterministic" というのは、一度判定した構造を絶対取り消さないこと。「ここif文っぽいから とりあえずif文と思って解析続けてみてダメだったら取り消し」とか軟弱なこと言わない。 好まれるのは何でかというと、速いから。あとメモリもあんまり喰わない。
で、"directional" で "deterministic" な手法は、大きく分けて２つあります。 LL と LR です。
LL(1) 法というのは、構文のはじめの 1 トークンで構造を決定していく方法。
if
っていうトークンを見たら即「ここからif文がはじまる！」と判定する。
もう即座に new IfStatement() とか言って構文木作っちゃう。
defっていうトークンを見たら「関数定義ｷﾀｺﾚ！」と決めつけちゃう（RubyとかPythonの場合ですね）。
LL(2) 法なら、はじめの２トークンまで見て決める。LL(3) なら、はじめの３トークン。以下略。 LL(0) は、要するに１文字も見ずに「次絶対if文来るね。マジ。間違いないね」とか予言しないと いけないのでつまり絶対無理なので、LL(0) という方法はありません。
LL(k)法は、構文の開始よりkトークン先まで読んで構文を予測するので、 「k トークン予測先読み (prediction look-ahead) する」などと言います。 あんまり言わないかもしれない。
逆に、LL(1) じゃない文法も見てみよう。C言語。
foo
って先頭のトークン見ても、これから foo = 100; っていう代入文が始まるのか、
foo myfunc(); っていう関数宣言が始まるのか、はたまた
foo[1]("hello"); という配列アクセスした上に関数呼び出しという怪しげな文が
始まるのか、まったく予測できない。こういうのは LL(1) じゃない。
実際のところ、四則演算の数式の文法が LL(1) で書けるとか、はじめの１トークンで「予測できる」 「予測できない」っていうのはそのままの直感とは外れるところもあるかとは思うんですけど、 基本的には、「最初の１トークンで何の文かわかるようになってる言語/文法」はLL(1)っぽいといえる。
LR(0) 法は、構文のおわりのタイミングで 「あ今if文終わったちょっとストップ」とかいう雰囲気で構文を判定する手法。
(foo bar buz)の閉じ括弧を読んだそのタイミングで、「はいはいS式S式」って言って、「前の括弧から今の括弧までがS式でした」 と構造をひとつ決定する。
while(...) { ... }の閉じ中括弧を見た時点で、「whileｵﾜﾀ」って言って、「バランスする中括弧の手前のwhileから 今の中括弧までwhile文でした」と決める。
一応構文をおわりまで読んでから決定するので、LL系の方法よりもLR系の方法の方が、何かと 判定能力は高かったりします。が、LR(0) はやっぱりちょっと弱いので、ここでも「先読み」 が活躍します。
SLR(1) 法は、構文のおわりのさらに次の１トークンまで見て決断を下します。 LR(0) は先読みできないので例えば
if(...) { ... }ここまで読んだ時点で、「今elseなしif文終わったよ！」と宣言しちゃってよいものか、 それとも、次elseが来る可能性があるのでここはスルーして
if(...) { ... } else { ... }になるのを待ってから「これぞif文！if文完成！」と叫ぶべきなのかわからない。 ちなみに「今○○文終わったよ！」と宣言することを専門用語で「reduce」といい、 スルーして次のトークンを読み込むことを「shift」といいます。 reduce すべきか shift すべきかわからなくて困ることを「shift/reduce conflict」と言います。
って、そうだ、SLR(1) の話をしてたんだった。SLR(1) の場合は、
if(...) { ... }この時点で、その次のトークンまでチラ見してから判定します。次が例えば「while」だったら、 「else無しif文でした！」って宣言しちゃっていいし、次が「else」だったら、 「else無しif文の後ろにelseが来るとか常識的に考えてあり得ない」ので、ここはスルーして良い。 このように、チラ見した次のトークンを使って、「○○文の後ろに△△が来ることがあり得るかどうか」 を考えて判定するのが SLR(1) です。
SLR(2) なら構文の後ろの２トークンを見て判定するし、SLR(3) なら３トークンを見て判定する。 構文のおわりのタイミングで判定するので、１トークンも先を読まないで判定する LR(0) はあり得ます。 LL(0) があり得ないのと対照的です。
SLR(k) の先読みは LL(k) と先読むところが違って、構文のおわったその後のトークンを読んで、 reduceするかしないか決めるものです。なので違う名前もついていて、 「還元先読み reduction look-ahead」などと言う。
LALR(1) は、SLR(1) をちょっと賢くした感じ。 同じ○○文でも、「後ろに来ることがあり得るトークン」は、場所によって違うのですよ。
struct foo { int x; ★
void foo() { int x; ☆こんな感じで、同じ変数宣言 "int x;" の構文でも、構造体の中でやったときと、 関数の中でやった時では、後ろに来れるトークンは違う。例えば "for" は☆には来れるけど ★には来れない。まあこれはあんまりいい例ではないですが（実際のCの変数宣言の文法は そもそも構造体内と関数内で完全に別物ですし）、まあそんな感じで、とにかく 「後ろに来ることがあり得るトークン」は場所によって違う。
というわけで、「○○文の後ろに△△が来ることは一見ありえるのでここはreduceすべき かもしれないが、今まで読んだトークン列をみる限りこの○○文は□□文の中の○○文なので その場合は△△は絶対後ろに続かないから正解はスルーだ。shiftだ。」みたいに 大変インテリジェントなのがLALR(1)です。
たぶん間違いだらけなので突っ込み期待しています！
x = (foo)*bar とかですね。てことで動画upされてるみたいです。わーい。 itouh2さんの発表を中継で見られなかったので今からチェックせねば。 みんな見るべし見るべし。私の部分40秒くらいしか撮れてなかったみたいなので、 前半の様子を知りたい人は各自妄想で補完すべし。
手書きでパーサ書くなら文法をLL(1)にして再帰下降、というのが一般的だと思うのですけど、 LR(0) や SLR(1) も適当でよければ手書きできて、結構それなりにわかりやすかったり 使いやすかったりするのではないかという気が昨日からしています。適当というのは reduce判定をオートマトンでやるのではなくて毎回スタックを覗く感じの実装で。
どうなんだろう。適当に検索したら comp.compilersの記事 がなんか出た。
でした。 なにもたいしたことしゃべってないけど一応 プレゼン資料 です。 遠隔プレゼンは思ったよりだいぶ大変だった…。 企画たてて下さったberoさん、楽しい発表を聴かせてくださった発表者のみなさま、 集まって盛り上がったDゲンガーのみなさま、 そして録画配信スペシャリストのcojiさん、 感謝感謝であります。
で、終わってから Haskell Hackathon にひっそり参加。こんな感じになりました。結局Dでトライ。
遅延評価とパターンマッチの実装に目標を絞って行きました。 型とかインデントとかIOとかは考えない。たらい回し関数が速くて 無限リスト[0,1,2,...]が作れてifを関数で実装できたので、まあいいんじゃないでしょうか。 IO は shinh さんが FizzBuzz 言ってたのを見てそうか FizzBuzz しなきゃと思って print と >>= だけ足してみた。 翌日追記：どうみても >> です修正。
