「単一代入」と「末尾再帰」ITproこの連載ではプログラミング言語理論の研究成果を紹介するということで,前回からOCamlという関数型言語を紹介している。前回の内容を簡単に復習してみよう。OCamlでは「式」を「評価」すると「値」になる。24また,「キーボードから二つの数字を入力すると,その積が画面に出力される」といった,副作用のある式も書ける。()しかし,そもそも「関数型言語」とは「副作用のないプログラミングを推奨する言語」のはず。,「副作用がある」というと「どこが関数型言語なんだ」と思われるかもしれない。そのOCamlを関数型言語たらしめているポイントの一つが,今回のテーマである「単一代入」だ。単一代入:変化しない「変数」Cなどの命令型言語では,変数への代入は,最も重要な機能の一つである。普通のプログラマは,もし「変数に代入をするな」と言われたら,どうやってプログラムを書けばいいのか,途方に暮れてしまうだろう。複雑なプログラムを開発するようになると,「代入」は意外にやっかいな機能であることがわかってくる。以下のようなC言語のプログラムがあったとしよう。x;}この場合,fの返り値は何になるか,そう簡単にはわからない。途中でxへの代入があるかもしれないし,xへのポインタを他の関数に渡しているかもしれないからだ。後者の場合,呼び出している関数の動作までチェックしないと,xの値が何になるかがわからないことが多い。これでは「複雑なシステムは,できるだけ独立した部品に分ける」という工学の鉄則にあわない。OCamlでも以下の構文を使って変数を宣言することはできる。8.39184791916424しかし,OCamlでは,変数の値は決してあとから変わらない。同じ変数をあとから宣言しても,それは名前だけが同じの,異なる変数とみなされる。このことは,次のような例からよくわかる。rate」は,次のような構文による関数の宣言である。式つまり,この例では,変数rateを116.78と定義し,それを用いて関数yen_to_dollarを定義している。あとから変数rateを定義し直しても,それはあくまで「名前だけが同じである異なる変数」なので,yen_to_dollarの定義には影響しない(詳しい人のために:OCamlでこのような動作になるのは,静的スコープを採用しているためである。初期のLispは動的スコープを採用しているのでこうした動作にはならない。ちなみに,Lispの動的スコープは,もともとは実装のバグであって,意図された仕様ではなかったという)。ちなみに,「変数の値をあとから変更しない」(単一代入)という考え方は,関数型言語だけでなく,命令型言語のコンパイラの最適化等でも,解析を単純にするなどの目的で有用だ。style)という関数型言語の概念とほぼ等価であることが指摘されている。http://citeseer.ist.psu.edu/kelsey95correspondence.htmlhttp://citeseer.ist.psu.edu/appel98ssa.htmlhttp://citeseer.ist.psu.edu/chakravarty03functional.htmlその意味では関数型言語の古典的な研究が,命令型言語の近代的なコンパイラに応用されているともいえるだろう。過激な表現をすると,命令型言語の研究は関数型言語の研究より30年ぐらい遅れている,というとらえ方ができるかもしれない(もちろん,このような断定は早計だとは思うが)。「ループがなければ再帰で書けばいいじゃない」さて,変数の値をあとから変更すること(破壊的代入)ができないとすると,一体どうやってプログラムを書けばよいのだろうか?例えば,整数mのn乗を計算したいとする。C言語ならば,ループを使って以下のように書くだろう。a;}OCamlの「式」と違って,C言語の「ループ」自体には値がない。ループを使う限り,何らかの計算結果を返すために,変数への破壊的代入は必須であるといってもいい。同じ関数をOCamlで素朴に書くとすれば,以下のようになる(参考のために,関数本体だけでなく,対話環境での出力と実行結果も掲載している)。1024ここで使っている以下の構文は,再帰関数の宣言である。上のプログラムは,ループではなく再帰を使って,nが0以下だったら,ただちに1を返すそうでなければ,mのn-1乗を再帰で計算し,その結果にmをかけて返すという内容を記述している。「ループではなく再帰で書く」というと,特に職人気質のプログラマは,「再帰はメモリーを消費するのではないか」と思うかもしれない。かのマリー・アントワネットは飢えた民に向かって「パンがなければお菓子を食べればいいじゃない」と言って怒りを買ったとされている(ただし史実ではないらしい)。「ループがなければ再帰で書けばいいじゃない」というわけだ。これは「パンがなければ...」と同様に暴言なのだろうか?この問いには二つの答えがある。一つは「現代のコンピュータでは,メモリーの消費は問題にならない」という答えだ。たしかに,データが小さければ(powerの例だと,nの値が小さければ)その通りだろう。メモリーの増加に合わせて,処理すべきデータの量も増加してきている。いつでもメモリーの消費を無視できるわけではない。一般に,再帰がメモリーを消費するのは,関数を呼び出すたびに,「関数が返ってきた後にする処理」の情報を保存しなければならないからだ(詳しい人のために:この情報が「継続」(continuation)である。命令型言語にせよ関数型言語にせよ,ほとんどの言語処理系では,関数呼び出しの継続はスタックに保存される。Jerseyのように,関数呼び出しの継続をヒープに保存する処理系もある)。1)を呼び出した後に,mをかけるという処理が必要である。逆にいうと,もしそのような「関数が返ってきた後にする処理」がなければ,関数呼び出しは単なるgotoとしてコンパイルできる。そのような「後にする処理」がない関数呼び出しのことを「末尾呼び出し」という。すべての再帰呼び出しが末尾呼び出しであるような再帰関数のことを「末尾再帰関数」という。上のpowerは,末尾再帰関数になっていない。一般に,powerのような再帰関数を末尾再帰関数にするには,「返り値も関数の引数として渡すようにする」というトリックが必要である。実際には,以下のように書き直すことになる。1024末尾再帰関数power_loopは,引数m,nと「途中の計算結果」aを受け取って,残りの計算の結果を返す。aは,aにmのn乗をかけた値を返す。1として呼び出しているだけだ。このコードをよく見ると,「はじめに挙げたCのプログラムと同じではないか」と思われるかもしれない。ほとんどの関数型言語では,末尾再帰関数は,ループと全く同様のコードにコンパイルされる。上のpower_loopも,Cで書いたwhileループと同じようにコンパイルされる。「じゃあ何がうれしいのか」といえば,「破壊的代入を使用しないでループと同様の計算を表現できる」という点である。関数型言語は命令型言語より「優れている」のか?末尾再帰のような,性能に関連するテクニックは,関数型言語に慣れていないと(あるいは命令型言語に慣れていると)はじめは難しいと思うかもしれない。それを補うぐらい「破壊的代入がない」というメリットは大きい。破壊的代入がないと変数定義や関数定義のインライン展開が簡単になり,コンパイラだけでなくプログラマにとっても,プログラムの意味が理解しやすくなる(ループの展開も,単に末尾再帰関数のインライン展開と考えることができる)。要するに「知らないうちに変数の値が変更されている」ことが決してないのである。これを「わかりやすい」と思うか「制限がきつい」と思うかは,主観や経験による面が大きく,どちらが優れていると決めつけることはできないだろう。実際に,OCamlにも命令型言語の機能がある。OCamlには変数への破壊的代入はないが,mutableと宣言されたレコードの要素には破壊的代入ができる。これは,カウンタのような目的には便利である。ループやwhileループの構文もある。逆に,C言語で破壊的代入のない関数型プログラミングをすることも不可能ではない。非末尾再帰版のpowerはCでは以下のように書ける。m;}また,末尾再帰版のpowerも書ける。最近のCコンパイラには,末尾再帰をループとしてコンパイルする機能を持ったものもあるので,末尾再帰にすることもあながち無駄ではない。1);}C言語では一般に,すべての変数の宣言にconstをつけてしまえば,破壊的代入はできなくなる。構文が複雑になるなど多少の無理はあるが,Cで関数型プログラミングを体験することもできるのである。「ループと再帰のどちらがわかりやすいか」「命令型言語と関数型言語のどちらが優れているか」といった議論は,もはや古典ともいえ,不毛といえるかもしれません。,「ループも再帰の一種である」「命令型言語も関数型言語も,静的単一代入(SSA)形式や継続渡しスタイル(CPS)に変換してしまえば同様である」と思ったほうが,いろいろなことが見えてきておもしろいのではないか,という気がします。農家が実感した自動飛行ドローンのすごさクラウド現場の負担軽減を!医療界でのAWS活用法SaaS導入で重要なID管理のコツとは?クラウドの新形態「aPaaS」のメリットDXを阻むコミュニケーションの壁とは?AWSとSAPの連携強化がもたらす利点はデジタル自治体では何が実現できるのか?500万社が導入。価値創造型の社内コミュニケーションとは発想を豊かにする有機的な会議ツールとは働き方が変わる。Reserved.このページに掲載されている記事・写真・図表などの無断転載を禁じます。掲載している情報は、記事執筆時点のものです。