Category Archives: 研究トピックス

Implementation of Conflict-free Collaborative Data Sharing

CCDSAgent is an agent for Conflict-free Collaborative Data Sharing for distributed systems based on our published papers:

Through the implementation of the CCDSAgent, we made several findings in details which are not described in the paper, e.g., Operational Transformation and Concurrent synchronization.

Our implementation reveals the versatility of the CCDS approach:

  • The CCDSAgent does not use any locks for shared data nor has any chances of blocking in message passing.
  • Separation of peer’s application from synchronization of shared data would demonstrate our proposal of “Sharing-Oblivious” design for distributed systems.

 

CCDSAgent for Conflict-free Collaborative Data Sharing

24年前の著書の中の参照情報について

先日、24年前に出版した書籍について、出版社（岩波書店）から、その中に記載した参照情報について「読者からの問合せ」があったという連絡がありました。

その参照情報は、インターネット上から得るソフトウェアに関するものです。現在も（よりいっそう）インターネット上で公開されている参照情報の引用も多くなっていますので、今後に向けて考えることも必要でしょう。

その書籍というのは

  • 武市正人著「プログラミング言語」（岩波講座 ソフトウェア科学  ４）
  • 1994年6月17日
  • ISBN4-00-010344-X C3355

です。

いまや多彩な「プログラミング言語」が存在しますが、執筆当時もそうでした。この本は特定のプログラミング言語について述べたものではなく、さまざまなプログラミング言語に見られる共通の概念を「プログラミング」によって示そうと試みたものです。すなわち、「プログラミング言語をプログラムする」(Programming Programming Languages)ことで「プログラミング言語」の基本を理解することを目指しています。その内容については「古典的」だといえるでしょう。この考え方をここで詳しく述べることはせずに、関心のある方には本書を見ていただくとして、ここでは、この本の読者の方から問合せのあったことについて書くことにします。

本書では、「・・・をプログラミングする」というのですから、当然、そのためのプログラミング言語を使っています。執筆当時にはGoferという関数型言語が一般的でした。また、その処理系が無償で配布されていて読者の方々にも使っていただけると考えてGoferを使いました。当時（から何度かの増刷の間）は、このGoferはYale大学のサイトで提供されていました。本書のpp.220-221には、参考書リストの末尾に「ソフトウェアの入手方法」を載せてあります。今とは違って、ftpによってアクセスしていたようで、そのアクセス法（と標準的なレスポンス）を書いてあります。

ところが、今はそのサイトにはアクセスできなくなっています。現在、関数プログラミングに携わっている方々でもGoferという名前を聞いたことがないかも知れません。実際、半年ほど前に、私自身が著書の中のプログラムを掘り起こして使おうとしたときには、Goferではなく新しい言語に書き直しました。24年前（の出版時よりも数年前）に使った言語から、今、使っている言語への（少しの）書き換えでしたが、昔、自分で書いたものですし、著書に説明も書いたのですからそれほど手間はかかりませんでした。

さて、現在、この本で使っているソフトウェアから現在のソフトウェアに移行するのはどうすればよいのでしょうか。Goferだけではありませんが、このような（Goferだけではなく類似の）言語の発展として、いまはHaskellが一般的だといえるでしょう。読者の方々にもこの情報を提供したいと考えてこの記事を認めています。実際、現時点でそのような環境を整えるには、インターネットで「Haskell インストール」で検索すれば多くの情報が得られるでしょう。大別すれば、Windows OS向けとMac OS向けでしょうか。手元のOSに合ったシステムを導入していただきたいと思います。具体的な手順については、それぞれの説明を参照していただくのがよいでしょう。

さて、24年前の本書に現れるGoferプログラムのコード（テキスト）についても、当時、安定的に提供できると考えていた著者の所属先サイトを示していました。７年ほど前にそこを辞した後、そのサイトも閉鎖されていますので、その対応も必要でしょう。上述のように、GoferプログラムがそのままHaskellで処理できるわけではなく、少し、手を入れる必要がありますが、それでもなお、もとのテキストがあるとないでは大違いでしょう。そこで、ひとまず、ここに掲載することにしました。

「プログラミング言語」の中のプログラム一式

zipファイルですが、ダウンロード後に解凍することによって各章のファイルが得られます。拡張子GSのついたファイルがGoferのプログラムで、拡張子LOGのファイルはGoferの処理系での実行結果です。さらに、GPという拡張子の付いたファイルでは、いくつかのGoferプログラムからなるプログラムの場合に関連するGoferのファイルを列挙したものです。活用いただければ幸いです。

ピアレビューの陥穽

驚きました。いまもなお、といってはなんですが、こういうことは繰り返されるのでしょうか。

国立国会図書館のカレントアウェアネス・ポータルに
「SpringerとIEEE、機械生成されたでたらめな論文120本以上をプラットフォームから削除」という記事が出ています。

2014年2月24日付けのNature誌の記事で、SpringerとIEEEの商用プラットフォームに収録されている会議録論文の中に、機械生成されたでたらめな論文120本以上が含まれていたことが報じられています。現在はこれらの論文は削除されているとのことです。

もとのNature News 2014/02/24 は

Publishers withdraw more than 120 gibberish papers

にあります。

Computer Science 分野の論文生成システム（といってよいのかどうか？）SCIgen – An Automatic CS Paper Generator で生成した論文だということです。冒頭に

Our aim here is to maximize amusement, rather than coherence.

とあるように、まったくのおふざけなのですが、2005年にSCIgenの作成者がある会議に投稿したり、その後も、話題にはなったようです。

20年ほど前だったでしょうか、IEEEと並ぶ、米国の（というより、国際的な）Computer Science の学会 Association for Computing Machinery (ACM) の雑誌の記事として（もちろん、冗談交じりに）出たことがあったように記憶しています。この頃には、人工知能(Artificial Intelligence, AI)の話題であったのでしょうか。SCIgenでは、グラフや表も生成されるようですが、その前にはテキストだけだったと思います。

今回のSCIgen論文が見つかったのは、SCIgenで生成された論文かどうかを判定するシステムによるとされています。SCIgen detection Site というのもあります。2010年頃には、いんちき論文を検出するためのアルゴリズムが発表されています。

学術論文の発行、公表は通常、ピアレビューが行われます。つまり、“同業者”が相互に論文を査読して、新規性や独創性など評価に値することを確認した上で公開するわけです。しかし、この、「専門家に委ねる」というところに落とし穴があることは、たびたび指摘されています。本当に査読ができているのかどうか、ピアレビューというのが機能しているのかどうかということは、論文誌の信用に関わることです。ついうっかり、ということで偽装論文を見過ごしてしまうと、ランダムに生成したという論文までもが掲載されるということも起こりかねません。

1995年には「ソーカル事件」が話題になりました。翻訳版「『知』の欺瞞――ポストモダン思想における科学の濫用」の副題にある「科学の濫用」は、学術界が社会に対する責任の危うさを示しているといえるでしょう。

論文の偽造だけではありません。身内で学会を作って論文を公表すれば、論文数を増やすことができるとか、実態のない国際会議をでっちあげて発表を募るといったことも目にします。いずれも、外形はもっともらしいので、疑いをもたない人たちには分からないでしょう。これも、ピアレビューの落とし穴でしょう。

学術の世界、また、科学者が社会から信頼されるためには、自らの誠実さに責任をもたなくてはならないといえます。

研究用ソフトウェア環境の整備

しばらくBlogを休みましたが、その間に、Mac OS Snow Leopard上に関数プログラミング言語Haskellの環境の整備をしました。

Haskellは1998年版が基準になっているということで分かるように、かなり歴史がある言語になりました。コンパイラはGlasgow版のGHCが一般的です。最新版のGHC6.12.1をインストールしましたが、その道筋は単純ではありませんでした。

以前に書いたPOPP(Parallelism-Oblivious Parallel Programming)の実験のために、GHC6.12.1をインストールしようと考えたのです。一方で、並列実行のプロファイルをとるツールとしてThreadScopeが開発されているのですが、これは、Gtk2hsというGUIライブラリを使っていて、GHC6.10.3でコンパイルする必要があるというので、バージョンの違うGHCを使い分けるという複雑なことになっていたのです。

詳細は省きますが、ともかく、2日がかりでこのあたりの事情はよく分かりました。これから、POPPの実験を始めようと考えています。今年度の卒業論文でT君が試みたものの、GHC6.10.4のランタイムシステムの並列実行の挙動がよく分からなかったところを追試してみたいと思います。

研究のための環境を整えることも研究の一環です。ソフトウェアの環境の整備は他に比べて楽だと思うのですが、最近は、なかなか複雑になっていて、手がかかります。終わってしまえば、そういうものかと分かるのですが、その過程ではいったいどうなるのか、やめた方がよいのではないかと思いながらも時間をかけて、環境整備を行ったことはよい経験でした。こういう作業も久しぶりでしたが、現状がよく分かりました。”An ounce of practice is worth a pound of theory” といえるでしょう。

シミュレーション技術と計算機科学

今日の夕方、JSTの「シミュレーション技術の革新と実用化基盤の構築」領域の打上げ会があります。7年ほど、アドバイザとしてお手伝いしました。というよりも、むしろ、各プロジェクト実施の研究者の方々から計算科学の実態をお教えいただいたように思います。これまでにも取り上げたことのある Parallelism-Oblivious Parallel Programming (POPP) という考え方が大事ではないかと思ったきっかけの一つだといえます。

余談になりますが、以前から、どうしようかと迷っていたのですが、Parallelism-Oblivious Programmingよりも、上に書いたPOPPのほうが誤解がないと考え、これからはPOPPにしようと思います。一月前、2010/2/16の「並列性忘却プログラミング」にもそのようなことを書きました。

モデル化を行ってシミュレーションによって物理的・化学的な現象を検証するというアプローチを「計算科学 (computational science) 」と呼ぶのが一般的でしょう。そこでは、スーパーコンピュータが活躍しますが、そのために(並列)プログラムを開発することが大きな課題となります。このような計算科学は、「理論」、「実験」に続く第3の研究方法論だそうです。科学の方法論には詳しくありませんので、このようなメタな議論には参加できません。しかし、シミュレーション技術が自然科学の方法論に影響を与えたことは分かります。

計算的手法による研究は多くの分野で一般的になってきています。いくらか抽象的ですが、計算科学を超えて(?)既存の知を高度に活用する第4の方法論として 「E-サイエンス (E-science) 」というものもあるそうです。目新しい用語に人が群がる姿はこれまでにも多くありましたが、ことばにしても概念にしても外国からの移入がほとんどです。E-サイエンスについては、計算科学とどこがどう違うのか、概念やねらいを正確に理解してから考えたいと思います。

このように、もう第4の足音が聞こえてきているところだそうですが、それでもなお、第3の方法論と言われる計算科学の核となるシミュレーション技術が多くの分野の研究を支えることはたしかでしょう。その基礎となるプログラム開発の手法、プログラミング方法論など、「計算機科学 (computer science) 」の研究が縁の下の力持ちとして支えることが大事だと思います。新たな方法論だけに向かうことだけでは困るでしょう。

今夕の打上げの後のことはまたいつか書くことにしたいと思います。

プログラムのレイアウト

昔から、プログラムの表記法にはいろいろな話題が尽きません。

今でも、多くのプログラミング言語は英字、数字、記号などの文字(いわゆる、ASCII文字)で書くのがほとんどだと言ってよいでしょう。それを1次元の文字列として考えるかどうかということもあります。さすがに、今では、大昔の(いわゆる)IBMカードを重ねたカードデック(カードの束)のように、物理的に2次元(?)の形状をとることはないでしょう。

最近は、Emacsに言語ごとにモードが設定できて、賢いレイアウトを行って、読みやすいレイアウトが自然にできるようになっています。1次元の文字列のプログラムを2次元にレイアウトして分かりやすく表示しているわけです。

関数型言語では、かなり前から、レイアウトによって区切り記号(デリミタ, delimiter)を省略しようとするのも一般的になっています。Haskellにも「オフサイドルール」が使われています。大雑把に言えば、前行よりも前に出ない部分はその前の行の文法上の構成の中の部分要素になっているというものです。また、一列に書くときにセミコロン(;)で区切るところを改行によって代用することもあります。

「オフサイドルール」は、1966年にLandinが提案したISWIM

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

にすでに現れているということです。ISWIMは実用的な言語ではありませんが、その後の関数型言語の設計に大きな影響を与えたものです。Landinは英国人だからというわけでもないでしょうが、サッカーやフットボールのオフサイドと発想に関連があるかも知れないと思ったりすることがあります。

http://en.wikipedia.org/wiki/Peter_J._Landin

2/16に「並列性忘却プログラミング」のことを書きましたが、最近、ときどき、Fortressという新しい言語を使ってみています。

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

この言語、大胆な試みが行われているのですが、なかでも、乗算(数のかけ算)の演算子は「とくにない」、いいかえれば、数学で普通に書くように、「空白」だというのです。一般のプログラミング言語で使うアステリスク (*) のように、目に見えるものは使わないのです。先日も、うっかりしていて、空白を一つ置いたのがエラーだというのが分からなくて難儀しました。もちろん、意識して乗算を表すときはよいのでしょうが、レイアウトの関係で空白を置いてしまったら、そこに乗算演算子があるというのは、なかなか気がつきません。

プログラムの表記を数学の表記に近づけるのはよいのですが、「幼児体験」としての先入観が邪魔をするところもあるようです。

内包表記と並列性忘却と

プログラムで扱う値の集合(や列)を表す表記法として、内包表記(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の中核となるでしょう。

双方向変換のための双方向関数

近年、構造をもつデータの双方向変換はいろいろな場で注目されています。われわれの研究室では、2003年度〜2007年度の5年間にわたって文部科学省リーディングプロジェクトe-Societyの「高信頼構造化文書変換技術」の中でXML文書の双方向変換の言語を設計し、それを用いて実用的な「WEBサイト編集支援システムVu-X」を構築しました。

http://www.psdlab.org/vux/index.html

もとのデータベース(構造をもつデータ)から注目する部分を抽出加工して、興味のあるビューを得るといった変換プログラムは多くの場面に見られるでしょう。双方向変換のうちの順方向の変換をこの変換だとすると、逆方向の変換はその逆変換ということになります。このような場面では、この逆変換は、ビューが更新されたときに、その変更をもとのデータベースに反映させるということになるでしょう。関数の逆関数という考え方がありますが、それに似ているといえます。ただし、膨大なデータベースからコンパクトなビューを作ることを考えると、ビューはもとのデータの一部の情報しか含んでいないので、ビュー上の変更だけでもとのデータベースをうまく更新することはできません。したがって、われわれが扱う双方向変換は、逆方向の変換でビューだけでなく、もとのデータベースも使うという形のものです。

Webページを構成するためのXHTMLやXMLによる文書は木構造のデータベースだと見ることができますので、双方向変換の対象は木構造ということになります。もちろん、対象とするデータ構造を枠を広げることも可能で、木構造からグラフ構造に広げる試みも行っているところですが、もう一度、XML文書処理のためのより一般的な仕組みも考え直しています。Vu-Xを開発したときの双方向言語Bi-Xはいわばアセンブリ言語のようなもので、プログラムの構造化の仕組みは存在しないので、変換プログラムの開発や保守にはかなりの熟練を要するものでした。そのために、プロジェクトでは、XML文書の標準的な(一方向)変換言語であるXSLTやXQueryで書かれたコードをBi-Xに変換するツールも開発しました。また、関数プログラミング言語HaskellでXML文書を扱うためのライブラリHaXmlに対する変換ツールも用意しましたが、これらのBi-Xへの変換にはさまざまな制限があって、実用的には課題が残っているというのが実態です。

XML文書の木構造を扱うには関数型言語が適しているでしょう。1999年に公開されたHaXmlは

http://www.cs.york.ac.uk/fp/HaXml/

にありますが、Haskellで書かれた関数群からなるライブラリです。よく整理されていて、単一方向の変換には便利なライブラリだといえます。そこで、それらを双方向変換向けに書き換えれば、単一方向の変換として書いたプログラムがそのままで双方向変換を実現することになって、いわば、タダで双方向変換のメリットを得ることができることになります。

このようにして、HaXmlライブラリを双方向化することを考えているときに、「双方向関数」(bidirectional function) を思いつきました。双方向関数はHaXmlだけではなく、より一般的な対象にも有効な「関数」です。これを用いて、HaXmlライブラリを双方向化したXHaXmlを作りました。このように、双方向関数を使えば、普通に書いたプログラムを簡単に双方化することができるようになるといえます。

並列性忘却プログラミング

最近、「並列性忘却プログラミング」に関心をもっています。「並列性忘却」は”Parallelism-Oblivious”の和訳で、「並列性を意識しないでよい」ということを表しています。「脱並列性」というのもいいかも知れません。

「最近」といっても、実は、2007年7月26日〜27日に Parallelism-Oblivious Programming (POP) のワークショップを開催したので、その頃から考えていたことです。ワークショップについては

http://www.ipl.t.u-tokyo.ac.jp/~kmatsu/pop07/index-j.html

にプログラムがあります。そのときの発表スライドは

http://www.ipl.t.u-tokyo.ac.jp/~takeichi/attachments/POP.pdf

です。

「並列」(parallel) は１カ所にしか現れていませんが、もちろん(?)、「並列性忘却並列プログラミング」(Parallelism-Oblivious Parallel Programming)、すなわち、「並列性を意識しないで並列プログラムを開発する」方法を追究しようというものです。POPよりもPOPP とするほうがよいのかも知れません。

1970年代には構造化プログラミング (structured programming) の議論がありました。いろいろな側面がありましたが、その中で、「同じ処理を記述するにしても、行儀のよい書き方をしよう」という教えも説かれました。プログラムの書き手によってその作風がまちまちだと、分かりにくいプログラムはそれが正しいかどうかも確認できないし、他人には理解できないのは問題だ、ということでした。プログラミングのよい「スタイル」を考えようということでした。

最近の並列プログラミングの世界はどうでしょうか？最新の並列計算機のアーキテクチャが頻繁に変わるということもあり、また、性能を最大限に活かすようにプログラムをチューニングしようということもあってか、細部にわたって並列制御のコードを書き込むということが多いようです。並列プログラミングに望ましい「スタイル」というものを見つけ出すことはできないのでしょうか。そのような疑問の中から出てきたものが並列性忘却のアイデアです。

私の所属している研究科では、教員の研究をわかりやすく伝えるために、科学記者の方によるインタビュー記事をホームページに掲載しています。最近、掲載されたものが

http://www.i.u-tokyo.ac.jp/news/focus/100215_1.shtml

にあります。こちらもお読み下さい。