94

関数型プログラミング言語が状態を保存できない場合、ユーザーからの入力を読み取るなどの単純なことをどのように行うのでしょうか? 彼らはどのように入力を「保存」しますか（またはそのためのデータを保存しますか？）

たとえば、この単純な C は Haskell のような関数型プログラミング言語にどのように変換されるでしょうか?

#include<stdio.h>
int main() {
    int no;
    scanf("%d",&no);
    return 0;
}

(私の質問は、この優れた投稿「名詞の王国での実行」に触発されました。それを読んで、オブジェクト指向プログラミングとは何か、Java がそれを極端な方法で実装する方法、関数型プログラミング言語がどのように機能するかについての理解が深まりました。対比。）

4

10 に答える 10

81

関数型プログラミング言語が状態を保存できない場合、ユーザーからの入力の読み取り (つまり、それを「保存」する方法) や、そのためのデータの保存などの簡単なことをどのように行うのでしょうか?

お察しのとおり、関数型プログラミングには状態がありませんが、データを格納できないわけではありません。違いは、（Haskell）ステートメントを次の行に沿って書くと

let x = func value 3.14 20 "random"
in ...

xの値は常に同じであることが保証されています...。何も変更することはできません。同様に、関数f :: String -> Integer(文字列を取得して整数を返す関数) があるf場合、引数を変更したり、グローバル変数を変更したり、データをファイルに書き込んだりしないことを確認できます。上記のコメントで sepp2k が述べたように、この非可変性はプログラムについての推論に非常に役立ちます: データを折りたたみ、スピンドル、および切断する関数を記述し、新しいコピーを返すことでそれらを連鎖させることができます。それらの関数呼び出しのうち、「有害」なことは何でもできます。それxは常にであり、誰かがの宣言の間のどこかにx書いたことを心配する必要はありません。x := foo barxそれは不可能だからです。

では、ユーザーからの入力を読み取りたい場合はどうすればよいでしょうか。KennyTM が言ったように、不純な関数とは、全世界を引数として渡された純粋な関数であり、その結果と世界の両方を返すという考え方です。もちろん、実際にこれを行う必要はありません。1 つは、これは恐ろしく扱いにくいことです。もう 1 つは、同じワールド オブジェクトを再利用するとどうなるかということです。したがって、これはどういうわけか抽象化されます。Haskell は IO タイプで処理します。

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

これmainは、何も返さない IO アクションであることを示しています。このアクションを実行することは、Haskell プログラムを実行することを意味します。ルールは、IO タイプが IO アクションを決してエスケープできないということです。このコンテキストでは、 を使用してそのアクションを紹介しdoます。したがって、 をgetLine返しますIO String。これは、2 つの方法で考えることができます。1 つ目は、実行時に文字列を生成するアクションとして。2 つ目は、不純に取得されたために IO によって「汚染された」文字列として。前者の方が正確ですが、後者の方がより役に立ちます。は<-からStringを取り出してIO String格納しstrますが、IO アクションを実行しているため、元に戻す必要があるため、「エスケープ」することはできません。次の行は整数の読み取りを試み ( reads)、最初に成功した一致を取得します (fst . head); これはすべて純粋 (IO なし) であるため、let no = .... noその後、 でとstrの両方を使用できます...。getLineこのように、純粋でないデータ (からstr) と純粋なデータ ( )を格納しましlet no = ...た。

IO を操作するためのこのメカニズムは非常に強力です。これにより、プログラムの純粋なアルゴリズム部分を純粋でないユーザー操作側から分離し、これを型レベルで強制することができます。minimumSpanningTree関数は、コード内の他の場所を変更したり、ユーザーにメッセージを書き込んだりすることはできません。安全です。

Haskell で IO を使用するために知っておく必要があるのはこれだけです。それだけでよければ、ここでやめてください。しかし、それが機能する理由を理解したい場合は、読み続けてください。(そして、これは Haskell に固有のものになることに注意してください。他の言語では別の実装が選択される可能性があります。)

したがって、これはおそらくちょっとしたごまかしのように見え、どういうわけか純粋な Haskell に不純物を追加しました。しかし、そうではありません — 純粋な Haskell 内で IO 型を完全に実装できることがわかりました ( が与えられている限りRealWorld)。アイデアは次のとおりです: IO アクションIO typeは function と同じでRealWorld -> (type, RealWorld)、現実世界を取り、型のオブジェクトとtype変更された の両方を返しますRealWorld。次に、狂気に陥ることなくこの型を使用できるように、いくつかの関数を定義します。

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

最初のものは、何もしない IO アクションについて話すことを可能にします。return 3これは、現実世界を照会せずに を返すだけの IO アクション3です。「>>=バインド」と発音されるオペレーターは、IO アクションを実行できるようにします。IO アクションから値を抽出し、関数を介してその値と実世界を渡し、結果の IO アクションを返します。>>=は、IO アクションの結果が決してエスケープできないという規則を強制することに注意してください。

次に、上記mainを次の通常の関数アプリケーションのセットに変換できます。

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

Haskell ランタイムmainは最初の でジャンプスタートし、RealWorld設定は完了です! すべてが純粋で、派手な構文を持っているだけです。

[編集: @Conal が指摘しているように、これは実際には Haskell が IO を行うために使用するものではありません。このモデルは、並行性を追加したり、実際に IO アクションの途中で世界を変更したりすると破綻するため、Haskell がこのモデルを使用することは不可能です。逐次計算でのみ正確です。したがって、Haskell の IO はちょっとした回避策である可能性があります。そうでなくても、これほどエレガントではないことは確かです。@Conal の観察によると、Simon Peyton-Jones がTackling the Awkward Squad [pdf]のセクション 3.1 で述べていることを参照してください。彼は、これらの線に沿った代替モデルに相当するものを提示しますが、その複雑さのためにそれを削除し、別の方法を取ります.]

繰り返しますが、これは、Haskell で IO と一般的な可変性がどのように機能するかを (かなり) 説明しています。これだけ知りたい場合は、ここで読むのをやめてください。最後にもう 1 度理論を説明したい場合は、読み続けてください。しかし、この時点で、私たちはあなたの質問とはかけ離れていることを忘れないでください。

最後に、この構造 ( returnandを使用したパラメトリック型>>=) は非常に一般的であることがわかります。それはモナドと呼ばれ、do記法 ,returnは>>=それらのどれでも動作します。ここで見たように、モナドは魔法ではありません。魔法のすべては、doブロックが関数呼び出しに変わることです。RealWorldタイプは、魔法を見る唯一の場所です。リストコンストラクターのような型[]もモナドであり、純粋でないコードとは何の関係もありません。

これで、モナドの概念について (ほぼ) すべてを理解できましたが (満たさなければならないいくつかの法則と正式な数学的定義を除く)、直感が欠けています。オンラインには途方もない数のモナドのチュートリアルがあります。私はこれが好きですが、オプションがあります。ただし、これはおそらく役に立ちません。直観を得る唯一の本当の方法は、それらを使用し、適切なタイミングでいくつかのチュートリアルを読むことです.

ただし、IO を理解するためにその直感は必要ありません。モナドを完全に一般的に理解することはケーキの飾りですが、今すぐ IO を使用できます。最初の機能を示した後、それを使用できますmain。IO コードを純粋でない言語であるかのように扱うことさえできます! しかし、基礎となる関数表現があることを覚えておいてください: 不正行為はありません。

(PS: 長くなってすみません。少し遠くまで行きました。)

于 2010-05-01T20:41:52.763 に答える
23

ここにはたくさんの良い答えがありますが、長いです。私は役立つ短い答えを出そうとします：

  • 関数型言語は、C と同じ場所 (名前付き変数とヒープに割り当てられたオブジェクト) に状態を配置します。違いは次のとおりです。

    • 関数型言語では、「変数」は (関数呼び出しまたは let バインディングによって) スコープに入ったときに初期値を取得し、その値はその後変更されません。同様に、ヒープに割り当てられたオブジェクトは、そのすべてのフィールドの値ですぐに初期化され、その後は変更されません。

    • 「状態の変更」は、既存の変数またはオブジェクトを変更することによって処理されるのではなく、新しい変数をバインドするか、新しいオブジェクトを割り当てることによって処理されます。

  • IO はトリックで動作します。文字列を生成する副作用のある計算は、World を引数として取り、文字列と新しい World を含むペアを返す関数によって記述されます。World には、すべてのディスク ドライブの内容、送受信されたすべてのネットワーク パケットの履歴、画面上の各ピクセルの色などが含まれます。トリックの鍵は、ワールドへのアクセスが慎重に制限されていることです。

    • World のコピーを作成できるプログラムはありません (どこに置きますか?)

    • どんなプログラムも世界を捨てることはできません

    このトリックを使用すると、状態が時間の経過とともに進化する、1 つの一意の World が存在することが可能になります。関数型言語で記述されていない言語ランタイム システムは、新しい World を返す代わりに、一意の World をその場で更新することにより、副作用のある計算を実装します。

    このトリックは、Simon Peyton Jones と Phil Wadler の画期的な論文"Imperative Functional Programming"で美しく説明されています。

于 2010-05-01T20:59:26.653 に答える
19

より多くのスペースを確保するために、新しい回答へのコメント返信を中断しています。

私が書いた：

私が知る限り、このIO話 ( ) は Haskell に当てはめたときの神話です。Haskell の型には並行性が含まれているWorld -> (a,World)のに対し、Haskell のモデルは純粋な順次計算のみを説明しているためです。IO「純粋にシーケンシャル」とは、命令型計算の開始と終了の間で、その計算以外の理由で、世界 (宇宙) でさえ変更できないことを意味します。例えば、あなたのコンピュータが動き回っている間、あなたの脳などはそうすることができません。並行World -> PowerSet [(a,World)]性は、非決定性とインターリーブを可能にする のようなもので処理できます。

ノーマンは次のように書いています。

@Conal: IO の話は、非決定論とインターリーブにかなりうまく一般化されていると思います。私の記憶が正しければ、"Awkward Squad" の論文にかなり適切な説明があります。しかし、真の並列処理を明確に説明している優れた論文は知りません。

@Norman: どのような意味で一般化しますか? 私は、非決定性と並行性を考慮していないためWorld -> (a,World)、通常与えられる表示モデル/説明が Haskell と一致しないことを示唆しています。IOなど、適合するより複雑なモデルがあるかもしれませんが、そのようなWorld -> PowerSet [(a,World)]モデルが作成され、適切で一貫性があることが示されているかどうかはわかりません。IO個人的には、FFI からインポートされた数千の命令型 API 呼び出しが存在することを考えると、そのような野獣が見つかるとは思えません。そのため、IOその目的を果たしています。

未解決の問題:IOモナドは Haskell の sin-bin になっています。(何かを理解できないときはいつでも、それを IO モナドに放り込みます。)

(Simon PJ の POPL トークからヘア シャツを着る ヘア シャツを着る: Haskell のレトロスペクティブ.)

Tackling the Awkward Squadのセクション 3.1 で、Simon はtype IO a = World -> (a, World)、「同時実行性を追加すると、アプローチがうまくスケーリングしない」など、うまくいかないことを指摘しています。次に、彼は可能な代替モデルを提案し、表示的な説明の試みを放棄し、次のように述べています。

ただし、代わりに、プロセス計算のセマンティクスへの標準的なアプローチに基づいて、運用上のセマンティクスを採用します。

正確で有用な表示モデルを見つけられなかったこの失敗は、私が Haskell IO を精神からの逸脱と見なし、私たちが「関数型プログラミング」と呼んでいるもの、または Peter Landin がより具体的に「表示プログラミング」と名付けたものの深い利点と見なす理由の根底にあります。 . コメントはこちらをご覧ください。

于 2010-05-02T17:14:44.740 に答える
17

関数型プログラミングは、ラムダ計算から派生しています。関数型プログラミングを本当に理解したい場合は、http://worrydream.com/AlligatorEggs/ をチェックしてください。

これは、ラムダ計算を学ぶ「楽しい」方法であり、関数型プログラミングのエキサイティングな世界にあなたを導きます!

ラムダ計算を知ることが関数型プログラミングにどのように役立つか.

そのため、ラムダ計算は、Lisp、Scheme、ML、Haskell など、多くの実世界のプログラミング言語の基盤となっています。

任意の入力に 3 を加算する関数を記述したい場合、次のように記述します。

plus3 x = succ(succ(succ x))

「plus3 は、任意の数値 x に適用されると、x の後続の後続の後続を生成する関数です」を読んでください。</p>

任意の数値に 3 を加算する関数は、plus3 という名前にする必要がないことに注意してください。「plus3」という名前は、この関数に名前を付けるための便利な省略形です。

(plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))

関数にラムダ記号を使用していることに注意してください (ワニの卵のアイデアがどこから来たのか、ワニのように見えると思います)

ラムダ記号はワニ(関数) で、x はその色です。x を引数と考えることもできます (ラムダ計算関数は、実際には 1 つの引数しか持たないと想定されています)。残りは、関数の本体と考えることができます。

ここで抽象化を考えてみましょう:

g ≡ λ f. (f (f (succ 0)))

引数 f は関数の位置 (呼び出し中) で使用されます。入力として別の関数を取るため、ga 高階関数と呼びます。他の関数呼び出し f は「卵」と考えることができます。作成した 2 つの関数または「Alligators」を使用すると、次のようなことができます。

(g plus3) = (λ f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

お気づきの場合は、λ f アリゲーターが λ x アリゲーターを食べ、次に λ x アリゲーターを食べて死ぬことがわかります。そして、私たちの λ x アリゲーターは λ f のアリゲーターの卵で生まれ変わります。次に、プロセスが繰り返され、左側の λ x アリゲーターが右側の別の λ x アリゲーターを食べます。

次に、「アリゲーター」が「アリゲーター」を食べるという単純な一連のルールを使用して文法を設計し、関数型プログラミング言語が誕生しました。

したがって、ラムダ計算を知っていれば、関数型言語がどのように機能するかを理解できることがわかります。

于 2010-05-01T19:36:46.703 に答える
14

Haskell で状態を処理する手法は非常に単純です。また、モナドを理解するためにモナドを理解する必要はありません。

状態を持つプログラミング言語では、通常、何らかの値をどこかに保存し、いくつかのコードを実行してから、新しい値を保存します。命令型言語では、この状態は「バックグラウンド」のどこかにあるだけです。(純粋な) 関数型言語では、これを明示的にするため、状態を変換する関数を明示的に記述します。

したがって、型 X の状態を保持する代わりに、X を X にマップする関数を記述します。状態について考えるのではなく、その状態に対して実行する操作について考えることに切り替えます。次に、これらの関数を連鎖させ、さまざまな方法で組み合わせてプログラム全体を作成できます。もちろん、X から X へのマッピングだけに限定されるわけではありません。関数を記述して、データのさまざまな組み合わせを入力として受け取り、さまざまな組み合わせを最後に返すことができます。

モナドは、これを整理するためのツールの 1 つです。しかし、モナドは実際には問題の解決策ではありません。解決策は、状態ではなく状態変換について考えることです。

これは I/O でも機能します。実際に何が起こるかは次のとおりです: と直接同等のものを使用してユーザーから入力を取得し、scanfそれをどこかに保存する代わりに、 の結果をscanfどうするかを示す関数を作成し、それを渡します。関数を I/O API に追加します。これは、Haskell でモナド>>=を使用するときに行うこととまったく同じです。IOそのため、I/O の結果をどこにも保存する必要はありません。変換方法を示すコードを記述するだけで済みます。

于 2010-05-02T04:57:32.483 に答える
8

(一部の関数型言語は、純粋でない関数を許可します。)

純粋関数型言語の場合、通常、現実世界の相互作用は次のように関数の引数の 1 つとして含まれます。

RealWorld pureScanf(RealWorld world, const char* format, ...);

言語が異なれば、プログラマーから世界を抽象化するための戦略も異なります。たとえば、Haskell はモナドを使用してworld引数を隠します。

しかし、関数型言語自体の純粋な部分はすでにチューリングが完了しています。つまり、C で実行できることは、Haskell でも実行できます。命令型言語との主な違いは、状態を適切に変更するのではなく、次のとおりです。

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

変更部分を関数呼び出しに組み込み、通常はループを再帰に変えます。

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}
于 2010-05-01T19:43:41.607 に答える
3

役に立つかもしれません 、私たちの残りの関数プログラミング

于 2010-05-02T00:04:33.617 に答える
3

関数型言語は状態を保存できます! 彼らは通常、そうすることを明確にすることを奨励または強制するだけです。

たとえば、Haskell のState Monadを調べてください。

于 2010-05-01T19:43:26.660 に答える
1

ハスケル:

main = do no <- readLn
          print (no + 1)

もちろん、関数型言語の変数に代入することもできます。それらを変更することはできません（したがって、基本的にすべての変数は関数型言語の定数です）。

于 2010-05-01T19:37:17.410 に答える