プログラミング言語:FPsystem

Backus' FP system

「プログラミングはフォン・ノイマン・スタイルから解放されうるか?」 (本棚) からちょっとサマライズ。
- 講演の中でBackusはシステムの完全な定義を与えているわけではない。原則と表現の例を挙げて概要を提案している。
- FP system はλ算法を基礎とはしていない。

関数の定義に仮引数はない。変数もない。
関数を適用する値は単一の値かシーケンス。

function ... あらかじめ定義しておく基本的な計算を表す関数
functional form ... 関数をどう組み合わせるかの形式的表現
object ... 値、シーケンス（関数はobjectではない!!!）
application ... functional form / function を値に適用すること。 form:object のように ":" で表現する。
----
functional form
FP systemでは、算法を表現するのにある種の演算子を使って、関数や定数を組み合わせる。

functional formを構成する演算子の例

・ <composition> ... 関数と関数の合成。
F・G:x = F:(G:x)

α <apply to all> ... 値がシーケンスであるとき、すべての要素に関数を適用する。
αF:<x,y,z> = <F:x,F:y,F:z>

／ <insert> ... 値がシーケンスであるとき、すべてのシーケンス同士の間に関数を挿入する。
／F:<x,y,z> = F:<x,(F:<y,z>)>

[ ] <construct> ... 値にそれぞれの関数を適用した結果をシーケンスにする。
[F,G,H]:x = <F:x,G:x,H:x>
----
例：行列の内積(IP = inner product)を求めるfunctional form
IP ≡ (／＋)・(α×)・Trans

使用されている関数
＋与えられた組の和を返す
× 与えられた組の積を返す
Trans 与えられた行列の転置行列を返す

IP:<<1,2,3>,<6,5,4>>
⇒ (／＋)・(α×)・Trans:<<1,2,3>,<6,5,4>>
⇒ (／＋)・(α×):<<1,6>,<2,5>,<3,4>>
⇒ (／＋):<×:<1,6>,×:<2,5>,×:<3,4>>
⇒ (／＋):<6,10,12>
⇒ ＋:<6,(＋:<10,12>)>
⇒ ＋:<6,22>
⇒ 28
----
Scheme で書かれた FP/FFP と Web インターフェース。=)
http://ca.meme.hokudai.ac.jp/people/tak/fp/fp-eval.html
- 注： ↑のサイト自身にはもうCGIはないようです。

[[id:1069]] 2002-09-08 23:55:22

FP system -- 素数を求める

ある実装からサンプルコード
#
# Print prime numbers from 3 to ?
#
{factors
&(+@[id %1]@*@[id %2])@iota@div@[id %4]
}
{isprime
|and@&(~=@[id %0])@&mod@distl@[id factors]
}
{primes
concat@&(isprime -> [id] ; %<>)@&(+@[id %1]@*@[id %2])@iota
}

※この処理系における記号のASCII表現

& == α(apply all) ... いわゆる map
@ == ・(composition)
| == ／(insert) ... いわゆる fold
% == ￣(constant) ... 定数関数
<pred> -> <true expr>; <false expr> == foo → bar ; baz (selector)
{<func-name> <functional-form>} == Def <func-name> ≡ <functional-form> ... 関数定義
~ == (不明) ＜コラ
----
もうひとつの実装では：
Def filter null o 2 -> _<>;
(bu = 0) o mod o [1 o 2, 1] -> filter o [1, tl o 2];
apndl o [1 o 2, filter o [1, tl o 2]]
Def sieve (null -> _<>;
apndl o [1, sieve o filter o [1, tl]])
Def primes sieve o tl o iota

記号類はこっちのほうがすっきりしててよさげ。=)
- composition -- "o"
- constant -- "_"
- definition -- "Def"

[[id:1130]] 2002-09-05 09:52:51

FP system -- ソート

#
# A divide-and-conquer sorting algorithm
#
{grpleft
concat @ &( > -> tl ; %<>) @ distl }
{grpright
concat @ &( < -> tl ; %<>) @ distl }
{arb 1}
{bsort
(>@[length %1] ->
concat@[bsort@grpleft [1] bsort@grpright]@[arb id]
; id)
}
{swap concat@[ [2,1],tl@tl ]}
{step (>@[1,2] -> swap ; id) }
{pass
(<@[length,%2] -> id ;
apndl@[1,pass@tl]@step)
}
{bubsort
(<@[length,%2] -> id ;
apndr@[bubsort@tlr,last]@pass)
}

[[id:1131]] 2002-09-05 10:24:51

Backus' FFP system

論文の中でBackus' FP system (#1)の次に説明されているのが FFP system (Formal systems for Functional Programming)。

こちらでは関数もオブジェクトで、apply:<x,y> ⇒ x:y となる。
apply:<add,<1,2>> ⇒ add:<1,2> ⇒ 3

またシーケンスを関数として値に適用することでFunctional Formを表現することができる。
そのために導入されるルールが Metacomposition Rule。

シーケンスを関数として評価すると、シーケンスの最初のオブジェクトである関数に、シーケンス自身と引数のペアが引数として渡される。つまり、
<X,Y,Z>:A
という式があった場合、
X:<<X,Y,Z>,A>
と変形され評価される。

[f,g,h]:x ⇒ <f:x,g:x,h:x> となるような演算子 [ ] (construct) を表す関数 CONS は、

Def CONS ≡ αapply・tl・distr

で定義できる。

<CONS,f,g,h>:x
CONS:<<CONS,f,g,h>,x>
⇒ αapply・tl・distr:<<CONS,f,g,h>,x>
⇒ αapply・tl:<<CONS,x>,<f,x>,<g,x>,<h,x>>
⇒ αapply:<<f,x>,<g,x>,<h,x>>
⇒ <apply:<f,x>,apply:<g,x>,apply:<h,x>>
⇒ <f:x,g:x,h:x>

ここで
distr は distr:<<a,b,c>,x> ⇒ <<a,x>,<b,x>,<c,x>>
tl は tl:<a,b,c> ⇒ <b,c>
となるような関数。

ちなみにcompositionを表す演算子・にあたる関数 COMP はprimitive function だそうな。
（なんかちょっとズルいような‥‥‥）

<COMP,f,g,h>:x ⇒ (f:(g:(h:x)))

[[id:1126]] 2002-09-04 12:08:43

キーワードはコンビネータ？

Backus' FP system (#1) の演算子というのはコンビネータなんだと思う。
FPsystemに変数が存在しないのは、コンビネータ・スタイルでは関数定義から仮引数が消えてしまうのとおなじことっぽい。

functional-form : <sequence...>
というのは見方を変えると function(args...) だともいうことができるので変数がないことと引数の中に関数呼び出しを置けないこと以外は普通の言語と同じなのかもしれない。‥‥‥って、その違いが一番でかいんじゃ！？（笑

":"の右辺に関数呼び出しを置けない代わりに、":"の左辺で関数をコンビネータで組み合わせてしまうことで表現力を持たせている感じ？

# SHIMADA

[[id:1133]] 2002-09-05 12:52:46

top recent

HashedWiki version 3 beta
SHIMADA Keiki