🦥C--で末尾再帰最適化を試してみる2021/02/05に公開2021/03/17Haskellghc末尾再帰最適化cmmtech想定される読者Haskellの処理系であるGHCをインストールしたことがある処理系がハードディスクに残っているC言語は、まあまあ読める言語の処理系そのものに興味があるアセンブリ言語についても、おおまかには知っているはじめにHaskellの代表的な処理系であるGHCでは、ソースコードはC--(を構文木にしたもの)にコンパイルされる。CではなくC--を使う理由のひとつとして、処理系の流れのコントロールをより自由にできることがある。一例としてC--では末尾再帰の(明示的な)最適化が非常にわかりやすく表現できることを示す。一例を示すのみで、構文の説明などはしない。Linux)の例であり、それ以外の環境では調整が必要かもしれない。まちがい等々がありましたら「やさしく」ご指摘ください。ここで紹介するコードは以下から入手できます。https://github.com/YoshikuniJujo/cmm/tree/master/qiita/tail_call_optC--とはC--がどんな感じなのかは、以下の論文にまとめられている。https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/ppdp.pdfかんたんに説明すると、つぎのようになる。高級言語のコンパイラを作成しようというときに、それぞれのハードウェアに対して、それぞれの機械語を生成するのではなく、どのハードウェアについても共通する中間的な表現を生成して、それをそれぞれの機械語のコードに変換するほうが効率がいい。そのような「共通する中間的な表現」として、C言語が使われることがあった。C言語のコンパイラは広く普及していたので、悪くない選択ではある。C言語はそのような「中間的な表現」として設計されているわけではないので、いろいろと問題が生じる。そのような問題を解決できるような「表現」が求められた。そこで設計されたのがC言語とアセンブラの中間的な表現であるC--である。C--のコンパイラは独立したプロジェクトとして、いくつか開発されていたが、現在ではいずれもメンテナンスされていない。メンテナンスされているC--の処理系として、GHCを使うことにする。Cの関数mainから呼び出すCの関数mainから呼び出して、C--からの返り値を表示してみよう。以下のようなコードを用意する。fun.cmmfoo(){return(123);}fooという手続き(ブロック)を用意する。これは返り値として123を返す。つぎに、fooを呼び出すC言語のコードを用意しよう。0;}関数mainのなかで、C--のfooを呼び出している。C--では%rbpをスタックポインタとして使うので、%rbpが指すアドレスにラベルprint_retの値を代入している。%rbpはこの前後で値を変化させたくないので、つぎのような処理を行っている。%rspから16減算する%rspの値に8加算したアドレスに%rbpの値を代入%rspの値を%rbpにコピーする%rbpの値が指すアドレスにprint_retの値を代入fooへジャンプfooからは%rbpの値が指すアドレスであるprint_retに処理がもどる%rspの値に8加算したアドレスから%rbpに値をもどす%rspに16加算するたぶん、これで安全にC--の処理を呼び出すことができる(と思う)。コンパイルして試してみよう。123GHCはデフォルトではCの関数mainを用意してくれる。今回は自前のmainを使いたいので-no-hs-mainオプションが必要だ。末尾再帰の最適化とはつぎのような階乗を求める処理があるとする。nを引数にしてfactorialを呼び出すnが0ならばsの値をかえすこの処理はnを1ずつ小さくしていき、sはその都度n倍になる。返り値はnの階乗になる。これをC言語の「関数呼び出し」で実装すると、factorialを呼ぶたびにスタックに「もどりアドレス」が積まれていき、nが0になったところで、そのスタックに積まれたアドレスに、順に処理がかえっていく。そんなことをする必要はない。nが0になった段階で一気にはじめの呼び出しもとにもどってしまえばいい。すればスタック領域を無駄にすることもない。そのように、「スタックにもどりアドレスを積んでいく」という処理と「その積まれたアドレスを順にたどる」という処理とを省略するのが末尾再帰の最適化である(たぶん)。階乗を計算する処理(最適化していないバージョン)末尾再帰最適化をしないバージョンの「階乗を計算する処理」は、つぎのようになる。1);return(ret);}だいたいわかるかと思う。呼び出しもとになるC言語のソースコードはcall_cmm.cを流用する。3628800階乗を計算する処理(最適化したバージョン)それでは、末尾再帰を最適化したバージョンを試してみよう。C--には処理を呼び出す方法にcallだけではなくjumpもあるというところがポイントだ。1);return(ret);}nが0より大きかったときの処理がcallではなくてjumpになっている。jumpで飛んだときには処理はもどってこない。スタックにもどりアドレスが積まれることもない。1回目にreturn命令でfactorialをはじめに呼んだfooに処理がもどる。余計なスタックの消費や余計なジャンプが省略されている。コンパイルして試してみよう。「階乗」だと結果が大きくなりすぎるので1からnまでの総和という題材で最適化する前後の処理を比較する。最適化なし最適化なしでのコードはつぎのようになる。0);return(ret);}乗算を和算に変えた。nを2000000(200万)にしてみた。./sum_no_optスタックの領域を使い切ってしまったのだろう。セグメンテーションフォールトになっている。末尾再帰を最適化したコードはつぎのようになる。0);return(ret)}最適化していないバージョンでセグメンテーションフォールトになった2000000(200万)で試してみる。2000001000000全然、余裕だ。それでは2000000(200万)ではなく1000000000(10億)で試してみよう。50000000050000000010億回、呼び出してもビクともしない。まとめ高級言語のコンパイラを作成するときに、それぞれのハードウェアごとの機械語を生成するのは大変だ。そのようなときにC言語を中間言語として使うのは「あり」だ。C言語はもともとそのような用途に使うようには作られていないので、いろいろと問題がある。その問題のひとつに、末尾再帰の最適化が困難というものがある。C--は高級言語をコンパイルするときの中間優現として設計された言語である。中間表現として、C--がCに対して優れている点として「末尾再帰の最適化がかんたん」という点がある。処理のブロックを呼び出すときにcallというやりかたでなく、jumpというやりかたが用意してあるためだ。かんたんな例で、C--による末尾再帰の最適化の様子を示した。重城良国Haskell好きバッジを贈って著者を応援しようバッジを受け取った著者にはZennから現金やAmazonギフトカードが還元されます。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。