30

ループを再帰に置き換えるというアイデアに慣れてきました。私はペット プロジェクトをいじっていて、いくつかのテキスト入力機能をテストしたかったので、特定の終了コマンドを受け取るまで繰り返し入力を求める小さなコマンド ライン インターフェイスを作成しました。

次のようになります。

getCommandsFromUser = do
    putStrLn "Enter command: "
    keyboardInput <- getLine
    let command = map toLower keyboardInput
    if command == "quit"
        then 
            putStrLn "Good-bye!"
        else do
            -- stuff
            -- more stuff
            putStrLn ("Sending command: " ++ commandURI)
            simpleHTTP $ getRequest commandURI
            getCommandsFromUser

main = do
    getCommandsFromUser

これは期待どおりに機能しますが、C/Java のバックグラウンドから来ているため、脳の深く暗い無意識の部分をまだくすぐり、蕁麻疹が出たくなるのです。getCommandsFromUser作成中は、新しいスタック フレームを作成しています。

さて、IO、モナド、状態、矢印などについてはまだ何も知りません。私はまだ実世界の Haskell に取り組んでいますが、まだその部分には到達していません。このコードの一部は、Google で見つけたものと一致するパターンです。

さらに、GHC の要点は、尾部再帰関数の美しい展開などの信じられないほどのことを行うように設計された、狂ったように最適化するコンパイラであるということです。

誰かがこの実装が「正しい」かどうかを説明できますか?もしそうなら、このプログラムが無数のサルの手に渡った場合に、このプログラムが爆発するのを防ぐ舞台裏で何が起こっているのかを説明してもらえますか?

テールコールの最適化とは何かを知っています。この場合、それがどのように機能するか、アクションと一般的な機能的不純物がどうなっているのかについてもっと心配しています.

この質問は、Haskell がスタックをどのように使用しているかについて混乱していたという考えに基づいているわけではなく、命令型言語のように機能することを期待していました。それは、Haskell がスタックをどのように処理するかを知らなかったという事実に基づいており、従来の C ライクな言語とはどう違うのかを知りたいと思っていました。

4

4 に答える 4

40

スタックについてはあまり心配しないでください。スタック フレームを使用して関数呼び出しを実装する必要があるという基本的なことは何もありません。これは、それらを実装するための 1 つの可能な手法にすぎません。

「スタック」を持っている場合でも、スタックを使用可能なメモリのごく一部に制限する必要があると言うものは何もありません。これは基本的に、命令型プログラミングに合わせて調整されたヒューリスティックです。問題解決手法として再帰を使用しない場合、無限再帰のバグが原因でコール スタックが非常に深くなる傾向があり、スタック サイズを非常に小さいものに制限すると、そのようなプログラムは、使用可能なすべてのメモリとスワップを消費する代わりに、すぐに終了します。死んでいる。

関数型プログラマーにとって、コンピューターがまだギガバイトの RAM を使用できる場合に、より多くの関数呼び出しを行うためにメモリを「使い果たし」、プログラムを終了させることは、言語設計のばかげた欠陥です。これは、ループを任意の反復回数に制限する C のようなものです。したがって、関数型言語がスタックを使用して関数呼び出しを実装している場合でも、可能であれば C で知られている標準の小さなスタックの使用を避けたいという強い動機があります。

実際、Haskell にはオーバーフローする可能性のあるスタックがありますが、それは C でおなじみのコール スタックではありません。呼び出し深度の制限。Haskell が持っているスタックは、決定を下すためにもう少し評価する必要がある「保留中」の値を追跡するために使用されます (これについては後で詳しく説明します)。この種のスタック オーバーフローの詳細については、こちらを参照してください。

例を見て、コードがどのように評価されるかを見てみましょう。1ただし、あなたの例よりもさらに単純な例を使用します。

main = do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

Haskell の評価は遅延2です。簡単に言えば、それは、決定を下すためにその項の値が必要な場合にのみ項を評価することを意味します。たとえば、計算してその結果をリストの先頭に追加すると、リスト31 + 1に「保留中」として残すことができます。しかし、結果が 3 に等しいかどうかをテストするために使用すると、 Haskell は に変換する作業を実際に行う必要があります。1 + 1if1 + 12

しかし、それだけでは何も起こりません。プログラム全体が「保留中」の値として残されます。mainしかし、それを実行するために、IO アクションが何に評価されるかを知る必要がある外部ドライバーがあります。

例に戻ります。そのブロックmainと同じです。doの場合IO、doブロックは一連の小さなアクションから大きなIOアクションを作成し、順番に実行する必要があります。そのため、Haskell ランタイムは、まだ必要ではない未評価のものが続くとmain評価します。input <- getLineキーボードから読み取り、結果を呼び出す方法を知っていれば十分String inputです。「foo」と入力したとします。これにより、Haskell は「次の」IOアクションとして次のようなものを残します。

if "foo" == "quit"
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

Haskell は最も外側のものだけを見ているので、これはほとんど「もし何とか何とか何とか...」のように見えます。ifIO-executor が何かを実行できるものではないため、何を返すかを確認するために評価する必要があります。ifどちらかthenのelseブランチに評価されるだけですが、条件を評価するには Haskell がどちらの決定を下す必要があるかを知る必要があります。したがって、次のようになります。

if False
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

これにより、全体ifを次のように縮小できます。

do
    putStrLn $ "You typed: " ++ "foo"
    main

そして再び、順序付けられた一連のサブアクションからなるアクションがdo得られます。IOしたがって、IO-executor が次にしなければならないことは、putStrLn $ "You typed: " ++ "foo". しかし、それもIOアクションではありません (結果が 1 になるはずの未評価の計算です)。ですから、それを評価する必要があります。

の「最も外側」の部分は、putStrLn $ "You typed: " ++ "foo"実際には$です。Haskell ランタイムと同じように表示できるように、中置演算子の構文を削除すると、次のようになります。

($) putStrLn ((++) "You typed: " "foo")

しかし、$によって定義されたばかりの演算子な($) f x = f xので、右辺を代入するとすぐに次のようになります。

putStrLn ((++) "You typed: " "foo")`

通常、これは の定義に代入して評価しますがputStrLn、これは Haskell コードで直接表現できない「魔法の」プリミティブ関数です。したがって、実際にはこのように評価されません。外側の IO-executor は、それをどう処理するかを単純に知っています。ただし、 の引数を完全に評価する必要があるputStrLnため、そのままにしておくことはできません(++) "You typed: " "foo"。

実際には、その式を完全に評価するには++、リスト操作の観点から の定義を行う多くのステップがありますが、それを飛ばして、 に評価されるとしましょう"You typed: foo"。そのため、IO-executor は (テキストをコンソールに書き込む) を実行し、ブロックputStrLnの 2 番目の部分に進むことができます。do

`main`

これは、アクションとしてすぐに実行できるものではありませんIO(Haskell のように組み込まれていませputStrLnんgetLine) main。

do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

そして、残りがどこに向かっているのかを見ることができると確信しています。

どの種類のスタックについても何も述べていないことに注意してください。IOこれらはすべて、アクションを記述するデータ構造を構築しているだけなmainので、外部ドライバーはそれを実行できます。特に特別なデータ構造ではありません。評価システムの観点からは、他のデータ構造とまったく同じであり、そのサイズに恣意的な制限はありません。

この場合、遅延評価は、このデータ構造の生成がその消費とインターリーブされることを意味します (そして、その後の部分の生成は、その前の部分を消費した結果として何が起こったかに依存する可能性があります!)、したがって、このプログラムは実行できます一定量のスペース。しかし、質問に対するshachafのコメントで指摘されているように、これは不要なスタックフレームを削除するための最適化ではありません。それは、遅延評価で自動的に起こることです。

それで、何が起こっているのかを理解するのに十分に役立つことを願っています. 基本的に、Haskell が への再帰呼び出しを評価するまでgetCommandsFromUserには、前の繰り返しで生成されたすべてのデータが既に処理されているため、ガベージ コレクションが行われます。したがって、一定量以上のメモリを必要とせずに、このプログラムを無期限に実行し続けることができます。これは単に遅延評価の単純な結果であり、IOが関係していても実質的に違いはありません。

1現在の Haskell の実際の実装については詳しく知らないことを前もってお断りしておきます。しかし、私はHaskellのような怠惰な純粋言語を実装するための一般的なテクニックを知っています. また、詳細に飛び込みすぎないようにして、物事がどのように機能するかを直感的に説明するだけにします。したがって、この説明は、コンピューター内で実際に何が起こっているかについての詳細の一部が間違っている可能性がありますが、これらのことがどのように機能するかを示しているはずです.

2言語仕様では、技術的には、評価は「非厳密」であるべきだと言っているだけです。これから説明する評価は、非公式に「怠惰な」評価として知られていますが、実際には可能な「非厳密な」評価戦略の 1 つにすぎませんが、実際に得られるものです。

3(1 + 1) : originalListそして、新しいリストは実際には、それが空かどうかを誰かが知る必要があるまで、「保留中」の結果として残すことができます。

于 2012-12-09T12:31:52.813 に答える
9

この実装は正しいです。

テールコールの最適化が、これを効率的に機能させるのに本当に役立つとは思いません。代わりに、それが効率的に機能することを可能にするのは、信じられないかもしれませんが、IO アクションの不変性です。IO アクションが不変であることに驚きましたか? 私は最初でした！つまりgetCommandsFromUser、「やるべきこと」のレシピです。評価するたびに、同じレシピgetCommandsFromUserに評価されます。(もちろん、レシピに従うたびに同じ結果が得られるわけではありません! しかし、それは完全に実行の別の段階です.)

この結果、 のすべての評価をgetCommandsFromUser共有できるようになります。GHC はレシピのコピーを 1 つメモリに保持するだけで、そのレシピの一部にはレシピの先頭に戻るポインタが含まれます。

于 2012-12-09T01:41:24.760 に答える
4

私が理解しているように、TCO については忘れてください。再帰呼び出しが末尾の位置にあるかどうかを尋ねる代わりに、保護された再帰の観点から考えてください。この答えは正しいと思います。また、常に興味深く挑戦的なブログ「Neighborhood of Infinity」のData と Codataに関する投稿もご覧ください。最後にSpace Leak Zooをチェックしてください。

編集: 申し訳ありませんが、上記はモナド アクションに関するあなたの質問に直接対応していません。特にIOモナドに対処するDanielWagnerのような他の回答を見ることに興味があります。

于 2012-12-09T01:41:59.797 に答える
1

IO が関係していることは問題ではありません。Haskell wikiでそれについて読むことができます：

内部のIO

または、Haskell の IO をより深く体験するには:

厄介なチームへの取り組み: Haskell でのモナド入出力、同時実行性、例外、および外国語呼び出し

于 2012-12-09T10:55:26.317 に答える