Onion開発日記

_ [その他]第4回つくばコンピュータサイエンス産学オープンカレッジ

が学内で12/14(水)に行われるらしい。肝心の内容はというと、概要から引用すると

Googleを代表するAPIのキーパーソンを本社エンジニアリングチームから招聘し，主要API (Maps, Desktop, Gadget)の紹介を行うとともに，新しい世代のアプリケーション開発を，デモやソースコードサンプルを交えながらわかりやすく解説します．

とのこと。これまでは基本的にほとんど学内の人しか参加していない ような印象だったが、今回はオレンジニュースからリンクが貼られていたり、いくつかのブログで取り上げられていたりしたので、学外の人で来る人が増えるかも？

_ [Java]内部クラスのインポート

今日までJavaプログラムを書いてきて、そんなことも知らなかったのかよと言われそうだが、一応メモ。

例えば、次のような内容のファイルを作っておく。

package foo;
public interface Foo {
  class A {
  }
  class B {
  }
}

また、それとは別に次のようなファイルを作成する。

package bar;
import foo.Foo.A;
import foo.Foo.B;
public class UseFoo {
  public static void main(String[] args){
    A x = new A();
    B y = new B();
  }
}

このプログラムは、Fooの内部クラスAとBをimportして、内部クラス名のみでアクセスすることができている点に注意。今まで自分は、importはトップレベルのクラスのみに対してできるものであり、内部クラスをimportすることはできないと勘違いしていた。

ところで、次のようにFooをimplementsすることで、同じような目的を達成することもできるが、これはインタフェースの実装をタイプ量を減らすという別の目的に使用していてわかりにくいため、使用すべきでは無いとされてきた。

追記: Java 5.0ではstatic importを使って同様の目的を達成できるため、上のテクニックは全く意味が無い。

package bar;
public class UseFoo implements Foo {
  public static void main(String[] args){
    A x = new A();
    B y = new B();
  }
}

_ [Java][言語]"Self Types" Trick

ゼミの後、研究室の教官と話していたら、ふとしたきっかけで教官からFortressの話を振られた。何の話だったかというと、Fortressのチュートリアルのスライドに次のようなコードがあるけど、この中のT extends Equality[T]って何なのよということだ。

trait Equality[T extends Equality[T]]
  opr =(self, T) :Boolean
end

で、ちょっと考えて、「それは型パラメータに自分自身と同じ型(かそのサブタイプだけを適用できるようにするためのテクニックじゃないですかね。確かJava Genericsでも同じテクニックを利用した例があったはずですよ。」とか言って、いかにもこのテクニックが使われてそうなComparableインタフェースのAPIを見てみたのだが、実はこのテクニックは使われておらず、単に

public interface Comparable<T> {
  int compareTo(T o);
}

となっていた。ひょっとしてJavaではこの"Self Types" Trickは使えないのかなと思って、次のようなコードで実験してみると、ちゃんとコンパイルを通った。

public interface MyComparable<T extends MyComparable<T>> {
	int compareTo(T other);
}

もちろん、このインタフェースを使ったコードもちゃんとコンパイルを通る。

public class A implements MyComparable<A> {
  int compareTo(A o){ ... }
}

さらに、変な型をMyComparableの型パラメータに適用した場合には、ちゃんとエラーになる。

//MyComparableの型パラメータにMyComparableを実装していないStringを渡しているため、コンパイルエラー。
public class A implements MyComparable<String> {
  int compareTo(String o){ ... }
}

じゃあなんで、標準APIのComparableではこのテクニックが使われていないんだろうと疑問に思ったのだが、考えてみれば、このテクニックを使っても、Fortressがどうかはわからないが、Javaでは次のようなコードがコンパイルを通ってしまうわけで、上のような使い方をエラーにできても大した意味が無いからかもしれない。

public class A implements MyComparable<A> {
  int compareTo(A o){ ... }
}
//無意味な使い方だけど、AはMyComparable<A>を実装しているので、コンパイルは通る。
public class B implements MyComparable<A> {  
  int compareTo(A o){ ... }
}

_ [その他]Binary 2.0カンファレンス2006

今年もあのBinary 2.0カンファレンスが行われるらしい。既に事前登録が開始していたので、早速申し込んだ。12月9日22:20現在、まだ申し込みは締め切られていないようだが、去年のことを考えるとすぐに定員が埋まる可能性があるので、参加したい人は早めに登録した方がいいかも。

_ [Groovy]Release of Groovy RC-1

Groovy RC-1が出たようだ。アナウンス

This is with great pleasure that I'm announcing the release of the first release candidate of Groovy. Groovy RC-1 is a very important milestone in the life of the project. It also means 1.0 will be released very shortly thereafter. The plan is to release the final version before the end of the month.

によると、近いうちに1.0もリリースされるとのこと。

早速ダウンロードして、インストールしてみた。かなり久しぶりにGroovyを触ったので自信は無いが、以前よりスクリプトの起動速度はだいぶ速くなっているようだ。ただ、配布サイズがかなりでかい(13MB超)。たぶん、色々ライブラリを詰め込んだ結果なんだろうけど。

_ [Java]java.util.Collections#sort()のAPIドキュメントが…

J2SEのjava.utill.Collections.sort()メソッドのAPIドキュメントが微妙だ。何が微妙かって、動作の仕様だけでなく、何故か実装詳細であるはずのソートアルゴリズムについて述べているところ。引用すると、

ソートアルゴリズムは修正マージソートです。このソートでは、下位のサブリストにおける最高レベルの要素が上位のサブリストにおける最低レベルの要素より小さい場合、マージは省略されます。このアルゴリズムは、常に n log(n) のパフォーマンスを提供します。この実装は、指定されたリストの配列へのダンプ、配列のソート、リストでの繰り返し処理を行うことにより、配列の対応する位置から各要素を再設定します。これは、リンクされたリストを適所にソートしようとした場合の n2 log(n) のパフォーマンスになるのを回避します。

実行性能のオーダーについて述べるのはまだ理解できるんだが、なんでマージソートを使っていることまで書く必要があるんだろう？これじゃまるで、他のJ2SE互換実装でマージソートアルゴリズム以外を使ってはいけないように見えてしまうと思うのだが。

追記: どうやら微妙だったのはAPIドキュメントの方ではなく、自分だった模様。鈴木さんからのツッコミを見て、 java.util.CollectionsのAPIドキュメントを見てみると、確かに

このクラスにあるさまざまなアルゴリズムのドキュメントには、通常、「実装」の簡単な説明が含まれています。この説明は、「仕様」の一部ではなく「実装情報」と考えてください。実装者は、仕様に反しないかぎり、ほかのアルゴリズムを自由に使用できます。たとえば、sort が使用するアルゴリズムはマージソートである必要はありませんが、「固定 (stable)」のアルゴリズムでなければいけません。

と書いてある。というわけで、結論としては、APIドキュメントの一部を読んだだけで、いい加減なことを言ってはいけません、ということで。

_ [Java]Java SE 6リリース

Java SE 6がリリースされたようなので、早速ダウンロードして使ってみた。とりあえず、Swingアプリケーションの速度(特に起動速度)がかなり向上しているのが良い。アプリケーションにもよるが、自分が普段使っているJavaアプリケーションで起動が21.5倍くらい早くなったアプリもあった。

また、Windows上でjarファイルに関連付けされるアイコンが、これまではワードパッドに関連付けされるアイコンと同じでまぎらわしかったのだが、ちゃんと専用のアイコンに関連付けされるようになるなど、地味に色々改善されているようだ。Java SE 6で追加されたAPIはまだ試していないが、今度、気が向いたときに試してみることにしよう。

_ [その他]金が飛んでいく

今週末はちょっと出費が激しくなりそう。

• 12/15: Binary 2.0 Conference
• 12/16: 某雑談会
• 12/17: 日本Rubyの忘年会

東京<->つくばの交通費だけで1150 * 2 * 3 + α = 6900 + α…。あと食事代とか考えると、計20000円超くらいと見ておくべきか。まあ、誰かに頼まれて参加するわけじゃなく、自分で行きたいから行くわけだし、金がかかろうが別に後悔してるわけじゃないが。

_ [プログラミング][その他]Binary 2.0カンファレンス2006

18:10頃会場に到着。shinichiro_hさんやk.inabaさんとちょっと雑談した後、 18:30から開始。

• 開会の辞?(高林哲さん)

  高林さんが、Binary Hacksの執筆から出版に至るまでの事情をネタを交えて語る。 普通に面白い。

  キーワード： Binary 2.0の発祥地は神保町？，中国語・韓国語版が出るかも？

• Hello, binary world(佐藤祐介さん)

  GCCの拡張機能を使いまくったHello, worldを出力するプログラムを紹介する発表。 無駄なこだわり方がすごい。Hello, worldを出力するだけのプログラムでも色々 こねくり回して遊べるということがよくわかった。

  キーワード：アリアリ，ナシナシ，58B，ELF GOLF，__attribute__((constructor))， mainを呼ばないハローワールド，main変数，warning: 'main' is usually a function， ゆとり，main = 195(RET命令)，スルー力の高いmain， __attribute__((section("text")))， cleanup属性を使ってRAIIイディオムを模倣

• X日で作る仮想マシンモニタ(に向けて)(金田憲二さん)

  仮想マシンモニタ(VMM)とはそもそも何かという話と、金田さんが開発された非常に 単純なVMMの紹介。対象アーキテクチャをAMD64にしぼることによって、構造を単純化 することに成功しているとのこと。発表自体は直前の発表がネタに走ったのと対照的に、 実に真面目な発表だった。自分がVMMに関してあまり明るくないため、いまいちピンと こなかったのが惜しい。

  キーワード：Nested Paging，分からない事をWebで検索したら自分のWebページがHit

• getcontextの怪(田中哲さん)

  過去にRubyがIA-64で動作しなかった問題の原因の一つであるgetcontext問題の 紹介。getcontext/setcontextはsetjmp/longjmpに似た動作をする関数らしいが、 このgetcontextをIA-64上のgccで使うと問題が起きたらしい。現在はgccの方に 対応してもらうことで、問題は解決されたとのこと。

  キーワード: context/setcontext，祝！SEGV，IA-64はレジスタがたくさん， レジスタスタック，IA-64のsetjmpはレジスタスタックのレジスタを保存・復元しない， レジスタスタックなんてなければいいのに，誰が悪いのかわからないけどgccに 対処してもらった，アセンブラで書くのがポータブル

• マルチコア時代の並列プログラミング：ロックとメモリオーダリング(中村実さん)

  メモリオーダリングが問題になる並列プログラムのテクニックである lock-free synchronizationの紹介。lock-free synchronizationを使った 基本的なデータ構造などが論文へのポインタ付きで紹介されていたのが、 勉強になった(気がする)。

  キーワード：プロセッサのメモリオーダリングに注意，Store Buffer，並列GCでは スレッド間の通信が多い，マルチコアではmutexがボトルネックになる(かも)， CAS(compare and swap)，LL/SC(load linked/store conditional)，Sequence Lock， Read Copy Update(RCU)，"Cas-based lock-free algorithm"，"Lock-free and practical doubly linked list-based deques using single-word compare-and-swap"， 衝突が少ないプログラムではmutexと性能に差が無い，lock-free synchronization はアルゴリズムが複雑なものが多い & 実装が難しい，メモリバリア，SFENCE命令， LFENCE命令，

• TTY Hacks for PS3 Linux

  PS3 Linux＆Wiiリモコンを使っての発表。Wiiリモコンを振るとスライドが回転＆ 効果音がするというネタ発表。間違って振ると変な方向にスライドが回転するのが 笑える。発表の内容よりこっちがやりたかったんじゃないかと勘ぐってしまう。 これは後日、是非ムービーとしてアップロードして欲しいな。

• Web 2.0時代のAjax Binary Hacks(竹迫良範さん)

  キーワード：web 2.0，web 2.1?，ふたりはバイナリアン，stable <-> unstable， クロスドメイン通信， JSONP

• 携帯Flashでバイナリ処理(鴨志田良和さん)

  キーワード：Flash Lite，100KB制限，Flash Liteは配列無し，温故知新， ハフマン符号化，文字列でバイナリ操作

• GNU on Binary 10.0(g新部裕さん)

  キーワード：普通のやつらの下を行け！，gUSB，CPLD，FPGA， トラ技2006年4月号，200行，いいお年を… = 0x0E(01110) or 0x11(10001)

• ASCII 1.0(野首貴嗣さん)

  キーワード：ASCIIのみで書かれた.com実行ファイル，uuencode，ish， endfish/defish，AA 2.0，Automated AA，aalib

_ [プログラミング][言語][その他]言語雑談会2006？

shinhさんの日記に書いてあるような経緯で、今年も言語雑談会が 行われた。参加者は、 shinhさん、 k.inabaさん、 YTさん、 w_oさん、 私、 soutaroさん、 ruto君、 shelarcyさん、 Cryoliteさん、 ささださん の計10名。

午前10:00頃、つくば組(私、soutaroさん、ruto君)の3人でつくばセンターに集合して、一路秋葉原へ。その後、soutaroさんの事前の要望で、御茶ノ水駅からちょっと歩いたところにあるペットショップへ。今までこういう所には行ったことが無かったのでなかなか面白かった。

その後、御茶ノ水か秋葉原のどちらかで昼飯を食べようという話になり、とりあえず御茶ノ水駅付近を散策してみるも、良さそうな場所は見つからず、秋葉原で食べることに。とはいえ、秋葉原で飯を食べたことがそんなにあるわけでも無く、結局一番無難な？山水でラーメンを食べることに。

食後、13:00頃に集合場所の秋葉原電気街口で参加者の一部と合流後、何かつまむものをということで、つくば組で輸入食品店とドン・キホーテを回ってお菓子とジュースを購入した後、会場であるダイビルへ。

いくつかの注意事項についての説明をささださんから受けた後、とりあえず自己紹介タイム。とはいえ、そこは言語雑談会、単なる自己紹介ではなく、各々の好きな言語や嫌いな言語をその理由を交えて語るというもので、これだけで延々1時間以上続くという異常な自己紹介に。かく言う自分もかなり熱くなってJavaについて語ってしまった。

その後、雑談タイム…にはならず、私によるNemerleについての紹介とCryoliteさんによるC++0xのconceptについての紹介が行われることに。

私の発表はNemerleの概要をなぞるだけのものだったので、正直聞いている人にとっては物足りないかもと不安だったが、とりあえず一番強調したい所だった、マクロの機能についての反応は悪く無かった(と思う)のでほっとした。

一方、Cryoliteさんの発表はC++0xで導入される見込みのconceptという機能についての紹介。conceptというのは聞いたことがあったものの、せいぜいtemplate引数に制約をつけるだけの機能だろうと侮っていたが、なかなかどうしてかなり便利な機能だった。どう便利なのかは、説明しきれないというか自分でも理解しきれているか自信が無いので割愛。ちなみに、このconceptという機能、既に一部が実装されているConceptGCCというものがあるらしく、今回の発表ではそれを使って実際にconceptの機能についてデモが行われた。

私とCryoliteさんの発表が終わったところで、18:00を過ぎていたので、そろそろ夕食にしようということで、秋葉原駅の近くにある宴会会場へ行って、飯を食べながら引き続き雑談をすることに。中学三年生のHaskellerがいるらしいとか、C++のコードがどんなアセンブリに落ちるか大体わかるらしいとかいくつも面白い話を聞くことができた。

なんかまとまりの無い文章になってしまいましたが、すごく濃い話をすることができて、本当に楽しかったです。呼びかけ人＆幹事役をしてくださったshinhさん、会場を提供してくださったささださん、その他の参加者の皆さん(特に関西(奈良)からわざわざ来てくださったCryoliteさん)ありがとうございます。

追記：発表で使ったり使わなかったりしたNemerleのマクロを使ったソースを載せてみました(以前の自分の日記から引っ張ってきたソースも入っています)。この内、factマクロとpatternマクロについては、発表した時に言及したもののデモでは見せることができなかった、引数が定数ならコンパイル時に計算を行い、そうでなければ実行時に計算するマクロになっています。

fact.n

public class Fact {
  public static f(n :int) :int {
  | 0 => 1
  | n => n * f(n - 1)
  }
}
macro fact(n){
  match(n){
  | $(m :int) => { 
      def r = Fact.f(m);
      Console.WriteLine("fact({0}) = {1}", m, r);
      <[ $(r :int) ]>
    }
  | _ => <[ Fact.f($n) ]>
}

use_fact.n

using System;
Console.WriteLine("fact({0}) = {1}", 5, fact(5));
def n = 10;
Console.WriteLine("fact({0}) = {1}", n, fact(n));

pattern.n

using System.Text.RegularExpressions;
macro pattern(s){
  match(s){
  | <[ ($s_ :string) ]> => { _ = Regex(s_); <[ Regex($s) >> }
  | _ => <[ Regex($s) ]>
}

def pat = pattern("***");

using System;
using System.Text;
using Nemerle.Collections;
using Nemerle.Macros;
using Nemerle.Compiler;
using C = System.Console;
using P = Nemerle.Compiler.Parsetree;


macro Printf(format :string, params args : array[expr]){
  def tokenize(f: string) : list[string] {
    def flag() {
      when(f.Length == 1){
        throw ArgumentException("flag name must be specified after '%'");
      }
      match(f[1]){
      | 'd' => ("%d", f.Substring(2))
      | '%' => ("%%", f.Substring(2))
      | _   => throw ArgumentException(
          "illegal flag '" + f.Substring(0, 2) + "'"
        )
      }
    }
    def cont() {
      def x = match(f.IndexOf('%')){
      | -1 => f.Length
      | n  => n
      }
      (f.Substring(0, x), f.Substring(x, f.Length - x));
    }
    if(f.Length == 0){
      [];
    }else{
      def (token, rest) = match(f[0]){
      | '%' => flag()
      | _   => cont()
      };
      token :: tokenize(rest);
    }
  }
  def parse(tokens :list[string], args :array[P.PExpr]) :list[P.PExpr] {
    mutable x = 0;
    def exprs = List.Map(tokens, fun(t :string){
    | "%d" => 
      if(x >= args.Length){
        Message.Error("not enough arguments");
        <[ C.Write("%d") ]>
      }else{
        def arg = args[x];
        x++;
        <[ C.Write($arg : int) ]>;
      }
    | "%%" => <[ C.Write("%") ]>
    | _    => <[ C.Write($(t :string)) ]>
    });
    when(x < args.Length){
      Message.Error("too many arguments");
    }
    exprs;
  }
  def exprs = parse(tokenize(format), args);
  <[ {.. $exprs} ]>;
}

def a = 10;
def b = 20;
Printf("%d + %d = %d\n", a, b, a + b);

macro swap(n, m) syntax("swap", n, "and", m){
  <[ def tmp = $n; $n = $m; $m = tmp; ]>
}

using System;
mutable x = 10;
mutable y = 20;
Console.WriteLine("(x, y) = {0}, {1}", x, y);
swap x and y;
Console.WriteLine("(x, y) = {0}, {1}", x, y);

using System;
using Nemerle.Imperative;


macro interact(){
  def prompt(s :string){
    Console.Write(s);
    Console.ReadLine();
  }
  mutable all = "";
  def f(){
    while(true){
      mutable line = prompt(">");
      when(line == "exit"){ break; }
      all += line;
    }
    all;
  }
  def result = f();
  <[ $(result :string) ]>
}

using System;
Console.WriteLine(interact());