【関数型言語】名前渡し(call by name) と必要渡し(call bye need)
Scala 関数型デザイン＆プログラミング http://amzn.asia/bIfSCQS
の「第5章 正格と遅延」に
Scalaの非正格かんすうは引数を値渡しではなく名前渡しでうけとります。
という記述があった。「名前渡し」は初めて聞いたので、ぐぐった。
いろいろな引数渡しの方式 — 値呼び・参照呼び・名前呼び・必要呼び
この中に、遅延評価と call by name, call by need の関係を説明している部分を見つけた。
いくつかの言語では，引数の計算を，その計算結果が使われるまで(自動的に) 遅らせる遅延評価(lazy evaluation)の仕組みが備わっている．遅延 評価の仕組みは，パラメータが複数回現れたときの処理の違いによって2種類 に分けられる．もっとも単純なやり方は，引数が使われる度に，thunk を thaw してして値を求めるもので，名前呼出し(call-by-name) と呼ば れ，Algol60 などで使われた．しかし，代入などの副作用が無い場合，くりか えし計算するのは同じ値が得られるだけで無駄である．これを改良したのが， Haskell などで採用された 必要呼出し(call-by-need) という仕組み で，一度 thaw した thunk はその値を覚えておいて，二度目以降に使われる ときには，覚えておいた値を使うものである．このふたつの機構は副作用がな い限り，同じ実行結果になる．しかし，代入などを使うと，このふたつの違い を見ることができる．
必要渡し(call by need) というのもあるらしい。Haskell で遅延評価のときに使われるらしい。
本物のプログラマはHaskellを使う - 第8回 遅延評価の仕組み：ITpro
こちらもまだ理解できていない。宿題。
【関数型言語】例外を使わないエラー処理
- Scala では Option/ Either型を使う。
- Hakell だと Maybe/Eitherモナドを使うらしい。
- C++17だと
- javascript だとMaybe/ Eitherモナド。
- elixir：通常はタプルを返すが、Option/Either と同等？要調査。
==> elixir は言語としては Maybe/Either は持たない。exMonad ライブラリで使えるらしい(2018/1/9)
【関数型言語】promiseとかfutureとか
恥ずかしながら、今日初めて promise とか future を知った（汗
非同期処理を行うための機能らしい。今どきの言語は大抵持っているとか（大汗
Haskell と elixir については、該当機能があるのか、わからなかった。今後の宿題。
【関数型言語】CPS(継続渡し）と末尾再帰最適化
ループと再帰
関数型言語ではループを再帰で表す（ことがおおい）らしい。だが、再帰はスタックオーバーフローする危険がある。それを避けるには、末尾再帰最適化をすればよい。これを使うと、再帰呼び出しにもかかわらず、スタックを消費しない。
scala, haskell, elixir で、合計、階乗、フィボナッチ数について、コードを書いてみた。
study_scala/GettingStarted.scala at master · kzono/study_scala · GitHub
study_elixir/recursiveLoop.ex at master · kzono/study_elixir · GitHub
study_haskell/TailRec.hs at master · kzono/study_haskell · GitHub
acc（アキュムレータ）を引数として追加することによって、再帰的な呼び出しで呼び出された後に実際に行う処理をなくす、というのがポイント。例えば呼び出された先で（関数内の処理として）total + sum(n-1) とするかわりに、関数呼び出すときの引数として足し算を計算してしまう sum(n-1, acc +n) といったかんじ。
どんなループの末尾再帰最適化できるのか？
調べていて気になったのは、「どんなループの末尾再帰最適化できるのか？」ということ。
継続渡しスタイルはクロージャを使った汎用的な方法で、クロージャがあるプログラミング言語であれば、継続渡しスタイルでプログラムを作成することができます。
CPS（Continuation passing style）とは
参考URL
http://practical-scheme.net/docs/tailcall-j.html
http://practical-scheme.net/docs/cont-j.html
CPSを使えば、スタックを消費しない（その代わりヒープを使う）ことができるみたい。全てのループを末尾最適化できるらしい。
継続渡しスタイルの関数では、関数の最後は「継続を表す関数に結果を渡す」ことになりますし*5、 継続渡しスタイルの関数を呼び出す場合もやはり末尾呼び出しになります。 そのため、再帰部分を継続渡しスタイルで書けば自動的に末尾呼び出しになるのです。
つまり、末尾再帰ではない再帰関数をCPS変換したら末尾再帰関数になり、末尾呼び出しの最適化がかかります。
再帰（末尾再帰最適化）の使いどころ
どういう場合に普通のループではなく、（末尾再帰最適化した）再帰呼び出しを使うべきか？また、使うべきでないか？
例えば、「1から10までの合計」といった場合は、通常のループのほうがよさそう。
（再帰関数に慣れてしまえば、ループと同値なのかも）
それに対し、ループの回数が自明でないような、本質的に再帰な課題の場合は、再帰で書いたほうがすっきりかける。漸化式で表せる数列とか、ツリー構造の巡回とか。
gibo と git-flow をインストールした
という記事で、 gibo と git-flow を知った。あ、git-flow は以前にもググったことがあったが忘れていた。 gibo は .gitignore をプロジェクトごとに自動生成してくれるツール。各種言語に対応している。
対応言語は gibo -l で表示してくれる。
一方、 git-flow は、git を使う時のブランチ操作などが便利らしい。インストールしただけなのでまだ嬉しさがわからない(汗。
現状、一人プロジェクトなので、master 以外のブランチを切っていないが、まともなブランチの使い方を理解するためにも、git-flow を使って、典型的なブランチの使い方を学ぼうと思う。
