トップ 最新 追記

Onion開発日記

2004|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|

ToDo:


2007-01-01

_ [その他]元旦

今回は、実家に帰らずにつくばで過ごしているのでちっともそれらしい 雰囲気が無いですが、それはともかく、あけましておめでとうございます。 今年もよろしくお願いします。

本日のツッコミ(全10件) [ツッコミを入れる]

Before...

_ buying classical music online [Good site :)]

_ arab sex [Thank you. ]

_ ass sex dildo milf [Thank you. ]

_ amputee fucking sex [Thank you. ]

_ tire rack [Thank you. Always yours, Tire Retreading Repair Shop. ]

本日のリンク元 | 6 | 5 | 3 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | TrackBack(0)

2007-01-03

_ [Nemerle]コンパイルタイムGUIプログラミング

久々にちょっとNemerleで遊んでみた。Nemerleのマクロでは.NET Frameworkのライブラリを全て使用することができるので、System.Windows.FormsのようなGUIライブラリでさえ使用することができる。それを利用して、指定した時間だけコンパイル中にプログレスバーを出して待機するという全く意味の無いマクロを作ってみた。ソースコードは以下。全く工夫の無いただのGUIプログラムだが、実行時と全く同じ感覚でコンパイル時プログラムを作ることができるのは中々楽しい(Lispのコンパイラマクロでも同じようなことができるんだろうけど)。

form.n

using System;
using System.Threading;
using System.Windows.Forms;
using System.Drawing;
using Nemerle.Imperative;

macro Wait(seconds :int){ def form = ProgressForm(seconds); Application.Run(form); <[()]>; }
public class ProgressForm : Form { progressBar :ProgressBar; startCondition :ManualResetEvent;
public this(seconds :int){ SuspendLayout(); Width = 400; Height = 200; Text = "Now compiling files ..."; FormBorderStyle = FormBorderStyle.FixedDialog;
startCondition = ManualResetEvent(false);
progressBar = ProgressBar(); progressBar.Location = Point(5, 50); progressBar.Name = "Progress Dialog"; progressBar.Size = Size(380, 30); progressBar.Minimum = 0; progressBar.Maximum = seconds;
Activated += EventHandler(fun(_ :object, _ :EventArgs){ _ = startCondition.Set(); (); });
Controls.Add(progressBar);
ResumeLayout(); Thread(fun(){ _ = startCondition.WaitOne(); for(mutable i = 0; i < seconds; i++){ Thread.Sleep(1000); when(IsDisposed) break; _ = Invoke(ThreadStart(fun(){ progressBar.Value += 1; })); } when(!IsDisposed){ _ = Invoke(ThreadStart(fun(){ Close(); })); } }).Start(); } }

このマクロを使用するコードは次のような感じ。

use_form.n

Wait(10);

このコードをコンパイルすると、コンパイル中に以下のようなウインドウが出てきて、マクロ引数で指定した時間だけ待たされる。

本日のリンク元 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | TrackBack(0)

2007-01-06

_ [Groovy]Groovy 1.0リリース

ここのところGroovyについては、MLを読んでいるくらいで、全然使っていなかったので、1.0リリースを機にダウンロードしてちょっと触ってみた。

まだ少ししか使っていないが、以前のバージョン(といっても(JSR-1とかそれくらいの頃に比べてだが))に比べて起動が高速化されているようで、これでちょっとした作業を行うスクリプトとしても、より使いやすくなったのではないかと思う。

ただ、対話型シェルであるところのgroovyshの使い勝手の悪さがちっとも改善されていないのはマイナス。RhinoやPnutsなどの対話型シェルでは、式を入力してEnterキーを叩けば、評価結果が返ってくるようになっているが、groovyshでは、評価したい式の列を全部入力し終わった後に、"go"というコマンドを入力しなければ式が評価されないようになっている。しかも、"go"によって式を評価した後は、それ以前の変数の値などは基本的に引き継がれないようになっており、かなり使いづらい。

本日のリンク元 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | TrackBack(0)

2007-01-07

_ [Pnuts]Pnuts1.2 beta

開発者がSunに雇用されて勢いづいているJRubyや、Java SE 6.0で標準添付されるようになったRhino、1.0が出て再びもりかえして来た?Groovyに比べて冷遇されている感のあるPnutsですが、ちょっと(といっても1ヶ月くらい?)前に1.2 betaが出ていたようなので、久しぶりに試してみました。

まずは無名関数の省略記法。これまではPnutsでは無名関数の生成はJavaScriptのようにfunction(x) ...のように記述しなければいけませんでしたが、1.2ではGroovyのように{x -> ... }と記述できるようになりました。今までfunctionというキーワードをタイプするのが面倒だなあと思っていただけに、ありがたい変更です。

> use("functional")
true
> map({x -> x * 2}, [1, 2, 3, 4, 5])
[2,4,6,8,10]

また、for文で複数の変数について繰り返すことができるようになりました。例えば、次のようにMapのkeyとvalueのペアについて繰り返すというのをfor文で簡単に記述できるようになりました。

> m = {"x" => 1, "y" => 2}
{y=2, x=1}
> for(k, v : m) println(k, " ", v)
y 2
x 1
null

さらに、Ruby風の多重代入もサポートされるようになりました。

> p = [1, 2]
[1, 2]
> x, y = p
[1, 2]
> x
1
> y
2

他にも、まだ試してはいませんが、クラス定義の機能も追加された(される?)ようです。

_ [Java]ネストし過ぎたGenericsの型パラメータ

以前作った、関数型プログラミングをするためのライブラリ から、関数のカリー化を行うメソッドだけを抜粋してみました。 型パラメータが何重にもネストして、凄まじい状態になっています。

package jp.gr.java_conf.mizu.fpl;

import static jp.gr.java_conf.mizu.fpl.Tuples.*;
public class Functions { public static <T1, T2, R> Fn<T1, Fn<T2, R>> curry2( final Fn<Tuple2<T1, T2>, R> fun ) { return new Fn<T1, Fn<T2, R>>() { public Fn<T2, R> call(final T1 t1) { return new Fn<T2, R>() { public R call(final T2 t2) { return fun.call(tuple(t1, t2)); } }; } }; }
public static <T1, T2, T3, R> Fn<T1, Fn<T2, Fn<T3, R>>> curry3( final Fn<Tuple3<T1, T2, T3>, R> fun ) { return new Fn<T1, Fn<T2, Fn<T3, R>>>() { public Fn<T2, Fn<T3, R>> call(final T1 t1) { return new Fn<T2, Fn<T3, R>>() { public Fn<T3, R> call(final T2 t2) { return new Fn<T3, R>() { public R call(final T3 t3) { return fun.call(tuple(t1, t2, t3)); } }; } }; } }; }
public static <T1, T2, T3, T4, R> Fn<T1, Fn<T2, Fn<T3, Fn<T4, R>>>> curry4( final Fn<Tuple4<T1, T2, T3, T4>, R> fun ) { return new Fn<T1, Fn<T2, Fn<T3, Fn<T4, R>>>>() { public Fn<T2, Fn<T3, Fn<T4, R>>> call(final T1 t1) { return new Fn<T2, Fn<T3, Fn<T4, R>>>() { public Fn<T3, Fn<T4, R>> call(final T2 t2) { return new Fn<T3, Fn<T4, R>>() { public Fn<T4, R> call(final T3 t3) { return new Fn<T4, R>() { public R call(T4 t4) { return fun.call(tuple(t1, t2, t3, t4)); } }; } }; } }; } }; }
public static <T1, T2, T3, T4, T5, R> Fn<T1, Fn<T2, Fn<T3, Fn<T4, Fn<T5, R>>>>> curry5( final Fn<Tuple5<T1, T2, T3, T4, T5>, R> fun ) { return new Fn<T1, Fn<T2, Fn<T3, Fn<T4, Fn<T5, R>>>>>() { public Fn<T2, Fn<T3, Fn<T4, Fn<T5, R>>>> call( final T1 t1) { return new Fn<T2, Fn<T3, Fn<T4, Fn<T5, R>>>>() { public Fn<T3, Fn<T4, Fn<T5, R>>> call(final T2 t2) { return new Fn<T3, Fn<T4, Fn<T5, R>>>() { public Fn<T4, Fn<T5, R>> call(final T3 t3) { return new Fn<T4, Fn<T5, R>>() { public Fn<T5, R> call(final T4 t4) { return new Fn<T5, R>() { public R call(T5 t5) { return fun.call(tuple(t1, t2, t3, t4, t5)); } }; } }; } }; } }; } }; }
public static <T1, T2, T3, T4, T5, T6, R> Fn<T1, Fn<T2, Fn<T3, Fn<T4, Fn<T5, Fn<T6, R>>>>>> curry6( final Fn<Tuple6<T1, T2, T3, T4, T5, T6>, R> fun ) { return new Fn<T1, Fn<T2, Fn<T3, Fn<T4, Fn<T5, Fn<T6, R>>>>>>() { public Fn<T2, Fn<T3, Fn<T4, Fn<T5, Fn<T6, R>>>>> call( final T1 t1) { return new Fn<T2, Fn<T3, Fn<T4, Fn<T5, Fn<T6, R>>>>>() { public Fn<T3, Fn<T4, Fn<T5, Fn<T6, R>>>> call( final T2 t2) { return new Fn<T3, Fn<T4, Fn<T5, Fn<T6, R>>>>() { public Fn<T4, Fn<T5, Fn<T6, R>>> call(final T3 t3) { return new Fn<T4, Fn<T5, Fn<T6, R>>>() { public Fn<T5, Fn<T6, R>> call(final T4 t4) { return new Fn<T5, Fn<T6, R>>() { public Fn<T6, R> call(final T5 t5) { return new Fn<T6, R>() { public R call(T6 t6) { return fun.call(tuple(t1, t2, t3, t4, t5, t6)); } }; } }; } }; } }; } }; } }; } }
本日のツッコミ(全3件) [ツッコミを入れる]

_ 斎藤ただし [むしろFunctionsを生成したcurryn.gr(ひょっとして.rb?)が見たいっす。 ]

_ 斎藤ただし [というか、「ネストし過ぎたGenericsの型パラメータ」のRDFの方のタイトルが、なぜか…。イースターエッグ?? ..]

_ みずしま [> Functionsを生成した 実はコード生成じゃなくて、手書きしました。 RubyかGroovy使ってJava..]

本日のリンク元 | 26 | 4 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | TrackBack(0)

2007-01-09

_ [Java]Genericなリストの簡略記法

航海日誌より引用:

前にも言ったけど上記みたいなのができるんなら,

ArrayList<Foo> foos = new ArrayList<Foo>();

とかはどうにかしてほしいなぁ.

大量に同じような記述があるなら,

List<Foo> newFoos() {
  return ArrayList();
}
List<Foo> foos = newFoos();

とかできなくはないけど(typedefの代用).

こういうときは、多相メソッドを使って楽をするのが良いかと思います。具体的には以下のようなユーティリティクラスを定義しておいて、

package collections;
import java.util.*;
public class CollectionUtils {
  public static <T> List<T> list() {
    return new ArrayList<T>();
  }
  public static <T> Set<T> set() {
    return new HashSet<T>();
  }
  public static <K, V> Map<K, V> map() {
    return new HashMap<K, V>();
  }
}

使う方のクラスは、以下のような感じで。list(),set(),map()メソッドに与える型パラメータは、戻り値を代入する変数の型から勝手に推論してくれるので、書く必要がありません。

import static collections.CollectionUtils.*;
public class Main {
  public static void main(String[] args) {
    List<String> strings = list();
    ... stringsを使ったコード ...
    Map<String, String> stringMap = map();
    ... stringMapを使ったコード ...
    Set<String> stringSet = set();
    ... stringSetを使ったコード
  }
}

リストリテラルなどが欲しい場合は、可変長引数を組み合わせればOKです。

package collections;
import java.util.*;
public class CollectionUtils {
  public static class Pair<A, B> {
    private A first;
    private B second;
    public Pair(A first, B second) {
      this.first = first;
      this.second = second;
    }
    public A getFirst() { return first; }
    public B getSecond() { return second; }
  }
  public static <T> List<T> list(T... elements) {
    return new ArrayList<T>(Arrays.asList(elements));
  }
  public static <T> Set<T> set(T... elements) {
    return new HashSet<T>(Arrays.asList(elements));
  }
  public static <K, V> Map<K, V> map(Pair<K, V>... entries) {
    Map<K, V> map = new HashMap<K, V>();
    for(Pair<K, V> entry : entries){
      map.put(entry.getFirst(), entry.getSecond());
    }
    return map;
  }
  public static <A, B> Pair<A, B> $(A first, B second) {
    return new Pair<A, B>(first, second);
  }
}
import static collections.CollectionUtils.*;
public class Main {
  public static void main(String[] args) {
    List<String> strings = list("A", "B", "C");
    ... stringsを使ったコード ...
    Map<String, String> stringMap = map($("X", "1"), $("Y", "2"));
    ... stringMapを使ったコード ...
    Set<String> stringSet = set("A", "B", "C");
    ... stringSetを使ったコード
  }
}
本日のリンク元 | 4 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | TrackBack(0)

2007-01-10

_ [Java]LinkedListに関する不適切な説明

mixiのJavaコミュニティでArrayListとLinkedListに関する議論が行われていたのだが、それに関して、ちょっと思ったこと。

よく、ArrayListとLinkedListの比較において、LinkedListはArrayListに比べてランダムアクセスは低速だが、要素の挿入/削除は高速という説明が見られる(googleでArrayList LinkedListで検索すると大量に出てくる)のだが、これって、かなり誤解を招く説明では無いかと思う。とはいっても、前半半分は別に間違ってはいない。確かにLinkedListのランダムアクセス性能はArrayListに比べて明らかに悪い。

問題なのは後半部分だ。平均的な入力において、LinkedListへの要素の挿入/削除は、ArrayListに比べて高速とは言えない。何故かと言えば、実はすごく当たり前の話で、ArrayListの場合は、途中への要素の挿入/削除は挿入位置より後ろの全要素をずらすため、O(n)時間かかるが、LinkedListの場合も、挿入する位置に到達するために、リンクを挿入するインデックスの数だけたどる必要があるため、結局O(n)時間かかってしまうためだ。そして、Webページの説明記事の多くは、何故かそのことをスルーして、LinkedListの場合は参照を張り替えるだけで済むためArrayListに比べて高速などのように書いてあるものが多い。

もちろん、リストの先頭あるいは先頭付近への挿入/削除が頻発する場合や、Iteratorで全要素をたどって、条件を満たしていない 要素全てを挿入/削除する場合などはLinkedListの方が高速になる。しかし、それならばリストの先頭への挿入/削除が高速あるいは、Iteratorで要素をたどりつつ挿入/削除する場合に高速と書けばいいのであって、挿入/削除を行う場合はLinkedListの方が高速と書くのは誤解を招くだけなので、やめた方がいいのではないだろうか。

ちなみに、自宅のPC(OS: Windows XP, JRE: JDK 6.0, CPU: Athlon 64 3000+, Memory: 1.5GB)でArrayListとLinkedListの性能を測定する次のような簡単なベンチマークプログラムを作って実験してみた。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListPerformance { private static final int NANO_MILLI = 1000000; private static final int DEFAULT_NUM_OF_CALLS = 100000; abstract static class ListBenchmark<T> { protected String operation; protected int count; protected List<T> target; ListBenchmark(String operation, int count) { this.operation = operation; this.count = count; } protected abstract void run(); protected void prepare(){} public final void measure(List<T> target) { this.target = target; prepare(); long start = System.nanoTime(); for(int i = 0; i < count; i++) { run(); } long time = (System.nanoTime() - start) / NANO_MILLI; System.out.printf("%7s:%6d[ms] using %s%n", operation, time, target.getClass()); } } public static void main(String[] args) { ListBenchmark<String> append = new ListBenchmark<String>("append", DEFAULT_NUM_OF_CALLS){ @Override protected void run() { target.add(""); } }; ListBenchmark<String> insert = new ListBenchmark<String>("insert", DEFAULT_NUM_OF_CALLS){ @Override protected void run() { target.add(target.size() / 2, ""); } }; ListBenchmark<String> prepend = new ListBenchmark<String>("prepend", DEFAULT_NUM_OF_CALLS){ @Override protected void run() { target.add(0, ""); } }; ListBenchmark<String> remove = new ListBenchmark<String>("remove", DEFAULT_NUM_OF_CALLS){ @Override protected void prepare() { for(int i = 0; i < count; i++){ target.add(""); } } @Override protected void run() { target.remove(target.size() / 2); } }; append.measure(new ArrayList<String>()); append.measure(new LinkedList<String>()); System.gc(); insert.measure(new ArrayList<String>()); insert.measure(new LinkedList<String>()); System.gc();
prepend.measure(new ArrayList<String>()); prepend.measure(new LinkedList<String>()); System.gc(); remove.measure(new ArrayList<String>()); remove.measure(new LinkedList<String>());
} }

結果は次の通り。append(末尾への追加)は両者ともほとんど同じ性能で、insert(リストの中間への要素の挿入)はArrayListの方が高速、prepend(先頭への挿入)はLinkedListの方が高速、remove(リストの中間からの要素の削除)は ArrayListの方が高速、という結果になった。

 append:    20[ms] using class java.util.ArrayList
 append:    21[ms] using class java.util.LinkedList
 insert:  5038[ms] using class java.util.ArrayList
 insert: 89355[ms] using class java.util.LinkedList
prepend:  9319[ms] using class java.util.ArrayList
prepend:    17[ms] using class java.util.LinkedList
 remove:  4253[ms] using class java.util.ArrayList
 remove: 38490[ms] using class java.util.LinkedList

M田さんからツッコミがあったので、追記。ここで言っているのはjava.util.LinkedListの話であって、データ構造とアルゴリズムで言うところのリンクトリストとは別であることに注意。

一般論としてはリンクトリストを提供するクラスから内部で使われているノードを取得できれば(あるいはリンクトリスト自体に、現在の位置情報を持たせれば)、あるノードの直後に挿入/削除する操作はO(1)時間で実行できるが、java.util.LinkedListクラスには内部で使われているノードを取得する手段が無い。同様のことを実現するには、LinkedListからIteratorまたはListIteratorを取得する必要がある。

_ [言語]Fortress Reference Implementation

さよなら、こんな毎日・・・ Script_on_Java経由。FortressのReference Implementationのソースコードが公開され始めた。ソースコード本体はここからダウンロードできる模様。Fortressについては前から興味があったので、そのうち試してみたいところ。

ところで、FortressのReference Implementationでは、Parserを書くのに既存のメジャーなParser Generator(JavaCCとか)ではなく、Rats!を使っているようだ。Packrat Parsingでないと構文解析が困難な文法だったということだろうか?

本日のツッコミ(全2件) [ツッコミを入れる]

_ M田 [Introduction to Algorithmsにはあったと思うけど、リストへの挿入、削除といったとき「n番目に..]

_ みずしま [はい。もちろん、その通りなんですけど、後者の「すでに位置情報がわかっているとき、そこへ挿入(削除)」という操作をLi..]

本日のリンク元 | 21 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | TrackBack(0)

2007-01-11

_ [Fortress]Hello, Fortress!

早速、公開されたFortressのソースをダウンロードしてきて、ビルドしてみた。まずは、ソースのルートにあるbuild.xmlをそのままantで実行してみる。 すると、assertEquals()などのjunit由来と思われる識別子が見つからないというコンパイルエラーが発生した。build.xmlを見てみると、junit.jarへのクラスパスが通っていなかったのでbuild.xmlを改変して、junit.jarへのクラスパスを通してみると今度はビルドに成功。

で、ビルドに成功したので次は実行と行きたいところだが、fortressのソースには、fortressインタプリタ実行用のシェルスクリプトが添付されていたものの、バッチファイルが無かった。しかし、自宅のPC環境はWindowsなので、シェルスクリプトはそのままでは実行できない(Cygwinとか使えば別だが)。シェルスクリプトでは、クラスパスを通してjavaコマンドを起動する程度のことしかやっていなかったので、シェルスクリプトを元に同等のことを行うバッチファイルを作成した。

ここまでで実行の準備が出来たので、最初のプログラムを実行してみる。やはり最初のプログラムと言えば、Hello, World!だろうということで、Fortressのソース中にあったhello.fssを実行してみた。

hello.fss

component Hello

export Executable
run(args:String...) = print "Hello, World!\n"
fortress hello.fss

しかし、ここで何故か

Parse of C:\fortress\ProjectFortress\FortressLibrary.jst ended EARLY at line = 1
,  column = 27
Trouble reading preparsed library AST.
java.io.IOException: Near line 1 and column 26 got Backslash escape P(hex 50)
        at com.sun.fortress.interpreter.reader.Lex.unexpected(Lex.java:295)
        at com.sun.fortress.interpreter.reader.Lex.readQuoted(Lex.java:261)
        at com.sun.fortress.interpreter.reader.Lex.name(Lex.java:210)

というメッセージを吐いてインタプリタが落ちてしまう。FortressLibrary.jstというファイルを見ると、どうやらFortressの基本ライブラリをAST化してファイルに保存したもののようだが、このファイルの1行目で字句解析に失敗しているようだ。で、FortressLibrary.jstの1行目を見てみると、

(Component @"C:\fortress\ProjectFortress\FortressLibrary.fss",18:0~1019:3

文字列中に単独で\記号が入ってしまったため、エスケープに失敗しているように見える。たぶん、開発がUnix環境上で行われていて、Windows上での実行は考慮に入れていなかったのだろう。仕方が無いので、パス名を表す文字列中の\を全部\\に置換することに。

改めて実行してみると、今度は成功。無事、以下のように"Hello, World!"が表示された。

Parsing hello.fss with the Rats! parser: 219 milliseconds
Read C:\fortress\ProjectFortress\FortressLibrary.jst: 312 milliseconds
Hello, Fortress!
finish runProgram
671 milliseconds

追記:間違えて、出力する文字列を"Hello, Fortress!"に変更したときの出力結果を貼り付けてしまった。

次は、階乗を計算するプログラム。r xでr * xを計算することができる。

factorial.fss

component Factorial

export Executable
factorial(n) = do var r = 1 for x <- seq(1#n) do r := r x end r end
run(args:String...) :() = println(factorial(5)) end

実行結果。

Parsing factorial.fss with the Rats! parser: 218 milliseconds
Read C:\fortress\ProjectFortress\FortressLibrary.jst: 297 milliseconds
120
finish runProgram
657 milliseconds
本日のツッコミ(全1件) [ツッコミを入れる]

_ ささだ [おおー ]

本日のリンク元 | 10 | 7 | 4 | 4 | 4 | 3 | 2 | 2 | 2 | 2 | TrackBack(0)

2007-01-12

_ [Java]SunのJVM(Java6 b105)のバグ?

きしだのはてなより引用:

再現できる最低限まで削っていったら、めちゃくちゃシンプルで誰でも書いていそうなコードになりました。 びっくりします。ローカル変数の定義順を変えると挙動が変わるところが一番のみどころです。

こんな感じです。Tomcat5.5.17+Java6 b105で確認してます。 5回くらいリロードすると結果が変わります。 最後の空ループの回数を少なくすると、現象が発生するまでのリロード回数が変わります。

package servlets;

import java.io.*; import javax.servlet.http.*; public class ProblemServlet extends HttpServlet { protected void doGet (HttpServletRequest request, HttpServletResponse response) throws IOException { response.setContentType("text/html"); PrintWriter out = response.getWriter(); boolean brk = true;//preと順番を逆にすると再現しない boolean pre = false; for(int i = 0; i < 3; ++i){ int j = 0; while(j < 1){ ++j; System.out.println("ループ先頭: " + pre); if(i == 0){ pre = brk; brk = false; System.out.println("continue:" + pre); continue; } if(i == 1) brk = pre; out.println(i); if(brk) out.println("<br>"); } } for(int i = 0; i < 1000; ++i);
out.close(); } }

変数preはif(i == 0)の中でしか変更してないので、「continue」の後の「ループ先頭」での値は必ず同じになるはずです。 でも、結果が変わったときには、continueしたあとでpreの値が変わっていることがわかります。 whileを通常のfor(int j = 0; j < 1; ++j)の形にすると再現しません。continueの処理がくさいです。

マジデスカ?本当に再現するなら、かなりやばいバグですね。というわけで、自宅のPC環境(Windows XP, Java6 b105)で現象を再現できるかどうか試してみました。とはいっても、サーブレットのリロードだと再現を確認するのが面倒だし、再現できたかどうかに確信が持ちにくいので、スタンドアロンのプログラムを作って再現できるかどうか確認してみました。

…再現できちゃいました。現象を再現するコードは以下の通り。元のコードをさらに削って、バグであることがわかりやすいようにしてみました。

public class BuggyAction {
  protected static void doSomething() {
    boolean brk = true;//preと順番を逆にすると再現しない
    boolean pre = false;
    java.util.List<String> messages = new java.util.ArrayList<String>();
    for(int i = 0; i < 3; ++i){
      int j = 0;
      messages.add("pre(for loop):            " + pre);
      while(j < 1){
        ++j;
        messages.add("pre(while loop):          " + pre);
        if(i == 0){
          pre = brk;
          brk = false;
          messages.add("pre(while loop continue): " + pre);
          continue;
        }
      }
    }
    for(String message : messages) System.out.println(message);
    //-XX:CompileThreshold=1にすると、この部分は無くても現象が再現。
    //やっぱりJITコンパイラの部分の不具合か?
    for(int i = 0; i < 1000; ++i);
  }
  public static void main(String[] args) {
    //i == 3くらいで現象が発生
    for(int i = 0; i < 5; i++){
      doSomething();
      System.out.println("----------------------");
    }
  }
}

実行結果は以下の通り。青い字の部分と赤い字の部分に注目。

pre(for loop):            false
pre(while loop):          false
pre(while loop continue): true
pre(for loop):            true
pre(while loop):          true
pre(for loop):            true
pre(while loop):          true
----------------------
pre(for loop):            false
pre(while loop):          false
pre(while loop continue): true
pre(for loop):            true
pre(while loop):          true
pre(for loop):            true
pre(while loop):          true
----------------------
pre(for loop):            false
pre(while loop):          false
pre(while loop continue): true
pre(for loop):            true
pre(while loop):          true
pre(for loop):            true
pre(while loop):          true
----------------------
pre(for loop):            false
pre(while loop):          false
pre(while loop continue): true
pre(for loop):            false
pre(while loop):          false
pre(for loop):            false
pre(while loop):          false
----------------------
pre(for loop):            false
pre(while loop):          false
pre(while loop continue): true
pre(for loop):            false
pre(while loop):          false
pre(for loop):            false
pre(while loop):          false
----------------------

再び引用:

こんだけ最適化したことでプログラマとしての満足感が得られてしまったので、バグデータベースへの報告はたぶんかなり後回しになると思います。もしそういうのが得意な方がいらっしゃったら、代わりに報告していただけるとありがたいです。こんだけ簡単なコードで再現するので、すでに報告されているかもしれません。

SunのBug Databaseを検索してみましたが、私が検索した限りでは該当するバグは見つけることができませんでした。私にできるなら、バグデータベースへの報告をしたいところですが、いかんせん英語能力が…orz。

追記:さらにコードを改造して、どの段階でpreが書き換わったのかをより詳しく調べてみました。どうやら、continue直後のwhileループの継続条件条件チェックの所で、既にpreが書き換わってしまっているようです。

public class BuggyAction {
  private static boolean p(java.util.List<String> list, String header, boolean arg) {
    list.add(header + arg);
    return true;
  }
  protected static void doSomething() {
    boolean brk = true;//preと順番を逆にすると再現しない
    boolean pre = false;
    java.util.List<String> messages = new java.util.ArrayList<String>();
    for(int i = 0; i < 3; ++i){
      boolean shouldContinue = true;
      messages.add("pre(for loop):            " + pre);
      while(p(messages, "pre(while loop cond):     ", pre) && shouldContinue){
        shouldContinue = false;
        messages.add("pre(while loop):          " + pre);
        if(i == 0){
          pre = brk;
          brk = false;
          messages.add("pre(while loop continue): " + pre);
          continue;
        }
      }
      messages.add("pre(for loop last):       " + pre);
    }
    for(String message : messages) System.out.println(message);
    //-XX:CompileThreshold=1にすると、この部分は無くても現象が再現。
    //やっぱりJITコンパイラの部分の不具合か?
    for(int i = 0; i < 1000; ++i);
  }
  public static void main(String[] args) {
    //i == 3くらいで現象が発生
    for(int i = 0; i < 5; i++){
      doSomething();
      System.out.println("----------------------");
    }
  }
}

実行結果:

pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop continue): true
pre(while loop cond):     true
pre(for loop last):       true
pre(for loop):            true
pre(while loop cond):     true
pre(while loop):          true
pre(while loop cond):     true
pre(for loop last):       true
pre(for loop):            true
pre(while loop cond):     true
pre(while loop):          true
pre(while loop cond):     true
pre(for loop last):       true
----------------------
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop continue): true
pre(while loop cond):     true
pre(for loop last):       true
pre(for loop):            true
pre(while loop cond):     true
pre(while loop):          true
pre(while loop cond):     true
pre(for loop last):       true
pre(for loop):            true
pre(while loop cond):     true
pre(while loop):          true
pre(while loop cond):     true
pre(for loop last):       true
----------------------
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop continue): true
pre(while loop cond):     true
pre(for loop last):       true
pre(for loop):            true
pre(while loop cond):     true
pre(while loop):          true
pre(while loop cond):     true
pre(for loop last):       true
pre(for loop):            true
pre(while loop cond):     true
pre(while loop):          true
pre(while loop cond):     true
pre(for loop last):       true
----------------------
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop continue): true
pre(while loop cond):     false
pre(for loop last):       false
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop cond):     false
pre(for loop last):       false
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop cond):     false
pre(for loop last):       false
----------------------
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop continue): true
pre(while loop cond):     false
pre(for loop last):       false
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop cond):     false
pre(for loop last):       false
pre(for loop):            false
pre(while loop cond):     false
pre(while loop):          false
pre(while loop cond):     false
pre(for loop last):       false
----------------------
本日のツッコミ(全6件) [ツッコミを入れる]

Before...

_ みずしま [どうもありがとうございます。確認してみたところ、確かに -serverオプションを付けると正常に動作しますね。 ]

_ M田 [再現しないよ... 1.6.0-b105 on Linux 2.6.17 ]

_ みずしま [うーむ。Windows版のみの現象なんですかね。 ]

_ M田 [Windows版では再現しました。もっと短いコード(doSomethingのみ) : protected st..]

_ M田 [とりあえずレポートしてみました。 ]

本日のリンク元 | 6 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | TrackBack(0)

2007-01-13

_ [Fortress]配列リテラル

Fortressは、普通のプログラミング言語ですから、当然配列を使えるわけです。配列型の変数の宣言構文は次のような感じで、これはまあ全然すごくないというか普通です。ちなみに、ZZ32は32bit整数型です。Fotressの言語仕様をちゃんと読んだわけじゃないので、間違ってる可能性もありますが、とりあえず整数型であることは間違いないようです。

arr :ZZ32[3, 3] (* 3*3の2次元配列を宣言 *)

さて、配列をあらかじめ決まった要素で初期化するのにいちいち順番に代入していくのは面倒ですから、Fortressでも他言語のように配列のリテラル表記を使うことができます。

arr :ZZ32[3, 3] = [ 9 8 7
                    6 5 4
                    3 2 1 ]

改行によって配列の行の終わりを示せるというのは、まあ良いでしょう。面白いのは、配列の要素のセパレータとして空白を使うことができるところです。え、面白く無い?いやいや、前回のFortressに関するエントリに書いたのですが、Fotressではx yのように空白で区切って式を並べて書くことで、乗算を書くことができるのです。Fortressの配列リテラルの中では、通常の計算式を書くことができますから、単純に考えて文法を設計したら、

arr :ZZ32[3, 3] = [ (9 8 7)
                    (6 5 4)
                    (3 2 1) ]

のように解釈されてしまうと思うわけです。で、こんな文法になっているということは、「配列リテラルの中に出現する式」だけを特別扱いしているに違い無いと思い、Rats!で書かれたFortressの文法を読んでいたら、案の定そうなっていました。Literal.ratsファイルから該当すると思われる箇所を引用すると、

Expr Literal =
     openparen w closeparen
     { yyValue = new VoidLiteral(createSpan(yyStart,yyCount)); }
   / yyValue:NumericLiteral
   / yyValue:CharLiteral
   / yyValue:StringLiteral
   / opencurly w a1:Entry a2s:(w comma w Entry)* w closecurly
     { List<com.sun.fortress.interpreter.useful.Pair<Expr,Expr>> elements =
           new ArrayList<com.sun.fortress.interpreter.useful.Pair<Expr,Expr>>();
       elements.add(new com.sun.fortress.interpreter.useful.Pair<Expr,Expr>(a1.getKey(), a1.getValue()));
       for (Entry e : (List<Entry>)a2s.list()) {
           elements.add(new com.sun.fortress.interpreter.useful.Pair<Expr,Expr>(e.getKey(), e.getValue()));
       }
       yyValue = new MapExpr(createSpan(yyStart,yyCount), elements);
     }
   / opensquare w yyValue:RectElements w closesquare ;

/* RectElements ::= NoSpaceExpr MultiDimCons* */ MultiDim RectElements = a1:NoSpaceExpr a2s:MultiDimCons* { if (a2s == null || a2s.isEmpty()) yyValue = new MultiDimElement(a1.getSpan(), a1); else yyValue = FortressUtil.multiDimCons(a1, a2s.list()); };
/* MultiDimCons ::= RectSeparator NoSpaceExpr */ com.sun.fortress.interpreter.useful.Pair<Integer,Expr> MultiDimCons = a1:RectSeparator a2:NoSpaceExpr { yyValue = new com.sun.fortress.interpreter.useful.Pair<Integer,Expr>(a1,a2); };

赤字で強調したところがポイントで、おそらく配列リテラル中では「NoSpaceExpr」だけが出現できるということなんでしょう。で、この「NoSpaceExpr」が一体何なのかということですが、これは定義が複雑なのでとりあえず置いておきますが、ただ単に「スペースを含まない式」では無いようです。というのは、スペースで区切った式でも()で囲むことで配列リテラル中に書けるからです。

本日のツッコミ(全3件) [ツッコミを入れる]

_ 斎藤ただし [こういうのは、Rats! or Packrat一般であるからやりやすい、みたいなところがあるのでしょうか(という素人..]

_ Ryo [Fortressの並列化支援やらについてのエントリきぼんです #なんかうさんくさいんですよねー ]

_ みずしま [斎藤ただしさん: > Rats! or Packrat一般であるからやりやすい、みたいなところ これについては、後..]

本日のリンク元 | 4 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | TrackBack(0)

2007-01-18

_ [Java]JDK6 b105のバグ、修正済

先日のエントリで話題にしたJDK6のバグだが、既に修正コードができているらしい。

きしだのはてなから引用:

神谷さんによれば、すでにコードは修正されたとのこと。
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6512534

ということで、一安心。それにしても、対応早いなあ。

本日のリンク元 | 53 | 30 | 15 | 6 | 5 | 4 | 3 | 2 | 1 | 1 | TrackBack(0)

2007-01-26

_ [パーザ]Packrat Parsingの嬉しさ

1/13のエントリのコメント欄で、斎藤ただしさんから

こういうのは、Rats! or Packrat一般であるからやりやすい、みたいなところがあるのでしょうか

というツッコミがあり、それに対して後で説明するということを書きつつ、今日まで説明してこなかったが、これから説明してみることにする。とはいえ、これから説明するのはPackrat Parsingの利点のうちのほんの一部なので、その辺は注意していただきたい。

まず前提として、今日一般的に使われている、プログラミング言語用の多くの構文解析アルゴリズムでは、構文解析アルゴリズムの都合上、構文解析より前の段階で字句解析処理を行う必要がある。字句解析は、よく知られているように、文字の列を解析し単語(トークン)の列に分解するという処理だが、このとき、文字列リテラルなど、開始記号 任意の文字の繰り返し 終了記号という並びになるものは通常、ここで処理され、単一のトークンになる。

さて、Rubyなどのスクリプト言語では、文字列リテラルの中に任意の式を埋め込む構文をサポートしているものがある。Rubyなら、"1 + 1 = #{1 + 1}"といった具合だ。

このような構文を扱う場合、文字列リテラルという字句解析で処理される構造の中に式という構文解析で処理される構造が埋め込まれているという点が問題になる。一般的に字句解析器は構文解析器とは分離しているため、字句解析器はその言語の構文を知らない。また、通常の字句解析器生成系(lexなど)は正規言語しか扱うことができないため、式のようにネストした構造を扱うことができない。このような構文を扱うためには、たとえば字句解析器と構文解析器が連携する必要がある。具体的には、字句解析器に文字列中であるか通常の式の中であるかという状態を持たせ、構文解析器の方から、文字列リテラル中で埋め込み式の開始位置に到達したときに「ここから式が始まるよー」というイベントを伝えて、字句解析器の状態を明示的に遷移させてやる必要がある。

一方、Packrat Parsingは字句解析という前処理が存在せず、文字列をそのまま構文解析することができる構文解析アルゴリズムである。そのため、上のような式を埋め込み可能な文字列リテラルも単純に、'"' ('#{' 式 '}' | 文字)* '"'のような構文として記述することができる。

他にも無限長の先読みをサポートしているとかバックトラックがあるとか嬉しい点があるのだが、とりあえずはここまで。

本日のツッコミ(全10件) [ツッコミを入れる]

Before...

_ みずしま [> なんか2つ(flex+bison)が1つで済んで「簡単」でかつ > 「柔軟」? > て、画期的だ。時代ハ進ンデイ..]

_ M田 [> LexのかわりにYaccを使えば、Yaccだけで完結するかな? 字句レベルパーザは、yylex()の本体がg..]

_ 斎藤ただし [みずしまくん> JavaCCとかANTLRとか みずしまくん> SableCCとか なるほど、だからJavaCCだ..]

_ rui [どうもはじめまして。植山といいます。Gauche向けのPEGコンビネータパーザを作っていたりします。 http://..]

_ みずしま [どうもはじめまして。確かに今回述べている利点は、 Packrat Parserそのものというより、PEGパーザの利点..]

本日のリンク元 | 8 | 4 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | TrackBack(0)

Mizushima Kota/e-mail: i021216{at}coins.tsukuba.ac.jp/SKype ID: mizu_standard