OCamlでの関数プログラミング

最初に、この実験における基本的な考え方を説明しておく。

プログラム言語を知る最善の方法は、そのプログラム言語の処理系を書くことである。
新しいプログラム言語を教えるとき、通常ならば、まず、その使い方に習熟し、しかるべき後にその処理系の構成などを習うであろう。この実験では、そうではなく、ほんの 1-2週間の使い方の練習の後、すぐさま、言語処理系の作成をはじめる。つまり、プログラム言語の使い方を理解することと、処理系を作成することがほとんど同時進行でおこなわれる。
たとえば、fun x -> e という式は関数を表すが、いったいこれの意味は何かまだよくわかっていないうちに、その形式を処理するプログラムを書き始めるのである。
このようにする理由は、時間を節約するためではなく、むしろ、「処理系を作成することが、そのプログラム言語を本当に理解するための近道である。」という理由による。

関数型プログラム言語は、非常に表現力豊かである。
実は、OCaml は「関数型プログラム言語らしくない」機能をいくつか持っている。たとえば、参照型 (ref型)を使えば、C言語の x = x + 1 と同じような式を書くことができるし、文字列などに対する操作は破壊的代入(文字列の一部を別の文字列に置換するとき、既存の文字列を破壊する)である。これらの機能は impure (純粋でない)機能といわれている。
効率などの理由により、これらの機能がどうしても必要な場面もあるのだが、本実験では、関数型プログラム言語の表現力を理解してもらうため、 徹頭徹尾、これらの impure な機能を使わない という方針で行く。(ただし、ファイルからの入出力などと、例外処理機能は使う。)
その方針であっても、本実験でわかるように、プログラム言語の機能を理解するためには十分な処理系が書けてしまうし、多くのアルゴリズムも書けてしまう、ということを体験してほしい。

以上の方針のもとに、本実験で必要な機能を厳選したものが、以下のリストである。

変数、if then else, fun, let, let rec, match
データ型: int、string, list、組(タプル)の型、関数の型、type定義
ファイルの読み込み、print, 例外 (exception)

これらの機能を知るため、さまざまな例題を与えて実行してみたファイルを以下に置く。ここでは、系統的な説明は与えていないので、必要に応じて参考文献(書籍、インターネット上の解説)などにあたって欲しい。

例題ファイル1 (基本)
例題ファイル2 (リスト)
例題ファイル3 (少しだけ型)

OCaml の最大の特徴の1つが、高度で洗練された型システムであるにもかかわらず、本実験では、型については、ほとんど立ち入らない。型について詳しくは、「宣言型プログラム論」か「計算論理」を参照のこと。

課題1.

2つの整数を与えられると、その最大公約数(Greatest Common Divisor) を求める関数 gcd を、 let rec, if then elseと、整数上の比較、引き算などを使って記述せよ。
ヒント: x,y ともに正の整数であるとき、以下が成立する。(Euclidの互除法)
```
gcd(x,y) = x            if x=y
gcd(x,y) = gcd(x-y, y)  if x>y
gcd(x,y) = gcd(x, y-x)  それ以外
```
もちろん、もっと効率よいアルゴリズムを使ってもよい。ただし、上記の問題文では、与えられた整数は正とは限らないことに注意せよ。

Fibonacci数を計算する関数fibを定義せよ。ただし、
```
fib(1) = 1
fib(2) = 1
fib(n+2) = fib(n) + fib(n+1)  if n>0
```
である。([2009.9.2] 最後のケースが "if n>2"となっていた誤殖を修正)
なお、上記の定義を単純に実装すると非常に効率が悪い。もし、余力があれば、効率を改善したプログラムを実装せよ。 (ヒント: OCaml では、2つの数mとn の組は (m,n) という式で表現できる。)
正の整数nが与えられると、n番目の素数を計算する関数primeを定義せよ。たとえば、
```
prime(1) = 2
prime(3) = 5
prime(5) = 11
```
である。なお、この問題では、高速化は一切考えなくてよく、ともかく与えられた仕様を満足する関数prime が書ければよい。

亀山幸義