言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > Smalltalk 勉強会@名古屋 STEPS プロジェクトご紹介

Smalltalk 勉強会@名古屋 STEPS プロジェクトご紹介

http://atnd.org/events/1593 のカンニングペーパーを貼ります。プレゼン資料: http://scratch.mit.edu/projects/propella/811272

自己紹介

こんにちは、山宮と言います。STEPS プロジェクトの紹介をします。

まず簡単に自己紹介をさせてください。2003 年に梅澤さん達と同時期に未踏事業で Smalltalk を作ったアランケイに会いまして、その関係で三年前から彼の研究所であるロサンゼルスのビューポインツに居ます。ビューポインツとは、アラン・ケイが率いるNPO の研究組織で、多くの Squeak 開発メンバーが参加しています。

概要

STEPS プロジェクトは 2007 年に NSF の支援を受けて始まった5 年間の研究プロジェクトです。今回 STEPS プロジェクトの内でも特にプログラミング好きの皆様が興味を持ちやすいポイントに絞ってご説明します。

  • 自由な環境(OS + 言語 + アプリ)

みなさんのような Smalltalk 愛好家にとっては、OS から アプリまでを含んだ自由なシステムの良さについて自明だと思うので省略します。

  • 短いコード

個人のための自由な環境にはプログラム全体の長さが重要です。システムが大きく複雑になると個人の手に負えなくなるからです。

例えば Windows XP で40,000,000 行、 SqueakV3.sources の行数は約400,000 行ですが、STEPS ではざっと桁を縮めて全体の大きさ 20,000 行を目標にしています。この大きさだと、一ページ50 行で換算して丁度 400 ページの文庫本に収まります。二、三日で読める一冊の文庫本に小説家の世界観が凝縮されているように、週末の読書で STEPS プロジェクトの全体像が理解出来るというのが目標です。

手法

それではどうすれば短いプログラムが可能になるでしょうか？注意しなくてはならないのが、短ければ良いという事では無いという事です。分かりやすく短くというのがポイントです。

STEPS ではまず、「ムード固有言語」という物を使います。これは DSL つまり、問題に応じて必要な言語を使い分けるという事です。ドメイン固有を極端に進めた形としてムード固有とシャレで呼んでいます。

STEPS プロジェクトの実装である COLA では、様々な言語で書かれてた小さなプログラムを PEG という仕組みで Lisp 風の内部表現に変換します。それからさらにまた PEG を使って今度はハードウェアやバーチャルマシン用のアセンブラに変換し、実行します。それでは細かく見て行きましょう。

DSL というと難しく聞こえますが、みなさんも、ある機能に特化されたミニ言語を使われる事はよくあると思います。

正規表現, HTML, Wiki, SQL, 設定ファイル, BNF/PEG

何故固有言語によって記述量が減るのかという事について確認します。言語には様々な特性がありますが、ここでは語彙と文法に着目しましょう。

まず語彙について考えます。問題によって使われる語彙が違うので、出来るだけ小さい語彙を使うと使い勝手がよくなります。単語の数が多くなると区別のために長い単語が必要になります。また予約語を上手く選択すると、複雑なアイデアを単純な記法で表現する事が出来ます。例えば SQL でよくある、テーブルを組み合わせて結果を出すような事をループを使ってプログラムで書くと、相当複雑になってしまいます。

次に文法について考えます。文法にはそれぞれ固有の複雑さがあるという事が知られています。例えば HTML では常にタグの対応に気を配る必要があり、失敗すると何も画面に表示されないという事が起こりますが、多くのWiki 記法は行指向で、失敗してもおかしくなるのはその行限りです。また、ウェブページに Javascript があると無限ループで固まる可能性がありますが、HTML だとその心配は不要です。これは、言語の文法には複雑な物と簡単な物があって、複雑になるほど出来る事が増える一方で失敗の原因も増えてしまうという事です。出来るだけ複雑さの無い文法を選択する事が重要になってくるでしょう。

結局、出来るだけ少ない語彙で、単純な文法を選ぶ事が短いプログラムに繋がります。

PEG

様々な種類の言語に対応する為に、STEPS では PEG という仕組みを使います。PEG とは言語のパーサを作るための仕組みで、プログラムで直接パーサを書くよりもシンプルに DSL を作る事が出来ます。ここで、私の同僚が作ったOMeta という PEG を使って動作をご紹介します。

(OMeta2 デモ)

どこでも PEG

ここまでは主にテキストとしての言語を上手く使い分ける話をしましたが、言語という物をもっと広く捉えて、中間的なデータ構造やコンピュータへの入力等、あるルールに従ってやってくる信号全てを言語と考えてみましょう。例えばマウスからの入力やネットからやってくるパケットにも構造があり、言語として捉える事が出来ます。こうした考え方は新しい物ではなく、コンピュータサイエンスの初期からありました。ちょっと歴史を振り返ってみましょう。

歴史

まず、ステートマシンと文法が対応するという考えは 1956 年にノーム・チョムスキーによって体系づけられています。彼のアイデアによると、表現出来る質によって様々なレベルの文法があって形式的に表現出来るそうです。

このアイデアは 1959 年にジョン・バッカスが Algol60 の仕様策定に使ったBNF 記法でプログラミング言語向けに練り直されました。それ以前のプログラミング言語の文法の説明には主にステートマシンを図示した物が使われていました。みなさんの中でも古い書籍の中に、丸い記号と矢印を使って言語の文法が図示されているのを覚えていらっしゃる方がいるかと思います。

そして 1964 年、D.V.ショーアが文法をコンピュータで実行する MetaII というアイデアを発表します。それまで文法仕様を元に人間が手でパーサーを書いていましたが、MetaII では書かれた文法をコンピュータで処理してパーサーを作り出す仕組みでした。その中で特に当時のハッカー達を喜ばせたのが、MetaII 自体の文法も MetaII で書かれていた点でした。

このアイデアはさらに発展し、テキストファイルだけでなくあらゆるデータ構造を文法を使って解析する Tree Meta という仕組みに発展しました。Tree Meta は ダグラス・エンゲルバードによる NLS の開発に使われ、大いに役立ちました。1968 年に公開された NLS のデモは大きな話題を集め、アラン・ケイ達若い研究者を刺激しました。

アラン・ケイ自体は Tree Meta を使う事はありませんでしたが、Smalltalk 72 の基本的なアイデアの一つは Tree Meta のパターンマッチングを言語に組み合わせて、拡張可能な言語を作り出す事でした。ここで例を挙げましたが、Smallalk 72 のプログラムは次のシンボルを読み進めながら実行パスを選択して行くという形になっています。今の Smalltalk がオブジェクトとメッセージ名の組み合わせでメソッドを選択するのに比べて、より柔軟で「メッセージ送信」というメタファに合っているかもしれません。

課題

ここで、折角 Smalltalk 勉強会ですので、アランさんがよく話題に出す
Smalltalk で実現出来なかった機能を三つ挙げます。

  • 拡張可能文法
  • 代数としての多態性
  • インターネット的プログラミング

拡張可能文法については先ほどお話しました。多態性とはオブジェクトが種類に応じて一つのメッセージに対して独自に処理を行うという物です。これは大変柔軟なアイデアでしたが、すぐに問題が明らかになりました。メッセージの実装については何の制約も無いので、プログラムを読んで実際の動作が予想出来ないという事が起こります。例えば Smalltalk では演算子の定義が出来るので、ユーザの作ったオブジェクトに加算や乗算を定義する事が出来ます。しかし例えばもしも気まぐれに加算の定義が引き算だったらプログラマは安心してプログラムを組む事が出来ません。

これを解決するには代数的な方法があります。代数では、演算につかうデータ、整数、実数、ベクトル等を気にしないで、演算子同士の関係を使って演算子の性質を定義します。例えば加算と乗算について考えると、おなじみの交換法則や分配法則が挙げられます。演算子が扱うオブジェクトが例え整数であっても複素数であっても、この法則さえ満たせば式だけを見て代数的な変換が出来ます。アランさんは Smalltalk にもこのような制約が必要だと考えていました。

また、Smalltalk のメッセージ送信というメタファを非同期通信に拡張する事も考えられていました。これは単にマルチプロセスを行うという事では無くて、理想としては一台のコンピュータがインターネットのようにシステムを止めずに進化して行く事を目標にしていました。つまり、私たち生物が細胞レベル、個体レベル、生態系レベルでフラクタルな循環系を持つように、コンピュータ内部にもネットワークを持つ事によって強靭なシステムが出来上がると考えたのです。

STEPS プロジェクトには、Smalltalk で実現されなかったこれらのアイデアを復活させようという狙いもあります。

demo

プロジェクトが開始されてからこれまで、私たちのチームは小さなプロトタイプを作ってはやり直すという事を繰り返してきました。その中からいくつかご紹介します。

  • tcp-ip
  • mouse driver
  • nile
  • COLA/Flash
  • rccola

まとめ

という事で STEPS についてご紹介しました。STEPS プロジェクトはSmalltalk の伝統を一度完全に破棄して新しい環境を作ろうと言う物ですが、一方で Smalltalk に込められたアランケイの最初の動機を忠実に再現しようとしている物とも言えます。まだ完成まではほど遠いですが、ここから生まれた部分的なアイデアもちょくちょく公開して行きますので是非ご期待下さい。

参考