3

私がやっていること:ファイルを解析し、それを一連の操作に変換し、数千のデータセットをそのシーケンスにフィードして、それぞれから最終的な値を抽出できる小さなインタープリターシステムを作成しています。コンパイル済みインタープリターは、データセットと実行コンテキストの 2 つの引数を取る純粋な関数のリストで構成されます。各関数は、変更された実行コンテキストを返します。

type ('data, 'context) interpreter = ('data -> 'context -> 'context) list

コンパイラは基本的に、次のように定義されたマップ記述を使用する最終的なトークンから命令へのマッピング ステップを備えたトークナイザーです。

type ('data, 'context) map = (string * ('data -> 'context -> 'context)) list

一般的なインタープリターの使用法は次のようになります。

let pocket_calc = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  Interpreter.parse map "path/to/file.txt"

let new_context = Interpreter.run pocket_calc data old_context

問題:、、メソッド、および対応する型 (あるコンテキスト クラスでは整数、別のコンテキスト クラスでは浮動小数点数など)pocket_calcをサポートする任意のクラスでインタープリターを動作させたいと考えています。addsubmuldata

ただし、pocket_calcは関数ではなく値として定義されているため、型システムはその型をジェネリックにしません。最初に使用すると、'dataと'context型は最初に提供したデータとコンテキストの型にバインドされ、インタープリターは次のようになります。他のデータおよびコンテキスト タイプとは永遠に互換性がありません。

実行可能な解決策は、インタープリターの定義を eta-expand して、その型パラメーターをジェネリックにできるようにすることです。

let pocket_calc data context = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  let interpreter = Interpreter.parse map "path/to/file.txt" in
  Interpreter.run interpreter data context

ただし、この解決策はいくつかの理由で受け入れられません。

  • 呼び出されるたびにインタープリターを再コンパイルするため、パフォーマンスが大幅に低下します。マッピング ステップ (マップ リストを使用してトークン リストをインタープリターに変換する) でさえ、顕著な速度低下を引き起こします。

  • 私の設計は、初期化時に読み込まれるすべてのインタープリターに依存しています。これは、読み込まれたファイルのトークンがマップ リストの行と一致しない場合にコンパイラが警告を発行するためです。インタプリタは最終的に実行されます)。

  • 特定のマップ リストを複数のインタープリターで再利用したい場合があります。単独で使用する場合もあれば、追加の命令 (たとえば"div") を先頭に追加する場合もあります。

質問: eta-expansion 以外に型をパラメトリックにする方法はありますか? モジュールの署名や継承に関係する巧妙なトリックでしょうか? それが不可能な場合、eta-expansion を受け入れられる解決策にするために、上記の 3 つの問題を軽減する方法はありますか? ありがとうございました！

4

2 に答える 2

4

実行可能な解決策は、インタープリターの定義をeta-expandして、その型パラメーターを汎用にできるようにすることです。

 let pocket_calc data context = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   Interpreter.run interpreter data context

ただし、このソリューションはいくつかの理由で受け入れられません。

  • 呼び出されるたびにインタプリタを再コンパイルするため、パフォーマンスが大幅に低下します。マッピングステップ（マップリストを使用してトークンリストをインタープリターに変換する）でさえ、顕著な速度低下を引き起こします。

あなたがそれを間違っているので、それは毎回インタプリタを再コンパイルします。適切な形式はもっとこのようなものです（そして技術的には、toの部分的な解釈がInterpreter.runいくつinterpreterかの計算を行うことができる場合は、それも外に移動する必要がありfunます）。

 let pocket_calc = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   fun data context -> Interpreter.run interpreter data context
于 2010-10-25T11:41:39.527 に答える
3

あなたの問題は、固定データ型を表す型パラメーターを持つ代わりに、閉じたパラメトリック型 (次の算術プリミティブをサポートするすべてのデータに対して機能する) を使用したい操作にポリモーフィズムがないことにあると思います。ただし、コードはテストするのに十分な自己完結型ではないため、これが正確であることを確認するのは少し困難です。

プリミティブの指定されたタイプを想定すると、次のようになります。

type 'a primitives = <
  add : 'a -> 'a;
  mul : 'a -> 'a; 
  sub : 'a -> 'a;
>

構造体とオブジェクトによって提供される一次ポリモーフィズムを使用できます。

type op = { op : 'a . 'a -> 'a primitives -> 'a }

let map = [ "add", { op = fun d c -> c # add d } ;
            "sub", { op = fun d c -> c # sub d } ;
            "mul", { op = fun d c -> c # mul d } ];;

次のデータに依存しない型が返されます。

 val map : (string * op) list

編集:さまざまな操作タイプに関するコメントについては、どのレベルの柔軟性が必要かわかりません。同じリスト内の異なるプリミティブに対する操作を混在させて、それぞれの特異性から利益を得ることはできないと思います: せいぜい、「add/sub/mul に対する操作」を「add/ に対する操作」に変換することしかできませんでした。 sub/mul/div" (プリミティブ型で反変であるため) ですが、確かにそれほど多くはありません。

より実用的なレベルでは、その設計では、プリミティブ タイプごとに異なる「操作」タイプが必要であることは事実です。ただし、プリミティブ型によってパラメーター化され、操作型を返すファンクターを簡単に構築できます。

異なるプリミティブ型間の直接的なサブタイプ関係をどのように公開するかはわかりません。問題は、これにはファンクタ レベルでサブタイプ関係が必要になることです。これは、Caml にはないと思います。ただし、単純な形式の明示的なサブタイピング (キャストの代わりにa :> bfunction を使用a -> b) を使用して、プリミティブ型から別の型へのマップが与えられると、1 つの操作型からもう一方。

進化したタイプの異なる巧妙な表現により、はるかに単純なソリューションが可能になる可能性は十分にあります。3.12 のファースト クラス モジュールも使用される可能性がありますが、それらはファースト クラスの存在型に役立つ傾向がありますが、ここではユニバーサル型を使用したくありません。

解釈上のオーバーヘッドと操作の具体化

あなたのローカルタイピングの問題に加えて、あなたが正しい方向に向かっているかどうかはわかりません。「事前に」（操作を使用する前に）、操作の言語表現に対応するクロージャーを構築することにより、解釈のオーバーヘッドを排除しようとしています。

私の経験では、このアプローチでは通常、解釈のオーバーヘッドが取り除かれず、別のレイヤーに移動されます。単純にクロージャーを作成すると、クロージャー層で再現された制御の解析フローが得られます。クロージャーの作成時に解析コードが入力を「解釈」したため、クロージャーは他のクロージャーなどを呼び出します。解析のコストを排除しましたが、最適ではない可能性のある制御フローは同じです。さらに、クロージャーは直接操作するのが面倒になる傾向があります。たとえば、シリアライゼーションなどの比較操作には十分注意する必要があります。

長期的には、操作を表す中間の「具体化された」言語に興味があると思います。テキスト表現から構築する、算術演算用の単純な代数データ型です。メモリ内の表現がまともであれば、パフォーマンスが直接解釈するよりもはるかに優れているかどうかはわかりませんが、それから「事前に」クロージャーを構築しようとすることはできます。さらに、中間アナライザー/トランスフォーマーをプラグインして操作を最適化することがはるかに簡単になります。たとえば、「連想バイナリ操作」モデルから「n-ary 操作」モデルに移行すると、より効率的に評価できます。

于 2010-10-25T10:03:17.650 に答える