FP (プログラミング言語)

FP

パラダイム	関数型プログラミング
登場時期	1977年
設計者	ジョン・バッカス
方言	FP84
影響を受けた言語	APL
影響を与えた言語	FL, Haskell, J

FP（Function Programming の略）は、ジョン・バッカスが関数型プログラミングパラダイムを支持するために創り出したプログラミング言語の1つである。名前が付けられた変数を排除することができる。本言語は、バッカスによる1977年チューリング賞受賞講演「プログラミングはフォン・ノイマン・スタイルから解放されうるか?: 関数型プログラミング・スタイルとそのプログラム代数」において発表された。同講演の内容に基づいて発表された論文は、関数型プログラミングの研究への関心をかき立て、結局はバッカスが期待していた関数レベルパラダイムではなく、モダンな関数型言語につながった。FPそれ自身は学術目的以外では決して使われなかった。バッカスは1980年代に後継のプログラミング言語FLを創り出したが、それも研究プロジェクトの域を出なかった。

概要

FPで書かれたプログラムがある別の値へと写像する値(value)は、列形式化(sequence formation)の下閉じている1個の集合(set)から構成される。

もし、x1, ..., xn が値であれば、列(sequence) 〈x1, ..., xn〉も値である。

これらの値は、真偽値、整数、実数、文字など任意のアトムの集合から組み立てることができる。

真偽値(boolean)	: {T, F}
整数(integer)	: {0, 1, 2, ..., ∞}
文字(character)	: {'a', 'b', 'c', ...}
記号(symbol)	: {x, y, ...}

⊥は未定義/不定(undefined)の値であることを表し、ボトム(bottom)という。列はボトムの性質を保存する(bottom-preserving)。

〈x1, ..., ⊥, ..., xn〉  =  ⊥

FPで書かれたプログラムは、ある単一の値xそれぞれを別の値に写像する関数 (function) fである。関数fを値xに作用させた結果を f:x と表現する。

関数は、原始的、すなわち、FP 環境において提供されるか、またはプログラム形式化演算（program-forming operation（関数形式functional formとも呼ばれる））から構築されたか、である。

原始的関数の一例に定数関数(constant)があり、これはある値xを${\overline {x}}$に変換する。関数は正格である。

f:⊥ = ⊥

別の例にセレクタ(selector)関数ファミリがある。ここで、1, 2, ... は、

i:〈x1, ..., xn〉	= xi	（1 ≦ i ≦ n のとき）
	= ⊥	（それ以外のとき）

を意味する。

関数形式

原始的関数とは対照的に、関数形式は他の関数に基づいて演算を行う。たとえば、加算 として0を、乗算 として1をとるような単元(unit value)を持つ関数もある。関数形式unitは次のいずれかである関数 fに適用される際にそのような値を生成する。

unit +	= 0
unit ×	= 1
unit foo	= ⊥

以下はFPの中核となる関数形式である。

合成	f∘g	f∘g:x	= f:(g:x)
組み立て	[f1, ..., fn]	[f1, ..., fn]:x	= 〈f1:x, ..., fn:x〉
条件式	(h → f;g)	(h → f;g):x	= f:x （h:x = T のとき）
			= g:x （h:x = F のとき）
			= ⊥ （それら以外のとき）
分配適用	αf	αf:〈x1, ..., xn〉	= 〈f:x1, ..., f:xn〉
右挿入	/f	/f:〈x〉	= x
		/f:〈x1, x2, ..., xn〉	= f:〈x1, /f:〈x2, ..., xn〉〉
		/f:〈 〉	= unit f
左挿入	$\backslash$f	$\backslash$f:〈x〉	= x
		$\backslash$f:〈x1, x2, ..., xn〉	= f:〈$\backslash$f:〈x1, ..., xn-1〉, xn〉
		$\backslash$f:〈 〉	= unit f

方程式型関数

関数形式により原始的関数から構築されているものに加え、関数はある方程式により再帰的に定義されることもできる。もっとも単純なものは次のものである。

f ≡ Ef

ここで Ef は、関数形式を用いて、原始的関数、他の定義済関数および関数記号 f それ自身から構築された1個の式である。

外部リンク

• Progopedia