62

「コードの匂い」という言葉は嫌いですが、これ以上正確なものは思いつきません。

コンパイラの構築、言語設計、関数型プログラミング (コンパイラは Haskell で書かれています) について学ぶために、空き時間にWhitespaceに高水準言語とコンパイラを設計しています。

コンパイラのコード生成フェーズでは、構文ツリーをたどる際に「状態」のようなデータを維持する必要があります。たとえば、フロー制御ステートメントをコンパイルするとき、ジャンプ先のラベルに一意の名前を生成する必要があります (ラベルは、渡され、更新され、返されたカウンターから生成され、カウンターの古い値を二度と使用してはなりません)。もう 1 つの例は、構文ツリーでインライン文字列リテラルに遭遇した場合です。それらはヒープ変数に永続的に変換する必要があります (ホワイトスペースでは、文字列はヒープに格納するのが最適です)。現在、これを処理するためにコード生成モジュール全体を状態モナドにラップしています。

コンパイラを書くことは関数型パラダイムに適した問題だと言われたことがありますが、私はこれを C で設計するのとほぼ同じ方法で設計していることに気付きました (C は実際にはどの言語でも書くことができます。 Haskell と状態モナド)。

Haskell 構文を使用した C ではなく、Haskell で (むしろ関数型パラダイムで) 考える方法を学びたいです。状態モナドの使用を本当に排除/最小化しようとするべきですか、それとも正当な機能的な「設計パターン」ですか?

4

8 に答える 8

47

私はHaskellで複数のコンパイラーを作成しましたが、状態モナドは多くのコンパイラーの問題に対する合理的な解決策です。しかし、あなたはそれを抽象的に保ちたいです---あなたがモナドを使用していることを明らかにしないでください。

これは、Glasgow Haskellコンパイラ（私は作成していません。いくつかのエッジを回避するだけです）の例です。ここでは、制御フローグラフを作成します。グラフを作成する基本的な方法は次のとおりです。

empyGraph    :: Graph
mkLabel      :: Label -> Graph
mkAssignment :: Assignment -> Graph  -- modify a register or memory
mkTransfer   :: ControlTransfer -> Graph   -- any control transfer
(<*>)        :: Graph -> Graph -> Graph

しかし、ご存知のように、一意のラベルの供給を維持するのはせいぜい面倒なので、次の機能も提供します。

withFreshLabel :: (Label -> Graph) -> Graph
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition
             -> Graph   -- code in the 'then' branch
             -> Graph   -- code in the 'else' branch 
             -> Graph   -- resulting if-then-else construct

全体Graphが抽象型であり、翻訳者は、モナディックが起こっていることに気付かずに、純粋関数型の方法でグラフを楽しく作成します。次に、グラフが最終的に作成されたら、コードを生成できる代数的データ型に変換するために、一意のラベルを提供し、状態モナドを実行して、データ構造を引き出します。

州のモナドはその下に隠されています。クライアントには公開されていませんが、の定義Graphは次のようになります。

type Graph = RealGraph -> [Label] -> (RealGraph, [Label])

またはもう少し正確に

type Graph = RealGraph -> State [Label] RealGraph
  -- a Graph is a monadic function from a successor RealGraph to a new RealGraph

抽象化レイヤーの背後に州のモナドが隠されているので、臭いはまったくありません！

于 2009-03-04T04:23:24.473 に答える
43

一般的に状態はコードのにおいではないと思いますが、それが小さく保たれ、適切に制御されている限りはそうです。

これは、State、ST、またはカスタムビルドのモナドを使用すること、またはいくつかの場所に渡す状態データを含むデータ構造を持つことは悪いことではないことを意味します。(実際には、モナドはまさにこれを行うための補助にすぎません!) しかし、いたるところに行き渡る状態 (はい、これはあなた、IO モナドを意味します!) は悪臭です。

これのかなり明確な例は、私のチームがICFP プログラミング コンテスト 2009のエントリに取り組んでいたときです (コードは git://git.cynic.net/haskell/icfp-contest-2009 で入手できます)。最終的に、これにいくつかの異なるモジュラー パーツができました。

  • VM: シミュレーション プログラムを実行した仮想マシン
  • コントローラー: シミュレーターの出力を読み取り、新しい制御入力を生成するいくつかの異なるルーチンのセット
  • ソリューション: コントローラーの出力に基づくソリューション ファイルの生成
  • ビジュアライザー: 入力ポートと出力ポートの両方を読み取り、シミュレーションの進行に伴って何が起こっているかの何らかの視覚化またはログを生成する、いくつかの異なるルーチン セット

これらにはそれぞれ独自の状態があり、VM の入力値と出力値を介してさまざまな方法で相互作用します。いくつかの異なるコントローラーとビジュアライザーがあり、それぞれが独自の異なる種類の状態を持っていました。

ここでの重要な点は、特定の状態の内部はそれ自体の特定のモジュールに限定されており、各モジュールは他のモジュールの状態の存在についてさえ何も知らないということでした。ステートフルなコードとデータの特定のセットは通常、数十行の長さで、状態には少数のデータ項目が含まれていました。

これはすべて、どの状態の内部にもアクセスできず、シミュレーションをループして非常に限定された関数を渡すときに、適切なものを適切な順序で呼び出すだけの、約 12 行の 1 つの小さな関数にまとめられました。各モジュールへの外部情報の量 (もちろん、モジュールの以前の状態とともに)。

状態がこのように限定された方法で使用され、型システムが誤ってそれを変更するのを防いでいる場合、扱いは非常に簡単です。これを実現できるのは、Haskell の優れた点の 1 つです。

1つの答えは、「モナドを使わないでください」と言います。私の観点からすると、これは完全に逆です。モナドは、とりわけ、状態に影響を与えるコードの量を最小限に抑えるのに役立つ制御構造です。例としてモナドパーサーを見ると、パーサーで使用されるすべてのコンビネーターを介して、解析の状態 (つまり、解析されているテキスト、どこまで到達したか、蓄積された警告など) を実行する必要があります。 . しかし、実際に状態を直接操作するコンビネータはわずかしかありません。それ以外は、これらのいくつかの関数のいずれかを使用します。これにより、状態を変更できる少量のコードをすべて 1 か所で明確に確認できるようになり、状態を変更する方法をより簡単に判断できるようになり、対処が容易になります。

于 2009-06-30T07:10:14.157 に答える
3

モナドの代わりにアプリカティブ ファンクターが必要になる可能性があります。

http://www.haskell.org/haskellwiki/Applicative_functor

ただし、元の論文はwikiよりもよく説明していると思います。

http://www.soi.city.ac.uk/~ross/papers/Applicative.html

于 2009-03-04T11:56:30.017 に答える
-5

まあ、モナドを使わないでください。関数型プログラミングの力は、関数の純度とその再利用です。私の教授がかつて書いたこの論文があり、彼は Haskell の構築を支援した人物の 1 人です。

この論文は「なぜ関数型プログラミングが重要なのか」と呼ばれています。一読することをお勧めします。よく読んでいます。

于 2009-03-03T20:12:59.223 に答える
-13

ここでは用語に注意しましょう。状態自体は悪くありません。関数型言語には状態があります。「コードのにおい」とは、変数に値を割り当てて変更したい場合です。

もちろん、Haskell の状態モナドが存在するのはまさにそのためです。I/O と同様に、制約のあるコンテキストで危険で機能しないことを実行できるようにします。

だから、はい、それはおそらくコードの匂いです。

于 2009-03-03T20:14:13.573 に答える