Hindley-Milner型推論アルゴリズムをGroovyで書いてみた
こないだ「Haskellのforallについて理解したことを書いておく(ランクN多相限定)」の記事を書いたときにHindley-Milner型推論アルゴリズム*1を調査するにあたって、こちらにある「Scala by Example」の16章にあるScalaでの実装例をGroovyに書きなおしたので晒しておきます。
以下のような型検査・推論ができます。実行はできません。
def listLenTest = LetRec('len', Lam('xs', App(App(App(Var('if'), App(Var('isEmpty'), Var('xs'))), Var('zero')), App(Var('succ'), App(Var('len'), App(Var('tail'), Var('xs')))) )), App(Var('len'), App( App(Var('cons'), Var('zero')), Var('nil')) ) ); assert listLenTest.toString() == 'letrec len = λ xs . (((if (isEmpty xs)) zero) (succ (len (tail xs)))) in (len ((cons zero) nil))' assert typeInfer.showType(listLenTest) == "Int[]"
型理論としてのHMを理論的に(型付ラムダ計算の定理の集合として)理解して実装しているわけではないのですが、先の「Scala By Example」の著者はScala開発者にしてJava Genericsの開発者、著名なる型理論学者Martin Odersky先生様その人ですので、プログラムの動作としてはまあ間違いはないと思っています。
コードから読み取ったことについて、多数のコメントを追記してあります。また、テストコードも追加したフルバージョンはこちらのgistにのせました。
Hindley-Milner型推論の特徴は、
- 双方向性。左辺・右辺の型、仮引数と実引数、宣言の型と使用側が期待する型、リターンしている型と返り値宣言の型、など、どっちかが決まれば、どっちかが決まるのだが、HMでは前後関係も関係なく、双方向で決まる。ここはScalaとかJava7/8とかGroovyの「型推論」と大きく異なる*2。
- 上の結果でもあるが、明示的な型宣言が(多くの場合?)不要*3。リテラルの型さえ決まっていれば、波及して型が決まる。矛盾があれば、エラーになる。字面上、明示された型指定が全く無いのに、例外無くすべて宣言されているのと同じように扱われる。もし決まらなければ(「\a->a」など)、自動的に多相型になる。
- 多相型に対応。つまり以下のコードはGenericsに対応している。こんな簡潔なコードなのに!!
- 多相型の解決と型推論の統合。つまり「型推論の開始時に未知の型」は、「多相型の型変数」と同じ枠組みで扱われて解決しようとする。
- 多相型の解決は識別子の使用を契機とするが、let変数とlambda変数では多相型解決についての意味上の違いがある。詳細はコメント参照。
でしょうかね。
Hindleyによって論文が書かれたのが1969年とのこと。なんかもう。
で、Groovy 2.1のカスタムタイプチェッカとしてHMを実装してみる野望(ゴゴゴゴ)*4
import groovy.transform.* import static TypeInfer.typeInfer @InheritConstructors class TypeError extends Exception {} /** * 構文木や式木をnewキーワード無しでオブジェクトを生成するために、 * @Newify AST変換を適用するアノテーション@ApplyNewifyを定義する。 * @AnnotationCollectorは、Groovyの合成アノテーション作成機能。 * [annotations]* @AnnocationCollector @interface 新規アノテーション {} * で、[annotations]*を指定したのと等価な新規アノテーションを作成する。 */ @Newify([Var,Lam,App,Let,LetRec,Tyvar,Arrow,Tycon]) @AnnotationCollector @interface ApplyNewify {} /** * Termおよびそのサブクラスによって構文木を構成する項を定義する。 * 項とは以下のいずれか。 * - 変数(Var) * - λ抽象(Lambda) * - 関数適用(App) * - let式(Let) * - letrec式(LetRec) * @Immutable AST変換を適用するとTupleConstructorと同様に、 * メンバーを引数で初期化するコンストラクタが生成される。 */ interface Term {} @Immutable class Var implements Term { String x @Override String toString(){ x } } @Immutable class Lam implements Term { String x; Term e @Override String toString(){ "λ $x . $e" } } @Immutable class App implements Term { Term f; Term e @Override String toString(){ "($f $e)" } } @Immutable class Let implements Term { String x; Term e; Term f @Override String toString(){ "let $x = $e in $f" } } @Immutable class LetRec implements Term { String x; Term e; Term f @Override String toString(){ "letrec $x = $e in $f" } } /** * Typeおよびそのサブクラスによって式木の構成要素を定義する。 * 型とは以下のいずれか。 * - 型変数(Tyvar) * - 関数型(Arrow) * - 型コンストラクタ呼び出し(Tycon)(具体型) * 型変数を含む型を多相型と呼ぶ。 */ interface Type {} @Immutable class Tyvar implements Type { String a @Override String toString(){ a } } @Immutable class Arrow implements Type { Type t1; Type t2 @Override String toString(){ "($t1 -> $t2)" } } @Immutable class Tycon implements Type { String k; List<Type> ts = [] @Override String toString(){ k + "[${ts.join(',')}]" } } /** * Substは「型に含まれる型変数の置換処理」を表わす。 * Subst represent a step of substitution of type variables of polymorphic type. * * Substはcallメソッドが定義されているので、Subst(のサブクラス)のイ * ンスタンスに対して関数のように呼び出すことができる(Groovyの機能)。 * 例えばx = new Subst(); x(..)と呼べるということ。 * 2種類の引数の型に対してcallが定義されている。 * * - call(Type) * 型中に含まれる型変数を置換する。 * - call(Env) * Envに含まれるすべての型スキーマに含まれる型変数を置換したEnvを返す。 * * 実装機構としては、Substのサブクラスのインスタンス1つは、「Innerクラ * ス→内部クラスを含むOuterクラスのインスタンス」、それをまた含む * Outerクラス…というチェインを構成する。そのチェインは複数の置換処理 * を連鎖である。callはOuterクラスのcallを呼び、という再帰処理が行なわ * れるので、複数の置換が適用できる。Innerクラスのインスタンスを作成す * るには、extendを呼ぶ。 */ @ApplyNewify abstract class Subst { /** * 指定した型変数の置換結果を返す。 * SubstのOuter/Innerクラス関係から構成されるチェインを辿って探す。 */ protected abstract Type lookup(Tyvar x) abstract String toString() /** * 型Type t中に含まれる型変数を置換した結果の型を返す。 * 型に含まれる型変数(つまり多相型の型変数)の変数を、変化しなく * なるまでひたすら置換する。置換の結果がさらに置換可能であれば、 * 置換がなされなくなるまで置換を繰り返す。(循環参照の対処はさ * れてないので現実装は置換がループしてないことが前提)。 */ Type call(Type t) { switch (t) { case Tyvar: def u = lookup(t); return (t == u) ? t : call(u) // TODO: this code could throw stack overflow in the case of cyclick substitution. case Arrow: return Arrow(call(t.t1), call(t.t2)) case Tycon: return Tycon(t.k, t.ts.collect{owner.call(it)}) } } /** * 環境Env eに含まれるすべての型スキーマに含まれる型変数を置換した * Envを返す。 */ Env call(Env env) { env.collectEntries { String x, TypeScheme ts -> // assumes tyvars don't occur in this substitution def tmp = new TypeScheme(ts.tyvars, owner.call(ts.tpe)) [x, tmp] } } /** * Innerクラスのインスタンスを生成する操作がextend()であり、「1つの * 型変数を一つの型へ置換」に対応するインスタンス1つを返す。ただし * extendで生成されたインスタンスは、extendを呼び出した元のオブジェ * クト(extendにとってのthisオブジェクト) =Outerクラスのインスタン * スとチェインしており、さらにcallにおいて、Outerクラスを呼び出し * て実行した置換の結果に対して追加的に置換を行うので、元の置換に対 * して「拡張された置換」になる。 */ Subst extend(Tyvar x, Type t) { new Subst() { Type lookup(Tyvar y) { if (x == y) t else Subst.this.lookup(y) } String toString() { Subst.this.toString() + "\n$x = $t" } } } /** * 初期値としての空の置換を返す。 * 任意のSubstインスタンスについて、OuterクラスのOuterクラスの… * という連鎖の最終端となる。 */ static final Subst emptySubst = new Subst() { Type lookup(Tyvar t) { t } String toString() { "(empty)" } } } /** * TypeSchemeは、型抽象(∀X.T)を表わす。 * 型抽象とは、「型引数」を引数に取り、型変数を含むテンプレートのよう * なものを本体とするような、λ式のようなもの。 * * TypeSchemeはTypeを継承していない。その結果、Typeの構造の途中に * TypeSchemeが表われることもない。 * * Haskellの「forall.」は型スキーマ(型抽象)に対応しているが、このHMアル * ゴリズムでは型スキーマ(抽象)はトップレベルの環境における識別子に直接 * 結びつく形でしか存在しない。つまりランクN多相を許していない。 * * もしTypeSchemeが型の一種であり、型構造の任意の部分に表われ得るなら * (つまりmgu()やtp()の型推定の解決対象の型コンストラクタなら)、ランク * N多相が実現されることになる。 */ @Canonical class TypeScheme { /** * tyvarsは型抽象において全称量化された型変数の集合を表す。 * tyvars are set of universally quantified types in the type scheme. * * tyvarsは「その外側に対して名前が衝突しないことの保証」を持った型 * 変数である。なぜなら型スキーマの使用に際してnewInstance()するこ * とでtpe中でのtyvars変数の使用がリネームされるからである。 * * 具体的には、プログラム中にVar(x)の形で識別子xが使用されるとき、 * 識別子xの型を得るために、環境に登録された「xに対応する型スキーマ」 * を取得した上で、Type型に変換する処理(TypeScheme.newInstance())が * 行なわれる。newInstance()は、type中のtyvarsと同じ名前を持った変数 * を、すべて重ならない新規の名前にリネーム置換したバージョンのtpe * を返す。 */ List<Tyvar> tyvars /** * 型のテンプレートを表わす。全称量化されている型変数と同じ型変数を * 含んでいれば、その型変数は、型スキーマがインスタンス化されるとき * に重ならない別名に置換される。 */ Type tpe /** * 型スキーマ(型抽象)を型に具体化する操作。 * * newInstance: TypeSchema → Type * * ちなみにgen()は反対に型から型スキーマを生み出す操作である。 * * gen: Type → TypeSchema * * newInstance()は、全称限量指定された変数およびそれに束縛された変 * 数(つまりフリー型変数を除いた全ての型変数)の使用を、新規の変数名 * にリネームする。この操作の結果は、環境には左右されず、 * TypeSchemeインスタンスのみの情報によって確定される。(変数名のシー * ドとなるtypeInfer.nの値には依存するが) * * newInstance()の結果として得られる型には全称限量で指定されていた * 型変数は含まれない。たとえば、型スキーマ * * TypeSchema s = ∀ a,b . (a,b型を含む型) * * に対して、newInstanceした結果は、 * * s.newInstance() = (a',b'型を含む型) * * であり、a,bは、a'b'に置換されるので、結果の型には決して現われな * い。 */ Type newInstance() { tyvars.inject(Subst.emptySubst){ s, tv -> s.extend(tv, TypeInfer.instance.newTyvar())} (tpe) } String toString() { "∀ (${tyvars.join(',')}) . ($tpe)" } } /** * 環境Envは、プログラムのある位置における、識別子と型情報(型スキー * マ)の対応表である。 * Env is map of identifier to type schema. * 環境Envは、意味的には型変数を含む制約の集合と見做すことができる。 * Env can be regarded as set of constraints of relationships concerning * types include type variables. So HM type checker is constraints solver for it. * 環境は、tp()が解くべき、型方程式の制約条件を表現している。 * Env: 「プログラム中の識別子→型スキーマ」の対応の集合 * * ちなみに、Substもある種の対応表であるが、型変数の書き換えルールの * 集合。 * * Subst: 「型変数→型(型変数|Arrow|Tycon)」という書き換え規則の集合 * * なお、明かにこの実装は空間効率が悪い。Scalaではタプルのリスト(連想リ * スト)で実現されていたところをGroovy化する際に、安易にMapにしてコピー * して受け渡すようにしたが、実用的には連想リストにすべき。 */ @InheritConstructors @ApplyNewify class Env extends LinkedHashMap<String, TypeScheme> { } /** * TypeInferはHM型推論の全体を含む。Scalaではオブジェクトだったので、 * @Singletonとして定義してある。サービスメソッドを呼び出すための静的 * import可能な変数として、static typeInferを容易してある。 * 型チェックの全体の流れは、 * * showType -> predefinedEnv * -> typeOf -> tp -> mgu * * である。 */ @ApplyNewify @Singleton class TypeInfer { int n = 0 def reset() { n = 0 } /** * 名前が重ならない新規の型変数を作成する。 */ Type newTyvar() { Tyvar("a${n++}") } /** * 環境中にで定義された識別子xに対応する型スキーマを取得する。 */ TypeScheme lookup(Env e, String x) { return e.get(x) } /** * 型tに含まれているすべての型変数の集合(A)から、この環境に登録され * ているすべての型スキーマの「全称量化に関するフリー型変数の集合 * (※1)」=(B)を除外したもの((A)-(B))を全称量化することで型スキーマ * を生成する。 * * (※1)λx.yのとき変数xに束縛されていることを「λ束縛」と呼び、 * 「λ束縛されていない変数」をフリー変数と呼ぶが、それと同様に、 * 型変数に関する∀y...のとき型変数yに束縛されていることを「全 * 称量化束縛」と呼び、「全称量化束縛」されていない型変数を「全 * 称量化に関するフリー型変数」とする(ここで作った言葉)。 * * 環境において「全称量化に関するフリー型変数」が発生するケースとい * うのは、具体的にはラムダ式 * * λ x . y * * において、識別子xに対応する型は、新規の型変数として環境に登録さ * れ、そのもとでyが型推論されるが、y解析中でのxの登場はスキーマ内 * で全称量化されていない、という状態である。 */ TypeScheme gen(Env env, Type t) { new TypeScheme(tyvars(t) - tyvars(env), t) } /** * 型に対するtyvars()は、指定した型Type t中に含まれる型変数のリスト * を返す。 */ List<Tyvar> tyvars(Type t) { switch (t) { case Tyvar: return [t] case Arrow: return tyvars(t.t1) + tyvars(t.t2) // 型コンストラクタ T[a,b]のとき、Tは型変数ではない。 case Tycon: return t.ts.inject([]) { List<Tyvar> tvs, Type elem -> tvs + tyvars(elem) } } } /** * 型スキーマに対するtyvars()は、指定した型スキーマTypeSchema tsの * 型テンプレート(ts.tpe)が使用している型変数から、全称量化された変 * 数(ts.tyvars)を除外したものを返す。これは、何かというと、型スキー * マの型テンプレート(TypeSchema.tpe)が含む「全称量化に関するフリー * 型変数)の集合」である。 */ List<Tyvar> tyvars(TypeScheme ts) { tyvars(ts.tpe) - ts.tyvars } /** * 環境Envに対するtyvarsは、その環境に登録されているすべての型スキー * マに対するtvarsの値全体を返す。 * つまり、環境全体が含む「全称量化に関するフリー変数の集合」を返す。 */ List<Tyvar> tyvars(Env env) { env.values().inject([]){ acc, it -> acc+tyvars(it)} } /** * 型tと型uのユニフィケーション。 * 型tと型uに対してs'(t) s'(u)が一致するような、sを拡張した置換s' * を返す。 */ Subst mgu(Type t, Type u, Subst s) { def (st, su) = [s(t), s(u)] if (st instanceof Tyvar && su instanceof Tyvar && st.a == su.a) { return s } // 等しい型変数 else if (st instanceof Tyvar) { return s.extend(st, su) } // 左辺が型変数 else if (su instanceof Tyvar) { return mgu(u, t, s) } // 右辺が型変数 else if (st instanceof Arrow && su instanceof Arrow) { // Arrow同士 return mgu(su.t1, st.t1, mgu(su.t2, st.t2, s)) } else if (st instanceof Tycon && su instanceof Tycon && st.k == su.k) { return zip(st.ts, su.ts).inject(s) { acc, it -> mgu(it[0], it[1], acc) } } throw new TypeError("cannot unify $st with $su") } /** * 二つのリストxs=[x1,x2,x3..], ys=[y1,y2,y3]のとき、 * [[x1,y1],[x2,y2],[x3,y3]..]を返す。 */ static zip(xs, ys) { if (xs.size() != ys.size()) { throw new TypeError("cannot unify $xs with $ys, number of type arguments are different") } Iterator itor = ys.iterator() xs.collect { [it, itor.next()] } } /** * エラーメッセージに含めるための、処理中の項への参照。 */ Term current = null /** * envのもとで、eの型がt型に一致するためのsを拡張した置換s'を返す。 * 数式で書くと以下のとおり。 * * s'(env) ├ ∈ e:s'(t) * * つまり、型の間の関係制約式(型変数を含む)の集合envのもとで、「s'(env)の * 型はs'(t)である」を満たすような、sを拡張した置換s'を値を返す。 */ Subst tp(Env env, Term e, Type t, Subst s) { current = e switch (e) { case Var: // 変数参照eの型は、eの識別子e.xとして登録された型スキーマを実体化(全称量 // 化された変数のリネーム)をした型である。 TypeScheme u = lookup(env, e.x) if (u == null) throw new TypeError("undefined: "+e.x) return mgu(u.newInstance(), t, s) case Lam: // λで束縛される変数とletで束縛される変数の扱いの違いにつ // いて。 // 変数(識別子)は、HMの多相型の解決において、キーとなる存在 // である。型スキーマは変数(識別子)にのみ結びつく。変数を介 // 在して得た型スキーマを基軸に、インスタンス化=全称量化=型 // 変数置換が実行される。 // // 識別子x,yに束縛される式が多相型であるとき、型変数の解決 // の扱いに関して両者には違いがある。 // // λx.eの場合、xに対応して環境に登録されるのは、xの型を表 // わす新規の型変数(a = newTyvar())を型テンプレートとする型 // スキーマ(型抽象)であり、かつaについては全称限量されない。 // つまり「全称量化に関するフリー型変数を含む型スキーマ」に // なっている。 // // let y=e1 in e2の場合、yに対応して環境に登録されるのは、 // e1の型を元にして、e1中の型変数群 // // 「e1.tyvars-tyvars(e1.e)」…(*) // // を全称限量した型スキーマ(型抽象)。例えば「new // TypeScheme(tyvars(e1), e1)」が登録される。 // なお、(*)における、tyvars(e1.e)は、e1中のフリー型変数だ // が、これが生じるのは、λ束縛の本体の型検査の場合である。 // つまり // // \ x -> let y=e1 in e2 // // のように、λ本体の中にlet式が出現するときに、let束縛され // る識別子yのために登録される型スキーマでは、xに対応する型 // スキーマで使用されている型変数がフリーなので全称限量対象 // から除外される。 // // [ここでのλとletの違いがどのような動作の違いとして現われるか?] // // Haskellで確認する。 // // ghci> let x=length in x [1,2,3]+x "abc" // 6 // ghci> (\ x -> x [1,2,3]+x "abc") length // <interactive>:5:12: // No instance for (Num Char) // arising from the literal `1' // Possible fix: add an instance declaration for (Num Char) // In the expression: 1 // In the first argument of `x', namely `[1, 2, 3]' // In the first argument of `(+)', namely `x [1, 2, 3]' // // letでのxに束縛された多相関数lengthの型(a->a)における型変 // 数aは全称限量される(Haskell流に書くとforall a.a->a)ので、 // 「x [1,2,3]」と「x "abc"」それぞれにおけるxの出現それぞ // れでaがリネームされ(1回目はa',二回目はa''など)、別の型変 // 数扱いになる。そのため、a'とa''がそれぞれのIntとCharに実 // 体化されても、型エラーにならない。 // // λの場合、xの型は全称限量されない(a->a)なので、a=Intと // a=Charの型制約が解決できず型エラーとなる。この動作はテス // トケースtestTpLamP2()、testTpLetP1() で確認する。 def (Tyvar a, Tyvar b) = [newTyvar(), newTyvar()] Subst s1 = mgu(t, Arrow(a, b), s) return tp(new Env(env)+[(e.x):new TypeScheme([], a)], e.e, b, s1) case App: Tyvar a = newTyvar() Subst s1 = tp(env, e.f, Arrow(a, t), s) return tp(env, e.e, a, s1) case Let: // λ x ...で束縛される変数とlet x= ..in..で束縛され // る変数の違いについては前述の通り。 Tyvar a = newTyvar() Subst s1 = tp(env, e.e, a, s) return tp(new Env(env) + [(e.x):gen(s1(env), s1(a))], e.f, t, s1) case LetRec: def (Tyvar a, Tyvar b) = [newTyvar(), newTyvar()] def s1 = tp(new Env(env) + [(e.x):new TypeScheme([], a)], e.e, b, s) def s2 = mgu(a, b, s1) return tp(new Env(env) + [(e.x):gen(s2(env), s2(a))], e.f, t, s2) } } /** * 環境envにおいてTerm eの型として推定される型を返す。 */ Type typeOf(Env env, Term e) { def a = newTyvar() tp(env, e, a, Subst.emptySubst)(a) } /** * 既定義の識別子(処理系の組み込み関数もしくはライブラリ関数を想定)を * いくつか定義した型環境を返す。型のみの情報でありそれらに対する構 * 文木の情報はない。 */ Env predefinedEnv() { Type booleanType = Tycon("Boolean", []) Type intType = Tycon("Int", []) Closure<Type> listType = { Type t -> Tycon("List", [t]) } Closure<TypeScheme> gen = { Type t -> gen(new Env(), t) } def a = newTyvar() return new Env(['true':gen(booleanType), 'false':gen(booleanType), 'if':gen(Arrow(booleanType, Arrow(a, Arrow(a, a)))), 'zero':gen(intType), 'succ':gen(Arrow(intType, intType)), 'nil':gen(listType(a)), 'cons':gen(Arrow(a, Arrow(listType(a), listType(a)))), 'isEmpty':gen(Arrow(listType(a), booleanType)), 'head':gen(Arrow(listType(a), a)), 'tail':gen(Arrow(listType(a), listType(a))), 'fix':gen(Arrow(Arrow(a, a), a))]) } /** * 項の型を返す。 */ String showType(Term e) { try { typeOf(predefinedEnv(), e).toString() } catch (TypeError ex) { "\n cannot type: $current"+ "\n reason: ${ex.message}" } } /** * @Singleton宣言したクラスのシングルトンはTypeInfer.instanceで保持 * されており、クラス外からも取得できる。しかし、 * 「TypeInfer.instance」が少し冗長なのと、Scala版に合せるため、シ * ングルトンを以下で定義する静的変数TypeInfer.typeInferで取得でき * るようにする。ただしSingletonの初期化タイミングの都合上か、遅延 * 設定のAST変換@Lazyを指定しないとうまくいかないようである。 */ @Lazy static typeInfer = TypeInfer.instance }
テストコードつきはこちら。
上記は元コード同様関数型っぽい作りになってる(Substによる実現とか)が、書き換えを許す前提でならもっと簡潔になりそう。型変数の一意性保証のために「型変数名」とかの置き換えにたよらず、型変数オブジェクトを単にシェアすればいいんじゃないかな…。
HaskellにおけるIOモナドとSTモナドの関係
HaskellにおけるIOモナド(IO a型)とSTモナド(ST s a型)について整理してみました。
IOの定義から知るST
IOモナドの考え方についての原論文に相当する「Lazy Functional State Threads」においては、IOの定義は
newtype IO a = ST RealWorld a
のようにST型を直接使用して定義されるものとして説明されています。ただ、「IO inside」によれば、GHCのライブラリ実装においてIO aの定義は
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))
だそうで直接STを使ってはいません。後者のは正格タプル非ボックス化タプルを使ってます(知らん!)。
IOモナドとSTモナドとの機能的関係
直接的な利用関係があるかどうかはともかく、記事「第7回 入出力と遅延評価の間を取り持つIOモナド - ITpro」からすると
STモナドは、「状態」を参照型などのより効率の良い仕組みで利用できるようにするため、IOモナドと同じ技術を使って実装されています
とのことです。
まず、IOモナドの機能を整理しよう
上記を踏まえて私の理解した限りでは、まずIOモナドには以下(1),(2)の2つの役割りがあります。
- (1) 副作用コードを分離する
- (1-1)純粋コードから副作用コードを呼べなくする。
- 静的型チェックおよびランタイムがmainを経由してからしかIOアクションを起動できないことによって
- (1-2)更新状態を外に持ち出せなくする。
- 静的型(多相型)チェックでコンパイル時に保証(ランクN多相によって)。ただし、IOでは(1-1)があるので(1-2)は試みることもできず、IO利用者からは(1-1)と一体的に認識される役割りである。
- (1-1)純粋コードから副作用コードを呼べなくする。
- 副作用は以下の二種類に分けて考えることができるが、実行順序の保証はいずれに対しても必須。
- (2-1)外部から観測可能なもの→入出力
- (2-2)外部から観測不能なもの→変数更新(IORef,newIORef,...)
おさらいでした。
そして、STモナドは?
STモナドは、機能的に前述の青字の(1-2)と(2-2)を得るものです。つまり、入出力を行なわず、変数更新(STRef,newSTRef..)だけを行なう用途に使用できます。STモナドには、入出力を行なえない、という制限がありますが、実行順序は保証されるので変数更新はでき、さらに有用なことに(1-1),(2-1)が無いので純粋関数からも呼べるという利点が得られます。
もうちょっと詳しく言うと、
- 「変数更新」のみを実行するコードは、そのコードがもはやコードの見た目としても実質としても状態更新バリバリの命令型(=評価順序が結果に影響を与える)であったとしても、呼び出し側から見たときの参照透過性さえ保てれば、純粋コードから呼んでも大丈夫だ問題ない(呼ぶ側のコードは純粋なので、呼ばれるかどうか、呼ばれる順序などはわからないが、一旦呼ばれたならその呼ばれるコード内なら順序が保たれる)。なぜなら、プログラムの外部から見て検知不能だからである。プログラムの最適化と同じである。ばれなきゃイカサマじゃないんだぜby承太郎である。
- しかし「入出力(=プログラム外とのインタラクション)」を行うコードは、たとえそれが「呼び出し側から見て参照透過(引数のみによって返り値が定まる)」としても、純粋コードから呼ばれるわけにはいかない。純粋コード自身が遅延評価によって、呼ばれるかよばれないか、あるいは呼び出し順序について保証がないからで、その状況下では外部から見ておかしなこと(起きて欲しい副作用が起きない・順序が変、など)が検出でき都合が悪いからである*1。だから純粋コードのような恐ろしいものから呼ばれないようにIOで守り、mainにつらなる「見えないバトン*2」の唯一の連鎖(the chain)に繋げる必要がある。
- IOは、入出力も変数更新も両方行なうことができる。しかし、入出力を行なわず、変数更新だけを行うコードをIOにするのは、純粋コードから呼べなくなるので嫌である。STモナドは、その目的のためにある。STモナドは入出力はできないが変数更新は行うことができる(ただし更新中の状態を外に持ち出せないように工夫がしてある)。そして、純粋コードからも(IOからも)任意に呼び出すことができる。
表にすると
入出力 | 起動方法 | 純粋関数から | 変数更新 | 順序の保証 | 相互に呼べるか | |
---|---|---|---|---|---|---|
STモナド | できない | runST | 呼べる | できる | ある | IOを呼べない(純粋関数と同様) |
IOモナド | できる | mainで起動 | 呼べない | できる | ある | ST,State含め純粋関数を呼べる |
Stateモナド | できない | runState | 呼べる | できない | ある | IOを呼べない(純粋関数と同様) |
まとめ
Haskellのforallについて理解したことを書いておく(ランクN多相限定)。
Haskellのforallについて理解したことを書いておくyo!(ランクN多相限定*1 )。
前提知識のおさらい: 型・多相型・型検査・型推論…
最初に基本概念を整理しておきます。
- IntやInt->Intは単相型、aやa->aは多相型である。ここでaを型変数と呼ぶ。型変数を含む型が多相型ってわけです。
- 言語処理系の実装上、型という概念は型変数や型コンストラクタのツリー構造として表現される。Int,Char,[],->,(,),(,,,),IO aなどが型コンストラクタ。 a,bが型変数。組合せて(a->[Int])->[b]->(a,b)とか。::の右に書くやつです。
- 型は、プログラムの字面上に直接的実体がある関数や変数だけではなく、値を生じさせる部分式すべてに付随し、コンパイル時に決定されるべき情報である(値あるところに型がある。*2 )。それを決定しようというのが(静的)型検査である。Haskellでは基本としてhindley-milner(以降、HMと記載するときもある)と呼ばれる型推論機構をベースにして多々拡張したもので型推論を行なう。この記事はhindley-milnerのロジック(こちらにscalaのコードがある)を読んで理解したことのみをベースにしHaskellに対して類推したものである*3。hindley-milnerでは型検査は型推論と一体化しているような気がするのでこの記事では「型検査」には「型推論」が含んでいるというつもりで「型検査」という用語を用いる。なお、Hindley-milner型推論の実装については、こちらの記事「Hindley-Milner型推論アルゴリズムをGroovyで書いてみた」もどうぞ。
- 多相型は、1個以上の型変数を含んだ型であり、多相型を解決するための仕組み(後述)を「型スキーマ」もしくは「型抽象」と呼ぶ。型スキーマ中の特定型変数を置換し(結果、単相型が得られるかもしくは単相型に近づく)、その結果を得る操作を型スキーマのインスタンス化と呼ぶ。これは、λ抽象に引数の値を与えると、具体的な結果の値が得られるのと同じ。値の世界のλ抽象は、値を与えると値が返るが、型の世界の型抽象は、型を与えて型が返るような型の世界の関数である。多相型というのは「パラメタを持った型」であり「パラメタに具体値をあてはめることで初めて利用できるような型」なわけです。まあ直感的にそれはそうでしょう。(Javaのジェネリクスも同じだと言える)
HM型検査器の構造と実行
- 「環境」という概念を導入する。環境は識別子*4から型スキーマへの対応表であり型検査に使用する(コンパイル一般のためには、環境は他の情報も含むのかもしれない。ASTとか)。環境は、処理開始時のトップレベルは「組み込み定義」情報だけを含んでいるところから始まり、関数を定義したり、あるいは他モジュールから識別子をインポートすることによって、あるいはラムダ束縛やlet束縛で識別子が定義されるたびに、エントリが拡張されそれぞれのネストレベルで使用される。
- オリジナルhindley-milnerではトップレベルの関数のみ*5に型スキーマを明示的に付与できる*6。
例: func :: a-> Int。これはfunc :: forall a. a -> Intの略記法である。
forallと型スキーマ・型抽象、インスタンス化のタイミング
- forallは型スキーマ(型抽象)を表わし、型の世界のλである。forallをλに機械的に置換してみると良い。先の例func :: λa.(a->Int)について
- (λa.(a->Int)) Int の返り値は、Int -> Int、
- (λa.(a->Int)) [String]の返り値は、[String] -> Int
- 型検査の過程において、プログラム字面上の「識別子の出現」が型スキーマのインスタンス化のタイミングである。なおインスタンス化一発ですべての型変数が消去できるわけではない。構文木をツリーとして再帰的に辿るhindley-milner型検査過程の各ステップで、型変数を媒介として双方向的・全体的に型がきまっていく*7。こんなことが可能なのはある意味驚きであるが、決まるそうなのである。これがHindley-milnerの凄いところである。処理対象プログラム中に識別子が現われたら、環境から型スキーマを引っぱってきてインスタンス化して、構文木構造(関数適用、let、lambda..)ごとに決められたルールで双方向パターンマッチ(ユニフィケーション、単一化)して型を決めていく。
ちなみに型検査器を外部から見て一言で言うと
- 外部から見ると、hindley-milner型検査器は、型変数を含んだ連立程式を解く、制約問題ソルバとみなせる。
ランクN多相は型スキーマを一級市民の型として扱うこと
forallの機能
- 型スキーマのインスタンス化について機能面で言及すべきことがあって、それは型変数名をリネームすることによる衝突回避機能を持つということである(これもλ抽象でできるのと同じ話だが)。型変数に単相型をマッチさせる、という行為に関して、型変数はそれを媒介とした型の一致・不一致の判別の一意性を判定するものであるからして、一致させないためにリネームしたり、リネームの効果がおよぶ特定の範囲では一致させる、というようなコントロールができる。これを利用しているのがかの有名なST Monadで、詳しくはこちら「Lazy Functional State Threads 」(って原論文を読むしかないのか…。しかしweb上では他に理解可能な情報を見付けられませんでした。)。
HMの限界
- hindley-milnerの型検査には双方向性があるため、「ある範囲」を対象とした「型変数の連立方程式」というか制約問題を解く必要があるのだが、そしてGHCはおそらくそれを「トップレベルに定義した関数」という単位でやる*8のだが、hindley-milnerオリジナルでは関数引数の型のインスタンス化について、「関数そのものに付随する型スキーマの実体化」1回分の中で決定しようとするため、識別子の複数回の使用それぞれで異なるインスタンス化ができない。このことは、多相関数を引数にとる関数を定義する際に多相性が1回限りしか発揮できないということなので不便なときがある。例えば、[a]->Intを引数にとる関数([a]->Int)->Intがあったとする。
func:: ([a]->Int)->Int
これは型エラーになる。なぜならf[Int]、f[ [Char] ]というfの出現2つにそれぞれ対応してインスタンス化されることで生成された、f::[Int]->Intとf::[ [ Char ] ] -> Intというボトムアップで定まる2つの型制約を、引数としての識別子fの型が同時に満せないからである。
func f = f [1,2,3] + f["a","b","c"]
ランクN多相の意義と動作例
名前が悪いぞforall
あとは非生産的な話。
- プログラミング言語としてのHakellにおける、forallというキーワードで起動される言語機構を理解するのに、全称量化を理解する必要はないし形式論理学の知識は不要である。「全称量化」という単語を知る必要すら一切ない。それは理解に寄与しない。ていうか理解の妨げになるだけだッ。名称としてそれしかないので「全称量化子」とか「全称量化された」とか呼ぶしかないので、しょうがない面もあるのだろうが、ミスリーディングなだけである。forallというキーワードから「all(全ての)」という含意を読みとる必要すらない。必要があるってのなら値に関して同型であるλについてもどういう意味でallなのか、allを付けないのかプログラミングレベルでの説明を聞かせてほしい。 ∀が型抽象の型表記で慣例的に使われてるのを敬意を表してなのか論理学者は慣れてるからなのか、結果的には無批判に導入しただけだろ、っていう。最終的にはカリー・ハワード同型対応で、そういう方面に応用できるのだとは思うが、Haskellをプログラミングのみに使いたいプログラマにとっては不要なことである。迷惑なことである。
*1:ここを読むと、ランクN多相を実現する以外に2つぐらい意味があると。ExistentialQuantificationについてはきちんと理解してないが理解したら何か書くかも。
*2:加えて、値が無いところにもたまに型がある。
*3:本当は「型システム入門」とかにさぞ詳しく書いてあるであろう。でも読めてません。ごめんなさい。
*4:環境のキーとなる「識別子」はプログラム本体で使われる識別子である。型側でのみ使われる「型変数」の名前ではない。混同しないこと。両者は混在することは決してない。
*5:Haskellでは::でlambda変数とかにも他にも付与できる
*6:例のscalaのコードから読む限りでだが、letで定義する識別子には暗黙に形成された型スキーマが付与される。なのでletを介入させるとランクN多相を導入しなくても型スキーマを複数回インスタンス化できそう(未確認)(2014.01.26追記できない)。この意味でletはlambda+関数適用のシンタックスシュガーではない。haskellもそうなってるようだ。不思議。
*7:最終的にもすべてが単相型に落ちずに、型変数が残ることもあるだろう。つまり多相関数はそれである。
*8:これも予想でしかない。前述のScalaのコードでは、任意の構文木の枝に対して型チェック(tp() )を起動可能だが、それは正しい環境を引数に渡せる前提である。正しい環境を構築するためには、上の方から解析を結局していかなければならないよね。だから関数単位だろうと予想しました。遅延評価とかを使って全然違う単位・順序で解析するのかもしれませんが。
*9:この動作は裏をとってない。SystemFなりHaskellのランクN拡張でどう実装しているかは不明。「私だったらそう実装したい」というレベルの話である。
Groovyで内包表記を作ってみた #gadvent
G*アドベントカレンダー2013第23日目の記事です。
大域AST変換と拡張メソッドを使って、Groovyでリスト内包表記を使えるようにしてみます。
リスト内包表記(list comprehension)というのは、HaskellとかScalaとかPythonにも似たものがある便利な言語機能であり、宣言的にリストを構築するためのものです。通常、ループを回したり、あるいはcollect()やfindAll()などの一連の関数呼び出しで作るところを、要素が満たすべき条件を与えることでリストが構築されます。
変数が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")(JCenterに登録したのでGrabResolver指定は不要になりました)
@Grab("org.jggug.kobo:groovy-comprehension:0.3")
@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
仕組み
この内包表記では、リストだけではなく、以下の条件を満たすデータ型が使用できます。
以下のコード
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つの抽象メソッドを再定義するだけで内包表記に使えるようになります。
これを見るとご存知の方はわかるように、これはモナドの定義です。
実際には、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 さんです。
プログラミング言語Frege(フレーゲ)を紹介します
これはマイナー言語 Advent Calendar 2013の21日目の記事です。
Frege(フレーゲ*1 )を紹介します。
Fregeは、Java VM上で動作するHaskell風の言語です。以下のような特徴を持っています。
これらの特徴は、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$IJ$1.class -rw-r--r-- 1 uehaj wheel 1104 12 21 05:59 Test$IJ$2.class -rw-r--r-- 1 uehaj wheel 1091 12 21 05:59 Test$IJ$3.class -rw-r--r-- 1 uehaj wheel 1004 12 21 05:59 Test$IJ$4.class -rw-r--r-- 1 uehaj wheel 674 12 21 05:59 Test$IJ$5.class -rw-r--r-- 1 uehaj wheel 1593 12 21 05:59 Test$IJ.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
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プログラマが興味を持つきっかけとしては良いと思います。
今後の発展を期待します。
参考
- IngoWechsung氏によるFrege紹介資料。おすすめ。
- 一番網羅的なポータル
- オンラインREPL+リンク集(おすすめ)
- こちらの仕様書PDF。
- 本体最新版ダウンロードhttps://github.com/Frege/frege/releases
- ライブラリリファレンスのHTMLドキュメントとダウンロード版
- FregeとHaskellの違い
- Javaインターフェース宣言のnative宣言のジェネレータnative-gen
- google group
- Real World Frege。Real World Haskellの例をFregeで書き直そうというプロジェクト
*1:命題論理と述語論理の公理化を最初に行なったドイツの先駆的論理学者ゴットロープ・フレーゲからの名前とのことです。
*2:REPLを本体側に同梱で配布して欲しいわ!
Java8のStreamでフィボナッチ数を計算する
フィボナッチ数ってあるじゃないですか。
Java8のStreamを使って書いてみます。Groovyで。
import static java.util.stream.Collectors.* import java.util.stream.* println Stream.iterate([1l, 1l]) { (old1, old2) = it [old1+old2, old1] }.map{it[1]}.limit(10).collect(toList())
こんな感じですか。10個のフィボナッチ数を表示します。
無限ストリームなんかを作っちゃっています。
% groovy fib.groovy [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
調べると、streamてのは本質的にはIteratorのフレームワークですな。
目的は並列処理うんぬんが主眼かもしれませんが、機構としてはIterator(Spliterator)のチェインをフルーエントなビルダーで作って、ケツのところでぶん回す、というものです。遅延リストとは違うし遅延評価とも関係ない*1。制約が多くてそれがおもしろい。別に記事書くかも。
Java 8のOptionalをGroovyから超簡潔に使用する
結論
Java8のOptionalは超すっきり扱えるよ、そう、Groovyならね。
Optionalって何?
Java 8で導入される新規クラスの一つ、java.util.Optionalは、メソッドの実行結果で成功する場合と失敗する場合があるときに、その返り値で成功と失敗を表現するためのものです。
- Opitonalは単一要素を保持するコンテナ型。成功した場合は返り値をコンテナで保持させたものを返す。(成功時の返り値をラッピングする)
- 「失敗」は固定のシングルトン(Optional.empty())として扱う
まあ、それだけの話といえばそれだけなのですが、効果は、
- 失敗のある可能性のあるメソッドと無いメソッドをコメントではなくプログラムの一部として明示し、両者の違いをコーディング上も区別する
- 失敗のある可能性のあるメソッドと無い混在・混同することのないようにコンパイル時チェックをできるようにする*1
- 全体としては、nullで失敗値を表現する場合と比べ、NullPointerExceptionが発生しにくくなる
というところ。しかしながら、ラッピングされた値を取り出すにはOptional.get()を使うのですが、Optiona.empty()に対してget()を実行すると、NoSuchElementExceptionが発生します。なので、getを実行して値を取り出す場合には、Optional.isPresent()で、値がemptyではないことのチェックをする必要があります。でもそれって、nullチェックと同等なのであって、Optionalの目的からして悲しいものがあります。
なので、Optionalに関しては、値を取り出さずに操作を可能とするいくつかのメソッド(orElse,orElseGet,orElseThrow,map,flatMap, ifPresent, )を積極的に使うべきです。
問題は、これらのメソッド群が、単一のOptional値を操作するものでしかないということです。例えばそれぞれString型を保持する2つのOptional値があったとき、それを文字列結合したいとします。(この例はきしださんの記事より)。その場合以下のようにする必要があります。
Optional<String> fullName = (lastName.isPresent() && firstName.isPresent()) ?
Optional.of(String.join(" ", lastName.get(), firstName.get())) :
Optional.empty();
これは駄目な方のパターンですね。そのために、flatMapというものがあり、
Optional<String> fullName = lastName.flatMap(ln -> firstName.flatMap(fn -> Optional.of(String.join(" ", ln, fn))));
こんな風に書けます*2。Optionalを使ったコーディングのキモは、「成功か失敗か」の個々値を組み合せた結果も「成功か失敗か」を正しく伝搬していることです。flatMap()はそれに関わってます(「複数のOptionalを組み合せた場合、どれか1つでも失敗したら全体は失敗」という意味を実装しているのはOptinalのflatMap())。
しかし、これらが、もともとやりたかったことは、
String fullName = String.join(" ", lastName, firstName);
だったわけですが、Optionalがちりばめられていて、たとえLambdaであろうとも、ちょっとごたごたしてますね。いやちょっとどころではない。
それ、Groovyで(ry
GroovyはJava 8に正式対応してるか不明ですが、試したbuild 1.8.0-ea-b115というバージョンでは動いているようです。
どうするかというと、Optionalに以下のようなメソッドを追加します。
Optional.metaClass.methodMissing = { String name, Object args -> assert args instanceof Object[] for (int i=0; i<args.size(); i++) { if (args[i] instanceof Optional) { if (args[i].isPresent()) { args[i] = args[i].get() } else { return Optional.empty() } } } if (delegate.isPresent()) { return Optional.ofNullable(delegate.get().invokeMethod(name, args)) } else { return Optional.empty() } }
ここではExpandoMetaclassを用いてますが、追加方法はuseでも拡張メソッド(ExtensionMethod)を含むモジュールとしてでも構わないでしょう。
すると、
Optional<String> fullName = lastName+" "+firstName
と書けます。つまりOptionalであることを意識せずに、通常の値と同様に透過的に操作でき、結果は結果をOptionalで包んだものになります。また、firstNameとlastNameのいずれかもしくは両方がOptional.empty()であるときには結果もOptional.empty()となります。
試してみます。
Optional<Integer> firstName = Optional.of("FirstName") Optional<Integer> lastName = Optional.of("LastName") Optional NULL = Optional.empty() assert (lastName + " " + firstName).get() == "LastName FirstName" assert (NULL + " " + firstName) == NULL assert (lastName + " " + NULL) == NULL assert (NULL + " " + NULL) == NULL
全体コードはこちら。
制約
もっとも制約もあって、Optionalに対する直接的なメソッド呼び出しを置き換えるだけなので、
- Optional値を、他のメソッド(例えばString.join())などに渡すというケースには介入できない。上記でString.join()を使わずに+" "+しているのはこれが理由。+は左辺に対するplusメソッドの呼び出しとGroovyでは解釈されるので、それをOptionalのそれを置き換えることで実現されるからです。
- 他にもあるかな?
という制約もあります。x.method(y,z,..)というパターンにおける失敗値の伝搬を解決するだけです。でもだいぶ可読性が高くなると思います。
Optional値を他のメソッド(例えばString.join())などに渡すというケースについては、以下のようにクロージャをOptionalに包んだ上でcallをmissingMethodでトラップしてクロージャに転送してもらえば良いですね。
assert (Optional.of{a,b -> String.join(' ', a, b) }("A", "B")) == Optional.of("A B")
完璧!
結論
Java8もGroovyで!
enjoy!
おまけ
Optionalをアプリカティブにする*3、ってのも考えましたが、結果は表記がGroovyとしてのメソッド呼び出しっぽくないので、いまいち。「&」がHaskellの<*>(ap)で%(mod)が<$>(fmap)に対応させています。全体はこちらに公開しておきます。
Optional<String> arg1 = Optional.of("Abc") Optional<String> arg2 = Optional.of("Def") Optional<String> NULL = Optional.empty() assert ({a,b -> a+' '+b} % arg1 & arg2) == Optional.of("Abc Def") assert ({a,b -> a+' '+b} % arg1 & NULL) == NULL assert ({a,b -> a+' '+b} % NULL & arg1) == NULL assert ({a,b -> String.join(' ', a, b)} % arg1 & arg2) == Optional.of("Abc Def") assert ({a,b -> String.join(' ', a, b)} % arg1 & NULL) == NULL assert ({a,b -> String.join(' ', a, c)} % NULL & arg1) == NULL Closure c1 = {a,b -> a+b} Closure c2 = {a,b -> a.toUpperCase()+b.toLowerCase()} Closure c3 = {a,b -> a.length() * b.length()} assert (c1 % arg1 & arg2) == Optional.of("AbcDef") assert (c1 % arg1 & NULL) == NULL assert (c1 % NULL & NULL) == NULL assert (c2 % arg1 & arg2) == Optional.of("ABCdef") assert (c2 % NULL & arg2) == NULL assert (c2 % NULL & NULL) == NULL assert (c3 % arg1 & arg2) == Optional.of(9)
汎用的といえば汎用的です。クロージャを介してですがString.joinも使えます。Haskellの<$>(fmap)に対応させている積りの%(mod)をClosureのメソッドに追加定義したかったところがExpandoMetaClassの制約により実現できず。できた*4。