Twitter: @kinaba
あらためて読み返してみると今年全然日記書いてないなー。
・わなD書いた。D 1.0って今年だったのか…。 なんかこんなの書くよりもちゃんとした規模のアプリ一本書く方がハタから見てて面白いよなーとか 思うんですけど、全然やる気がないのが問題。 ・PLAN-X'07行って発表。 ・アスカなんですけど今見たら回数4000回近くなってたので カンストの後何時間やってるんだ俺は。今年は冥炎と銀猫とカカルーと一致と盾なし白蛇クリアして万歩に挫折中です。 ・COBOL覚えた。 ・"扉の外Ⅱ" 読んだ。ⅠとⅢはそこそこだけど これはかなり自分内ヒット。ゲームを段階的に多重に重ねてく辺り巧い。 ・Boost本改訂してたのって今年だったのか…。 ・食人賞に "Sweet Days" っていうのが本当凄いなあと感心したり。 ・J覚えた。 覚えたんだけどこれでゴルフ以外のコード書ける気がまだ全然してこないので困る。 ・"檸檬" はじめて読んだ直後に "電子レンジで温めたらバナナが爆発した" 読んだのでなんか凄いツボに入ったりしました。 ・PEG会のネタはまだ色々その先考えてるんですけどなかなかまとまらない…。 ・オーストラリア１ヶ月行った。来年あと８ヶ月くらい行くはず。 １ヶ月もいれば英語に慣れるさと思ってたけど、 むしろ言葉聞き取れなくてもどうにかすることに慣れることがわかりました。
てな感じで。皆様よいお年を！
今回は Coq → PLAN-X → POPL に参加してきます。
Coq のチュートリアルは、最近本当に "to write my next paper in Coq" したい 気分になってきているので、真面目に実際的な使い方を目に焼き付けにいきたいという目論見。 ただし発表資料作ってて聴いてる暇が無いおそれがあります。 PLAN-X はMTTトップバッターよろしくお願いします！！っと。 POPLは、ほとんどタイトルしか見てないですけど個人的に初日の最終セッションの 発表３つが非常に面白そうに見える。 他に「これ面白いよー」とかおすすめあったら皆様教えてくださいませませ。
某駅伝に間に合うようにさっき帰ってきました。
早くちゃんとしたビザが欲しいでござるよ。
とりあえず NICTA→シティ→ハーバーブリッジ→家。 途中雨降りだしたのでバスで帰ろうと思ったら晴れたので再開したりとか色々適当でした。 東京23区はだいぶ歩き尽くした感があったので、新マップ追加！みたいな気分です。 今後の課題としては、東岸のビーチを端から端まで全部巡る、mameに倣って電車の路線沿いに進むなど のルートを開拓したいと考える次第でありますよ。
kzkさんの記事 で知った "What Every Programmer Should Know About Memory" を、ここしばらくジワジワと読み進めています。今NUMAのところ。これはヤバい面白い。 こう下から上まできっちり語れる人は本当に凄いよなあと思う。
[PDF] Dissection を実装しようとしてたんですけど dmd がバグだらけで挫折しました。 途中の産物として、新しくも何ともないですが、コンテナっぽいクラスを定義して渡すと 適当にイテレータを生成する Generic Iterator。
import genite, std.stdio;
class List(T) { T car; List cdr; }
void main() {
alias Constructor!(List!(char)) Cons; // ※疑似コンストラクタを定義してるだけで本題とは無関係
List!(char) lst = Cons('x', Cons('y', Cons('z', null)));
for(auto it = iterator(lst); it.next;)
write( it.get );
writeln();
}
Listに使えばListのイテレータになり…（表示は xyz）
import genite, std.stdio;
class Tree(T) { Tree l; T c; Tree r; }
void main() {
alias Constructor!(Tree!(string)) Node;
Tree!(string) t = Node(Node(null,"Hello",null), "World", Node(null,"!!!",null));
for(auto it = iterator(t); it.next;)
write( it.get );
writeln();
}
Treeに使えばTreeのイテレータになり…（表示は HelloWorld!!!）、というもの。 ソース: genite.d。 まあ単純にクラスのフィールドを再帰的に辿ってってるだけなので、 列挙順は宣言順に引きずられるし、一つのクラスで再帰定義されてるデータ構造じゃないと 全然使えないのですが。配列等使ってデータ格納されててもダメです。 マジメに実装すれば順番はともかくデータ定義の仕方はもっと柔軟にはできます。 が、そんなことはDissectionしたかった自分にはどうでもよかった。
ちょっと面白いかなと思うのが
import genite, std.stdio;
class FList(T) { T car; FList cdr; int flag_used_for_impl = 0xcdcdcdcd; }
void main() {
alias Constructor!(FList!(int),2) Cons;
FList!(int) lst = Cons(123, Cons(-456, null));
for(auto it = iterator(lst); it.next;)
write( it.get );
writeln();
}
List!(int) を再帰的に辿るときに、なにか実装詳細でたまたま使ってるint型があったりしても、 それは返さないようになっているところ。（表示は 123-456 になる。） テンプレート引数の T 型で宣言されていたフィールドだけを列挙します。
こういうの（特に最後の例など）が例えば、「型」の持つパワーだと思うのですよ。
型のある言語は好かないという人に見えている「型」は、プログラムにはめる足枷でしかないのだろうと思う。
けれども、自分に見える「型」は、いわば一つのメタデータであり、WebにおけるRSSだ。
つまり別に無くても困らない違った間違えた。いや無くてもプログラムは書けるという意味で
困らないのは確かなのだけれども、それがあることで、それを足がかりに構築できる遙かに広い世界がある。
そしてその世界に足を進めるのはとても楽しい。
But if there is a message for programmers and programming language designers, it is this: the miserablist position that types exist only to police errors is thankfully no longer sustainable, once we start writing programs like this. By permitting calculations of types and from types, we discover what programs we can have, just for the price of structuring our data. What joy!
Conor McBride, "Clowns to the Left of me, Jokers to the Right" より
Dのニュースグループで 最近日本でD言語ってどうなのよ っていう話題が出てたので、誰か最近どうなのか知ってる人は何か書き込むといいと思うよ！
この辺の会話 を見てて。一般的にMapと言ったら水島さんのおっしゃるとおり「とにかくキー -> 値を対応付けられる何か」 だと思います異論なしです。が、"C++のmap" に関してだけ言えば、実装を規定しているわけじゃないですが、 計算量までは規格で定められています (23.1.2 Table 69)。 find, insert, erase は対数時間以内で…などなど。 あとイテレータがソートされた順序で要素を返すことも保証されてるので、 事実上バランス木を使うしか実装方法がない感じだったり。
twitterの会話を見ててといえば、 いいかげんな発言 って具体的にどういうのだろうとか訊くと平気で7年前の日記とかを示されて悶死しそうで怖いからやめた。
悶死といえば、書き物部屋 をがさっと更新して、 手元のPCに残ってた発表スライドを全部まとめて置いておきました。 正直、発表スライドなどというものは全てその場しのぎで作っているので 7日前のものですら見返すと恥ずかしくて逃げたくなりますので、何か訊かれても知らないよ 無責任放置ということでお願いします。 Purely Functional Data Structures のとPEGのくらいしかこの世に存在する価値のあるスライドが 無いような気がしますけども。
Amazonのギフト券をGreenPadのユーザーの方からいただいてしまった。あわわわわわ。 ありがとうございます。大切に使います。 多分 Parsing Techniques に化けます。 それはそうとシドニーの紀伊国屋は全然 狼と香辛料6 を入荷しないことを深く反省すべきだと思います。
アパート契約しましたよ。 場所はここです。 ちなみに誰も聞いてないと思いますが物件はこれです。 皆様お近くにお越しの際は冷やかしに来てみるといいんじゃないかと思います。 最初部屋探しのサイト見たときには「この豪邸が月600ドルか！安！！！」などと思いながら眺めてたのですが、 あとで家賃は週当たり表示だということに気づいてしょんぼりしたり色々。
Post's Correspondence Problem (PCP) という決定不能問題を教えてもらいました。これは面白い。 Grammar等の決定不能性の証明の帰着先としてよく使われるらしい。
のーみそコネコネ としたい。
peg.zip ちょっと更新。 おかげさまでちゃんと無限の候補を全部混ぜていけるようになりました。
そうなるとmatch判定ルーチン側がすぐスタック溢れで落ちるのが悔しいので、 今の「文法定義から、Rubyの関数群へのコンパイラ」をやめて 「再帰しないで手動でスタック操作する文法定義インタプリタ」 を実装。そしたら倍くらい遅くなったので 「文法定義から、手動でスタック操作するRuby関数へのコンパイラ」 にすることに。普通にジャンプテーブルにするしか思いつかなかったのですが もっと元の文法の形保てるかなあ…。
irb(main):001:0> puts Pegexp.new("A<-aB/a \n B<-bA/b")
def match_ce(s, ce, i)
memo = {}
stk = []
goto = -1
while true
case goto
when 4 #--- A <- ["aB", "a"] ----------------------------
if s[i]!="a" then goto=6 else i=i.succ
if memo.key?(k=(i<<7)+66)
(i=memo[k]) ? (goto=1) : (goto=6)
else
stk.push [k, i, 1, 6]
goto = 5
end end
when 6
i = stk[-1][1]
if s[i]!="a" then goto=0 else i=i.succ
goto = 1
end
when 5 #--- B <- ["bA", "b"] ----------------------------
略
#--- 0:fail, 1;success, 2:allfail, 3:allsuccess
when 0; k,_,_,goto = stk.pop; memo[k] = nil
when 1; k,_,goto = stk.pop; memo[k] = i
when 2; return nil
when 3; return i
else; i,goto = ce.call(stk,s,i,goto)
end
end
end
これだけもろに goto してると YASM で直接ジャンプ命令を生成したくなるのですが、stk.pop して goto している部分は結局 case文で分岐しないといけなくて（RubyVMにはgccのgoto &&的な命令がないので）その辺だるい。 ちゅーことで、最適化器に手を入れて [putobject n→setlocal v→jump L (→[L: getlocal v→dup→opt_case_dispatch tbl])] を [putobject n→dup→setlocal v→jump tbl[n]] に書き換えるという誰の役にも立たなそうな最適化を入れたりして遊んでいました。 そしたら本当に誰の役にも立たなくて↑のコードですらほとんど速度が変わらなかったり……。
とりあえず家探しまくり中です。おかげで地名とバス路線には一気に詳しくなれたかもしれない。 さっき見学に行ったとこが悪くないような気がしてきたので、 明日朝一で申し込みに行こうかと思っているところ。問題なく進めば、やっと落ち着けます。
オーストラリアは線を引くコストのせいかインターネット環境が日本と比べるとかなり劣る
（数MbpのADSLが上限、ほとんどのプランで月当たりの通信量制限あり）ので困ったなーと思っていたのですが
さっき KDDI AUS. がいい感じなことに気がつきました。
日本宛は最速級
と申したか。これ繋がるだろうか。
研究の方は PLAN-X 通ったので必死に直し中です。あとこっちに来てからManethせんせとの議論の結果、 その論文のネタの発展でちょっと面白い結果が出せたかもしれない。すばらしい。
食べ物屋はタイやベトナムやらの東南アジア系料理が多いですね。色々巡ってみてます。 世界各国McDonaldに行こう同盟の自分としては当然ながら行ってみましたが、 こっちのはパンの焼き方が薄い気がして個人的に微妙。
町中を歩いてたら紀伊国屋があって普通に日本のマンガが買えました。ばんざい。
オーストラリアはお札はカラフルだし、貨幣の大きさの順が($2 < $1 < 50c なのを除いて) 額の大きさの順と同じなので、覚えやすくていいですね。50c のデカさにはちょっとビビった。
英語。英語は、他の英語圏の地域と比べて、自分のダメダメな発音を聞き取ってくれる率が物凄く高くてありがたいです。 こっちが聞き返すことはしょっちゅうでも、向こうから聞き返されることはほとんどない。 言われているとおり本当に多国籍な感じの街なので、みなそういう英語に慣れているんだろうなあと。
まあこんな感じで。
皆様ありがとうございます！！ 実はものすごく表面的にしか目を通せてないのですけどとりあえずリンク返し。
Haskellで。
Rubyで。
Pythonで。
言語によらず。
「無限リストと無限リストのペアを全列挙」 だと、両方のリストを１歩ずつ進めながら逆順zipしてナナメ線を 列挙する書き方が自分の頭の中にすごく残っていて、他の混ぜ方の解説は全部自分の記憶から飛んでいたようです。 むむむ情けない。
def iflatten(aa,bb)
as = bs = []
loop{ zip(as=[aa.next]+as, bs=bs+[bb.next]){ |a,b| yield [a,b] } }
end
iflattern = enum []
where enum al (a:ar) bb = zip al bb ++ enum (a:al) ar bb
-- enum al [] bb = concatMap (zip al) (tails bb) -- 有限リスト対応する場合
しかしこれってSICPでなければ最初どこで見たんだっけか…。
リストのリストの全要素を列挙したリストを作ろうと思ったら、 まあ適当に全部結合すると思います。
flatten :: [[a]] -> [a]
flatten [] = []
flatten (lst:rest) = lst ++ flatten rest
flatten [[1,2,3], [4,5,6]]
=> [1,2,3,4,5,6]
無限リストの無限リストだとどうでしょう。 単純にflattenしてしまうと、先頭にあったリストの要素以外は永遠に出てきません。
flatten [[0,3,6,9,...], [1,4,7,10,...], [2,5,8,11,...], [3,6,...], ...]
=> [0,3,6,9,...] -- 1,4,7,10,... は一生出てこない
これだと不便なこともあります。というわけでお題。順番はどう変えてもいいから、 とにかく『どの要素もいつかは出てくる （有限ステップ以内には出てくる）』ように列挙したリストを返す関数を作ってみてください。
「みてください」なんて言っちゃって偉そうですが実態は、自分でちょっと考えてエレガントな書き方が 思いつかなかったので、なにか定番の書き方などご存じの方がいらしたら教えていただきたいなあ という他力本願君です。
iflatten [ [a1, a2, a3, ...],
[b1, b2, b3, ...],
[c1, c2, c3, ...],
... ]
=> [a1, a2,b1, a3,b2,c1, a4,b3,c2,d1, ...]