この連載ではプログラミング言語理論の研究成果を紹介するということで,前回からOCamlという関数型言語を紹介している。まず前回の内容を簡単に復習してみよう。OCamlでは「式」を「評価」すると「値」になる。

# 12 + 3 * 4 ;;
- : int = 24

 また,「キーボードから二つの数字を入力すると,その積が画面に出力される」といった,副作用のある式も書ける。

# Printf.printf "%d\n" (read_int () * read_int ()) ;;
5
6
30
- : unit = ()

 しかし,そもそも「関数型言語」とは「副作用のないプログラミングを推奨する言語」のはず。だから,「副作用がある」というと「どこが関数型言語なんだ」と思われるかもしれない。そのOCamlを関数型言語たらしめているポイントの一つが,今回のテーマである「単一代入」だ。

単一代入:変化しない「変数」

 Cなどの命令型言語では,変数への代入は,最も重要な機能の一つである。普通のプログラマは,もし「変数に代入をするな」と言われたら,どうやってプログラムを書けばいいのか,途方に暮れてしまうだろう。

 しかし,ちょっと複雑なプログラムを開発するようになると,「代入」は意外にやっかいな機能であることがわかってくる。例えば,以下のようなC言語のプログラムがあったとしよう。

int f() {
  int x = 123;

  /* なにか複雑なコード */

  return x;
}

 この場合,fの返り値は何になるか,そう簡単にはわからない。なぜなら,途中でxへの代入があるかもしれないし,xへのポインタを他の関数に渡しているかもしれないからだ。特に後者の場合,呼び出している関数の動作までチェックしないと,xの値が何になるかがわからないことが多い。これでは「複雑なシステムは,できるだけ独立した部品に分ける」という工学の鉄則にあわない。

 一方,OCamlでも以下の構文を使って変数を宣言することはできる。

let 変数名 = 式

 例えば,以下のように使える。

# let rate = 116.78 ;; (* 1ドル = 116.78円 *)
val rate : float = 116.78
# 980. /. rate ;; (* 「日経ソフトウエア」の定価980円は何ドルか *)
- : float = 8.39184791916424

 しかし,OCamlでは,変数の値は決してあとから変わらない。もし同じ変数をあとから宣言しても,それは名前だけが同じの,異なる変数とみなされる。このことは,次のような例からよくわかる。

# let rate = 116.78 ;;
val rate : float = 116.78
# let yen_to_dollar yen = yen /. rate ;;
val yen_to_dollar : float -> float = <fun>
# let rate = 3.14 (* 全く違う値を新たにrateとする *) ;;
val rate : float = 3.14
# yen_to_dollar 980. ;; (* でもyen_to_dollarの返り値は変わらない *)
- : float = 8.39184791916424

 3行目の「let yen_to_dollar yen = yen /. rate」は,次のような構文による関数の宣言である。

let 関数名 引数名1 引数名2 ... 引数名n = 式

 つまり,この例では,変数rateを116.78と定義し,それを用いて関数yen_to_dollarを定義している。あとから変数rateを定義し直しても,それはあくまで「名前だけが同じである異なる変数」なので,yen_to_dollarの定義には影響しない(詳しい人のために:OCamlでこのような動作になるのは,静的スコープを採用しているためである。一方,初期のLispは動的スコープを採用しているのでこうした動作にはならない。ちなみに,Lispの動的スコープは,もともとは実装のバグであって,意図された仕様ではなかったという)。

 ちなみに,「変数の値をあとから変更しない」(単一代入)という考え方は,関数型言語だけでなく,命令型言語のコンパイラの最適化等でも,解析を単純にするなどの目的で有用だ。実際に,バージョン4.0以降のGCCや,商用の高度なコンパイラでは,静的単一代入形式(static single assignment form:SSA形式)という中間言語を採用している。静的単一代入形式は,1970年代に提案された継続渡しスタイル(continuation passing style)という関数型言語の概念とほぼ等価であることが指摘されている。

http://citeseer.ist.psu.edu/kelsey95correspondence.html
http://citeseer.ist.psu.edu/appel98ssa.html
http://citeseer.ist.psu.edu/chakravarty03functional.html

 その意味では関数型言語の古典的な研究が,命令型言語の近代的なコンパイラに応用されているともいえるだろう。過激な表現をすると,命令型言語の研究は関数型言語の研究より30年ぐらい遅れている,というとらえ方ができるかもしれない(もちろん,このような断定は早計だとは思うが)。

「ループがなければ再帰で書けばいいじゃない」

 さて,変数の値をあとから変更すること(破壊的代入)ができないとすると,一体どうやってプログラムを書けばよいのだろうか?

 例えば,整数mのn乗を計算したいとする。C言語ならば,ループを使って以下のように書くだろう。

int power(int m, int n) {
  int a = 1;
  while (n > 0) {
    a *= m;
    n--;
  }
  return a;
}

 OCamlの「式」と違って,C言語の「ループ」自体には値がない。だから,ループを使う限り,何らかの計算結果を返すために,変数への破壊的代入は必須であるといってもいい。

 一方,同じ関数をOCamlで素朴に書くとすれば,以下のようになる(参考のために,関数本体だけでなく,対話環境での出力と実行結果も掲載している)。

# let rec power m n =
    if n <= 0 then 1 else
    power m (n - 1) * m ;;
val power : int -> int -> int = <fun>
# power 2 10 ;;
- : int = 1024

 ここで使っている以下の構文は,再帰関数の宣言である。

let rec 関数名 引数名1 ... 引数名n = 式

 上のプログラムは,ループではなく再帰を使って,

  • nが0以下だったら,ただちに1を返す
  • そうでなければ,mのn-1乗を再帰で計算し,その結果にmをかけて返す
という内容を記述している。なお,OCamlでは,関数適用の優先順位は2項演算より高いので,上のコードの中のpower m (n - 1) * mは(power m (n - 1)) * mと同じである。

ループと同じコードにコンパイルされる「末尾再帰」

 「ループではなく再帰で書く」というと,特に職人気質のプログラマは,「再帰はメモリーを消費するのではないか」と思うかもしれない。かのマリー・アントワネットは飢えた民に向かって「パンがなければお菓子を食べればいいじゃない」と言って怒りを買ったとされている(ただし史実ではないらしい)。まさに「ループがなければ再帰で書けばいいじゃない」というわけだ。これは「パンがなければ…」と同様に暴言なのだろうか?

 この問いには二つの答えがある。一つは「現代のコンピュータでは,メモリーの消費は問題にならない」という答えだ。たしかに,データが小さければ(powerの例だと,nの値が小さければ)その通りだろう。しかし,メモリーの増加に合わせて,処理すべきデータの量も増加してきている。いつでもメモリーの消費を無視できるわけではない。

 では,どうすればいいのか? 一般に,再帰がメモリーを消費するのは,関数を呼び出すたびに,「関数が返ってきた後にする処理」の情報を保存しなければならないからだ(詳しい人のために:この情報が「継続」(continuation)である。命令型言語にせよ関数型言語にせよ,ほとんどの言語処理系では,関数呼び出しの継続はスタックに保存される。ただし,一部のSchemeコンパイラや,Standard ML of New Jerseyのように,関数呼び出しの継続をヒープに保存する処理系もある)。先のpowerでいうと,power m (n - 1)を呼び出した後に,mをかけるという処理が必要である。

 逆にいうと,もしそのような「関数が返ってきた後にする処理」がなければ,関数呼び出しは単なるgotoとしてコンパイルできる。そのような「後にする処理」がない関数呼び出しのことを「末尾呼び出し」という。特に,すべての再帰呼び出しが末尾呼び出しであるような再帰関数のことを「末尾再帰関数」という。

 上のpowerは,末尾再帰関数になっていない。一般に,powerのような再帰関数を末尾再帰関数にするには,「返り値も関数の引数として渡すようにする」というトリックが必要である。実際には,以下のように書き直すことになる。

# let rec power_loop m n a =
    if n <= 0 then a else
    power_loop m (n - 1) (a * m) ;;
val power_loop : int -> int -> int -> int = <fun>
# let power m n = power_loop m n 1 ;;
val power : int -> int -> int = <fun>
# power 2 10 ;;
- : int = 1024

 末尾再帰関数power_loopは,引数m,nと「途中の計算結果」aを受け取って,残りの計算の結果を返す。言い換えれば,power_loop m n aは,aにmのn乗をかけた値を返す。関数powerは,そのpower_loopを,a = 1として呼び出しているだけだ。

 このコードをよく見ると,「はじめに挙げたCのプログラムと同じではないか」と思われるかもしれない。その通りである。ほとんどの関数型言語では,末尾再帰関数は,ループと全く同様のコードにコンパイルされる。もちろん,上のpower_loopも,Cで書いたwhileループと同じようにコンパイルされる。「じゃあ何がうれしいのか」といえば,「破壊的代入を使用しないでループと同様の計算を表現できる」という点である。

関数型言語は命令型言語より「優れている」のか?

 末尾再帰のような,性能に関連するテクニックは,関数型言語に慣れていないと(あるいは命令型言語に慣れていると)はじめは難しいと思うかもしれない。しかし,それを補うぐらい「破壊的代入がない」というメリットは大きい。例えば,破壊的代入がないと変数定義や関数定義のインライン展開が簡単になり,コンパイラだけでなくプログラマにとっても,プログラムの意味が理解しやすくなる(ループの展開も,単に末尾再帰関数のインライン展開と考えることができる)。要するに「知らないうちに変数の値が変更されている」ことが決してないのである。

 ただ,これを「わかりやすい」と思うか「制限がきつい」と思うかは,主観や経験による面が大きく,どちらが優れていると決めつけることはできないだろう。実際に,OCamlにも命令型言語の機能がある。例えば,OCamlには変数への破壊的代入はないが,mutableと宣言されたレコードの要素には破壊的代入ができる。これは,カウンタのような目的には便利である。また,for ループやwhileループの構文もある。

 逆に,C言語で破壊的代入のない関数型プログラミングをすることも不可能ではない。例えば,非末尾再帰版のpowerはCでは以下のように書ける。

int power(const int m, const int n) {
  return n <= 0 ? 1 : power(m, n - 1) * m;
}

 また,末尾再帰版のpowerも書ける。最近のCコンパイラには,末尾再帰をループとしてコンパイルする機能を持ったものもあるので,末尾再帰にすることもあながち無駄ではない。

int power_loop(const int m, const int n, const int a) {
  return n <= 0 ? a : power_loop(m, n - 1, a * m);
}

int power(const int m, const int n) {
  return power_loop(m, n, 1);
}

 C言語では一般に,すべての変数の宣言にconstをつけてしまえば,破壊的代入はできなくなる。構文が複雑になるなど多少の無理はあるが,Cで関数型プログラミングを体験することもできるのである。

著者紹介 住井 英二郎

 東北大学 大学院 情報科学研究科 助教授。「ループと再帰のどちらがわかりやすいか」「命令型言語と関数型言語のどちらが優れているか」といった議論は,もはや古典ともいえ,不毛といえるかもしれません。むしろ,「ループも再帰の一種である」「命令型言語も関数型言語も,静的単一代入(SSA)形式や継続渡しスタイル(CPS)に変換してしまえば同様である」と思ったほうが,いろいろなことが見えてきておもしろいのではないか,という気がします。