Laboratory

Have fun

現在の武市教授・胡助教授による数理第七研究室，旧称「情報処理工学研究室」（ "IPL"）では，関数型言語を中心に据えて以下のような研究活動が行なわれています．

• 言語処理系
• プログラム運算（プログラム変換）
• XML処理
• 並列計算
• モデル検証
• 連想検索エンジン

そこで，2004年度修士1年の皆さんには夏学期中に"immigration seminar"として，論文を十数本挙げそれらを分担して読んでもらいます．

進め方

（一度書いたものを消してしまいました…）

1. 下に挙げられた論文をまず自力で探しましょう．次のような方法があります．

(a) Webでの入手（その1―正規の論文を電子的に）

東京大学ではオンラインジャーナルとして多くの論文が入手可能となっています．東京大学で利用できる電子ジャーナル検索から入手したい論文誌やプロシーディングスを探してみましょう．プロクシ経由でのアクセスで，特に最近のものであればそのまま電子的に入手できます．出版社別の情報については，大手出版社別利用案内へ．
プロクシを経由しなくても，学内からであればACM（the Association for Computing Machinery）のDigital Libraryが利用可能です．

(b) Webでの入手（その2―ドラフト版などを）

ResearchIndexという，主にウェブ上に載せられている論文の収集および解析を行なっているサービスが存在します．関連研究を調べる際には重宝します．また，直接論文を探す，ということではありませんが，dblp: Computer Science Bibliographyという論文および著者に関するデータベースがあり，非常に便利でまた有用な情報を提供してくれています．
Googleなどのウェブ検索エンジンを使って検索したり，著者のページをあたってみるのも良いことです．

(c) コピーの入手

実際の論文誌やプロシーディングスを求め，図書館に足を運びましょう．多分おなじみの工学部6号にある物工・計数図書室や，関連書籍を多く所蔵する理学部 7号のコンピュータ科学専攻の図書室，また所在地の近さから情報基盤センターの資料室が便利です．
東京大学外の図書館では，私はかつて大岡山にある東京工業大学の附属図書館をよく利用させて頂きました．
勇気のある人は，直接著者に連絡をとって論文を頂く，というのもひとつの方法です．

2. 論文を読みましょう．内容の理解の上で必要な知識なども一緒に調べ，身につけましょう．"Reference"の部分から関連研究を調べるのも重要です．
内容についての疑問や，どうしても先に進まないところが出てきた場合は，周囲の友人や教員，またPSDの研究員の方々にディスカッションを求めてみましょう．

3. 当日の発表は，40分を各自の準備したスライド，20分を質問という形式にします．長い発表時間ではありませんので，論文の要旨を掴んで発表して下さい．なお，発表中必要に応じて適宜質問してもOKです．

論文一覧

以下の流れで進めていきたいと思います．

1. Functional programming, introduction

John Hughes, "Why Functional Programming Matters"

Computer Journal 32(2): 98--107, 1989.

2. Parallel programming

Sergei Gorlatch, "Send-Recieve Considered Harmful: Myths and Realities of Message Passing"

ACM Transactions on Programming Languages and Systems 26(1): 47--56, 2004.

3, 4. Program transformation

Alberto Pettorossi, Maurizio Proietti, "Rules and Strategies for Transforming Functional and Logic Programs"

ACM Computing Surveys 28(2): 360--414, 1996.

5. Attribute grammars

T. Johnsson, "Attribute grammars as a functional programming paradigm"

In Proceedings of the Conference on Functional Programming Languages and Computer Architecture, Portland, Oregon, USA, 1987.

(collected in Lecture Notes in Computer Science, Vol. 274.)

6. Partial evaluation

Neil D. Jones, "An Introduction to Partial Evaluation"

ACM Computing Surveys 28(3): 480--503, 1996.

7. Skeletal parallel programming

D.B. Skillicorn, W. Cai, "A Cost Calculs for Parallel Functional Programming"

Journal of Parallel and Distributed Computing 28(1): 65--83, 1995

8. Program derivation

Richard S. Bird, "Using Circular Programs to Eliminate Multiple Traversals of Data."

Acta Informatica 21: 239-250, 1984

9. Function fusion

• P. Wadler, "Deforestation: Transforming Programs to Eliminate Trees"

Theoretical Computer Science 73(2): 231--248, 1990.

• W.-N. Chin, "Safe Fusion of Functional Expressions"

In Proceedings of the Conference on Lisp and Functional Programming, San Francisco, California, USA, 1992.

• A.J. Gill, J. Launchbury, S.L. Peyton Jones, "A Short Cut to Deforestation"

In Proceedings of the Conference on Functional Programming Languages and Computer Architecture, Copenhagen, Denmark, 1993.

10. XML types using regular tree grammars

• H. Hosoya, B.C. Pierce, "Regular expression pattern matching for XML"

In Proceeding of the 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, London, UK, 2001.

• H. Hosoya, J. Vouillon, B.C. Pierce, "Regular expression types for XML"

In Proceeding of the 5th ACM SIGPLAN International Conference on Functional Programming, Montreal, Canada, 2000.

11. Maximum marking problems

• R.S. Bird, "FUNCTIONAL PEARLS: Maximum marking problems"

Journal of Functional Programming 11(4): 411--424, 2001.

• I. Sasano, Z. Hu, M. Takeichi, M. Ogawa, "Make it Practical: A Generic Linear-Time Algorithm for Solving Maximum-Weightsum Problems"

In Proceedings of the International Conference on Functional Programming, Montreal, Canada, 2000.

12. Function fusion (hylomorphisms)

• A. Takano, E. Meijer, "Shortcut Deforestation in Calculational Form"

In Proceedings of the Conference on Functional Programming Languages and Computer Architecture, La Jolla, CA, USA, 1995.

• Z. Hu, H. Iwasaki, M. Takeichi, "Deriving structural hylomorphisms from recursive definitions"

In Proceedings of the International Conference on Functional Programming, Philadelphia, Pennsylvania, USA, 1996.

出てきた議論

論文発表をしてもらった際の議論で出てきた事柄をメモとして残します．

1. Functional programming, introduction （2004年4月20日）

• 著者によるページ

• higher-order functionsとcatamorphismの関連 → 12. Function fusion (hylomorphisms)

• top-down評価について → 3. Attribute grammars

• lazinessとプログラム変換

• lazinessとco-routine/thread

• call-by-value, call-by-name, call-by-need evaluations

• lazinessの実装 → S.L. Peyton Jones, The Implementation of Functional Programming Lanugages, Prentice Hall, 1987（計数図書室から貸し出されているものが研究室にあります）

• 数値計算，ゲームプログラミング

おまけ

「なお，これら論文の選定には，教授の武市先生，助教授の胡先生，産学官連携研究員の西岡さん，林さん，穆さん，中野さん，博士課程学生の松崎君，横山君に意見を頂く予定です．」

ということで，頂いた意見（および勝手な目論見）を順次列挙します（更新日：2004年2月27日，3月1日）．

program derivation

• Richard S. Bird: Functional Algorithm Design.
  Sci. Comput. Program. 26(1-3): 15-31 (1996) （穆さん）
• Richard S. Bird: Using Circular Programs to Eliminate Multiple Traversals of Data.
  Acta Inf. 21: 239-250 (1984) （穆さん）

Program optimization problems

• Richard S. Bird, Oege de Moor: Solving Optimisation Problems with Catamorphism.
  MPC 1992: 45-66, ps.gz file （穆さん）
• Richard S. Bird: Maximum marking problems.
  Journal of Functional Programming 11(4): 411-424 (2001) （穆さん）

program transformation, partial evaluation

• A. Pettorossi, M. Proietti: Rules and Strategies for Transforming Functional and Logic Programs.
  Comput. Surv. 28(2): 360-414 (1996) （筧）
• Neil D. Jones: An Introduction to Partial Evaluation.
  Comput. Surv. 28(3): 480-504 (1996) （筧）

連想検索エンジン GETA

• 西岡さんがお書きになる（予定の）論文

一般部分計算（GPC: Generalized Partial Computation）に興味をお持ちの方は，二村教授のページの「推奨論文」を御覧下さい．