夏ゼミ2011

大学

9月8日から10日まで，諏訪湖の近くで行われた研究室の夏ゼミに参加していた．
各自が情報工学に関する何かについて自由に発表するというもので，俺は型レベルプログラミングについて話した．
FunctionalDependencies, FlexibleContexts, FlexibleInstances, UndecidableInstances といった定番(?)の拡張について，なぜそれらが必要になって，具体的にどのような拡張を行うかといった点についても触れたつもり…
本当は http://research.microsoft.com/en-us/um/people/simonpj/papers/fd-chr/ に基づいて話そうと考えていたけど，間に合わなくて全体的に「こういうものなんですよ」みたいな話になってしまった．
まぁ時間内に型レベルプログラミングっぽいところまで持って行くにはむしろこれでよかったのかもしれない…


最後に見せたコードはこんなの．UndecidableInstances の下では Turing-complete になるということで Brainf*ck のナイーブなインタープリタ．
http://www.ideone.com/bcofH
メモリの持ち方がなぜか assoc list．メモリのアドレスもメモリの内容も自然数．
. と , の実装は省き，eval は実行が終了したときのメモリの状態を返している．


他の人の発表の中では CAM (Categorical Abstract Machine) の話が一番気になった．
何か関数型な言語の真面目なコンパイラを書いてみたい．

追記 2011-09-13 23:08

スライドへのリンクを貼り忘れていた…
http://dl.dropbox.com/u/162725/slides/110908.pdf

C80

院試が控えているので(?)ビッグサイトへは行かなかったけれども横浜のメロンととらへは行った．
比較的読みたい度が高くて店頭で見つけられたものから．なんと5冊．

現地行くとおまけ貰えたりグッズとかもちょっと買ったりするんだけど，そういうのが一切ない点でもなんか寂しい．
あと興味があった技術っぽい本たちはどうしようかなー的な．

Linux 3.0 で SBCL 1.0.50 が起動直後に Segmentation fault する問題

Arch では Linux 3.0 が core に入った．
http://www.archlinux.org/news/changes-to-kernel-package-and-filenames/
これに関連してドライバの問題やブート時の問題が結構 bug tracker に報告されているけど，自分の環境ではそういった問題は起こっていない．


が，意外なところに影響があった．
それは SBCL が起動直後に Segmentation fault するというもので，strace してみると uname(2) の直後に死んでいた．
これは Linux のバージョン番号の付け方が変わって，今まで 2.6.n という形式だったのが 3.n となったため，x.y.z という形式であるという仮定が崩れたために発生していた様子．
開発版では既に修正されている．
http://sbcl.git.sourceforge.net/git/gitweb.cgi?p=sbcl/sbcl.git;a=commit;h=b43c51beeb0569a38900e1e5a78606711f987742
Linux 3.0 で SBCL を使いたい場合，次のバイナリがリリースされるまでは SBCL 以外の Common Lisp 処理系を用意して，この変更以降の SBCL をソースからビルドする必要がある．
http://www.sbcl.org/getting.html
でもまぁ，リリースサイクル的にそろそろ 1.0.51 がリリースされそうなので，それを待ってもよさそう．

追記 2011-08-14 16:37

Arch は上のパッチを当ててリビルドしたものを 1.0.50-2 としてリリースした．
https://bugs.archlinux.org/task/25470

Arch Linux で PT2 (DVB 版ドライバ earth-pt1 + fuse_b25)

Linux PT2

以前 Arch Linux での PT2 環境のセットアップをまとめた．そこでは chardev 版のドライバを利用していた．
http://d.hatena.ne.jp/eagletmt/20110307/1299492620
が，BKL が削除されたことによって最近の Linux だとそのままではコンパイルできなくなっている．
(un)lock_kernel() を spin_(un)lock() に変えるという簡単な変更で対処できるらしいものの，これから先に不安が残る．


もうひとつのドライバである earth-pt1 のほうは既に Linux のメインラインに取り込まれており，取り込まれている間は少なくともコンパイルはできるよう保守されるはず．
earth-pt1 はずっと使ってみようとは思っていたんだけど，これまでの Linux だと自分の環境では earth-pt1 を正常にロードすることもできなかった．
そのへんの問題が今回の Linux 3.0 において改善されていると聞いて試してみた．
たぶんこれ http://git.kernel.org/?p=linux/kernel/git/stable/linux-3.0.y.git;a=commit;h=cae72c7c63fd4a8f20efc001108f12f34076c17b ．
その結果，たしかにちゃんと動作したのでそのログ．

Linux 3.0

Arch Linux では testing リポジトリに Linux 3.0 が既にある．しばらくすれば順当に core にもくるでしょう．
Arch Linux では既にデフォルトのカーネルが 3.0 になっている．
今までの kernel26 というパッケージ名から linux という名前に変更されているので注意．

earth-pt1

最初に

% zgrep CONFIG_DVB_PT1 /proc/config.gz
CONFIG_DVB_PT1=m

で earth-pt1 がちゃんと含まれていることを確認し，

% ls /dev/dvb
adapter0  adapter1  adapter2  adapter3

で adapter が作られていることを確認する．0, 2 が BS 用で 1, 3 が地デジ用．
作られていない場合は dmesg あたりを見るといいかも．
adapter が作られていれば

% dmesg | grep DVB
[    4.951584] DVB: registering new adapter (earth-pt1)
[    4.951791] DVB: registering new adapter (earth-pt1)
[    4.952031] DVB: registering new adapter (earth-pt1)
[    4.952239] DVB: registering new adapter (earth-pt1)
[    5.219681] DVB: registering adapter 0 frontend 0 (VA1J5JF8007/VA1J5JF8011 ISDB-S)...
[    5.219767] DVB: registering adapter 1 frontend 0 (VA1J5JF8007/VA1J5JF8011 ISDB-T)...
[    5.219820] DVB: registering adapter 2 frontend 0 (VA1J5JF8007/VA1J5JF8011 ISDB-S)...
[    5.219847] DVB: registering adapter 3 frontend 0 (VA1J5JF8007/VA1J5JF8011 ISDB-T)...

こんなかんじのログになるはず．
ハードウェア的に認識されているかどうかは前回のエントリのように lspci で確認する．

s2scan

次に http://2sen.dip.jp/cgi-bin/dtvup/source/up0588.zip に含まれている s2scan をビルドして，受信可能なチャンネルの一覧を作る．

% unzip up0588.zip
% cd dvb_apps_0.92/cmds
% make clean
% make
% ./s2scan -a 1 > channels.txt

-a の後の数字はスキャンする adapter の番号．
しばらく待つと，channels.txt に

tvk1:DTV_DELIVERY_SYSTEM=8|DTV_FREQUENCY=503142857:24632
TOKYO　MX1:DTV_DELIVERY_SYSTEM=8|DTV_FREQUENCY=515142857:23608
TOKYO　MX2:DTV_DELIVERY_SYSTEM=8|DTV_FREQUENCY=515142857:23609
フジテレビ:DTV_DELIVERY_SYSTEM=8|DTV_FREQUENCY=521142857:1056
(snip)

こんなかんじの出力が得られているはず．

tune

そして http://2sen.dip.jp/cgi-bin/pt1up/source/up0219.gz の tune を修正してビルドする．
tune.c に

static struct channel isdbt_channels[] = {
        {   1, "NHK東京 総合",    557142857 },
        {   2, "NHK東京 教育",    551142857 },

みたいな一覧があるので，そこに channels.txt を基に

static struct channel isdbt_channels[] = {
        {   1, "NHK東京 総合",    557142857 },
        {   2, "NHK東京 教育",    551142857 },
        {   3, "tvk",             503142857 },

こんなかんじに設定して make する．チャンネル名は表示に使っているだけなので，自分がわかるように設定すればいい．


そうするとこの tune を使って

% ./tune 1 3 &
Successfully tuned to tvk .
% cat /dev/dvb/adapter1/dvr0 > tvk.ts

と録画できるようになる．録画を止めるには cat と tune を殺せばいい．
tune の1つ目の引数は adapter の番号で，2つ目の引数はさっき設定したチャンネルの番号．

fuse_b25

が，例によってスクランブルがかかっているのでこのままだと見ることはできない．
後から arib25 で解除する手もあるけど，ここでは fuse_b25 を利用する方法でいくことにした．
PKGBUILD を書いたのでビルド・インストール方法はそっちを参照．fuse と pcsclite をインストールしてから普通に configure + make するだけでいい．
https://github.com/eagletmt/PKGBUILDs/blob/master/fuse_b25/PKGBUILD
ただし，現時点で最新版の ccid 1.4 系ではなく 1.3 系を使うことに注意．
1.4 系を使うとおそらく FUSE_B25 から

Card I/O failed too many times.
dropped an ECM due to the failed/slow card.

というようなエラーログが syslog 経由で大量に吐かれてまともに動作しない．


fuse_b25 で既存の adapter に対して，デコードしたものを出力する新しい adapter を作ってそこから録画する，というような使い方をする．

# mkdir /dev/dvb/adapter9
# fuse_b25 --target /dev/dvb/adapter1 -o allow_other /dev/dvb/adapter9

と新しい adapter を作って，

% ./tune 9 3 &
Successfully tuned to tvk .
% cat /dev/dvb/adapter9/dvr0 > tvk.ts

と，さっきと同様に録画してみると，スクランブルが解除された状態で保存され，mplayer 等で見ることができる．
新しく作る adapter の番号は被らなければ何でもいいが，(元の番号) + 8 で作るのが慣例になっているっぽい．


ただまぁこの fuse_b25，無駄に CPU 負荷が高い気がする．
chardev 版ドライバを使った recpt1 はリアルタイムにデコードしても Core i3 で CPU 使用率数%程度だったのに対し，fuse_b25 は30%から50%くらい．

で，tune + cat で一応録画はできるものの，使い勝手はよくない．
例えば recpt1 のように，指定した時間だけ録画して終了したり，被っている時間帯に録画しようとしたときは空いているデバイスを勝手に探して使う，といったことをしてもらいたい．
こういう recpt1 のようなツールは既にあるんだろうか．俺は tune のコードをほぼコピペしつつ，今挙げた機能を入れた DVB 版の recpt1 っぽいツールを自分で書いて使ってみているところなんだけど．


DVB という標準的な仕組みに従っているため，MythTV でやるという方法もあるらしい．
http://www43.atwiki.jp/mythtv-dvb/
けれども recpt1 を使ったなんちゃって録画システムを既に作って使っていて，それほど不便さは感じていなかったので，MythTV という大きなツールを使うより recpt1 のような小さなツールだけあるといいなぁと思ってる．

参考

http://aqua-linux.blog.so-net.ne.jp/2010-12-26 を大いに参考にさせてもらった．

ICPC2011 国内予選

haskell-lover というチームで参加していた．メンバーは俺と id:osa_k と id:draftcode．
結果は全体で10位，学内で1位になれました．
http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/common/guest_standings_ja.php
http://imoz.jp/icpc/2011-domestic.html


基本的には模擬国内予選のときみたいに

  • draftcode が C からどんどん問題を読んで，解き方を考えてもらう
  • osa_k が A を考えて書いて，D を考えてもらう
  • eagletmt が B, C を考えて書く

で，それ以降はよしなにやる，というかんじの予定だった．

A

いつも通りやるだけなので osa_k に適当に書いてもらう．

B

どう見てもやるだけだったのでそのまま osa_k に書いてもらう．

C

すべてのマスについて色を変更できると勘違いしてやや重いかと思ったけど，電極が左上のマスに固定されているということを指摘されて，これなら全通り試せばいいだけで実装も簡単っぽい．
やや実行速度が遅かったが，書いてほぼ一発でサンプルと最初のインプットが通った．
しかし2回目のインプットに対してまさかの WA．コーナーケースも思いつかないし，アウトプットを眺めてみてもそんなに変な値は入っていないっぽい．
そこでふと提出するときに誤ってインプットを送っていたかもしれない*1ことに気付いて，注意しながら提出し直したら AC．
提出ミスにすぐ思い当たって本当によかった…
すみませんすみません…と3つめのアウトプットも送って AC．

D

解けるという話だったので osa_k に任せて E 以降を見ることにする．

E

draftcode から説明を受けてやることはだいたいわかったけど解法がわからない…

F

やることは明快で幾何ゲーっぽい．これはがんばって実装すればいけるのでは(←まちがい)

G

任意の一箇所のドアが壊れていてそのときの各最短経路の最大を求めるだけかと最初勘違いして，30x30 だしまさかやるだけ？と思ったが，ちゃんと読み直すと解釈が違っていることに気付いた．
うーん…


だいたいこのあたりで osa_k が D を通し終えていた．
問題を軽く説明した後，E を osa_k と draftcode が考えて，F を俺が考えることにした．

F

図を書き散らしながら，方針を考えつつ場合分けが必要な場面を列挙していく．
まず杭(原点)と建物の各4点の角度でソートして，右から処理しつつできる弧の軌跡の長さと，左から同様に処理してできる弧の軌跡の長さを足す，という方針にした．
疑似コードっぽいものを書いているうちに，最後に弧が交わるケースだと弧の軌跡の長さを覚えているだけでは対処できないことに気付く．
でもそれなら弧をそれぞれ全部記憶しておいて，後で比較しつつ交わるなら交点を求める，という風にすればいいのでは，と思った．
これで大まかな方針は固まったものの，場合分けがしんどい．それと弧と弧の交差判定と交点をどうやって求めよう？という問題もあった．


なんか E を通せたらしい．すごい．
F の方針を説明して，いくつかツッコミを受けてから書き始める．
が，バグバグで全然求めていた値が出ない．何度も指摘されて修正していくものの結局そのまま終了．

E を解いてくれた2人に感謝．
噂によると GCJ だと Presentation Error は Wrong Answer ではなく単に弾かれるだけらしいので，アウトプットに Case #n を強制するなどして ICPC もそういうシステムになるといいのでは…
幾何修行の必要性は自分でも感じたし，kinosaki さんにチームで1人は幾何問題に対して実装しきるよう修行しないとと言われたので，幾何から逃げずに修行しようと思います．

*1:本当にインプットを送っていたかどうかは謎

uim-skk で server completion を利用する

SKK

http://gihyo.jp/admin/serial/01/ubuntu-recipe/0175
で SKK の server completion というものを知った．
yaskkserv + DDSKK でそれなりに便利なかんじだったので，uim-skk でも使えるようにするパッチを書いた．
https://github.com/eagletmt/uim-skk-server-completion
ところで yaskkserv 以外で server completion できる skkserv ってあるんですかね．
そして server completion を利用できるクライアントも DDSKK 以外にあるんですかね…