25年前の未来の言語の話

私ごとですが、12月の9日に50歳になりました。そこでというわけでもないのですが、25年くらい前のプログラミング言語の技術について書きたいと思います。お話は大学院で学んだ動的型付けの並列オブジェクト指向の実装に偏っています。

# 背景
時は1990年代前半、今と同じようにCPUの性能は頭打ちになり解決策は並列化しかないということで盛んに並列処理の研究がされていました。もっとも、その後CPUは1000倍以上速くなっているのですが。
1981年にBYTE誌でSmalltalk-80を衝撃的に紹介されたのをきっかけにオブジェクト指向が注目されC++によって実用レベルで使われだしてきました。それとは別にSmalltalkのごく初期の実装（-72）にインスパイアされた、オブジェクト指向によく似た並列な計算モデルとしてアクターモデルというものが1973年に提唱されていてアクターモデルを応用した並列処理言語が盛んに開発されていました。

## アクターモデルと並列オブジェクト指向
アクターモデルは1970年代初頭にCarl Hewittさん達が提唱したモデルです。もともとのアクターモデルは、「規則は一杯」ではなく少数の規則、すなわち

* 場にアクターというものがあってメッセージのやり取りをして計算します。アクターは並列に動きます
* アクターはメッセージを受け取ると、アクターを作ったり、別のアクターにメッセージを送ります

からなります。これだけでプログラムを書くのはλ式でプログラムを書くようなものなので、もうちょっとアクターを賢く拡張するのが普通です。
似たような話にCSP(Communicating Sequential Processes)がありますが、CSPでは発信者がメッセージを投げた時に受信者は受け取る準備をしていなければなりません。一方、アクターモデルではメッセージは相手の都合にお構いなく投げてもよいです。このような動作のため、実装ではメッセージをためておくためのキューが通常必要になります。
アクターモデルはメッセージパッシングで通信するという本来のオブジェクト指向に近く、本質的に並列なのでアクターモデルを拡張して並列オブジェクト指向言語を開発するという考えは非常に自然であると思いますし、現にそう言う処理系がたくさんあります。
またアクターモデルはアクター間でデータを共有しないのでメモリを共有しない多数のコンピュータからなる環境(分散環境)での実装に有利です。そして25年前の当時、ハイエンドのコンピュータはベクトル型からメモリを共有しない多数のCPUを高速ネットワークでつないだ超並列コンピュータ(その代表的な例がCM-5)が主流になりつつありました。

## リフレクション
私の通っていた大学院(JAIST一期生です)は入学のためのペーパーテストとかはなく、大学院でやりたいことを小論文にまとめてその内容をプレゼンするという内容でした。ここで、私はComputer Todayで読んだリフレクションの記事に感動してリフレクティブ言語のプログラミング環境というネタを提出しました。
幸い、無事合格したのですが、その後大学(学部)の担当教官に、「で、リフレクションとはそもそも何かね？」って聞かれたのですが、うまく答えられませんでした。自分自身への計算ですとか答えたのですが、それって昔からやられている自己書き換えと何が違うの？って突っ込まれて撃沈です。JAISTの面接で聞かれなくて本当によかったです。
あれから28年、私が理解しているリフレクションの定義を出来る限り丁寧に説明したいと思います。

説明にあたって、とりあえずリフレクションではなく給料計算を考えてみましょう。
給料計算をおこなうためには、基本給だけではなく、どれだけ残業したかその時の残業代はいくらかとか、残虐行為手当[^1]に該当する業務なのか、その金額はいくらかなどいろいろ考える必要があります。これらの決まりは通常、就業規則に書かれています。
これは見方をかえると、就業規則の賃金に関する項目のシミュレーションを行っていると考えることもできます。もっと一般化すると、全てのプログラムはある「物」(実在しているかもしれないし、していないかもしれない)のシミュレータと言えるわけです。この「物」を横文字でモデル(model)とか言うわけです。

[^1]: pit fighterというATARI社の格闘ゲームの用語です。このような手当てのある会社はおそらく日本には無いです

さて、このモデルを自分自身(コンピュータ)を考えたらどうでしょうか?(コンピュータ科学者や数学者はすぐこういうことを考えがち)
この場合、自分自身を表す何らかのモデルがあり、そのモデルを色々いじることで、自分自身の状態を知ったり状態を変えたりできるわけです。ここで重要なのは、計算機の状態という通常プログラムで扱えないものを自分自身のモデルを持つことでプログラムで(おそらくデータかAPIとして)扱えるということです。このように自分自身をモデルに持ち、自分自身に対して色々操作したり状態を見たりできるのがリフレクション(自己反映計算)といいます。
どのようなモデルにすると自分自身がちゃんとモデル化できるか、使いやすさを無視すれば簡単です。たとえば、前述の担当教官の自己書き換えを使うという話もモデルとして考えることが出来るでしょう。この場合は自分自身のモデルとして、「メモリ全体を配列として表現したもの」とすればいいです。もちろん、ものすごく使いにくくて多くの場合実用にはならないですけど。

ではどういうモデルがいいのか？というとリフレクションについてバイブルみたいな論文([Reflection and Semantics in Lisp](https://www.ics.uci.edu/~jajones/INF102-S18/readings/17_Smith84.pdf) があり、この中では関数を呼び出した時点での、継続(これから行う計算を抽象化したもの)と環境(変数のシンボルとその値の表)を引数として渡してもらうことで実現しています。
そうじゃないモデルもあり、たとえば自分自身への操作をちょうどOSのシステムコールのように一覧の表にしてそれをカスタマイズするようにするモデルや(RbCl)、関数の集合(CLOS)、オブジェクトの集合(Aperitos)などいろいろ考えられます。

この自分自身のモデルを操作する処理をメタレベル、そうではない通常の処理をベースレベルといいます。

### リフレクティブタワー

自分自身をモデル化するということは、そのモデルには自分自身をモデル化したものも含まれている（ややこしいですけど)と気付く人もいると思います。言いかえれば、メタレベルのメタレベルのメタレベルの...と無限に続くわけです。これをリフレクティブタワーといい、非常に人気のある概念ですが、実装を大変にする原因でもあります。
リフレクティブタワーが何に使えるかというと私の知る限りでは余り思いつかないのですが[^2]、美しい概念なので取り入れたいものです。
[^2]: Aperitosのメタオブジェクト空間を構成するメタオブジェクトのカスタマイズにはリフレクティブタワーが有効な例である気がする

最近の言語ではメタのメタのようなものを考えずにリフレクティブタワーを実装しない傾向があるように感じますが、25年前はみんなまじめにリフレクティブタワーを実装しようと取り組んでいました。


## リフレクションと並列オブジェクト指向
並列オブジェクト指向とリフレクションがどう関係するのでしょうか？リフレクションは並列オブジェクト指向言語を分散環境で実装するときに効力を発揮します。分散環境では様々なことがプログラムが解決したい問題とその実行環境に依存します。

例えば、２つのオブジェクトが大量の計算をおこなうなら別のCPUにあった方がいいだろうし、頻繁にメッセージのやり取りをするなら同じCPUに合った方が有利。そういう状況でどのCPUにオブジェクトを生成するかを決めるのは、解決したい問題と環境の詳細(どのくらいの速さのCPUがいくつあって、その通信速度はどのくらいかみたいな情報)が必要になるでしょう。つまり、自分自身の環境の情報を知っている必要があります。
また、どのCPUにオブジェクトを作るか決定するといった、問題の本質とは関係ない処理は解きたい問題とは切り離して記述したいものです。
このような場合、ベースレベルに解決したい問題を、メタレベルにどのCPUにオブジェクトを生成するかのような実装に関する問題を書けば綺麗に記述できるでしょう。

もっと面白い例もあります。多数のCPUが同時に動くシステムだといちいち同期をとっているとものすごく遅くなるので、他のCPUの動きにお構いなく処理を進めるという方法があります。こうすると、当然他のCPUとの絡みで過去に受け取っていなければならないはずのメッセージを受け取るなどつじつまが合わなくなる可能性があります。あらかじめ状態を保存しておいて、そう言うつじつまの合わない事態になったら時間を巻き戻すのです。こういうアルゴリズムをTime Warpアルゴリズムといい、大規模な並列環境でもいい感じにスケールするみたいです。NASAジェット推進研究所ではOSが開発されています(https://www.math.fsu.edu/~bellenot/tw/)
こんなの普通に書いているとものすごく大変ですけど、リフレクションを使うと綺麗に書けたりします。

# 実装

リフレクション、よさそうだけど遅そうって思った方、正解です。プログラムの動作をカスタマイズできるようにするということはコンパイラの言語とインタープリタ(JIT無し)の言語を比べるようなものです。しかし、頑張って高速化しようとしています。
高速化のためのテクニックは例えば実行時に型をプロファイルしてある型に特定化したり、メソッドキャッシュを使ったり色々あるのですが、リフレクションの高速化のための技法としては部分評価が大きいです。

## 部分評価
　
例えば
f(x, y) = x + y
という関数を考えてみましょう。この時、必ずｘは1であることが分かっているなら、fは
f'(y) = 1 + y
とすることが出来ます。このように引数の全部が分かっていてその値が分かるわけではないが、引数の一部が分かっていてそれを元により効率的なコードが生成することを部分評価といいます。この例では簡単ですが一般的に部分評価を実装するのはそれなりに大変です。

部分評価といえば二村射影を外すわけにはいかないでしょう。二村射影は、部分評価とインタープリタ・コンパイラの関係の話です。インタープリタIを考えてみましょう。インタープリタIはプログラムPとプログラムPの入力dを受け取って出力rをえると考えられます
　I(P, d) →　r
となります。
さて、Pはインタープリタ起動時には当然わかっている(dはI/Oなどがあると分かっていない可能性がある)ので、I(P, d)をPで部分評価できます。そうして出来たI'は
　　I'(d) → r
となり、ちょうどPをコンパイルしたのと等価になります。このようにインタープリタを部分評価することでコンパイラになります。これを二村射影っていいます。

リフレクションを実装しようとすると、インタープリタの嵐になります。リフレクティブタワーをサポートしようとすればメタメタのインタープリタ、メタメタメタのインタープリタとか出てきてなおさらです。でも、二村射影でそれが最適化されたらどうでしょうか？そう言う感じで部分評価を使って静的に分かっているメタレベルの情報から出来る限り効率的なコードを生成するのが最先端だったようです。

# まとめ
こうしてみると、25年前もそれほど変わっていないように感じますが、いかがでしたでしょうか？静的型付けの言語は無かったの？という感想の人がいるかと思いますが、もちろんありました[^3]が私が語れるほど詳しくないだけです。
[^3]: たとえばpSather

しかし、大きく変わったこともあります。これまで説明したようなシステム、25年前は本気で分散環境を構築してこのような言語を実行しようと思うと、安くてウン百万、高いと億の値段のコンピュータが必要でした。今はどうでしょう？ラズベリーパイを8個ほど用意してスイッチングハブでつなげば20万円以下で構築できそうです。当時限られた人だけが見ることが出来た景色をその気になれば多くの人がみられる時代、事態はよくなっています。