📝関数型プログラミング

📝関数型プログラミング


関数型言語 #

すべての計算や処理などを関数の定義の組み合わせとして記述していくタイプのプログラミング言語.

「同じ入力には必ず同じ出力を返す」「関数の評価が他の関数に影響を及ぼさない」など数学における関数と似た性質を持った関数の定義としてプログラミングを行い, プログラムの実行は記述された関数群の評価として行われる.

ref: 関数型言語とは 【 functional language 】: IT 用語辞典

広義の意味では, What をコンピュータに示すもの (How を示さない). 狭義の意味では, プログラミングの中で数学を用いたもの (Function, Relation).

  • 式と関数でプログラムを組み上げる (Use of MathMatics)
  • 関数を値として扱える (Higher-order programming)
  • 副作用を起こさない (Impliclite State, Stateless)

関数が第一級オブジェクトである言語.

関数型プログラミング #

狭義の意味では,

  • 状態をもたない
  • 一時変数を持たない
  • loop を持たない
  • 手続的制御構造を持たない

広義の意味では,

関数型言語の意味は変わりつつある #

  • 昔は, 高階関数 をサポートする言語という緩い定義だった.
  • 現代のモダンな言語 (Haskell, Scala など) は,

数学的理論を背景にプログラムを記述する言語

以下に数学的概念と関数型言語の対応マップがある.

背景 #

ハードウェアのメニーコア, 大容量メモリ化によって, 性能のボトルネックが I/O ではなくて, アプリケーションとなってきた. アルゴリズムが勝負の世界. アプリがボトルネックになってきた. そのため, 言語レベルで平行・並列処理が書きやすい言語が求められるようになった.

Cloud Computing において, 異常が発生したら全体をとめるのではなくて, 一部を停止して運用を継続させる必要がある.従来の例外処理では処理するのが複雑になってきた.そのため, 言語レベルで分散コンピューティングやFault Tolerant をサポートするような言語が求められるようになった.

計算の考え方 #

命令型では, 計算の基本は蓄えられている値を変えること.

関数型では, 計算の基本は引数に関数を適用すること.

Languages #

  • 狭義の意味では Lisp, XPath, Haskell,,,
  • 広義の意味では, Scheme, Clojure, ocame, F#, Scala, Smalltalk, Ruby…

メリット #

  • コード量が少なくなる
  • 高階関数を使った技が使える
  • 最適化がしやすい
  • 並列処理が書きやすい
  • バグりにくい (定理と証明)
  • ドキュメントが少なくなる

デメリット #

  • 関数実行のオーバヘッドが大きい
  • メモリ大量消費
  • スタック使用量が見積もれない (再帰)

コンパイル = 証明 #

コンパイルを通すということは, 正しさを証明すること

関数型言語では, コンパイルが通るとバグがほとんどでない. 純粋関数の世界でプログラミングをすることによって, 実現できる. 背景には数理論理学がある. (Curry-Haward 対応)

このことがなぜ大事かというと, 並列プログラミングのバグとりは大変. テストですべてのバグをとれたという保証ができない.

関数型ならば数学をベースにして, バグがないことを証明することができる

命令型プログラミングと関数型プログラミングの比較 #

🏷Imperative Programming

impelative paradium #

  • ループで反復構造を実行

  • 異なる関数の間で共有する状態を変更

    var i = 0
    while (i < args.length) {
      if (i != 0) {
        print (" ");
      }
      print (args (i));
      i += 1;
    }
    println ();
    

functional paradium #

  • 再帰で反復構造を実行
  • arg は変数ではなくて, 不変な定数
args.foreach (arg => println (arg))

for (arg <- args)
  println (arg)

不定性 | Immunity #

副作用を起こさない.

Implicate (declarative) State #

暗黙的状態. 宣言的状態, Stateless, ともいう.

  • 関数の実行結果が値をもつ
  • 同じ入力には必ず同じ出力を返す.
  • Explicite State との対概念.
  • 参照透明性.

Referential Transparency: 参照透過性 #

式の値はその構成要素 (例えば変数や関数) によってのみ定まる.

参照透過性 - Wikipedia

  • 変数の値は最初に定義した値と常に同じ
  • 関数は同じ変数を引数として与えられれば同じ値を返す

pure function: 純粋関数 #

同じ引数を渡す限り, どのような順番で何度呼んでも同じ結果が返るような関数.

同じ式を評価すると, いつも同じ結果になる参照透過性を持っていること.

副作用がある関数の対概念.

Side effect: 副作用 #

ある機能がコンピュータの (論理的な) 状態を変化させ, それ以降で得られる結果に影響を与えること.

あるいは,

  • 状態を参照することで出力が変化すること
  • 状態に変化を与えることで出力が変化すること

例としては,

  • 破壊的代入
  • I/O 制御 (write/print 等)

破壊的代入 #

代入というのは, 「右辺にあるものを左辺に代入する」という意味.

左辺にある変数内のデータを消し, 新しく右辺にあるデータを代入する」とも言い換えられます. この仕組みのことを「破壊的代入」という.

Monad |モナド #

(理解不十分…)

モナド (プログラミング) - Wikipedia

以下のような問題は, モナドという概念で説明できるらしい.

  • 入出力等をもたらすプログラム
  • 例外を返すプログラム
  • 引数に対して値を返さない (停止しない) プログラム
  • 同じ引数でも返り値が異なる可能性のあるプログラム

値およびその値を使う計算の並びという観点からいえば, 計算を構造化 する方法.

Introduction

-> 詳細は Haskell の章に移動.

リスト内包表記 | List Comprehensions #

リスト内包表記, List Comprehensions.

既存の集合から新しい集合を生成する.

  • 生成器 … 集合からの取り出しかたの定義
  • ガード … 生成する条件

高階プログラミング | Higher-order programming #

高階プログラミング.

高階関数(=procedure value) をサポートしている言語でのプログラミング技術.

  • 関数を引数としてわたす能力.
  • 関数を戻り値としてかえす能力.

われわれはプログラマとして, プログラムの根底にある抽象をみつけ, より強力な抽象化ができるように努めてなければならない.

高階手続きの重要さは, それにより抽象をプログラム言語の要素して確かに表せ, 他の計算要素として扱えるようになる点にある.

関数における orderとは #

帰納的定義は以下.

  • first order: A function whose inputs and output are not functions.
  • Nth order: if its inputs and output contain a function of maximum order N.

第一級オブジェクト(first-class object) #

たとえば生成, 代入, 演算, (引数・戻り値としての) 受け渡しといったその言語における基本的な操作を制限なしに使用できる対象のこと.

第一級オブジェクト - Wikipedia

以下のような特徴をもつ (関数プログラミング実践入門)

  • リテラルがある
  • 実行時に生成できる
  • 変数に入れて扱える
  • 手続きや関数の引数として与えることができる
  • 手続きや関数のの結果として返すことができる.

関数型言語とは, 関数が第一級オブジェクトであること.

SICP から (p43)

  • 変数として名前がつけられること
  • 手続きに引数として渡せる
  • 手続きの結果として返される
  • データ構造に組み込める

Lisp は手続きに完全な First Class を授与した.

第一級関数(first-class function) #

関数を第一級オブジェクトとして扱うプログラミング言語の性質.

第一級関数 - Wikipedia

mapやfilterなどと高階関数をつかってプログラムを組む言語にとっては当たり前かもしれないが, 関数型パラダイムから外れるとそうではない. たとえばC 言語には関数ポインタがある. C 言語は 第二級オブジェクト. 2 階関数.

Genericity #

引数に関数を受け取るもの.

declare
fun {Map F L}
   case L of nil then nil
   [] H|T then {F H}{Map F T}
   end
end

Instantiation #

戻り値に関数を渡すもの.

declare
fun {MakeAdd A}
   fun {$ X} X+A end
end

高階関数 | High-order functions #

第一級関数 をサポートしているプログラミング言語のなかで以下のいずれかを満たす関数.

  • 関数を引数としてわたす能力.
  • 関数を戻り値としてかえす能力.

高階プログラミング言語だからって書き方で高階関数でないものも書ける.

高階関数はいろいろ種類があるが, 3大高階関数といえば以下でしょう.

  • map
  • filter
  • reduce

map(高階関数) #

リストの各要素に関数を適用する.

Prelude> map (+1) [1,3,5,7]
[2,4,6,8]

filter(高階関数) #

リストの各要素で条件に一致したものを取り出す.

Prelude> filter even [1..10]
[2,4,6,8,10]

reduce(高階関数) #

T.B.D.

無名関数(Annonimous Functions) #

無名関数. 名前付けされずに定義された関数.

Function Literal (関数リテラル), 匿名関数といわれることもある.

メリットは,

  • 一度しか使わない関数の名前を付けなくて済む.
  • 名前の衝突を考えなくて済む.
  • 関数の引数などに直接渡せる

examples:

  • Ruby {|x, y| x + y}
  • Scala (x :Int, y :Int) => x + y , (x, y) => x + y
  • Haskell \ x y -> x + y

Closure | クロージャ #

引数以外の変数を実行時の環境ではなく, 自身が定義された環境 (Static Scope) において解決する.

Procedure Value (Oz), Lexical Scoped Closure ともいう.

関数とそれを評価する環境のペアとも言える.

Procedure value は ペアでメモリ上の値にバインドされる.

  • Procedure code
  • Contextual environment

Javaの無名クラスもクロージャの一種.

Rubyだと ブロック(do - end)という表現で登場する. 必ずしも表現が無名関数ではない.

Contextual environments #

関数の内部で参照されていて, 関数の外部で宣言されているすべての識別子の集合を, その関数の contextual environments という.

関数オブジェクト #

関数をオブジェクトとしたもの.

note: Java7以前でよく登場したかな?今はきかないな.

cf. クロージャは関数オブジェクトと環境のペア.

ラムダ式 #

  • Ruby: lambda{|x, y| x + y}
  • Scala:
  • Haskell:

デリゲート #

オブジェクトへの参照と関数オブジェクトへの参照をペアにして持つもの.

C#, Visual Basic .NET などの, .NET Framework のプログラミング言語にある機能.

部分適用 #

一部の引数を固定化して新しい関数を作り出すことを部分適用と呼ぶ.

カリー化 | Currying #

カリー化. 複数の引数をとる関数を以下であるような関数にすること.

  • 引数が「もとの関数の最初の引数」で
  • 戻り値が「もとの関数の残りの引数を取り結果を返す関数」

カリー化 - Wikipedia

部分適用を容易にすることが可能になるというメリットがある.

💡カリー化と部分適用の違い #

よく混同されやすい. 答えられるようにしたいところ.

  • 関数を引数1つずつに分割してネストさせることをカリー化と呼ぶ.
  • 一部の引数を固定化して新しい関数を作り出すことを部分適用と呼ぶ.

カリー化は元の関数の表現を変えたにすぎない. カリーな表現. 一方, 部分適用はもはや別の関数を新たに生成している.

カリー化や部分適用はHaskellやJavaScriptの例で検索でよくみかける. Haskellはデフォルトで引数は一つであり, わかりやすい表現のために複数引数で表現したとしても内部の処理ではカリー化されて処理される(automatic curryingいう?).

ref: カリー化と部分適用の違いと誤用 - Togetter

x,y,z -> V をx -> (y->(z->V)) に変換するのがカリー化。x,y,z-> Vのyに値を束縛して結果的にx,z->Vという関数になるのが部分適用。どこが同じなんだろうか。

なぜ混同するかはよく一緒に登場するからか?カリーで表現された関数から別の関数をつくる.

アリティ | arity #

関数が取りうる引数の個数. 関数型パラダイムや計算機科学でよく使われる.

ref: アリティ - Wikipedia

invariant programming #

不変式プログラミング. 再帰的に呼ばれる度に, 数学的に真になる式.

Recursion #

再帰的プログラミング.

tail-recursion #

末尾再帰.

その中にただ 1 つの再帰呼び出しがあり, かつその呼び出しが手続き本体の最後にあるもの.

関数がそれ自身を最後の処理で呼び, かつ, 関数のスタックが再利用されるもの.

tail-recursion の例. Factorial

declare
fun {Fact N}
   local Fact1 in
      % tail-recursive でない
      % 計算のたびにスタックがたまる.
      fun{Fact1 N}
	 if N==1 then 1
	 else N*{Fact1 N-1}
	 end
      end

      local Aux in
      % tail-recursive
      % 計算のたびにスタックがたまらない.
	 fun {Aux N Acc}
	    if N==0 then Acc
	    else {Aux N-1 {Fact1 N}|Acc}  % call Fact on N here!!!
	    end
	 end
	 {Aux N nil}
      end
   end
end

State pattern #

関数型パラダイムでの実装

fun {While S}
  if {isDone S} then S
  else {While {Transform S}} end /* tail recursion */
end

手続き型パラダイムでの実装

state whileLoop (state s) {
  while (!isDone (s)) // 終了条件
    s = transform (s) // 再帰
  return s;
}

Accumulator #

C++ の, numeric ライブラリ (accumuulate など) で利用されている.

スタックのサイズが均一なことが特徴的.

Specification #

Principle of communicating vases #

% principle of communicationg vases
% n! = i! * a
%    = i * (i-1)! * a
%    = (i-1)! * (i*a)
% We have: i' = i-1 and a' = i*a
declare
fun {Fact2 I A}
   if I==0 then A
   else {Fact I-1 I*A} end
end

Type: 型 #

Algebraic data type: 代数データ型 #

関数型パラダイムで利用される.

それぞれの代数的データ型の値には,以下をもっている.

  • 1 個以上のコンストラクタ
  • 各コンストラクタには 0 個以上の引数

2 引数で与えられた他のデータ型の値を, コンストラクタで包んだようなもの.

Visual Basic #

Variant 型. なんでも入れることが出来る型だが, メモリ使用量が多いので乱用はさける.

Haskell #

Haskell では, 以下を合わせて代数データ型と呼ぶ

  • 列挙型他の言語における enum
  • 直積型
  • 直和型

参考:

Enum: 列挙型 #

プログラマが選んだ各々の識別子をそのまま有限集合として持つ抽象データ型.

番号を持たないカテゴリ変数. 一意の文字.

実行時には, 番号が振られることが覆いが, 言語によっては番号はプログラマに見えないこともある.

Monadic Programming #

モナドを中心にプログラムを組む方法.

モナドとは,

  • コンテナ
  • パイプライン
  • インタプリタ

モナドにはいろいろな種類がある.

  • IO モナド
  • State モナド
  • Future モナド

モナドの使い方は難しいのだけれどもパターンがあるのでなれれば簡単.

Functinal Reactive Programming #

ある変化に応じて動作する, イベント駆動のプログラミング方法.

Reactive Programmig には, 2 つの種類があるそうだ.(浅海さんのプレゼンから)

  • Actor Model
  • Monadic Model

以下の記事がわかりやすい.

GUI, インフラ, ビッグデータ処理など様々な場面で浸透しつつあります. 今までは複雑すぎて作ることが難しかったアプリケーションが簡単に設計できるようになっていくでしょう.

時間とともに変化する"値を表すデータ型.

FRP は非同期データストリームを用いるプログラミングである ( FRP is programming with asynchronous data streams)

シグナル #

シグナルとは, 時間とともに変化する値. このシグナルを扱ってイベントを処理する方法.

シグナルには以下の面倒をみる責務がある.

  • 現在の値
  • 現在の値に対応する評価
  • その値に依存する他のシグナル (Observers)

リアクティブ性 #

2015 年に備えて知っておきたいリアクティブアーキテクチャの潮流 - Qiita

リアクティブと一言で言った時に, 現状では 2 つの含意があります.

  • アーキテクチャの各要素をメッセージ駆動でつなげ, 反応的に変化させること.
  • メッセージの送受信を隠蔽し値同士の関係 (data-flow) を宣言的 (関数型的) に記述するプログラミングパラダイム

変数 a, b について, 以下のように情報を更新したとき,

  1. a = 3
  2. b = 2 + a
  3. a = 1

最終的には, a = 1, b = 3 になるようにする. 手順 3 で, a の更新に対して b も更新されるところがリアクティブ.

リアクティブ宣言 #

リアクティブ宣言なんという, かっこいい文章も存在する.

4 つの原則がある

  • Responsive:即時応答する
  • Elastic:伸縮自在である
  • Message Driven:メッセージ駆動である
  • Resilient:回復力がある

Object-Functional Programming (OFP) #

オブジェクト指向のパラダイムと関数型のパラダイムの両方を利用してプログラミングする.

上流工程では, 今までどおりオブジェクト指向設計で考えることになる. ユースケースで今までどおり要件定義をして, コンポーネント分割までする. そこから, オブジェクトかファンクションのどちらかつかって責務を実現する. なので, OOP と FP は共存関係にある.

OFP 新三種の神器.

  • トレイト
  • モナド
  • 型クラス

OFP を導入することメリットは, 以下.

  • 高階関数 や DSL を書くことで 開発効率 をあげる
  • Monadic Programming を行うことで並列処理の品質をあげる

どこに Functional Programming を適用するか? #

Functinal Programming で書くと, バグが出にくいので, Functonal Programming の割合をできるだけ増やしていくのがベスト.

システム開発では, OO:FP の割合は 6:4 くらいか??

FP でつくるのに適した部分は, DSL の部分. OOP で, Framework と呼ばれている部分.

アプリ開発は Java でもいい. アプリ開発の基盤にある DSL 部分を 関数型でかく.

DSL #

DSL とは,特定のタスク向けに設計されたコンピュータ言語. DSL は一種類のタスクをうまく実行することに集中したもの.

そして, FP (というよりも Scala) は, DSL を書くことに適している (Scalable language). なぜなら, 簡単に独自の型や制御構造を定義できるので.

Functional Programming Patterns #

Based on bellows.

recursion #

list 型のデータ構造を扱うときの手法.

tail recursive #

pattern matching #

tuple 型のデータ構造を扱うときの手法.

overlapping pattern: 重複パターン #

ボリモーフィズムによってパターンマッチをする方法.

数学的帰納法によって, 定義される関数.

last :: [a] -> a
last [x] = x
last (_ : xs) = last xs

数学的背景 #

数学対応マップ #

以下に数学的概念と関数型言語の対応マップがある.

ラムダ計算 #

数理論理学 #

Curry-Howard 同型対応 #

プログラミング言語理論と証明論において, 計算機プログラムと証明との間の直接的な対応関係のことである.

  • 「プログラム=証明」 (proofs-as-programs)
  • 「型=命題」 (formulae-as-types)

カリー=ハワード同型 (Curry-Howard isomorphism) は, 数学の一見無関係に思えるふたつの領域, 型理論と構造論理を結びつける実に驚くべき関係

コンパイル = 証明 #

コンパイルを通すということは, 正しさを証明すること

関数型言語では, コンパイルが通るとバグがほとんどでない. 純粋関数の世界でプログラミングをすることによって, 実現できる. 背景には数理論理学がある. (Curry-Haward 対応)

このことがなぜ大事かというと, 並列プログラミングのバグとりは大変. テストですべてのバグをとれたという保証ができない.

関数型ならば数学をベースにして, バグがないことを証明することができる

抽象代数学 #

Functional Laws #

Based on Brian Lonsdorf’s Great Presentation.

Composition laws #

Currying #

Lenses laws #

A function that acts as both a getter and setter.

Fmap laws #

Null checking #

Error handling #

Monad laws #

Future values #

Functor #

Nesting #

Applicative laws #

Monoid laws #

Accumulation #

Monoid #

Arrow laws #

Combinators #

Arrows #

Functional Design Patterns #

Functional Design Patterns

Bookmarks #

関数型言語でプログラミングすることで, 学生は, データが帰納的に定義出来ることや, たくさんの興味深いアプリケーションが基本的にデータ型のパターンマッチを使っていることや, コードは本質的にデータとは異なることや, 副作用を最小限に抑えることで連結が楽になることなど, 重要な見識を広げます. これらは例えあなたが Java や C++ でプログラミングするつもりであったとしても有用な見識なのです

有名なページだけど理解できなかった. またあとで.

Active Recalls #

カリー化と部分適用の違いはなんですか? #

カリー化は複数の引数を受け取る関数の表現を一つの引数を受け取る関数の連鎖に書きすこと.

部分適用は関数の一部の引数を固定化して新しい関数を作り出すこと.

カリー化は元の関数の表現の変形にすぎないが部分適用は元の関数とは別の新たな関数.