d.y.d.

19:02 09/02/25

Program Committee

って何やればいいのかよくわかってないんですけど、何事も経験だーということで引き受けてみたので宣伝などしてみます。 1st International Workshop on Schema Languages for XML (X-Schemas 2009) だそうな。

This workshop is intended to bring together researchers and practitioners that are interested in sharing new ideas or experiences that are related to XML schema languages. We therefore invite original contributions that deal with any theoretical or applied aspects of XML schemas. Areas of interests include, but are not limited to:
・Modelling and visualization of XML schemas ・Reverse engineering of XML schemas ・Design patterns for XML schemas ・Integration and exchange of XML schemas ・Similarity of XML schemas, XML schema matching ・Inference of XML schemas ・XML grammars and automata ・New languages for XML schema specification ・Analyses of real-world XML schemas ・XML schema evolution and versioning ・Schema driven optimization ・XML type checking and validation

本

先日読み終わった『チョコレートコスモス』がとても面白かったです。『ガラスの仮面』へのオマージュらしい。演劇の天才がぶつかりあう物語。恩田陸はとにかく中盤の盛り上げが神懸かっているのだけれどラストがなんだかあやふや、という印象が私の中であるのですが、このお話は前半の山場である「僕からこの林檎を手に入れてごらん」のシーンでいつもの絶頂の迫力に持ち上げたまま、残り300ページ一度も息を切らさずに最後まで駆け抜けて行っている。文字・単語・フレーズを鍵にして、読み手の頭の中から「なにかすごいもの」というイメージを引きずり出して見せてくれる、っていうのは小説の醍醐味ですね。

22:08 09/02/14

Adathon

Ada Hackathon 行ってきました。

結局当日までほとんど予習してなくて Ada 書けない状態で突撃。すみませんすみません。以下自分のやっていたこと。

Dでいう public import みたいなのを新しく標準化する際の構文をどうするか議論が激しくて面白い、という話をytさんから聞くなどする。新しい予約語増やさずに既存の予約語の組み合わせでそれっぽくするアイデア色々で面白かった。そこから連想で変なこと考えてましたが、元のAdaの話はもちろんそこまで変でないです。
とりあえず、午前中は Wikibooks の Ada Programming を読みながら必死に勉強することに決める
range と type と subtypeの辺り面白いなー。この辺りの型チェックだけできる処理系でも作るかなあ
String(1..10) は長さピッタリ10の文字列を格納できる型（添え字は1～10）。 String は、可変長の文字列型…ではなく、String(未定) みたいなもので、初期化時に入れた文字列の長さで型が決まって、あとで別の長さの文字列を入れようとすると、実行時エラー。なるほど。
```
s: String := "Hello";
...
s := s & s; -- エラー
```
ある長さ"以下"の文字列を格納する Bounded_String や、可変長の Unbounded_String という型はライブラリとして提供されている。ふむふむ。

ところで

Bounded_String って generic で定義されてて、その generic のパラメタとして最大長を渡すみたいなのだけど、サンプルでコマンドラインの第一引数の長さを渡しているように、実行時の値を渡せるらしい。へー
つい C++ のテンプレートや Java/C# のジェネリクスからの連想で考えてしまっていたのだけど、これ、一番近いのはMLの(Generativeな)ファンクタなんですよね。別に、値でパラメタ化された型というわけでもないので、パラメタがコンパイル時定数である必要はどこにもない。

shinh さんが「クロージャというかC++のbindみたいなのってAdaでどうなるの」みたいな話を横でしていたので、せっかくなので、今覚えた generic の引数に実行時の値として束縛引数を保持する技を使ってみよう、と思って書いてみた。2引数→1引数の場合。

with ada.integer_text_io;
with ada.command_line;

procedure Hello is
   function add(x: Integer; y: Integer) return Integer is
   begin
      return x+y;
   end add;

   generic
      type T1(<>) is private;
      type T2(<>) is private;
      type  R(<>) is private;
      with function f(x1: T1; x2: T2) return R;
      x1: T1;
   function bind(x2: T2) return R;

   function bind(x2: T2) return R is
   begin
      return f(x1, x2);
   end bind;

begin
   declare
      -- addの第一引数をコマンドライン引数の長さに固定した関数addVを作る
      function addV is new bind(
         Integer, Integer, Integer,
         add, ada.command_line.Argument(1)'Length);
   begin
      ada.integer_text_io.put( addV( 10 ) );
   end;
end Hello;

できた。これに至るまでに関数をgenericの引数にする方法がわからなくて教えてもらいました。ていうか関数ポインタを引数に取らせようとしたらコンパイラが落ちた。楽しい。
後で wikibooks のを見てたら、この with ～で関数取る例がでてきた。
```
   function f(x: Integer) return Integer is
   begin
      return x * 2;
   end f;

   generic
      with function f(x: Integer) return Integer is <>;
   function do_f return Integer;

   function do_f return Integer is
   begin
      return f(123);
   end do_f;
```
のように is <> と書くことで、 function foo is new do_f; とすればデフォルトでそのスコープで見える関数 f が使われるし、 function bar is new do_f(f => some_func); として、中で使う f をその場で指定もできるらしい。便利便利。C++0x の concept_map や Haskell の implicit parameter とかその辺りと対比してちゃんと理解しておきたい。

て、そうこうしているうちに、あと１時間半しかなくなっている！

何も作らないで終わるのはアレだなー、と思って HelloWorld だけは動かせるAdaインタプリタを作ってお茶を濁す、という暴挙に出ることに決定。
OMeta/js でざっくりと。実は今まで配列のパターンマッチにしか使ったことなかったので結構手間取った。 seq とか始めて使ったよ。あと空白スキップの面倒を手で見るのはやっぱり面倒かなあ。 OMeta 自身の実装はもっと系統的に空白処理しているっぽく見えたのであとでちゃんと読んでおこう。
できたー EXPR ::= VAR | STRING_LITERAL; STATEMENT ::= 'put_line' '(' EXPR ')' ';' という酷い言語が！

というわけで何も作れていないですが、かなり Ada の勉強になりました。基本的なところは意外と書けるようになってきた。面白かったです。

19:12 09/02/13

TLE

Submitされた解答公開されてる！以下、ネタバレ感想。

KEY: 空白なんて元々使わないですし、ゴルフで使う予約語ってforくらいなので、ループを再帰に直してあとは普通に縮めるのみ。回文化は//で後ろに足すだけ。

SHORTEN: 読み解いた限りでは、『テストケースは一行に自然数2つ"a b"で入力は"0 0"終端、各ケース毎に、区間 [a,b] 内のある条件を満たす数を全て出力せよ』という問題の解答コードのつもりだと思うんですが、与えられたコードは、最適化のためかすべてのテストケースを一括で処理しようとして強烈にバグっているという酷い状態で酷かった。ただ、これ、ちゃんと「正しい」ままでも2000点くらいは超えられると思うので、問題とスコアの設定どっちもおかしかった気がする。

INPOUT: 空白文字を文字数にカウントしないゴルフ、という設定の裏をかいて空白とタブで出力をエンコードして全部埋め込んだら615点。それより上は、ちゃんと真面目に解いて到達するゾーンらしい…。自分のマジメ解は400点くらいで詰まってしまったので、それは無理だと思い込んでました。良いゴルフ問題。

CODEHASH: コメントを32文字入れればコメント部分を変えることで自由自在にハッシュ値を操れる、というのが自分の出した解。それより上は、ハッシュ値を直接 printf するコードに空白などを入れて微調整しつつ不動点を見つけることになるんだと思う。ズレが2バイトだけのものまではできたんだけどそこで力尽きた。これを解ける人はほんと凄い。

CLASS: 空白文字を一個も使わずに指定された名前のクラスを定義せよという。知っていれば簡単。別解があるとは思わなかった…

PENGUIN: ランレングスで埋め込み。文字番号×28＋(連長-1) にエンコード。文字は10種類で28*9=252なので、9番を割り当てる文字は連長4以下なものになるように。あと \" と \\ が不要になるように適当に調整するだけ。

PRINT: ほぼ普通に回文Quine。あんまり得意でないのでほどほどで。

NP, TESTGEN: Greedyに支配集合を求める解を送るだけ送っといた感じ。

ARBIT: コード解読 → ProjectEuler風数学問題 → ゴルフ、の三段構え問題。面白かった。結局、コードをほどくと「入力a,bに対して、1≦x≦aかつ1≦gcd(a,x)≦bなxの個数を表示」という処理になってるんですが、元プログラムは1≦x≦a（ただしaは最大10億）をループして数えてて遅いので、 1≦g=gcd(a,x)≦b（bは最大1万）の方で回して、オイラーのφ関数のφ(a/g) の和を取ると速い。

THINK: 結局3番わからなかったー！

さて、終わったと思ったら今度は MathematiKa '09 が始まってるんですが、どうしようかな…。

Derive Your Dreams