Scalaの言語としての利点を1つ学びました。
トレードオフ
昔Nカタさんという職場の先輩に次のようなことを習いました。
人間にとっての理解しやすさ
goto < for < 再帰 < fold
gotoを使ったコードはforで書くとよりきれいになり、forを使ったコードは再帰で書くとよりきれいになり、再帰を使ったコードはfoldで書くとよりきれいになる。
つまり、右に行くほど抽象度が上がり、しかも包含関係になっているということです。
同じ事ですが、次のようなことも言えます。
実装可能な領域の広さ
fold < 再帰 < for < goto
foldでうまく書けないコードは再帰で書くと簡潔になる場合があり、再帰でうまく書けないコードはforで書くと簡潔になる場合があり、forでうまく書けないコードはgotoで書くと簡潔になる場合がある。
単純な読みやすさで関数型マンセーになっていた僕は先輩のこの言葉に衝撃を受けました。
これを書いていて、中学1年生で同じクラスだった、今も親交のある天才のM君が、
「Haskellは書きやすいけどCより遅いから書かない」
と言っていたのを思い出しました。だから今でも彼と僕の間には10年ぐらいの差があるのでしょう。
それはともかく、このことから、次の2点がトレードオフであることが分かります。
具体的な実装の幅 ⇔ 抽象度の高さ=人間にとっての理解しやすさ
関数型言語でプログラミングをしていると、forや再帰を使うよりはfoldが主役だと思います。しかし、これが分かりやすいが遅いコードにコンパイルされることがあります。
例えば有名な「foldLeftによるstackoverflow」です。
参考リンク：(Qiita)トランポリン化でStackOverflowの回避
実際は、これは関数型言語だけの問題ではなく、javaでも同様の問題が起こります。
つまり、関数であれオブジェクトであれ、何らかの抽象度の向上によって、実装の幅が狭まっている事態だといえます。
Scalaの言語としての利点
Javaは末尾再帰最適化をサポートしていません。JavascriptもES5までは末尾再帰最適化をサポートしていません。ES6はサポートしています。
Scalaは末尾最適化をサポートしていて、@tailrcを書けば最適化対象になります。最適化ができない場合はコンパイラがエラーメッセージを表示します。
Javaにはありません。これがScalaの言語としての利点の一つです。
末尾再帰最適化とは
再帰をwhile文に翻訳することです。
この翻訳が可能であるための十分条件が、再帰が末尾再帰的であることです。すなわち、末尾呼び出し行が、副作用を持たない純粋関数であることです。
再帰関数はスタックフレームを消費しますが、副作用がなければスタックフレーム内の変数を変更しないため、スタックフレームは不要となります。
while文はスタックフレームを消費しません。その結果、元のscalaコードをwhileで書いても再帰で書いても同じ実行速度になります。
アセンブリの実装
実際には以下のブログで説明されるような実装方法になっています。
スタックの戻りアドレスをスキップし、結果を保持するためのアキュミュレーター変数(ダイナミックプログラミングみたいな感じ)を一つ持ちます。
参考リンク：(英語)Tail call optimization in ECMAScript 6
図がたくさんあるので英語が苦手でもわかりやすいです。いつか翻訳してみたいです。
学習リソース
[amazonjs asin=”4844337769″ locale=”JP” title=”Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)”]
この本ではEx3.13で必要になります。foldRightをfoldLeftで実装せよ、という問題です。パターンマッチでfoldRightを書くと末尾再帰的にならないため、トランポリン化してfoldLeftに渡すようにします。
|
1 2 |
def foldRight[A,B] (list:List[A], z:B, op:((A,B)=>B) ) : B = list.foldLeft(()=>z)((b,a)=>()=>op(a,b()))() |
やはり、foldは
- 大抵のものは1行で書ける
- varが不要で、無名関数だけで書ける
ので、書きやすい・見やすい・理解しやすいです。
[amazonjs asin=”4844330845″ locale=”JP” title=”Scalaスケーラブルプログラミング第2版”]
この本では08章「関数とクロージャー」p165～168に、末尾再帰最適化後のjavaバイトコードが載っています。
また、バイトコードまで見るのが面倒な場合は、スタックトレースを吐かせてスタックフレームの数を覗く方法が書かれています。このためには、わざと再帰中に実行時例外を投げます。
最後に、scalaの末尾再帰最適化が、実は特殊な場合のみにしか実装されていない不完全な性能のものであることが書いてあります。これは、java仮想マシンの命令セットの限界によるものです。
[amazonjs asin=”4798135984″ locale=”JP” title=”計算機プログラムの構造と解釈第2版”]
紫本と呼ばれている本です。schemeができないので読んでいません。末尾最適化を超えて、正格化や、抽象の構築がテーマです。
コンパイラの授業
同僚曰く「普通にコンパイラの授業受けてればわかる」そうです。情報学科に行けばよかったです。