uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかReactとかFregeとかJavaとか -

Javaにも不変データ構造に基づいた(Cons セルベースの)リストがあるのだよ

TL;DR

JDK(tools.jar)中、com.sunパッケージ配下に、javacが内部的に使っている「com.sun.tools.javac.util.List 」が含まれており、これは不変データ構造としてのリストのように(Cons セルベースのリストのように)利用できる。

はじめに

ScalaのコードをGroovyやJavaなどに移植する際に、いつも悲しい思いをするのが不変データ構造に基づいたリスト処理ライブラリが見あたらない、ということでした。JDKの標準コレクションライブラリには、Scalascala.collection.immutable.Listのような、不変データ構造を用いて実装されているリストがありません。

ここで言う不変データ構造に基づいたリストとは、JDKjava.util.Collections.unmodifiableList()等で取得できるような変更禁止ビュー、つまり「要素追加などを禁止するバージョンのリスト」のことではなく、あるいはGrooovyの@Immutableによるイミュータブル指定でもなく、

「要素の追加は可能だが、その意味は、元のリストの変更ではなく、要素が追加された新しいリストを返す」

というもので、さらに実装として「リストを丸ごとコピーして追加して返す」のではなく、「追加前のリストと実体を共有することによって、メモリ利用効率を下げない(そして追加前のリストは不変であることも保証される)」ことが期待されます。もう少しぶっちゃけて言えば、Lispの「ConsセルベースのList」が欲しいのです*1

もちろん、サードパーティ製のものもあるにはあるでしょう。Functional javaのとかClojureのを使うとかはできるのかな。しかし基本的にはやみくもには外部依存を増やしたくはないものです。自分で作りたくもない。

com.sun.tools.javac.util.List

最近知ったのですが、少なくともjava8までのJDKには、com.sunパッケージ配下に「com.sun.tools.javac.util.List 」というクラスがあり、これがまさに求めるものです。ただし、com.sunパッケージにあることから判るように標準APIの一部ではなく、将来的に使える保証はありません。もし使う場合は、将来使えなくなるリスクを覚悟して使う必要があります。さらに、rt.jarではなくtools.jarに含まれているので、JREとしては使用できずJDKの元で使えるものです。javaコマンドから利用する場合、tools.jarをクラスパスに指定することが必要となるでしょう。

※ @kmizuさんにご指摘いただきましたが、これはコメントに記載があるようにGJCつまりGeneric Java Compiler由来のもので、確かこれはScalaのMartin Oderskyさんの関わっていたプロジェクトではないですか。ある意味ご縁があるわけです。

使い方

com.sun.tools.javac.util.Listの機能としてはこんな感じ。

意味(適当な表記) 書き方
nil List.nil()
car(a) a.head
cdr(a) a.tail
cons(a,b) b.prepend(a)
[a,b,c] List.of(a,b,c)

使用例

これを使えば、例えば2リストキューを用いた非破壊的キューもほらこのとおり(cf.20分でわかるPurely Functional Data Structures)。

import com.sun.tools.javac.util.List;
import java.util.function.*;

public class Queue<E> {
    public static class Tuple<E> {
        E value;
        Queue<E> queue;
        Tuple(E value, Queue<E> queue) {
            this.value = value;
            this.queue = queue;
        }
    }

    private List<E> front;
    private List<E> rear;

    public Queue(List<E> front, List<E> rear) {
        this.front = front;
        this.rear = rear;
    }
    public Queue() {
        this(List.nil(), List.nil());
    }

    long size() { return front.size() + rear.size(); }

    public String toString(){ return "front<"+front+rear.reverse()+">rear"; }

    public Queue<E> add(E e) {
        return new Queue<E>(front, rear.prepend(e));
    }
    public Tuple<E> remove() {
        if (front == List.nil()) {
            if (rear == List.nil()) {
                return new Tuple<E>(null, this);
            }
            return new Queue<E>(rear.reverse(), List.nil()).remove();
        }
        else {
            return new Tuple<E>(front.head, new Queue<E>(front.tail, rear));
        }
    }
}

Groovyでさらに

Groovyでは以下の点で使いやすいです。

  • tools.jarは標準でGroovy実行時のパスに入っている
  • 名前のかぶるListではなく、「import com.sun.tools.javac.util.List as ConsList」のようにリネームしてインポートできる。

なお、残念ながらGroovyでは右結合の演算子オーバーロードできないので、ScalaHaskellの::のようにカッコなしで要素繋げる表記を使用することはできません(AST変換を使わないかぎり)。

もっと、もっと…欲しいんじゃっ…!

連想リストのマップっぽく使えるようした物が欲しいですが、それは見つけられませんでした(実装するのはたぶん難しくない)。

Purely Functional Data Structures
Chris Okasaki
Cambridge University Press
売り上げランキング: 50,281
Purely Functional Data Structures
Chris Okasaki
Cambridge University Press
売り上げランキング: 242,093

*1:LispのListが実際に不変であるか、といえば、実はそうではない。rplaca/rplacdといった破壊的操作があるから。以下で紹介するjavac.tools.Listも同じ。だとすると「不変データ構造と呼ぶべきか」が怪しいといういか間違い。本稿では「不変データ構造のように使えるリスト」として記載。(本件、@yasushia さんにもご指摘いただきました。ありがとうございます。)

JCUnitのBuilder APIをためす

以前、以下の記事で紹介した、JCUnitの開発がすすんでいます。(開発ブログ, ソース)

uehaj.hatenablog.com

主な拡張としては、状態機械をモデリングしてテスト生成ビルダーAPIの整備などなど*1

Spockからの利用サンプルをかきなおしてみました。ビルダーAPIを使用しています。

@Grab('com.github.dakusui:jcunit:0.5.4')
@Grab('org.spockframework:spock-core:1.0-groovy-2.4')
import com.github.dakusui.jcunit.core.factor.Factors
import com.github.dakusui.jcunit.core.factor.Factor
import com.github.dakusui.jcunit.generators.TupleGenerator
import com.github.dakusui.jcunit.core.FactorField;
import com.github.dakusui.jcunit.core.tuples.Tuple;
import com.github.dakusui.jcunit.constraint.constraintmanagers.ConstraintManagerBase;
import com.github.dakusui.jcunit.constraint.ConstraintManager;
import com.github.dakusui.jcunit.exceptions.UndefinedSymbol;
import spock.lang.*

class HelloSpec extends Specification {

    static ConstraintManager closureConstraintManager(names, Closure clos) {
        return new ConstraintManagerBase() {
            @Override
            boolean check(Tuple tuple) throws UndefinedSymbol {
                Binding binding = new Binding()
                names.each {
                     if (!tuple.containsKey(it)) {
                         throw new UndefinedSymbol(it)
                     }
                     binding.setProperty(it, tuple[it])
                }
                clos.delegate = binding
                clos.call()
            }
        }
    }

    static Collection genPairwiseTestData(Map factors, Closure constraint = null) {
        def builder = new TupleGenerator.Builder()
        if (constraint != null) {
            builder = builder.setConstraintManager(closureConstraintManager(factors.keySet(), constraint))
        }
        builder.setFactors(new Factors(factors.collect{k,v -> new Factor(k, v)}))
        .build()
        .collect{ it.values() };
    }

    static intLevels =  [ 1, 0, -1, 100, -100, Integer.MAX_VALUE, Integer.MIN_VALUE ];
    static stringLevels = [
        "Hello world", "こんにちは世界", "1234567890", "ABCDEFGHIJKLMKNOPQRSTUVWXYZ",
        "abcdefghijklmnopqrstuvwxyz", "`-=~!@#\$%^&*()_+[]\\{}|;':\",./<>?", " ",
        "" ]

    @Unroll
    def "分配法則(a=#a,b=#b,c=#c)"() {
    expect:
        c*(a+b) == c*a + c*b
    where:
    [a,b,c] << genPairwiseTestData([a:intLevels,
                                    b:intLevels,
                                    c:intLevels])
    }

    @Unroll
    def test1() {
    expect:
        c*(a+b) == c*a + c*b
    where:
    [a,b,c] << genPairwiseTestData([a:intLevels,
                                    b:intLevels,
                                    c:intLevels], { return a > 0 && b != c })
    }

    @Unroll
    def test2() {
    expect:
        (a+b).size() == a.size() + b.size()
    where:
    [a,b] << genPairwiseTestData([a:stringLevels,
                                  b:stringLevels])
    }

    @Unroll
    def test3() {
    expect:
        a+b == b+a
    where:
    [a,b] << genPairwiseTestData([a:[1,2,3],
                                  b:intLevels])
    }

    @Unroll
    def test4() {
    expect:
        a == b || a != b
    where:
    [a,b] << genPairwiseTestData([a:MyBoolean.values() as List, b:MyBoolean.values() as List])
    }

}

enum MyBoolean {
    True,
    False
}

以前のようにアノテーションを使用せずとも使用できるようになりました。

気付いた点としては、

  • 各型のレベルのデフォルト値をAPIクラスからうまく参照できなかったので自前で定義しています。 (上記の static intLevels = [ 1, 0, -1, 100, -100, Integer.MAX_VALUE, Integer.MIN_VALUE ]の部分)
  • SpockのデータパイプAPIにもうちょっと柔軟性が欲しい。今の呼び出し方だとデータ指向テストの疑似変数名の指定に重複があるので、疑似変数名を取得もしくは設定できるAPIがあると良いのだが。Spock Extensionで触れるフックがあるかな。

など。楽しいです。

*1:他に、生成テストデータの保存、再生などもなされているようです。

Java VM上の言語の覇者を決める(但しJava以外)スクリプトボウルの履歴

米国開催のJavaOneカンファレンスで恒例の人気セッションとなっている「スクリプト・ボウル」というのがあります。Java VM上で動作する言語同士のガチ勝負で、コード例とか、技術力とかいろいろな側面からパネルセッションでバトルして、その年勝者を決める、というものです。

自分では残念ながら直接見たことはないので想像ですが、「朝まで生テレビ」で言語バトルするようなものです。違うか。

エンターテイメント要素も多々あるでしょうし、人気とか「情熱」みたいなのも評価されるかもしれないし、コミュニティの「動員力」とかの要素もひょっとしたらあるかもしれませんね。そういうものも含めて、おもしろい勝負なのではないかと思います。もちろん技術者同士でやってるので、技術的なおもしろみとかもあるでしょう。プレゼンのうまさとかもあるでしょう。

んでその過去の結果をまとめてみました。

候補結果
2008Scala,Groovy,JRuby,Jython JRuby優勝 リンク
2009Scala,Groovy,JRuby,Jython,Clojure Groovy優勝 リンク
2010Scala,Groovy,JRuby,Clojure Groovy優勝 リンク
2011Scala,Groovy,JRuby ScalaとGroovyが同位優勝 リンク*1
2012Scala,Groovy,JRuby,Clojure Scalaが優勝 リンク
2013Scala,Groovy,Nashorn,Clojure Groovyが優勝 リンク

圧倒的じゃないか!!
とか言ってみる。
少なくとも皆勤賞ではある。

*1:リンク先を見るとScalaの人は相当納得してない。

オフラインどう書く第九回の問題をJava 8 Lambdaでやってみた。

という記事を書きましたが、今回はJava 8 Lambda式を使って書きなおしてみました。

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

class BusJava8 {
  
  int ceil10(int n) { return (int)(Math.ceil(n/10) * 10); }
  
  int half(int n) { return ceil10(n/2); }
  
  List parse(String input) {
    String[] tmp = input.split(":", 0);
    String p = tmp[0];
    String list = tmp[1];
    return Arrays.asList(Integer.parseInt(p), Arrays.asList(list.split(",", 0)));
  }
  
  int calc(int basePrice, List<String> passengers) {
    Map<String,Function<Integer,Integer>> map = new HashMap<>();
    map.put("An", (Integer it)->it);
    map.put("Ap", (Integer it)->0);
    map.put("Aw", (Integer it)->half(map.get("An").apply(it)));
    map.put("Cn", (Integer it)->half(map.get("An").apply(it)));
    map.put("Cp", (Integer it)->0);
    map.put("Cw", (Integer it)->half(map.get("Cn").apply(it)));
    map.put("In", (Integer it)->half(map.get("An").apply(it)));
    map.put("Ip", (Integer it)->0);
    map.put("Iw", (Integer it)->half(map.get("In").apply(it)));
    Map<String,List<List>> groups =passengers.stream()
      .map(it -> Arrays.asList(it, map.get(it).apply(basePrice)))
      .collect(Collectors.groupingBy(it -> (((String)it.get(0)).substring(0,1))));
    long size = (long)(groups.get("I").size()-groups.get("A").size()*2);
    groups.get("I").sort((a, b) -> (Integer)(a.get(1)) - (Integer)(b.get(1)));
    List<List> tmp = new ArrayList(groups.get("A"));
    tmp.addAll(groups.get("C"));
    tmp.addAll(groups.get("I").stream().limit(size).collect(Collectors.toList()));
    return tmp.stream().mapToInt(it->(Integer)it.get(1)).sum();
  }
  
  static void test(String input, String answer) {
    Java8 b = new Java8();
    List tmp = b.parse(input);
    int basePrice = (int)tmp.get(0);
    List<String> passengers = (List<String>)tmp.get(1);
    int expected = Integer.parseInt(answer);
    int result = b.calc(basePrice, passengers);
    assert result == expected;
  }

  public static void main(String[] args) {
      test("1480:In,An,In,In,In,Iw,Cp,Cw,In,Aw,In,In,Iw,Cn,Aw,Iw", "5920");
  }
}

上では、自分がJava8に全く不慣れなため、非効率・冗長な記述をしているところがあるかもしれません。また、そもそも元のクロージャを駆使したアルゴリズムがGroovy向きだった、など比較としてはフェアではないかもしれませんので、ご留意を。Java 8Lambdaの仕様も未確定だと思いますので、現時点でのeaでの仕様であることも注意ください。

で、感想を言うと、こりゃ書くのたいへんだわ、です。Java8の補完対応IDEを使わなかったこと、などもあると思いますが…。あと結構エラーメッセージが怖いです。たとえば

Java8.java:28: エラー: 不適合な型: 推論変数Rには、不適合な境界があります .collect(Collectors.groupingBy(it -> (((String)(it.get(0))).substring(0,1))));
^
等価制約: Map>>
上限: Map,Object
R,Tが型変数の場合:
メソッド collect(Collector)で宣言されているRはObjectを拡張します
インタフェース Streamで宣言されているTはObjectを拡張します
INT#1,INT#2がintersection型の場合:
INT#1はObject,Serializable,Comparableを拡張します
INT#2はObject,Serializable,Comparableを拡張します

とか。型指定を1つ間違えただけで上のメッセージは…。

他に、Groovyと比べると、例えLambdaを使っても、

  • オペレータオーバーロードが無い
  • Collectionとstreamが別ものである
  • リストやマップリテラルが無い
  • 破壊的ではないリストの結合とかsortとかが無い(見付けられなかっただけかも…)ようなので、メソッドチェインが途切れてしまうのも気になります

などにより、冗長性は高くなるようです。シンプルなケースを除き、高階関数をバリバリ使って関数型ライクに書くのは余り積極的になれない気がしました。リリースまでには多くが解決されてしまうかもしれませんが*1

Lambda式の良い点は、GroovyのCompileStticに比べても、型推論の精度が高いということ。GroovyのCompileStaticでは、クロージャの戻り値の型は推論に寄与してないようで、チェインすると2個目以降に明示指定が必要になります。

さて、速度はどうだったか、などはJJUG CCC 2013 Springのセッションにて(ステマ)。

*1:まあ、lambdaの主眼はマルチコア細粒度並列処理と言われているので、もしそうなら通常の処理にあえて使う必然性もないわけですけれども。

てっとり早くGroovyでJava8のLambdaを使う

追記
http://groovy.codehaus.org/Groovy+2.3+release+notes#Groovy2.3releasenotes-OfficialsupportforrunningGroovyonJDK8

groovy 2.3以降、Goovyクロージャはfunctinal interface(sum型)が要求される場所で使用される場合、自動的にそのインターフェースに変換されるようになりました。

Groovy-MLで議論も始まっており、Groovyは将来的にはJava8正式対応するかと思いますが、世の中ではJava8アーリーアクセス版とかで話題になってるので、試してみました。

シンタックスのレベルでは、当然GroovyはLambda式を扱えませんが(決まってないし!)、Lambda式の実装がSAM型のサブクラスのインスタンスであることを踏まえると、以下のように例えばExpandoMetaClassでアダプタを定義してやれば、クロージャでJava8のStreamを叩けるわけです。

import java.util.function.*
import java.util.stream.Stream

class StreamTest {
  static test01() {
    List<String> names = ["hoge hoge", "foo bar", "junji", "uehara"]
    names.forEach{ println it }
  }
  
  static test02() {
    List<String> names = ["hoge hoge", "foo bar", "junji", "uehara"]
    names.stream()
      .filter { it.length() > 5}
      .map {"[" + it + "]"}
      .forEach{ println it }
  }
  
  static main(args) {
    Iterable.metaClass.forEach = { Closure clos -> delegate.forEach(new Consumer(){ void accept(arg){ clos.call(arg) }}) }
    Stream.metaClass.forEach =  { Closure clos -> delegate.forEach(new Consumer(){ void accept(arg){ clos.call(arg) }}) }
    Stream.metaClass.filter = { Closure clos -> delegate.filter(new Predicate(){ boolean test(arg){ clos.call(arg) }}) }
    Stream.metaClass.map = { Closure clos -> delegate.map(new Function(){ Object apply(arg){ clos.call(arg) }}) }
    test01()
    test02()
  }
}

もちろんこんなことしなくても上のレベルはGroovyだけでできるし、無限長コレクションを使いたければGroovy Stream(github)というのもあるんだけど、上はあくまでJdkAPIのStreamをGroovyのクロージャで利用している、というところがポイントです。

先のMLでの議論にあるように、クロージャとLambda式では得失がある*1ので、将来のGroovyにおいて、クロージャとLambda式が併存するのか、クロージャに一本化するべきなのか、その逆か、実装は、などはこれからの議論ということになるのでしょう。

使用したJava8のバージョンは

java full version "1.8.0-ea-lambda-nightly-h4200-20130429-b88-b00"

です。

参考:

*1:例えばGroovyのクロージャにおけるローカル変数のキャプチャは実効finalとかではなくリファレンスを経由してアクセスするので、値を変更できる代りにローカル変数アクセス時のオーバーヘッドがある

JavaOne 2012 Tokyo/JVM言語BOF

JavaOne Tokyoに参加しています。
表記のBOFにはスピーカーの一人として参加致しました。資料はこちら。

直前の暴風雨で、予定していた懇親会が流れたせいで(?)、慣れ合い/筋書き/打ち合せなしのガチンコ勝負へ…。

@yuyoroさんの究極の秘密兵器とその崩壊、唖然とさせるダッシュボード、「Javaは○○だし」暴言などなど、個人的にも最も楽しかったセッションでした。

客観的に見ると、マイナー言語同士で争ってどうすんだ、って話ではありますが、id:nobeansさんの奮闘の甲斐あり、Groovyがめでたく1位に(ぱちぱち)。でも、さすがの@nahiさんによるJRuby with indyの性能は素晴しい。Scalaのパターンマッチうらやましい。@tmizuさんの冷静なつっこみ、id:kiy0taka さんの司会もすばらしす。奥さんの投票アプリ*1はGroovyFXというのも加点ポイントだったか。LTでは明らかに理解している人が僅少であろう型プログラミングの話題や、Jrubyのコミッターはいい人(これが唯一の和む話題)とか、Oracleの牙城でうっかり禁句のAndroidのgradle試験の話題をだす@kyon_mmさん、などみんな楽しい。これがBOFの醍醐味かと。@toby55kijさんの的確な時間管理のおかげで流れも良く終りました。みなさん、おつかれさまでしたありがとう。
次回は完膚なきまでに打ちのめしますのでまたやりましょうw
だれかTogetterでまとめてくれないかのう。

(追記)
id:orangecloverさんがまとめてくれました。たいへんありがとうございました。
http://togetter.com/li/283845

*1:この堅牢たる高可用性・ハイスケーラブルアプリの裏話はLTで明らかになりましたが、愕然。

GVM: GroovyでJavaVMを書いたよ

前置き

さてやっと発売日となりました、私も著者の一人として執筆に参加している「プログラミングGroovy」ですが、ご覧になった方もいらっしゃると思います。

プログラミングGROOVY
プログラミングGROOVY
posted with amazlet at 11.07.06
関谷 和愛 上原 潤二 須江 信洋 中野 靖治
技術評論社
売り上げランキング: 4587

興味がありましたら読んで見てください。Groovy普及の1助になれば幸いです。Javaプログラマであれば読んで損はない本だと思います。

ghello

さて、発売日といえば、昨日は著者の1人である関谷さん(id:ksky)が、#ghelloというイベント(まとめサイトGoogleキャッシュ)を行っていて、これはみんなでGroovyでいろいろな「Hello World表示プログラム」を書いて、Twitterで#ghelloタグつけて発言する、というもので、なかなか盛り上りました。私も及ばずながら2、3個ツィートして見ました。2番目の「ぉうききぐじぐこきぅ」というのがちょっと狂気入ってそうな感じでお気に入りです。



良い企画だったと思います。ただ、Twitterなので140文字(しかもハッシュタグと次の人指名含めて)制限があり、これが予想外に厳しくて、ストレスが溜る溜る。

GVM: JVM Written in Groovy

なので、カッとなって、文字数制限なしで作ってみました*1。方針としてはGroovyでJava VMを書いてその上でHello Worldを表示させるJavaコード(コンパイルしたクラスファイル)を動作させる。

コードはgistに公開しましたのでリンクしておきます。本体は長いのでこのエントリには末尾に貼っておきます。

以下は実行例です。

$ cat Hello.java
package sample;
public class Hello {
    public static void main(String[] args){
        Hello h = new Hello();
        h.hello();
        System.out.println(h.plus(1,2));
        for (int i=0; i<10; i++) {
            System.out.print("i=");
            System.out.println(i);
        }
    }
    void hello() {
        System.out.println("Hello World");
    }
    int plus(int i, int j) {
        return i+j;
    }
}
$ mkdir classes
$ javac -d ./classes Hello.java
$ groovy ./gvm.groovy -cp classes sample.Hello
Hello World
3
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9

$ groovy ./gvm.groovy -h
usage: groovy gvm.groovy <class FQCN>
 -cp,--classpath <arg>   classpath
 -demo,--demo            demo
 -h,--help               usage
 -v,--verbose            verbose

デモモード(-demo)もあるので、Javaソースを作ったりjavacしなくてもgvm.groovy単体で実行することができます。

クラスファイルの読み込みとクラス構造やバイトコードの保持については、asmにすべて任せて*2さぼっています。asmはGroovyに組みこまれているバイトコード操作用のライブラリです。Groovy自体がasmによるバイトコード生成に依存して動作しています。

機能的には、足し算はできるが掛け算は(サンプルコードに含まれてないので)実装してないとか、読み込めるクラスは1つでディレクトリのみからでjarは対象外とか、そんな極小な感じです。

Java VMは前から一度は実装してみたいなと思ってて、Groovyなら短時間でできるだろうと思ってやってみました。確かにわりと簡単にはできたのですが*3、適当に作りすぎたのであんまり勉強にはならなったorz。

工夫としては、asmのバイトコード命令をあらわすクラス群(*InsnNode)にmetaClassで「.eval()」メソッドを注入しているところで、これによってコード量が劇的に削減され、単純化されてるんじゃないかと思います。一般に、JavaのクラスライブラリやAPIと連携したりカスタマイズしたりして動くコードを書くのは、Groovyの右に出るものは無いわけです。

Groovyの書き易さは、あらためて本当に体感しました。いやこれはほんとに凄い技術です。Javaで書く気には到底ならないなあ。

Groovy Rocks!

gvm.groovyコード

*1:というのはウソで、半分ぐらい正月につくって放置してましたのを一区切りつけただけです。

*2:asmだとクラスファイルフォーマットの汚いところ(コンスタントプールでlong値は2エントリ取る)とか見えなくなるので逆に味けない。

*3:開発工数は子育てしながらで合計3〜4日ぐらい。