2013-12-23

Groovyで内包表記を作ってみた #gadvent

G*アドベントカレンダー2013第23日目の記事です。

大域AST変換と拡張メソッドを使って、Groovyでリスト内包表記を使えるようにしてみます。

リスト内包表記(list comprehension)というのは、HaskellとかScalaとかPythonにも似たものがある便利な言語機能であり、宣言的にリストを構築するためのものです。通常、ループを回したり、あるいはcollect()やfindAll()などの一連の関数呼び出しで作るところを、要素が満たすべき条件を与えることでリストが構築されます。

実装方法とソースコードの入手先(github)

ソースはこちら。

変数が1つの単純な例

以下、サンプルコードです。

import groovyx.comprehension.keyword.select;   // ....(1)

def list = select(n) { n:1..10 }   // ....(2)
assert list == [1,2,3,4,5,6,7,8,9,10]

(1)のようにクラスgroovyx.comprehension.keyword.selectを明示的にimportすることで(2)の内包表記構文が使用できるようになります*1。

なお、

import groovyx.comprehension.keyword.select as foreach;   // ....(*)
def list = foreach(n) { n:1..10 }

のようにimport asを使ってリネームすることで、内包表記を指定するキーワードをselect以外の別のもの(上ではforeach)に変更することもできます。

利用設定

Gradleでの使用方法

内包表記を利用するための拡張モジュールのバイナリjarを、githubのgh-pagesリポジトリにmaven リポジトリの形でアップロードしてあるので、Gradleから使用するにはbuild.gradleで例えば

gradle 1.7 or later:

apply plugin: 'groovy'

repositories {
    jcenter() // specify jcenter
}

dependencies {
    groovy 'org.codehaus.groovy:groovy-all:2.2.1'
    compile 'org.jggug.kobo:groovy-comprehension:0.3'
//  compile 'org.jggug.kobo:groovy-comprehension:0.3:java8'
    testCompile 'junit:junit:4.11'
}

のように指定します。
Gradle 1.7 以前のバージョンでは上記repositriesのところを以下のようにします。

repositories {
    maven {
        url "http://jcenter.bintray.com/"
    }
}

(上記は2014.4修正。JCenterに登録したため)

Jarを手動で取得する方法

こちらから直接groovy-comprehension/0.3/groovy-comprehension-0.3.jarを取ってきて、CLASSPATHの通っているところ、例えば~/.groovy/libなどに置くか-cpオプションなどで指定してください。

Grape/@Grabによる使用

以下のようにGrapeの@Grabアノテーションを指定します。

@GrabResolver(name="maven-repo", root="https://raw.github.com/uehaj/maven-repo/gh-pages/snapshot")
@Grab("org.jggug.kobo:groovy-comprehension:0.3")(JCenterに登録したのでGrabResolver指定は不要になりました)

@Grab("org.jggug.kobo:groovy-comprehension:0.3")
import groovyx.comprehension.keyword.select

以下で指摘したgroovyのバグは修正されましたので今は問題なく使用できます。(GROOVY-6446,GROOVY-6447)

注意!
現在のGroovyのバージョン2.2.1において、Grape/@Grabで拡張メソッドを使用すると、JDK7では、不定のタイミングで無効になるときがある(メソッドが拡張されない)という現象に遭遇してしまいました*2。さらにJDK8 eaでは拡張メソッドは常に無効となってしまいます。拡張モジュールの拡張メソッドがgrapeからそもそも使用可能なのかは明確ではないのですが。バグ報告チケットは切っておきましたGROOVY-6446,GROOVY-6447が将来修正されるかどうかは不明です。
拡張メソッドが有効になっていないと以下のような例外が発生します。

Caught: groovy.lang.MissingMethodException: No signature of method: groovy.lang.IntRange.bind() is applicable for argument types: (sample1_2$_run_closure1) values: [sample1_2$_run_closure1@5587f3a] :

~~もし、このような問題が発生するなら、gradleやmavenを使用するか直接jarを使用してください。~~

文法解説

先の例の

def list = select(n) { n:1..10 }  // ....(A)

の(A)が内包表記の使用です。意味は、1から10の範囲のnを取ってくる、ということです。つまりこの場合(A)は

list = 1..10

と同じ意味です。なお、(A)は

def list = select { n:1..10; yield(n) }  // ....(B)

と書くこともでき、意味は等価です。

制約条件(Guard)を付ける

「nが偶数」という条件を以下のように追加することもできます。

def list = select(n) { n:1..10; n%2 == 0 }
assert list == [2,4,6,8,10]

「n:1..10」の次に、nが満すべき条件式「n%2 == 0」をガードとして列挙します。
上記は

def list = select(n) { n:1..10; guard(n%2 == 0) }
assert list == [2,4,6,8,10]

と書くこともできます。guard指定しようとする式が、実行時にboolean型の値を返すなら、guardを省略することができるということです。この機能をAuto Guardと呼んでいます(オリジナルの工夫)。

複数の条件を指定することもできます。

def list = select(n) { n:1..10; n%2 == 0; n%3 ==0 }
assert list == [6]

上記は「n%2 == 0 && n%3 ==0」のように&&で繋げたのと同じ意味です。

変数が2つの例

複数の変数を指定できます。以下では、nに加え、変数mの指定を範囲'A'..'B'で追加しています。

def list = select(n+m) { n:1..10; m:'A'..'B' }
assert list == ['1A', '1B', '2A', '2B', '3A', '3B', '4A', '4B', '5A','5B',
                '6A', '6B', '7A', '7B', '8A', '8B', '9A', '9B', '10A', '10B']

この場合、変数nとmのすべての組み合わせに対してn+mを計算したものをリストとして得ることができます。上記は以下と等価です。

def list = []
for (n in 1..10) {
     for (m in 'A'..'B') {
         list += (n+m)
     }
}
assert list == ['1A', '1B', '2A', '2B', '3A', '3B', '4A', '4B', '5A','5B',
                '6A', '6B', '7A', '7B', '8A', '8B', '9A', '9B', '10A', '10B']

変数2つに制約条件を組合せる

以下のようにさらに制約条件を付けることもできます。

def list = select(n+m) {
             n: 1..10
             n%2 == 0 // 偶数
             m: 'A'..'B'
           }
assert list == ['2A', '2B', '4A', '4B', '6A', '6B', '8A', '8B', '10A', '10B']

ピタゴラス数を求める

ちょっと応用的な例として、方程式「a ^ 2 + b ^ 2 == c ^ 2」を満たす数の組(ピタゴラス数)を求めてみます。cを長辺、a,bを他の辺とする直角二等辺三角形の辺の長さの間の関係です。aが1..10の範囲のときに限定すると、

def list = select("(a=$a,b=$b,c=$c)") {
   a: 1..10
   b: 1..a
   c: a..a+b
   a**2 + b**2 == c**2
}
assert list == ["(a=4,b=3,c=5)", "(a=8,b=6,c=10)"]

Java8のストリームでピタゴラス数を求める

いままでは、リストに対する内包表記でした。Java8のストリーム
(java.util.stream.Stream)を内包表記で使用することも可能です。

import static java.util.stream.Stream.*
  :
def answer = select ([a,b,c]) {
   a: iterate(1,{it+1})
   b: iterate(1,{it+1}).limit(a-1)
   c: iterate(a,{it+1}).limit(b)
   a**2 + b**2 == c**2
}.skip(100).findFirst().get()
assert answer == [144, 108, 180]

上では無限ストリームを生成した上で101番目の解を表示しています。
なお、Streamに対する拡張メソッドは、Java 8用のjar中にのみ含められているので、Gradleとかで指定する場合は

dependencies {
        :
    compile 'org.jggug.kobo:groovy-comprehension:0.3:java8'

のようにclassifierに「java8」を指定して取得してください。直接取得する場合はこちらにある「groovy-comprehension-0.3-java8.jar」を使用してください。

覆面算を解く

もう一つ応用例です。以下のような覆面算を解いてみます。

   SEND
+) MORE
~~~~~~~~~~
  MONEY

リスト内包表記を使用して上記を解くコードは以下のとおり。

import groovyx.comprehension.keyword.select;

def digits = 0..9
select("""\
  $S$E$N$D
+)$M$O$R$E
 $M$O$N$E$Y
""") {
    S:digits-0
    M:digits-S-0
    E:digits-S-M
    O:digits-S-M-E
    N:digits-S-M-E-O
    R:digits-S-M-E-O-N
    D:digits-S-M-E-O-N-R
    Y:digits-S-M-E-O-N-R-D
    (S*1000+E*100+N*10+D) + (M*1000+O*100+R*10+E) == (M*10000+O*1000+N*100+E*10+Y)
}.each { println it }

S、Mなどの変数ごとの値の範囲と、解が満す条件をガードで与えるだけで、以下のように解が出力されます。

          9567
        +)1085
         10652

仕組み

この内包表記では、リストだけではなく、以下の条件を満たすデータ型が使用できます。

bindメソッドが定義されている
yieldメソッドが定義されている(=return, unit)
autoGuardメソッドが定義されている

以下のコード

def list = select("(a=$a,b=$b,c=$c)") {
   a: 1..10
   b: 1..a
   c: a..a+b
   a**2 + b**2 == c**2
}
assert list == ["(a=4,b=3,c=5)", "(a=8,b=6,c=10)"]

がAST変換によって変換された変換後のコードは以下のような感じです。

    public java.lang.Object run() {
        java.lang.Object list = (1..10).bind({ java.lang.Object a ->
            delegate.autoGuard((1.. a )).bind({ java.lang.Object b ->
                delegate.autoGuard(( a .. a + b )).bind({ java.lang.Object c ->
                    delegate.autoGuard( a ** 2 + b ** 2 == c ** 2).bind({ java.lang.Object $$0 ->
                        delegate.yield("(a=$a,b=$b,c=$c)")
                    })
                })
            })
        })
        list == ['(a=4,b=3,c=5)', '(a=8,b=6,c=10)']
        this.println(list)
    }

bind, autoGuardなどのメソッドがGroovy拡張モジュールのメソッド拡張機構によってjava.util.Listに注入されているので上記が動作します。

メソッドの有無が問題であり、継承は不要です。しかし利便のため、MonadPlusクラスも準備されています。こちらには標準的なguard,autoGuardメソッドが定義されているので、これを継承する場合、以下3つの抽象メソッドを再定義するだけで内包表記に使えるようになります。

bindメソッド
yieldメソッド(=return, unit)
mzeroメソッド

これを見るとご存知の方はわかるように、これはモナドの定義です。
実際には、LinqやScalaのそれと同じように、「モナド内包表記」なのです。

Maybeモナドの例

モナドの例として、Maybeを定義してみます。Maybeの定義を含む全体はこちらから。
以下はMaybeを使用している部分の抜粋です。

import groovyx.comprehension.keyword.select;
import groovyx.comprehension.monad.MonadPlus

@Newify([Just,Nothing])
class MaybeMonadTest extends GroovyTestCase {
    void test01() {
        assert (select {
                    Just(1)
                    Just(3)
                    Nothing()
                    Just(7)
                }) == Nothing()
    }
    void test02() {
        assert (select {
                    Just(1)
                    Just(3)
                    Just(4)
                    Just(7)
                }) == Just(7)
    }
    void test03() {
        assert (((Just(1) >> Just(3)) >> Nothing()) >> Just(7)) == Nothing()
    }
}

まあ、Maybeに関しては内包表記で簡潔になるわけではないですね。上記のtest03()のようにbindで繋いだ方がよほどましです(Maybeでは演算子>>>(rightShiftUnsigned)をbind(Haskellの>>=),>>(rightShift)を引数を束縛させないbind(haskellの>>)の意味で定義しています)。

Java8 Optionalについてはまた今度別の記事で書きます。

これは内包表記なのか？

Haskellとの対応で言うと上記はdo構文に対応するわけで、内包表記と呼ぶべきではないのかもしれません。しかしながら、autoGuardで簡潔だし、select (式) { ... }のように先行的にyield(return)式を指定する形式があるので内包表記と呼ぼう、ということです。そうだそうしよう。Scalaのfor「内包表記」の例もあることだし。

ちなみにGroovyにおける同種のものとしては、monadologieの表記や、functional javaを元にしたfunctional groovyなどがあります。他を良く知っているわけではないのですが、今回実装したものの特徴は以下です。

表記が簡潔(AST変換で実装するものとしては、私としては限界…)
autoGuard
java8 Stream対応

制限と将来

IteratorとかSetに対応してませんがそのうち対応させたいと思います。
モナド(カテゴリ)ライブラリにするつもりはありません。Maybeはおまけです。LinqみたいにDBアクセスに対応させる気もありません。Groovy SQLがあるし。
Parsecみたいなパーサコンビネータを作るのが目標ではあるのですが、表記的にどうすべきか困っているところでもあります。

おわりに

クリスマスももう目前ですね。
Groovy!(それでは良いお年を)。
全コマ埋まってよかった!
次はid:touchez_du_bois さんです。

*1:大域的AST変換として実装されているのですが、このように明示的にimportしないと有効にならないので、selectという識別子を既に使用している既存コードに影響を与えることはありません。

*2:MacOS 10.9, Groovy Version 2.2.1、JVM: 1.7.0_10で確認。

2013-12-21

プログラミング言語Frege(フレーゲ)を紹介します

haskell JVM Frege

これはマイナー言語 Advent Calendar 2013の21日目の記事です。
Frege(フレーゲ *1 )を紹介します。

Fregeは、Java VM上で動作するHaskell風の言語です。以下のような特徴を持っています。

純関数型言語
非正格評価(いわゆる遅延評価)
Hindley-Milner型推論に基づく静的型言語

これらの特徴は、Haskellと共通するものであり、構文も基本的なところについてはHaskellとだいたい同じか似ているかもしくはサブセットです。標準関数やデータ型やモジュールについても、Haskell 2010からたくさん引っぱってきているそうです。

しかしながら、Fregeはその目標において、Haskellとの完全な互換性を達成しようとはしていません。実際かなり違っています。特にJava VM上で有用であることに重点が置かれており、プリミティブ型はJavaのものと等価なものを使用しており、Javaで定義されたメソッドを呼び出すためのインターフェースが工夫されています。

また、Haskellですっきりしてないところなどを直したり、改良しようとしているところもあります(例: MonadはApplicative型クラスのインスタンスとかデータ型がスコープを持つとか。)。またHakell標準ではない機能(GHC拡張)を標準的に使えるようにしているところもあります(例えばランクn多相,RankNTypes)。

Fregeの面白いところの一つは、fregeのコンパイラは中間コードとしてJavaのソースコードを吐くところです。コンパイル結果としてJavaソースも静的ファイルとして残るので、遅延評価っていったいどういうことだろう？など、Javaコードを良く読むとわかるかもしれません。REPLではオンメンモリでjavacを走らせてるみたいです。

fregeの使い方紹介

オンラインREPL

お気軽に試すにはオンラインのREPLがありますのでどうぞ。
「:java」で生成されたJavaソースを見ることができます。

REPLをインストールして動かす

frege-replのページからたどれるダウンロードページからfrege-repl-x.x.xの一番新しいのをダウンロードして展開、

$ mkdir /tool/frege
$ cd /tool/frege
$ unzip ~/Downloads/frege-repl-1.0.1.zip
Archive:  ~/Downloads/frege-repl-1.0.1.zip
  inflating: jline-2.10.jar
  inflating: frege-interpreter-1.0.0.jar
  inflating: frege-maven-plugin-1.0.5-frege-3.21.232-g7b05453.jar
  inflating: ecj-4.2.2.jar
  inflating: memory-javac-1.0.0.jar
  inflating: frege-repl-1.0.1.jar

REPLを起動します。

$ java -jar frege-repl-1.0.1.jar
Welcome to Frege 3.21.232-g7b05453 (Oracle Corporation Java HotSpot(TM) 64-Bit Server VM, 1.7.0**)

frege> 1+1
2
frege> quicksort [] = []

frege> quicksort (x:xs)   =  quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs, y>=x]

frege> quicksort [3,0,1,3,4,5]
[0, 1, 3, 3, 4, 5]

ghciでは関数とかを定義する際にlet文にすることが必要ですがfregeのreplではいりません。

コンパイルして実行する

前述のfrege-replのzip中にあったfrege-maven-plugin*.jarにはfrege本体のjarも含まれているので、これを使ってFregeソースコードをJavaクラスファイルにコンパイルすることができます。とはいえ、frege-maven-plugin*.jarに入っているfregeは最新版ではない可能性があるので、最新版を使いたい場合こちらから直接ダウンロードする必要があります*2。

まずソースを確認。

$ cat test.fr
module sample.Test where
quicksort [] = []
quicksort (x:xs)   =  quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs, y>=x]
main _ = print $ quicksort [1,3,2,4,5,0,7]

コンパイラを実行。

$ java  -cp /tool/frege/frege-maven-plugin-1.0.5-frege-3.21.232-g7b05453.jar frege.compiler.Main test.fr
runtime 4.304 wallclock seconds.

生成結果を確認。

$ ls -la sample
total 120
drwxr-xr-x  12 uehaj  wheel    408 12 21 05:59 ./
drwxr-xr-x  10 uehaj  wheel    340 12 21 05:59 ../
-rw-r--r--   1 uehaj  wheel   2445 12 21 05:59 Test$1Flc$1_3259.class
-rw-r--r--   1 uehaj  wheel   2448 12 21 05:59 Test$1Flc$4_3263.class
-rw-r--r--   1 uehaj  wheel    939 12 21 05:59 Test$Ĳ$1.class
-rw-r--r--   1 uehaj  wheel   1104 12 21 05:59 Test$Ĳ$2.class
-rw-r--r--   1 uehaj  wheel   1091 12 21 05:59 Test$Ĳ$3.class
-rw-r--r--   1 uehaj  wheel   1004 12 21 05:59 Test$Ĳ$4.class
-rw-r--r--   1 uehaj  wheel    674 12 21 05:59 Test$Ĳ$5.class
-rw-r--r--   1 uehaj  wheel   1593 12 21 05:59 Test$Ĳ.class
-rw-r--r--   1 uehaj  wheel   8570 12 21 05:59 Test.class
-rw-r--r--   1 uehaj  wheel  14999 12 21 05:59 Test.java

sample/Test.javaが生成されていますね。実行はこうです。

$ java -cp /tool/frege/frege-maven-plugin-1.0.5-frege-3.21.232-g7b05453.jar:. sample.Test
[0, 1, 2, 3, 4, 5, 7]
runtime 0.248 wallclock seconds.

これでわかるように、「module sample.Test where」というモジュール宣言をしたFregeソースは、FQCNが「sample.Test」であるJavaクラスにコンパイルされます。モジュール名のパッケージを除いた部分(Javaではクラス名)である「Test」は大文字で始まる必要があります。このモジュールで定義された関数は、sample.Testクラスのstaticメソッド定義にコンパイルされます。例えば上のquicksort関数は

final public static PreludeBase.TList quicksort(
  final PreludeBase.COrd ctx$1, final PreludeBase.TList arg$1
) {

こんなメソッドシグネチャのメソッドにコンパイルされるようですね。

Gradleでコンパイル

こちらにGradleプラグインがあります。とはいえこのプラグイン自身がどこかのリポジトリに上がってるわけではないので、このプラグインソースを自分のプロジェクトのbuildSrc配下に展開しておく必要があります。んで以下のようにして、開発するfregeソースはsrc/main/fregeに置きます。

apply plugin: "java"
apply plugin: org.gradle.frege.FregePlugin

repositories {
  flatDir name:"frege-lib", dirs:"lib"
}

dependencies {
  compile ':frege:3.21.232-g7b05453'
}

compileFrege {
  outputDir = project.file("$buildDir/frege")
  verbose = true
}

サンプルコード

ほぼHaskellなので例を挙げて紹介するのは省略します。自分がオフラインどう書くの問題をいくつかFregeで解いたものはこちら。ほとんどHakellで書いてからFregeに書きなおしてます。本体配布物に含まれている例はこちら。
Real World Haskellの例をFregeで書き直そうというプロジェクトReal World Fregeというのもあります。

特徴を散発的に紹介

lambdaに複数引数は使えない。ただし、\x -> \y -> expは\x \y -> expと書ける(\x y -> expが駄目)。
関数合成演算子の「.」はクラスのメンバー指定という意味に転用されている。関数合成には代りに •(BULLET,U+2022)を用いる。なお、互換性のために、「.」の前後に空白が置くもしくは「(.)」と書くと合成の意味になるようにしてあるそうです。
データ型は名前空間になるので、レコードフィールド名がトップレベルを汚染しない。runSTとかrunStateとかバリエーション作らなくてもrunで良いわけです。
正規表現リテラルが使えて、パターンマッチに使える。

     frege> test ´^[ABC]´ = "start with A or B or C"
     frege> test "CDEF"
     start with A or B or C
     frege> test "GHI"
     frege.runtime.NoMatch: test at line 3 no match for value GHI

ランクN多相GHC拡張に相当するものを標準で使える。STの定義に使われている。
型クラスの機能はHaskellにくらべ不完全とのこと。
モナドとかの型階層は違っている(MonadはApplicativeとか。結果としてApplicativeのpureはreturnにリネームされている)
「パッケージから外部に公開するときにexport」するんじゃなくて「デフォルトは公開で、公開したくないときprivateを付ける」。abstractを付けるとすべてのConstructorがprivateになる。
演算子は任意に定義できる(:で始まらなくても良い)。
数値型はJavaのを使う(Int,Double,Float)
文字列定数はjava.lang.Stringでありリストではない。charのリストと相互変換するにはunpack/packを使う。
Bool型はjavaのbooleanのAliasであり、代数データ型ではない。データ構築子True,Falseも無い。trueとfalseが予約語(リテラル)。
レイアウトルールは何か違うらしい。
read(s) は s.atoi
トレースするには以下をガードに入れる(便利)

   | traceLn (":"++show x) = undefined

QuickCheckの移植版もあるが使い方がよくわからない
javadocみたいなドキュメントコメントシステムがある
Eclipse Pluginもあるけど試してない

Javaとのインターフェース

時間不足により、今回は詳しい紹介を断念しますが、非常にエレガントです。Java メソッドを何もせずに直接呼び出せる、というわけではなく、入出力の有無と状態変更をするかどうか(評価順を定めるかどうか)によって、IO aとST s aでラップした宣言をして呼び出します。副作用がなければ、pureと宣言します。たとえば以下はHashSetをFregeから使うための宣言で、native-genというnative宣言のジェネレータで生成しました。Javaのメソッドがpureかどうかは今のところ人間が判定するしかないので、この自動生成ジェネレータはすべて安全サイドに倒して評価順の定まる処理の中で評価されるようにSTとして宣言されます。Imutableなクラスとそれに対するメソッドであれば、pureと宣言すれば純粋関数からも直接呼び値を得たり処理したりすることができます。
STモナドについてはこちら。

data HashSet e = native java.util.HashSet where

  native new :: Int -> STMutable s (HashSet e)
              | Int -> Float -> STMutable s (HashSet e)
              | Mutable s (Collection e) -> STMutable s (HashSet e)
              | () -> STMutable s (HashSet e)

  native add :: Mutable s (HashSet e) -> e -> ST s Bool

  native clear :: Mutable s (HashSet e) -> ST s ()

  native clone :: Mutable s (HashSet e) -> ST s Object

  native contains :: Mutable s (HashSet e) -> Object -> ST s Bool

  native isEmpty :: Mutable s (HashSet e) -> ST s Bool

--  native iterator :: Mutable s (HashSet e) -> STMutable s (Iterator e)

  native remove :: Mutable s (HashSet e) -> Object -> ST s Bool

  native size :: Mutable s (HashSet e) -> ST s Int

instance Serializable (HashSet e)

まとめ

Fregeの最大の利点は、Haskellに似ている、ということです。そして、最大の障壁(？)の一つは、おそらく、Haskellに似ている、ということです。今のところ、Fregeを理解するにはHaskellの知識が色々な意味で間違いなく必須です。純粋関数型言語に興味があるというJava プログラマが興味を持つきっかけとしては良いと思います。
今後の発展を期待します。