Haskell状態モナドの使用はコード臭いですか?
-
03-07-2019 - |
質問
「コード臭」という言葉は嫌いですが、これ以上正確なことは考えられません。
高水準言語を設計しています&コンパイラの構築、言語設計、関数型プログラミングについて学ぶために、暇なときに Whitespace にコンパイラコンパイラはHaskellで記述されています)。
コンパイラのコード生成フェーズでは、構文ツリーを走査するときに「状態」のようなデータを維持する必要があります。たとえば、フロー制御ステートメントをコンパイルする場合、ジャンプするラベルの一意の名前を生成する必要があります(渡され、更新され、&返されたカウンターから生成されたラベル、およびカウンターの古い値は決して使用しないでください) 。別の例として、構文ツリーでインライン文字列リテラルに遭遇した場合、それらを永続的にヒープ変数に変換する必要があります(ホワイトスペースでは、文字列はヒープに最適に格納されます)。現在、これを処理するために状態モナドでコード生成モジュール全体をラップしています。
コンパイラを書くことは機能的なパラダイムに非常に適した問題であると言われましたが、私はこれをCで設計するのとほぼ同じ方法で設計していることがわかります(実際にCを書くことができます言語-Haskell w / stateモナド)
Haskellの構文を使用したCではなく、Haskellで(むしろ、機能的なパラダイムで)考え方を学びたい。本当に状態モナドの使用を排除/最小化しようとするべきですか、それとも合法的な機能的な「設計パターン」ですか?
解決
状態が小さく保たれ、十分に制御されている限り、一般に状態はコードの匂いではないと思います。
これは、State、ST、またはカスタムビルドのようなモナドを使用したり、いくつかの場所に渡した状態データを含むデータ構造を持っているだけでも悪いことではないことを意味します。 (実際には、モナドはまさにこれを行うための支援です!)しかし、あちこちに行き渡る状態(はい、これはあなた、IOモナドを意味します!)は悪臭です。
これのかなり明確な例は、私のチームが ICFPプログラミングコンテスト2009 (コードはgit://git.cynic.net/haskell/icfp-contest-2009で入手できます)。これにより、いくつかの異なるモジュラーパーツが作成されました。
- VM:シミュレーションプログラムを実行した仮想マシン
- コントローラー:シミュレーターの出力を読み取り、新しい制御入力を生成するルーチンのいくつかの異なるセット
- ソリューション:コントローラーの出力に基づいたソリューションファイルの生成
- ビジュアライザー:入力ポートと出力ポートの両方を読み取り、シミュレーションの進行中に何が起こっているかの視覚化またはログを生成するいくつかの異なるルーチンセット
これらはそれぞれ独自の状態を持ち、VMの入力値と出力値を介してさまざまな方法で相互作用します。いくつかの異なるコントローラーとビジュアライザーがあり、それぞれに異なる種類の状態がありました。
ここで重要なのは、特定の状態の内部構造はそれぞれの特定のモジュールに限定され、各モジュールは他のモジュールの状態の存在すら知らないということでした。ステートフルなコードとデータの特定のセットは、通常、数十行の長さで、州内には少数のデータ項目がありました。
これらはすべて、状態の内部にアクセスせず、シミュレーションをループして適切な順序で適切なものを呼び出して通過した約12行の1つの小さな関数に一緒に接着されました各モジュールへの非常に限られた量の外部情報(もちろんモジュールの以前の状態と共に)。
このような限られた方法で状態が使用され、型システムが不注意による変更を防止している場合、処理は非常に簡単です。これを行うことができるのはHaskellの美しさの1つです。
1つの答えは、「モナドを使用しないでください」と言います。私の観点から、これはまったく逆です。モナドは、とりわけ、状態に触れるコードの量を最小限に抑えるのに役立つ制御構造です。モナドパーサーを例として見ると、パーサーで使用されるすべてのコンビネーターを介して、パーシングの状態(つまり、解析中のテキスト、到達したテキスト、蓄積された警告など)を実行する必要があります。 。ただし、実際に状態を直接操作するコンビネーターはわずかです。それ以外は、これらのいくつかの機能のいずれかを使用します。これにより、状態を変更する可能性のある少量のコードをすべて1か所で明確に確認でき、変更方法をより簡単に推論できるようになり、対処が容易になります。
他のヒント
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
抽象化レイヤーの背後に状態モナドが隠されているので、臭いはまったくありません!
属性文法(AG)を見ましたか? ( wikipedia および Monad Readerの記事)
AGを使用すると、属性を構文ツリーに追加できます。これらの属性は、 synthesized および inherited 属性に分けられています。
合成された属性は、構文ツリーから生成(または合成)されたものです。これは、生成されたコード、すべてのコメント、または関心のあるその他のものです。
継承された属性は構文ツリーへの入力です。これは環境、またはコード生成中に使用するラベルのリストです。
ユトレヒト大学では、属性文法システム( UUAGC )でコンパイラを記述します。これは、提供された .ag
ファイルからhaskellコード( .hs
ファイル)を生成するプリプロセッサです。
ただし、まだHaskellを学習しているのであれば、今度はその上に抽象化の別の層を学習し始める時ではないかもしれません。
その場合、属性文法が生成する種類のコードを手動で記述することができます。例:
data AbstractSyntax = Literal Int | Block AbstractSyntax
| Comment String AbstractSyntax
compile :: AbstractSyntax -> [Label] -> (Code, Comments)
compile (Literal x) _ = (generateCode x, [])
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls
in (labelCode l code', comments)
compile (Comment s ast) ls = let (code, comments') = compile ast ls
in (code, s : comments')
generateCode :: Int -> Code
labelCode :: Label -> Code -> Code
ではなく、適用可能なファンクターが必要な場合があります モナド:
http://www.haskell.org/haskellwiki/Applicative_functor
しかし、元の論文はwikiよりもそれをよく説明していると思います:
http://www.soi.city.ac。 uk /〜ross / papers / Applicative.html
State Monadを使用して、状態をモデル化するのに使用されたコード臭いだとは思わない。
関数を通して状態をスレッド化する必要がある場合、 これを明示的に行うことができます。状態を引数として受け取り、各関数でそれを返します。 State Monadは優れた抽象化を提供します:それはあなたのために状態を渡し、 状態を必要とする機能を組み合わせるための便利な機能を多数提供します。 この場合、State Monad(またはApplicatives)を使用することはコードの匂いではありません。
ただし、State Monadを使用して命令型のプログラミングをエミュレートする場合 機能的な解決策で十分ですが、物事を複雑にしているだけです。
一般に、可能な限り状態を回避するように努めるべきですが、それは常に実用的ではありません。 Applicative
は、効果的なコードをより美しく、より機能的に見せます。特にツリー走査コードはこのスタイルの恩恵を受けることができます。名前生成の問題については、かなり良いパッケージが利用可能になりました: value-supply 。
さて、モナドを使用しないでください。関数型プログラミングの力は、関数の純度とその再利用です。私の教授がかつて書いたこの論文があり、彼はHaskellの構築を支援した人物の一人です。
この論文の名前は&quot; なぜ機能的なプログラミングが重要なのか &quot ;、これを一読することをお勧めします。良い読み物です。
ここで用語に注意しましょう。状態自体は悪くありません。関数型言語には状態があります。 「コードのにおい」とは変数値を割り当てて変更したいときです。
もちろん、Haskell状態モナドはまさにその理由で存在します。I/ Oの場合と同様に、制約されたコンテキストで安全で機能しないことを実行できます。
つまり、はい、おそらくコードのにおいです。