プログラミング・シンポジウムで新言語Suzuについて発表します

第56回プログラミング・シンポジウムにて、「環境にメソッドを直接格納する新しいオブジェクトシステムの提案」というタイトルで発表を行います(発表プログラム)。

独自に考案した全く新しいオブジェクトシステムを搭載する新言語Suzuについての発表です。興味のある方はぜひ。

そのうちSuzuの処理系(OCamlで書かれています)とその解説記事を公開する予定です。

私が愛するオブジェクト指向とそれを使わない理由

この記事では、私がオブジェクト指向のどこを愛しどこを素晴らしいと感じていて、そのうえでなぜオブジェクト指向を使うことを避けているのかを書き留めておきます。関数型言語使いの方で、「オブジェクト指向の何がいいのかわからない」「オブジェクト指向難しすぎ・複雑すぎ」とおっしゃる方にぜひ読んでいただきたいと思っています。また、「オブジェクト指向言語完璧に理解したわ」と思っている方にも読んでいただきたく思います。

なお、ここでのオブジェクト指向の定義は、「各言語でオブジェクト指向と呼ばれているものすべて」とします。JavaScalaJavaScriptSmalltalkRubyCommon LispOCamlオブジェクト指向と呼んでいるものすべての総称です。もっとまともな定義が知りたい方は以下の記事がおすすめです。

オブジェクト指向の概念の発明者は誰ですか?(改訂版) - Smalltalkのtは小文字です
“オブジェクト指向”の本質 - Smalltalkのtは小文字です

私がオブジェクト指向を愛する理由

私はプロトタイプベースオブジェクト指向言語を自作したり、「ぼくのかんがえたさいきょうのオブジェクト指向」を妄想する生粋のオブジェクト指向好きです。

Cyan, Yet Another New language - takuto_hの日記

そんな私がオブジェクト指向を愛する理由は大きく分けて6つあります。

1. すべてをメッセージパッシングとしてとらえるという理念

これはSmalltalkの(より正確にはアラン・ケイの)オブジェクト指向にあたります。以下はメッセージパッシングを軸とするオブジェクト指向の理念を学べる良書です。

SMALLTALKで学ぶ オブジェクト指向プログラミングの本質

SMALLTALKで学ぶ オブジェクト指向プログラミングの本質

Smalltalkは、オブジェクト同士のメッセージのやり取りによってプログラムを表現しようとしました。それが正しい抽象化かどうかはさておき、プログラム内のオブジェクトがまるで生体内の細胞のように情報をやり取りするさまは、イメージするだけでわくわくしてきませんか?もちろんこれが単なる絵空事ではないことは本書が証明してくれます。私がオブジェクト指向を愛するきっかけとなった1冊です。

2. メタ階層

Smalltalkにはクラスがありますが、先の理念に基づくプログラミングにおいてクラスは必須のものではなく、単に効率のために導入されたととらえるべきだそうです。
すべてのオブジェクトにメソッドのコピーが含まれていたらメモリ効率が悪いので、メソッドはクラスにまとめてオブジェクトはクラスを参照するようにしたとのこと。ただ、クラスを特別な存在とするのは理念に反するので、クラスそのものもオブジェクトとするためにメタクラスを導入し、メタクラスのクラスを導入し、メタクラスメタクラスを導入しました。

なんだかとても複雑なように思えますが、グラフにするととてもシンプルです(Ruby1.9 のクラスのメタ階層を整理する 2 - Smalltalkのtは小文字ですの、「Squeak Smalltalk の場合」を参照)。このメタ階層のおかげでクラスの振る舞いに手を加えることもでき、柔軟なオブジェクト指向が可能となっています。そしてなによりRubyと比べてグラフがとってもかわいいです。

3. クラスのないオブジェクト指向

クラスのないオブジェクト指向言語というとJavaScriptが思い浮かぶかもしれませんが、プロトタイプって「メソッドをまとめてオブジェクトから参照できるようにしたもの」なのだからそれってつまりクラスそのものです。そうではなくて、プロトタイプチェーンも使わず、ハッシュテーブルに無名関数を突っ込んだものをオブジェクトと呼んでもいいよね?ということです。メタテーブルを使わないLuaのオブジェクト、と言った方がわかりやすい人もいるかもしれません。あるいは『On Lisp』という書籍ではそのものずばりのオブジェクトシステムをCommon Lispで実装しています。

On Lisp

On Lisp

先ほどクラスは必須ではないと申し上げたように、ある意味これがオブジェクト指向の源流にもっとも近い形なのかもしれません。『On Lisp』を読めばわかりますが、実装も簡単です。クラスがないために生成したオブジェクトの振る舞いをあとから変えにくいという欠点はありますが、こんなオブジェクト指向もあるよ、という意味ではきっと興味深いと思っていただけるはずです。

4. CLOS(Common Lisp Object System)

オブジェクトシステム界の異端児といっていいであろうCLOSです。CLOSの解説は『On Lisp』やfireproject.jp - このウェブサイトは販売用です! - クラス ジェクト ファイヤー パターン ファイル リソース 関数 ゾンビ リソースおよび情報ホームページ移転のお知らせ - Yahoo!ジオシティーズにお任せします。これからCLOSを勉強する方は、きっとJavaScriptオブジェクト指向を学んだ時の何倍も驚嘆することでしょう。一般的なオブジェクトシステムと比べてできることはさほど変わりませんが、何よりその実現方法は一見の価値ありです。

5. 多重継承問題

やってきました、多重継承です。この問題は「クラス」という概念が生まれた時点で自然と付きまとうものです。つまりクラスさえなければ……でもクラスがないと……といった感じで妄想がはかどりますが、それはさておき。

クラスにはメソッドがまとめられており、時としてこれを再利用したくなります。そこでクラスからクラスへの参照を持たせる、いわゆる継承をするわけですが、ここで問題が生じます。多重継承を許すと継承関係がグラフになるので、メソッドの探索順序を一意に定めにくいのです(なお、C++ではもう一つ、メモリレイアウトにかかわる問題が起きますが、これは省略)。

これまで様々な言語がこの問題の解決策を提示してきました。

Java
実装の多重継承禁止。再利用したければ合成と委譲を使う。
Python, Perl
多重継承許可。C3線形化でメソッドの探索順序を一意に定める。
Ruby, Scala
ミックスインのための機構を導入。Scalaのトレイトは後述のトレイトとは違い、Rubyのモジュールに近いです。
Squeak Smalltalk, Perl, PHP
トレイト(PerlではRoleと呼ばれる)を導入。

Javaのやり方が窮屈なのはみなさんご存知でしょう。何度委譲のためだけの中身のないメソッドを書いたことか……。

PerlPythonに導入されたC3線形化は、ほとんどの場合でメソッドの探索順序を望み通りに決定してくれるアルゴリズムです。しかしながら、Class::C3, Algorithm::C3 を勉強したよ! - IT戦記の最後の方にあるように、もしかするとうまくいかない可能性があります。

ミックスインというのは、多重継承の使い方を表すものです。他のクラスを継承しないクラスならばいくら多重継承しても問題ありませんから、このような継承を指して特にミックスインと呼びます。Rubyはモジュールという多重継承可能なメソッドの集まりをクラスとは別に導入し、クラスは単一継承のみ・モジュールはインスタンス化できないようにすることで、ミックスインを推奨する文化を作り上げました。ただし、モジュールがモジュールを多重継承すると当然問題が生じる可能性があります。

module って super できたんだ - まめめも

Perlなどに実装されているトレイトは、ミックスインとは少々異なるアプローチです。トレイトはメソッドの集まりですが、クラスから継承するのではなく、クラスにメソッドを追加することで拡張します。

TraitとMoose::Role

真にただのメソッドの集まりであるトレイトを足したり引いたりすることで衝突を解決するさまは、ハッシュテーブルに無名関数を突っ込んだだけの原始的なオブジェクトを操作しているようにも思える趣深いものです。ある意味原点回帰ともいえるでしょう。

6. メソッドが所属する名前空間

Selector namespace、ClassBox、Refinementsなどの機構のことです。メソッドが(CLOSでいうジェネリック関数ではなく)クラスに所属する言語において、いかにして「ある範囲でのみ見えるメソッド」を定義するかという問題に対処しています。

るびま
Selector namespaceやClassBoxを比較した論文

メソッドは他の変数とは異なる空間に属しているため、メソッド用の名前空間を用意しようという話です。ここまで来るとなんだかオブジェクト指向の本末転倒感がにじみ出てきますが……。

まとめ

6つの理由を通して、オブジェクト指向の世界の一部をご紹介することができたのではないかと思います。私が愛するのはまさにこの世界における営みです。もちろん、「こういう場合に書きやすい」「こういう場合に読みやすい」「こういう場合に保守しやすい」といった実用面での利点もあるでしょう。ただ、私にとってはオブジェクト指向という営みそのものがそれ以上に興味深く、愛らしい対象なのです。

私がオブジェクト指向を使わない理由

至極単純です。

「私がプログラムを書く時に必要としないから」

です。

私はよく言語処理系を書きます。今まで様々な言語で言語処理系を書いてきました。JavaやらC#やらRubyやらCommon LispやらSchemeやらJavaScriptやらHaskellやら……。そして現在はOCamlに落ち着いています。OCamlはオブジェクトシステムを持っていますが使っていません。

昔はJavaC#で字句解析器や構文解析器をオブジェクトにしたり、構文木をオブジェクトにしたり、VMの命令をオブジェクトにしたりと、いろいろ試しました。

字句解析器や構文解析器をオブジェクトにしても状態がグローバル変数のように参照できるというだけで、OCamlでレコードを第一引数として渡して中身を見ながら操作するのとそんなに労力は変わりません。データの中身を隠蔽したいと思うかもしれませんがそれはモジュールで十分です。

構文木をオブジェクトにすると型検査器とコンパイラのコードが各構文要素に分散するので、とても読みにくいです。型検査モジュールやコンパイルモジュールを作ってその中で完結させた方がはるかに読みやすくなります。VMの命令をオブジェクトにした場合も同様です。

また、型推論器はバリアントとパターンマッチがないとだいぶ書きにくいです。これはJavaScript型推論器を書いたときに実感しました。

JavaScriptで型推論器を作りました - takuto_hの日記

つまり、私が、言語処理系を書く際に、オブジェクト指向は有用ではないのです。

なぜOCamlなのか

欲しい機能が、当たり前のようにあるからです。GC、第一級の値としての関数、バリアントとパターンマッチ、副作用のある式、例外処理機構、モジュールシステム、型推論。これだけあれば私としては十分事が足ります。

最後に

この記事の要旨は、「オブジェクト指向そのものはとっても面白いから、もっと知るといいよ。でも私が作るプログラムには必要ないから使わないよ」ということです。特に後半については、「適材適所」と一言で済ませられるほど当たり前のことなので、がっかりした方もおられるかもしれません。

ただ、私が声を大にして主張したいのは、いわゆる関数型言語を好んで使う方々とオブジェクト指向言語を好んで使う方々が、お互いをよく知らないままに批判し合うのが非常にナンセンスだということです。結論から見ればこの記事は関数型言語の使用を推奨しているように思えますが、そうではありません。「私にとっては」関数型言語が適していたというだけの話です。

お互いが何を好んでその言語を使用しているのかを理解することで、言語ユーザー間のいざこざは緩和されることと思います。ここに私がなぜオブジェクト指向言語を愛しているのかを述べることで、理解が深まれば幸いです。

謝辞

私がオブジェクト指向にはまるきっかけを作ってくださったid:sumim様と、私がこの記事を書くきっかけを与えてくださった下記の記事に感謝いたします。

存在しない記事 - 標高+1m

型推論を可視化してみた

型推論をスライドショー形式で可視化してみました。
http://www.geocities.jp/takt0_h/ibis-js/visualize.html
各フォームの機能は以下の通りです。

Control

interpret
Edit欄の内容をパーズ・型推論・評価し、結果をResult欄とScreen欄に表示します。
clear
Edit欄の内容をクリアします。
factorial
Edit欄に階乗を求める関数のコードを入力します。
fizzbuzz
Edit欄にFizzBuzzのコードを入力します。
peano
Edit欄にバリアントを用いた自然数の定義とその上での演算をするコードを入力します。

Edit

ここに式を入力してください。interpretボタンを押すとResult欄とScreen欄に結果が表示されます。

Result

Edit欄に入力したすべての式の型と評価結果が順に表示されます。

Expression

Screen欄に表示する式を変更できます。

Inference

型推論の過程をたどることができます。

Screen

Edit欄に入力した式のパーズ結果と型推論の過程が表示されます。

JavaScriptによる型推論器の実装:バリアント型

前:let と let rec 目次

パターンマッチ対象の型推論

昨日挙げた以下のコードではバリアントを使用していますが、パターンマッチ対象である m の型はどこにも明示されていません。

let rec add =
  fun m -> fun n ->
    case m of
      Zero -> fun _ -> n
    | Succ -> fun k -> Succ (add k n)
http://d.hatena.ne.jp/takuto_h/20110405/variant

Ibis の case 式はバリアントのみを対象とするという制限がありますから、m がバリアント型であることは確かです。しかしそれ以上のことはわかりません。では、どのようにして具体的な型を推論しているのでしょうか。

タグ環境

話は単純で、パターン内に現れるコンストラクタ名から推論します。コンストラクタ名からそれによって生成されるバリアント型を取り出せる環境を用意しておき、それを参照すればよいのです。これをタグ環境と呼びます。イメージとしては

{ Zero: nat, Succ: nat }

のような形式です。
Ibis では variants という変数にタグ環境が入っています。

 91:    case "VariantDef":
 92:      var typeName = expr.typeName;
 93:      var paramTypeExprs = expr.typeCtors;
 94:      var paramTypes = {};
 95:      var variantType = Type.createVariant(typeName, paramTypes);
 96:      Env.add(env, typeName, variantType);
 97:      for (var ctorName in paramTypeExprs) {
 98:        var typeExpr = paramTypeExprs[ctorName];
 99:        var paramType = eval(env, typeExpr);
100:        paramTypes[ctorName] = paramType;
101:        var ctorType = Type.createFun(paramType, variantType);
102:        Env.add(ctxt, ctorName, Type.createTypeSchema([], ctorType));
103:        Env.add(variants, ctorName, variantType);
104:      }
105:      return Type.Unit;
https://github.com/takuto-h/ibis-js/blob/ibis-js-1.0.0/src/inferer.js

バリアント型の定義(type という予約語を使った式)の型推論では、103行目でタグ環境 variants に コンストラクタ名 ctorName をキーとしてバリアント型 variantType を登録しています。

106:    case "Case":
107:      var inferredType = infer(ctxt, env, variants, expr.variantExpr);
108:      var clauseExprs = expr.clauseExprs;
109:      var elseClause = expr.elseClause;
110:      var variantType = null;
111:      for (var ctorName in clauseExprs) {
112:        variantType = Env.find(variants, ctorName);
113:        if (!variantType) {
114:          throw new IbisError("undefined constructor: " + ctorName);
115:        }
116:        break;
117:      }
118:      unify(inferredType, variantType);
..
https://github.com/takuto-h/ibis-js/blob/ibis-js-1.0.0/src/inferer.js

case 式の型推論では、112行目でいくつかのパターン節 clauseExprs から最初に取り出せたコンストラクタ名 ctorName を使ってタグ環境 variants からバリアント型 variantType を取り出しています。

このことによって、コンストラクタ名からバリアント型は一意に定まらなくてはならないために、同一のスコープ内で異なる型を返す同名のコンストラクタを同時に定義することはできないことがわかります。

前:let と let rec 目次

Ibis のバリアントとパターンマッチ

パターンマッチは必須か

Ibis にバリアント型を実装する際問題となったのが、バリアントをどのように分解するかです。多くの関数型言語ではパターンマッチを使いますが、パターンのパーズやさまざまなデータ型への対応が必要となるため、少々面倒です。Ibis では実装の容易さを優先するため、通常のパターンマッチとは異なる手法を採用しました。

最低限のパターンマッチ

Ibis で採用した手法は以下のとおりです。

  1. バリアントはタグとただひとつの値を保持する。
  2. パターンマッチはタグによって分岐し、保持していた値に関数を適用する。
  3. パターンマッチの対象はバリアントのみ

例えば、

type nat = Zero of unit | Succ of nat

というバリアント型 nat の定義では、コンストラクタ Zero によって作られるバリアントは Zero というタグと unit 型の値を保持し、コンストラクタ Succ によって作られるバリアントは Succ というタグと nat 型の値を保持します。

case n of Zero -> f | Succ -> g

という式は、nat 型のバリアント n のタグがもし Zero なら保持していた unit 型の値に f を適用し、Succ なら保持していた nat 型の値に g を適用します。

case n of Zero -> f | else -> g

という式の場合、タグが Zero なら同様ですがそれ以外なら n 自体に g を適用します。

例:自然数の加算

例として、nat 型の値を自然数ととらえ加算する関数 add の定義を挙げます。

let rec add = fun m -> fun n -> case m of Zero -> fun _ -> n | Succ -> fun k -> Succ (add k n)

インデントを整えると、

let rec add =
  fun m -> fun n ->
    case m of
      Zero -> fun _ -> n
    | Succ -> fun k -> Succ (add k n)

OCamlで等価なものをあえて冗長に書くなら

let rec add =
  fun m -> fun n ->
    match m with
      Zero _ -> n
    | Succ k -> Succ (add k n)

となります。

Ibis 流パターンマッチの実用上のメリットはほとんどありません。ただ、小さなプリミティブで新しいデータ型の定義というそれなりに高度な機能が実現できるのは、言語を作るのが趣味の人間として魅力を感じるところです。

JavaScriptによる型推論器の実装: let と let rec

前:多相型 目次 次:バリアント型

再帰関数の型推論

以下は、階乗を求める関数 fac の定義です。

let rec fac = fun n -> if n = 0 then 1 else n * fac (n - 1)

このように、Ibis で再帰関数を定義する際は let ではなく let rec を使います。これは OCaml に倣ったものです。この二つの違いは何か、型推論の観点から説明します。

再帰関数と型変数

上の fac の場合、関数本体の型推論をする際、そこに fac 自身が現れます。そのため、あらかじめ fac の型を仮に決めておかなくてはなりません。そこで型変数が登場します。let と let rec の型推論のコードを見比べてみましょう。

47:    case "Let":
48:      var inferredType = infer(ctxt, env, variants, expr.valueExpr);
49:      var typeSchema = createPolyType(inferredType);
50:      Env.add(ctxt, expr.varName, typeSchema);
51:      return createAlphaEquivalent(typeSchema).bodyType;
52:    case "LetRec":
53:      var varType = Type.createVar(null);
54:      var newCtxt = Env.createLocal({}, ctxt);
55:      Env.add(newCtxt, expr.varName, Type.createTypeSchema([], varType));
56:      var inferredType = infer(newCtxt, env, variants, expr.valueExpr);
57:      unify(varType, inferredType);
58:      var typeSchema = createPolyType(inferredType);
59:      Env.add(ctxt, expr.varName, typeSchema);
60:      return createAlphaEquivalent(typeSchema).bodyType;
src/inferer.js

let rec のほうには varType という変数があり、そこに型変数が代入されています。これが仮決定した fac の型です。fac の型を varType とした新しい環境 newCtxt で、関数本体の式を推論します。仮決定した型 varType と推論結果 inferredType は一致していなくてはなりませんから、この二つを単一化します。後は、let の場合と同様です。

このように、Ibis において let と let rec では推論の手順がわずかに異なります。もし let rec がなければ再帰関数は定義できません。

再帰でない let の必要性

では、もし let にあたるものがなければどうなるでしょうか。この場合、過去に定義された同名の変数を新しい定義内で参照できなくなります。これについては以下のページがわかりやすいです。

let が再帰でない理由というかメリット - camlspotter’s blog

Ibis では構文をなるべく OCaml に近づけようという思いからこの区別を採用しました。

前:多相型 目次 次:バリアント型