Haskell勉強会

関数型プログラミングの学習日記

すべてを関数と見なす

関数型プログラミングの特徴として、「すべてを関数と見なす」という考え方が紹介されていました。

 

関数型言語ML (SML, OCaml, etc.), Part 7

10 :デフォルトの名無しさん:2017/12/28(木) 09:57:11.71 id:H09IESsG.net

関数型って変数が定数になっただけ?


11 :デフォルトの名無しさん:2017/12/28(木) 17:39:41.34 ID:N/80jHgY.net

すべてを関数と見なすだけ

定数も「定数を表す関数」と見なす

immutableかどうかは別の話

 

言われてみたら、「そんなかんじだよな~?」と思いつつも、いまいちピンと来ない部分もあったので、ちょっと調べてみました。

 

すべてを関数と見なす - Google 検索

 

第16回 すべてのものは関数である | 日経 xTECH(クロステック)

2007/11/14

数理科学的バグ撲滅方法論のすすめ

第16回 すべてのものは関数である

 

すべてのものは…である

 SmalltalkRubyなど,いわゆる生粋のオブジェクト指向言語では,「すべてのものはオブジェクトである」(everything is an object)と言われることがある。JavaC++などと異なり,整数の「123」や浮動小数の「4.56」といった,基本データ型の値もオブジェクトとして扱うことができるからだ。

 では,オブジェクト指向言語のまねをして,関数型言語において「すべてのものは関数である」と言うことはできるだろうか?

 もちろん,オブジェクト指向と違って,関数型プログラミングはあくまで「数学的な(=副作用のない)関数を中心とするプログラミング」に過ぎず,「すべてのものを関数とみなす」ことを目指しているわけではない。したがって,通常,「123」や「4.56」を関数とみなす,といった欲求はない。

 

という対比になっているわけじゃない、と。

 

 ところが,関数型言語のモデルとなっている基礎理論では,実は「すべてのものを関数で表す」ことができる。より正確にいうと,(計算機自体の一般的なモデルである)チューリングマシン」で可能な計算は,すべて関数で表せることが知られている。それが今回紹介するλ計算(ラムダ計算)という計算モデルだ。

 

なるほど!

関数型プログラミングで「すべてを関数と見なす」と言った場合、その背景にあるのは、ラムダ計算の考え方を指しているのですね?

 

 純粋なλ計算は,一言でいうと「関数しかないプログラミング言語」だ。純粋なλ計算のプログラム(λ式)の構文は,以下の3行で表される。

  • λ抽象「λx. e」
  • 関数適用「e1 e2」
  • 変数「x」

 ただし,xは変数一般を表す記号,e,e1,e2などはλ式一般を表す記号とする。

 λ抽象「λx. e」は,OCamlの「fun x -> e」に相当する構文で,xを受け取ると,eを評価して返す関数を表す。関数適用と変数の意味はOCamlと同様だ。

 

プログラムを構成する要素は、「データ」と「処理」の2つがあります。

  • 「データ」は状態
  • 「処理」は変化

INPUT(データ:前の状態) → PROCESS(処理:変化) → OUTPUT(データ:後の状態)

プログラムは、このサイクルが延々と続いているだけですね。

 

f:id:hamamuratakuo:20151121110052p:plain

 

この「処理」の部分が、関数というのは直感的に分かります。

それでは、「データ」の部分も関数と考えることもできるのでしょうか?

 

INPUTとOUTPUTが同じ場合=変化のbeforeとafterが同じ場合=これは引数と返値が同じ関数、ということになりますね。→ f(x)=x みたいな関数

 

定数関数 - Wikipedia

数学の分野における定数関数(constant function; 定値写像)とは、それがとりうる値が変数の変動によって変わらない定数値の関数写像)のことを言う。

例えば、関数 f(x) = 4 はすべての値を 4 へと写すため、定数関数である。

 

http://www.geocities.jp/koga58/computer/clogic.html

コンビネータ論理(Combinatory Logic) のお話

 

K コンビネータ

K x y = (K x ) y = x

直観的には,プログラム言語のif文「if 条件 then 式1 else 式2」 の 部条件文の部分に true を入れた文のような機能を持っている.

K のもう一つの重要な機能は,定数関数を作るという機能である.どんな 引数をもらっても,ある決まった式 Exp を返したいときは,(K Exp) とすればよい.

(K Exp) x = Exp

となる.つまり,(K Exp) は Exp を抱え込んでいて,何か受け取るといつでも Exp を返す機能を持っている.

 

f(x) = 1 という定数関数なら、変数xに何を入れても、答えは全部1になります。

 

これが冒頭で引用した

定数も「定数を表す関数」と見なす

という意味かな?

 

第一級関数 - Wikipedia

計算機科学において、第一級関数(first-class function)とは、関数を第一級オブジェクトとして扱うことのできるプログラミング言語の性質、またはそのような関数のことである。

その場合その関数は、型のある言語では function type などと呼ばれる型を持ち、またその値は関数オブジェクトなどになる。

具体的にはプログラムの実行時に生成され、データ構造に含めることができ、他の関数の引数として渡したり、戻り値として返したりすることのできる関数をいう。

この概念はメタプログラミングとは異なり、コンパイラ呼び出しやeval関数によって生成された関数は含まれない。無名関数も参照。

 

第一級関数は関数型言語には必要不可欠であり、高階関数のような形で日常的に用いられる。

例として、関数とリストを引数に取り、リストの各要素に関数を適用した結果のリストを返すmap (mapcar) 関数が挙げられる。

map関数をサポートするプログラミング言語は、何らかの形で関数を関数の引数として渡すことを許容しなければならない。

 

  • 「データ」も「処理」として扱える → 定数は「定数を返す関数」として表せる
  • 「処理」も「データ」として扱える → 第1級関数

 

関数型プログラミングを勉強するとき、

  • 「すべてを関数と見なす」
  • ラムダ計算

という考え方を念頭に置いて、進めてみたいと思います。

 

 

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)