関数型言語Part5

たとえば、自動販売機の状態遷移図があったとして、それを実装しようとした時、
OOP なら素直にクラスを作って、素直に状態遷移の処理が書ける
デザインパターンにもあるくらいだし

一方、これを関数型で実装しようとすると、状態遷移図の読み取ってから、
それをコードに落とすまでに、素直に作業が進むとは言いがたいと思う
（実際にそういう経験が多々ある）
図ではそれぞれの状態は分かれて書かれているのに、
関数型のコードにすると局所化されずに関係が全体に広がってしまう感じ

なんていうか、図とコードの一体感が薄い

OOP だって図とコードが一対一に対応しているわけでは決して無いんだけど、
OOP の場合は他人のコードを読んで、それを逆に状態遷移図に起こすことも、
そのコードが元々ちゃんとした状態遷移図からコード化してるのなら比較的素直にできる
それくらいには図とコードの一体感がある

関数型の場合、それが難しいと感じるケースが多い

状態遷移自体は必要なのだから何らかの図は必要なのだが、
今までの UML の状態遷移図が関数型にフィットしていないのか、
それともそれを関数型のコードに落とす手法に問題があるのか、
それとも単に私がまだまだ未熟なだけなのか

そんな難しいことここで言うなよｗ

状態という考え方と関数型プログラミングとは馴染まないんだよ。
そもそも状態遷移をガンガン使うって事は変数の値を次々に書き変える事で処理を進める手続き的パラダイムで考えてるって事だからね。
もちろん、そういうパラダイムの処理を関数型でシミュレートする（状態を表す引数を次々に渡す）事はできるが、
本来の関数型のパラダイムはそういう変数への破壊的な代入（バインディングとは等価でない代入）を避けるべきだという哲学に基づいているから
馴染まなくて当然だし、そういう状態遷移の処理を書くのならば関数型よりも手続き型の方が自然に書けて当然なんだよ。

>>491-493
お前らにまとめて聞きたい
お前らはCのような手続き型言語であれば状態遷移機械を書けるのか？
実は書けない、あるいは今まで書いた事が一度も無いんじゃないのか？
情けない奴ら、お前らの将来はIT土方一直線で決定だ

反論があるなら、その前にまずWikipediaでトピック「有限オートマトン」にある
数学モデルの節を読め
ここではトランスデューサ型で決定性オートマトンだけを見ればいい
面倒であればトピック「ミーリ・マシン」を直に見てもいい

これだけ簡潔な数学的定義があるのに、まだ難しいとか馴染まないとか言うつもりか？！

foldlは実はミーリマシンなんだよな

>>493
>本来の関数型のパラダイムはそういう変数への破壊的な代入を避けるべきだという

再帰的に状態値を次々に渡していくのなら、破壊的代入にならないのではないかと....小一時間

状態絡みはFRPに落とし込めばおけー(´・ω・｀)

>>491
状態機械を素直に書けない関数型言語があるってのはちょっと信じられない
>それともそれを関数型のコードに落とす手法に問題があるのか、
>それとも単に私がまだまだ未熟なだけなのか
このどちらかだと思う

具体的なコーディングは次のような感じ

1. 各状態に対応する関数を一つづつ作って、それらが
次状態に対応する関数を末尾呼び出しするようにする
コーディングは楽だけど、状態機械側から能動的に入力を取ってくる方法がある場合に限る

2. そうでない場合は、状態に対応する型を定義する
2-1. 一般には関数を使う。Haskellの記法で、
newtype State = State (Input -> IO (Output, State))
みたいな
2-2. 一目で全体を見渡せる小さい状態機械なら、具体的な列挙型のほうが楽なこともある
data State = State1 | State2 | State3...
みたいな

Haskellだと、スレッド+チャネルを使ったり継続モナドを使ったりすれば、あらゆる状態機械を1.の方法で書ける
（そのぶんコードが複雑になるので、本当にやるかどうかはケースバイケース）

FRPはまだまだ使えない技術
M$もRxでReactiveの方にも力入れてたのに結局Async選んだからな

>>493
状態遷移を避けるべきなんて言ってる関数型言語は聞いたことがない
(教科書にはそう書いてあるかもしれないが、それは手続き型言語にどっぷり漬かった
学習者のための方便で、実際にコードを書くときに盲目的に従うものじゃない)
大抵、一つのプログラムには、関数的に書いた方が素直な部分と
手続き的に書いた方が素直な部分が共存してる
いわゆる実用的な「関数型言語」は、この両方を簡単に扱えるように作られてる

あ、「型を定義する」うんぬんは、静的型付けの言語を想定してた
動的な場合は、頭の中かコメントで定義すれば良いはず

>>499
AsyncとFRP（Rx)は別物だよ。
Asyncは主にIOなどの実行に時間がかかるものに対しての継続の制御方法で、Rxは解釈にもよるだろうがデータフローの意味合いが強く、その中に継続のコントロールも入っていて両者を組み合わせて使うことも可能。

関数型は状態を持たないと言うよりも、"副作用の原因となる"状態を持たない。

でも正式採用されたのはAsyncだけだよねっていう

>>498,500
ようやく、平常な水準で語ってくれる人が登場してくれて安心した

自動販売機/信号機/通信プロトコルといった実時間システム(Real Time System)は、
動いて当たり前、バグ0で数年間連続稼働するのがマジで求められる世界
病院の生命維持装置や宇宙船の航行制御装置などを想像すれば分かってもらえるハズ
だから、そういったソフトウェア品質/安全性を求む組み込み系の開発現場(の一部?)では
堅固な型体系を持つ関数型言語への強い期待があったりする

そんな訳で、関数型言語に状態機械は馴染まない/難しいみたいな発言は哀しいんだYo....

そういう人たちが言う関数型ってhaskellみたいなもんじゃなくてStrong functional programmingとかTotal Functional Programmingのことでしょ
依存型がもっと軽量に扱えるようにならんと話にならん

>>506
そのStrong functional programming/Total Functional Programmingとは何？
少なくともHaskellはシミュレーションやモデル検証には適しているかもしれないが、
状態機械の「実装言語」としては全く認識していない。(今のC/C++実装を置き換えたい....)
軽量/簡潔な言語仕様のSML処理系を候補にしたいと思ってる。(OCamlは仕様/実装とも重すぎ)

http://en.wikipedia.org/wiki/Total_functional_programming

>>508
Total_functional_programmingって初めて知るけど、全域関数しか認めない帰結として無限ループが使えない、よってチューリング完全ではない、という理解でO.K.？
無限ループが使えない、って組み込み系としてはかなりダメダメのような…

無限ループが絶対に使えない「安全な領域」と無限ループがありえる「危険な領域」を、C#のunmanaged codeみたいに、あるいはHaskellのIOモナドみたいに隔離してあつかえる言語が望ましいのかも

たとえば状態Ａと状態Ｂ、状態Ｃがあるとする
今状態Ａであるときにイベントｘが起きたら、
状態Ａが保持してる内部の変数の値とxで計算して、
その結果ｙをまた状態Ａの内部変数に格納する
ｙの値によって次に状態Ｂか状態Ｃへ遷移する

こういう場合、OOP なら素直に状態毎にクラスを作る
あるいは一つのクラスのインスタンスを状態毎に作る
で、状態Ａを表現するインスタンスのメンバ変数は、
そのインスタンスの中で完結していて外に出ることはない

一方、関数型でこれを実現するとき、
「状態を引数に入れて、計算して、戻り値として状態を返す」
ということを（再帰的に）繰り返すという方法をとると、
状態Ａの内部変数に相当する値も色んなところへ運ばれる事になる
そうしないと、また状態Ａに戻った時に計算できない

また、Haskell の State モナドのような仕組みを使っても同じ
本来は内部に閉じ込めておくべき情報が外に出ることに変わりはない

たとえ何らかの方法で、状態Ｂや状態Ｃの計算をしてる時には
状態Ａの内部変数に相当する値にはアクセスできない仕組みがあるとしても、
その仕組みを作っている時は、色んなところへ情報が漏れることを
ちゃんと意識してプログラミングする必要がある
（一般的な OOP ならその仕組みは改めて作る必要は無い）

また、状態Ａの計算の最後に状態Ｂを末尾呼び出しする方法は、
状態間の繋がりがますます強くなる

情報の漏れと結合度の強さ、これらをもう少し改善する方法はないだろうか

>>508
紹介ありがとう
ただ、ざっとリンク先を読んでみたけど明らかに違う
そういった数理的な完全性という狭い分野での品質向上を求めているわけじゃなくて、
開発工程全体に渡る効果を期待しているし、現状を一切切り捨てるという判断は到底無理

おそらくリンク先のトピックはCafeObjのような形式的手法やCoqのような定理証明系、または
このスレならHaskellベースの帰納的な(純粋関数型の?)設計手法が該当するんだろう
そういった手法は提供範囲を限定すれば効果はあるだろうけど、開発工程全体への波及は期待できない
たとえば仏生まれのCoqなら、もしOCaml処理系全体の定理証明が完成すれば認識を改めたい

チューリング完全でないのはその通りだけど、
何かを出力し続ける、あるいは外界と相互作用する無限ループは(余再帰という形で)扱えるはず
特定の値を求めるべき関数が無限ループするのは禁止

>>510
> 一方、関数型でこれを実現するとき、
> 「状態を引数に入れて、計算して、戻り値として状態を返す」
> ということを（再帰的に）繰り返すという方法をとると、
> 状態Ａの内部変数に相当する値も色んなところへ運ばれる事になる
> そうしないと、また状態Ａに戻った時に計算できない

ん？？？　ここが不可解
それって、あなたがいっているOOPでも、状態Aから状態Bに遷移しても「状態Aのインスタンス」を保持しておいて、状態Aに戻ったときにそれを復帰させるってこと？

それはもう状態マシンの設計として破綻してない？
なんか、状態マシンと別の何かをごっちゃにしているような・・・

>>512
余再帰とか高度なことは分からないので十分に理解できないけど、考えてみると、
たしかにほとんどの「無限ループ」はプログラム全体（あるいはエントリポイント）をインプットからアウトプットへの関数として定義すれば、
いいような気はする。

>>510
情報の漏れに関してはHaskellやOCamlならモジュールで隠す
隠蔽の単位がクラスからモジュールになっただけで、一般的なOO言語とそんなに違わない

結合度については、状態機械なら、自分が次にどの状態に
移行するかを知ってなきゃいけないのは仕方ないんじゃね

>>510
let..inとかwhereで関数内関数（または変数）じゃ駄目なん？
モジュールだって在るし。

ＧＣあるとリアルタイム制御厳しいよね
ＧＣのない関数型言語ってあるのかな？

>>517
実験レベルのものなら
https://github.com/pikatchu/LinearML

ぴかちゅー
線形型か・・・

>>517
遅延評価の関数適用順序がリアルタイム性も考慮して進化してったら、そう言う用途にも使える様にならんかな。。。

>ＧＣあるとリアルタイム制御厳しいよね

[過去] Linuxでリアルタイム制御厳しいよね
　　　組み込み系にJava VMって重すぎるよね

[現在進行形] 組み込み系にRubyって.......

勘弁しておくれ

>>513
正直、何か別のものと混同してる感じは自分もする
状態マシンというものを勝手に拡張して解釈しているかも知れん

結合度の事はとりあえず置いておいて、>>510 の前半で言いたかったのは、
C# だとこんな感じなる状態遷移の実装（文法や初期化とかは気にするな）
実際に状態遷移させるのは別のクラスで状態遷移表なんかを使ってやってるとする

class State {
public int next (int e);
}

class StateA : State {
private int x;
public State next (int e) {
x = f(x, e); // 適当な関数 f によって計算
return x;
}

状態Ａの次にどの状態に遷移するかは状態Ａのメンバ関数 next の戻り値に依るんだけど、
その戻り値が状態Ａが保持してるメンバ変数 x に依存してる
つまり、状態Ａのメンバ変数 x はずっと保持しておかなければならない
他のクラスのインスタンスからもアクセスされてはいけない

こういうパターンって普通にあるよね（ゲームなんか作ってるとよくある）

これ、関数型（わたしは Haskell しか使えないけど）だと、
自分では未だになかなか綺麗に関数型らしく書けなくて毎回悩むところ
（IORef で妥協するのは何か気持ち悪い）

>>522
まぁ IORef 使ったって、結局その IORef 型の変数の値を運ぶことになるんだけどね

関数型らしく書こうとするのを止めればいいんじゃね
IORefを使って綺麗に書けるならそうしない理由はないと思う

大抵のFRPはそのIORefのプールを保持して適切にアップデートするような作りになってるな
とりあえず上のコードで喩えるとxが消えて
見かけ上はStateAはeと別の信号fから違う信号を生成するってだけの関数ぐらいには楽に変えられる

成熟したFRPライブラリが存在しない現状、
アプリ全体を関数型でかっこよく書くのは諦めた方が速い

なんだかんだで関数型言語は組込でもRubyに負けちゃうのかな。

>>522
それ Haskellなら

module State (State, next) where
class State s where
　next :: s -> e -> s

module StateA (StateA(), stateA) where
data StateA = StateA Integer

sateteA = StateS

instance State StateA where
next (StateA i) e = f i e
　　where
　　　f = ...


みたいにすれば良いんじゃね？

>>522
状態機械どころか、OOP(GoF)のState Patternですらない

クラス名 State や StateA は状態という概念である必然性が無い。
たとえば Room と RoomA や Level と LevelA でもかまわない。
単にあるオブジェクトが別のオブジェクトへ変化するだけ。
それは状態機械ではないし、State Pattern ですらない。

回路設計に関数型言語とかあったけどあれも死んだっぽいな
証明支援系を利用した超強力な形式手法をサポートしたものぐらいじゃないと
手続き型でもどうにかなるものに対しては置き換える価値を示せないのだろうな
逆に言えばそういうのじゃないとどうしようもない複雑すぎる問題が増えてくれば自然にそっち方向にシフトしていくと思う

>>527
秋月電気にpic様のbasicインタプリタ置いてる時点で、rubyの方がまだ可能性は在るんだろうな

>>525
大抵のFRPがどれを指してるのか分かんないんだけど、
たとえば Yampa や reactive は確かに内部で IORef は使ってる

でもそれって、それらのライブラリ内で自身の構造を保つ為に使ってるのであって、
そのライブラリのユーザー側が定義した情報を遷移させても保つ為のものでは
ないような気がするんだが

もう一度 FRP ライブラリをよく見てみます

>>528
StateA --> StateB --> StateC --> StateA と回った時、
最初に StateA の next を計算した時の値は、
次の StateA の next を計算する時にまた使わなければならないけど、
それはどこかに保存しておくか、遷移時に運ぶデータとして連れて行かないといけない

>>529
やはり勘違いしていたか
申し訳ない、全然話が別だったね

じゃあ、状態機械とか State Pattern の話ではなくて、
純粋に単なる >>522 のようなパターンの時に、
関数型ではどうしてるのかなという話で
（わたしはこういうパターンでも、同じような図を描いて設計してた）

ハード的には状態機械は
f.reset(env, orig_state) -> f(env, state)
f(env, state) -> f(env, state')
ってな形のフィードバックループで実現するんだが,

state を変数にするか， 関数の名前のにするのか程度の違いじゃないのか?

f の内部レジスターが state になることがほとんどだから,
個人的には， 関数名が違ってる方が理解しやすいが...

# つか, わざわざ外部に状態用のレジスターを作るのはトランジスタの無駄

とんちんかんな事いっているかもしれないが
組み込みとリアルタイム制御を混同しているような
人に待ってもらえるアプリならばrubyでも問題ない

車の制御系をlinux,java,ruby,haskellでできるのか
ブレーキかけた時にGCが始まってしまうと困るのだが

関数型言語がすばらしいというのはわかるが
じゃあ、C、アセンブラに代わりうるものなのかな

>>534
リアルタイム制御の話は一瞬出て、一瞬で終わっただろ

誰もCやアセンブリに代わるとも言ってねぇし

でも当然研究はされてると思う

研究されているとかイチイチ気にしないほうがいいぜ。
どうせドンピシャな研究してても説明下手くそなのと、よくわからん秘密主義で
余計コストかかるだけだよ。

この手の研究は大抵 SIGPLAN に論文が投稿されて、
たった25ドルで一年間読み放題だ

ソフトリアルタイムシステムまでは
Erlangっていう実績がある
RubyのRiteもソフトリアルタイムまでをターゲットにしていたはず

問題はハードリアルタイムなシステムで、
NASAの国際宇宙ステーションだったかの、制御プログラムが仕様通り動作することを
定理証明支援系で検証した話を聞いたことが、あるような無いような

>>496
> >>493
> >本来の関数型のパラダイムはそういう変数への破壊的な代入を避けるべきだという
>
> 再帰的に状態値を次々に渡していくのなら、破壊的代入にならないのではないかと....小一時間

だから変数への破壊的代入に比べて引数を引きずり回さねばならないってのは不自然あるいは煩雑な記述だろうが。
状態遷移の考え方から素直に生まれたのが内容を破壊的に書き換え可能なメモリとそれへの代入命令をベースとする
手続き型プログラミングのパラダイム。
関数型プログラミングのパラダイムでベースとなっている概念はメモリを用いずに値をどんどん変換という考え方。

>>540
破壊的な代入を隠蔽したのがFRPだと思ふ(´・ω・｀)

隠蔽してメリットあんの？

>>540

>>496のつっこみはたしかに日本語に不自由している感じはあるが、一般論として

> だから変数への破壊的代入に比べて引数を引きずり回さねばならないってのは不自然あるいは煩雑な記述だろうが。

というのには反論したい。

例えば、ある種のステートマシンは、Haskellなら

state1 (Event1:es) = state2 es
state1 (Event2:es) = state3 es
state2 (Event1:es) = state1 es
state2 (Event2:es) = state3 es
state3 (Event1:es) = state1 es
state3 (Event2:es) = state2 es

みたいに書くことができる。

これは破壊的更新を避けて値を引きずり回しているけど、破壊的更新をするよりも、自然かつ簡明になっていると思う。