内包表記と並列性忘却と

プログラムで扱う値の集合(や列)を表す表記法として、内包表記(comprehension)というものを備えているプログラミング言語があります。聞き慣れない方もおられることでしょうが、数学の集合を書き表す際に馴染みのある

{x | x ∈ A, P(x)}

のような表現法のことです。この表現は、集合Aの元xのうちで、条件Pを満たすようなxからなる集合を表すものです。

この表現は、2/16の記事「並列性忘却プログラミング」、 すなわちPOP (Parallelism-Oblivious Programming) でも注目しています。集合Aをxを生成する生成子(generator)ということもあります。Aを生成し、Pでテストするということを自然に表わていますので、Generate-and-Test の方式で解を得る一般的な計算を表現しているといえます。そして、この表現の中には、逐次的に実行しなければいけないというところがない(生成したものをテストするという順序だけ?)ので、並列化の自由度が高いという点で、「並列性を意識しないで並列プログラムを開発する」ことにピッタリだというわけです。

この表記法、目新しいようですが、いつからあったのでしょうか。

私がこの表記法でプログラムを書いたのは、D.A.Turnerによる関数型言語Mirandaのシステムを使ったときでした。しかし、集合論のZermelo-Frankelの名を冠して、ZF-記法と呼んで関数型言語に導入したのはMirandaの前身KRCだったようです。

http://en.wikipedia.org/wiki/Miranda_(programming_language)

Mirandaが出たのが1985年といいますから、もう四半世紀になります。TurnerはMirandaの前身の言語SASLやKRCを公開してから、いわば、製品版としてMirandaを出しました。SASLのインプレメンテーションには驚くべきアイデアがありましたが、その話はまたの機会にします。そのアイデアをもとにMirandaが開発されたのです。

話が逸れますが、開発者のTurnerはMirandaのライセンスを販売する会社Research Software Ltd. を作ったようでした。私は使ってみようとして、そこからMirandaライセンスを購入しました。20年余り前のことです。金額は忘れましたが、大学で英ポンドでの購入手続きは一般的ではなく、手間取ったことを思い出します。Mirandaを使ったプログラム例が拙文

武市正人. 関数プログラミングの実際. コンピュータソフトウェア8 (1), pp.3-11, 平成3年(1991).

にあります。実行例に

“The Miranda System version 2.009 last revised 14 November 1989, “

とあります。内包表記はそのプログラム例にも現れています。

現代的な(といっても、四半世紀以上前の)SASLやMiranda、それに最近のHaskellなどの関数型言語の表現法の原型は、1966年のISWIMにあるといえます。

http://en.wikipedia.org/wiki/ISWIM

しかし、プログラミング言語に内包表記を導入したのは1980年頃のKRCが最初でしょう。D.A.Turnerの卓見だといえましょう。

われわれがPOPの実験を行っている言語Fortress

http://projectfortress.sun.com/Projects/Community

にも入っています。

計算のステップを感じさせない水準の高いこのような記法がPOPの中核となるでしょう。

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中