1999年〜2000年の進捗報告

Progress reports in 1999-2000

東工大在籍中の1999年〜2000年までの月々の進捗報告とセミナー等の際に使用したレジュメです。

Author: KANDO Takayuki
Homepage: http://www.nerimadors.or.jp/~kando/
E-mail: kando@nerimadors.or.jp

CSS: http://www.nerimadors.or.jp/~kando/kando_std.css
Notice: http://www.nerimadors.or.jp/~kando/Notice.html

[index]

Contents

月報 (Monthly Progress Reports)
[2000] [1999]
セミナー資料 (Seminar resumes):
[2000] [1999]

(Word file viewer for Windows: Wdview97.exe)

Monthly progress reports

2000

10
09
08
07
06
05
04
03
02
01

1999

12
11
10
09
08
07
06
05
04

Seminar resumes

2000

10/05 LS Seminar 論文紹介：「部分評価の紹介」
"An Introduction to Partial Evaluation" (Neil D. Jones, ACM Computing Survey, Vol.28, No.3 Sep., 1996)
部分評価器（partial evaluator）は、 ある汎用プログラムから特定の入力に特化した プログラムを生成するプログラム特殊化器（program specializer）とみなせる。 このような部分評価の第1の目的は高速化で、 あまり変更されない部分（静的入力）を前もって評価して特殊化できれば、 何度も走らせた場合に高速化できることになる。 部分計算とそのself-applicationは多くの応用があり、 プログラム・ジェネレータ（コンパイラ、コンパイラ・ジェネレータ、プログラム変換系） の生成とその高速化に役立つ。
[Resume] [Resume(Word 2000 file)]
[Slides] [Slides(Powerpoint 2000 file)]
06/01 LS Seminar 論文紹介：「多重定義に関する2度目の考察」
"A Second Look at Overloading" (Martin Odersky and Philip Wadler and Martin Wehr, 1995, Conference on Functional Programing and Computer Architecture)
入出力や算術演算など多くの処理は必ずしも総称的には書けないが、 呼び出される際の構文では区別をつけず多相的に呼び出せることが望ましい。 そこで型推論を拡張し、多重定義したい関数は多重定義されていると宣言し、 かつそれらの引数については型を明示することにして、 呼び出し時には型環境を通じてそのように宣言されているものから適切なものを選ぶ （総称関数のようにインスタンスを作るのではなく）ようにすることを考える。
[Resume] [Resume(Word 2000 file)]
[Slides] [Slides(Powerpoint 2000 file)]
＜参考＞
03/31 LS Seminar 論文紹介：「多態型推論」
"Polymorphic type inference" (Daniel Leivant 1983 POPL)
強い型付けによるコンパイル時のエラー検出とプログラムの検証の利点は良く知られている。 強い型付けは、関数の適用が中心的な構文である関数型言語では特に自然で、 そこでの型の整合性の検査はプログラムの検証の中心だが、 全ての式に意識して型を割り当てるのは大変煩雑になり得るので、 与えられた型のない式からシステムが型を推定する型推論というものを考えれば、 ユーザーは型のないプログラミング言語のようにプログラミングでき、 ジェネリックな関数を書くことができる。 しかし多相型（型変数を持つような型）を許さない古典的な型推論だけでは、 関数がプログラム中で一回呼び出されれば 関数の型はそこで確定してしまうので、 一つのジェネリックな関数を色々な型の引数について呼び出すことが出来ない。 しかし無制限に型変数を導入した型システムの型推論は計算不能であるという問題がある。 そこで型変数を含むような関数の宣言に制限をつけて計算可能にすることを考える。
[Resume] [Resume(Word 2000 file)]
＜参考＞
02/04 Seminar 02/17の院試口頭試問に向けた練習：
「修論以降の研究経歴及び数学ソフトウェア向け言語の設計について」
修論以降の研究経歴を概説した。主な話題は以下の通り。
  1. C++クラスによる既存ライブラリへのインターフェース・ライブラリ
  2. 多倍長浮動小数点演算と初等関数値計算ライブラリ
  3. 多項式の対話的表示法
  4. 数式処理システムの並列計算機への移植
博士課程に入学後の研究テーマ「数学ソフトウェアの記述に向いた言語」について、 Fatemanの規準を紹介し、関連する幾つかの課題を述べた。 [Resume] [Resume(Word 2000 file)]
[Slides] [Slides(Powerpoint 2000 file)]
＜参考＞

1999

11/16 LS Seminar 論文紹介：
"A new method for functional arrays" (Melissa E. O’Neill and F. Warren Burton, J. Functional Programming 7(5): 487-513, Sep. 1997)
純粋な関数型言語では関数の数学的な定義と同様に副作用が許されない。 通常の命令型言語におけるような配列の要素の更新は代入であり、 副作用を持つ。そこで純粋な関数型言語では、更新という操作は 配列のようなデータについて更新済の値を持つ複製を(論理的に)作成する と考える。このような機能をサポートする配列をPersistentな配列型という。
ここで紹介している論文ではPersistentな配列型の実装として binary treeに基づく方法と version tree(trailer arrays)に基く方法を紹介した後、 新しい実装方法としてfat elementを用いる方法を提案し、 (理論と実験で)評価している。 結論としては、以下の二点を述べている。 [Resume(HTML file)] [Resume(Word 2000 file)]
07/22 Seminar 論文紹介：
"How to Declare an Imperative"(Philip Wadler. ACM Computing Surveys, 29(3), p.240-263, Sep., 1997 （ WWW:Wadler: Monads )
pure関数型言語に相互作用を命令型プログラミング風に追加するものとして monad方式を紹介。
理論的な要点は、入出力関数から入力出力意図を意味する値を返させるようにし、 それらを結合演算子で簡単に結合できるようにしておいて、 トップ・レベルの変数に束縛された際に実際の動作に束縛すること。
そしてpureかつlazyな関数型言語であるHaskellにmonadを導入した結果、 何が簡単になったかを他の各方式（synchronized stream、continuations、 linear logicやside effect）との比較によって紹介。 （例は全て単一monadの事例） 最後に課題として一階の言語、論理型言語へのmonadの導入について紹介。
[Resume(HTML file)] [Resume(Word 2000 file)]
05/17 LS Seminar「数学ソフトウェアの記述を考える - 自己紹介に代えて（仮）」
自己紹介を兼ねて今までやってきたことを概説した。主な話題は以下の通り。
  1. C++クラスによる既存ライブラリへのインターフェース・ライブラリ
  2. 多倍長浮動小数点演算と初等関数値計算ライブラリ
  3. 多項式の対話的表示法
  4. 数式処理システムの並列計算機への移植
これに関連して、ポリモルフィズムと数学ソフトウェアの関係について述べた。 最後に今後どういう方向で勉強して行くつもりかについて述べた。 その中でアルゴリズムを漸化式で記述する件について、 有効性に疑問が提示された。今後、文献を漁って遅延評価言語を中心に 依存関係と評価順序について理解を深めつつ、 アイディアを具体化していきたい。
[Resume] [Slides]