2018/05/06

 Scalaと関数型プログラミングに関連するトピックなど

  1. 名前渡し(Call-by-name)、評価戦略/遅延評価
  2. プロパティベースのテスト
  3. Recursion Scheme
  4. モナドなどの型クラス
  5. 抽象解釈(Abstract interpretation)
  6. 依存型(Dependent type)
  7. 参考文献
  8. 練習問題
  9. 読み物

Scalaについて勉強した時のメモ(その7)です。その他関数型プログラミング関連の話題について。

※ 元々はmarkdownで書いていたテキストの転載。

名前渡し(Call-by-name)、評価戦略/遅延評価

  • プログラムの実行順序のこと。
  • calaには、通常の評価戦略(call-by-value)に加えて、名前渡し(call-by-name)がある。 その他、stream型だと、遅延リストになる。

プロパティベースのテスト

  • 特定のケースのみを対象としたテストケースではなく、関数の引数に対する戻り値の性質をテストする。
  • 固有のテストケースを持たないと言う意味で従来の関数に対するユニットテストとは大きく異なる。
  • ScalaTestのProperty-based testing などで使用できる。

Recursion Scheme

  • fold/unfold系関数の一般化。
  • catamorphism, anamorphism, hylomorphism ...などなんとかモルフィズムという名前が付いている。
  • Recursion Schemeに基づくプログラムの融合変換などもある。
  • ScalaだとMatryoshka というライブラリが有名。

モナドなどの型クラス

  • ファンクタ、アプリカティブファンクタ、モナド、コモナド、モノイド(Functor, applicative functor, monad, comonad, monoid)
  • 特に公式の用語集(以下)にも出てこないので、Scalaでは特に普段は意識する必要はない(と思われる)。
  • モナドはモナド則と呼ばれる関数の合成規則を持った型クラスの事。よく副作用を表現する時に使われる。(勿論、副作用以外も表すことができる)
    • モナド同様、ファンクタはファンクタ則を、アプリカティブファンクタはアプリカティブファンクタ則がある型クラスのこと。
    • ファンクタ、アプリカティブファンクタ、モナドの順に制約(性質的な縛り)が強くなる。
    • コモナドはその双対(圏論の用語なので詳しく知りたい場合はその辺りを参照)
  • 単に副作用を表現するだけでなく、自分でカスタマイズできる事から愛好者も多い(と思われる。特にHaskeller)。
  • モノイドは、foldまわりでよく使われる二項演算の一般化。
  • ScalaだとScalaz でよく使われる。

抽象解釈(Abstract interpretation)

  • プログラムの抽象的な実行のこと。静的型付けと同じ、静的解析の一種。
  • 似たようなものとしてSymbolic Execution(記号的実行)というのもある。
  • Scalaだと、Jadom というのがあるらしいが。。。

依存型(Dependent type)

  • 一般的なプログラムの型付けより詳細な型を付けることが出来る。例えば0以上のInt型など。
  • Scalaで言われているDependent typeと関数型言語で言われる依存型は意味が異なる。
  • ScalaだとStainless というライブラリがある。

参考文献

練習問題

読み物

  Recursion Scheme モナド Scala 型クラス 関数型プログラミング 依存型 評価戦略 抽象解釈