プログラミング言語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 プログラマが興味を持つきっかけとしては良いと思います。
今後の発展を期待します。