Clever Geek Handbook

Nemerleとサテライト、または最小のAF



最近、HabreでNemerleについて頻繁に言及されています。 それが何であり、どのように食べられるのか、むしろそれをどのように食べるのか（パズル）を知りたいですか？



簡単な例を示してみますが、このためには



そもそも



すぐには言わないでください:)



構文などの機能については詳しく説明しません。 -誰でも独自にhttp://www.nemerle.org/およびgoogle詳細で読むことができます 。 要するに、Nemerleは.netプラットフォーム用のハイブリッドプログラミング言語です。 ハイブリッド-命令型OOPと手続き型のプロパティ、Cライクな構文、関数型言語の柔軟性と能力を組み合わせることを意味します。



パラダイムの機能、衛生マクロ、および静的型付けを使用してこの完全にコンパイルされた言語で構文を変更する方法については説明しません。



Nemerleは「気に入らない」変数であり、デフォルトでは 、 if 、 for 、 returnループなど、多くの命令的なものに言語でアクセスできないことは伝えません。 実際には、それらは言語そのものではありません-すべてが特別なストリートマクロによって実装されています。



最後に、驚異的な細心の規則を備えたNemerleがオブジェクトタイプを推測できるという事実については語りません。



一般に、これは悪い記事になります。Nemerlefenkiを使用して機能的パラダイムの問題を美しく解決する方法を説明するだけだからです。 まあ、 タスクは私たちの言語に似ています-最近のicfp2009コンテストから。 むしろ、その一部-機能的なスタイルでOrmeral VMをNemerle上に記述します。



上記の行がほとんどまたはほとんど何も言っていない人のために、コンテストの仕様へのリンクを提供し、ポイントが何であるかを以下に簡単に説明します。



以前のコンテスト（2008年）では、JRE、gcc、ghc（Haskell）、CLOS（Lisp）、Pythonなど、誰も気分を害さないようにソリューションを起動するためのテスト場として、さまざまな「バッテリー」を備えたLiveCD Knoppixを使用しました。 実践では、浮動小数点の操作の違いにより、すべての言語で同じ結果が得られるわけではなく、控えめに言っても一定の難しさが生じることが示されています。 そのため、今年（2009年）に、主催者はVMに関する明確な仕様を公開しました。これにより、問題の解決策をもたらすことができます。



4つのオプションを持つ4つのタスクグループ（初期条件が異なるタスクグループ内、グループ間-目標）があり、タスクグループごとに、OVMのバイトコードとデータメモリの初期状態を含むバイナリコードが提供されました。 プログラムをOVMにロードした後、マシンの特別な入力ポートに数値（1000 + Nオプション）を設定してプログラムを構成し、1クロックサイクルをオフにする必要がありました。 そして、フライトへ。



私は自分の言葉で始めました-全体としてのタスクは、センサーの読み取り値を読み取り、衛星のサーボモーターを制御することで「曲技飛行」を読み取ることでした。 他の誰かの衛星を追いつき追い越し、資本主義の深byに転がり込むなど すべてのOVM命令の1回の実行は、シミュレーション時間（simsek）の1秒に相当しました。



チームからのソリューションログ（つまり、時間に関するサーボモーターの一連のコマンド）のみが必要だったため、原則として、タスクは「頭の中で」のみ解決できました。 しかし、厳しい現実が示したように、勝利チームはすべてVMを使用して結果をデバッグしました。 （さらに、例外なくすべてのチームがVMを使用したようですが、一部のチームは独自のVMを使用していませんでした:)）。



さまざまなチームの不運、および誰かから車を「引っ張った」人の詳細については、まだわからない場合はこちらを参照してください。



実装します。



ビジネス向け



仕様を読んだ後、この非常にOrbital VM（OVM）を一般的に想像できます：16Kのデータメモリ空間と、I / Oポート用の個別の16Kアドレス空間（IとOに別々）を持つレジスタマシン。

手がスクラッチし、サイクルでプログラムカウンターが増加するサイクルをスケッチします。プログラムカウンターからプログラムカウンターによって読み取られた結果は、ビット操作を使用して解析され、巨大なスイッチに送られます。



すべて正しいです。 それは可能ですか？ はい しかし、私は急いではならず、FP-Taoの道をたどり、上から下に設計することをお勧めします:)



したがって、時刻T 0でのOVMの状態を考慮してください。 1つの指示に従うと、マシンの状態が変わります。 したがって、この目的のための1つのOVM命令は、入力時-マシンSの状態、出力S *での関数と見なすことができます。



S n + 1 = INSTR n （S n ）;



小さな結果-各命令が新しい状態を返す場合、これは、ストーリーを保持するためにタイムスタンプ付きの別のリストに保存できることを意味します。 些細なことだが、いい



したがって、OVMのプログラム全体は命令のストリームであり、クロージャー関数のリストで表されます。 プログラムを実行するには、リストの最初の関数から順番にすべての関数を順番に呼び出し、前の関数が返した次の各状態に渡す必要があります。 最初の関数では、初期状態S 0を渡します 。 数学的に言えば、左（文字通りの意味）の畳み込み（左折り）を実行します。



だから、コードに近い。 ネメルルで、その上で、ダーリン。 私は簡単ですが、説明をします。



タイプエイリアスを定義します。

type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .



  1. type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .



  2. type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .



type INSTR = OVMState -> OVMState; type PROGRAMM = list [INSTR] * OVMState; * This source code was highlighted with Source Code Highlighter .





INSTRは、OVM状態を受け入れてOVMを返す関数を定義するタイプです。

PROGRAMM-OVM用のプログラム。 命令のリスト（これはコマンドのストリームです）と初期状態で構成されるタプル。 構文「*」は、これら2つのタイプを連結してタプルにする必要があることを示しています。



メイン関数は簡単に笑えます：





  1. メイン（）： void {
  2. def （命令、initialState）= load_program（ "bin1.obf" ）; //例外
  4. //設定します
  5. vmi_set_problem（1001、initialState）;
  6. def state = exec_one_cycle（instructions、initialState）; //例外
  7. vmi_set_problem（0000、状態）;
  9. //すべてのデータを読み取ることができるため
  10. Console .WriteLine（ "x = {0}、fue​​l = {1}" 、
  11. vmi_get_x（状態）、vmi_get_fuel（状態））;
  12. }
*このソースコードは、 ソースコードハイライターで強調表示されました。


最初の行（defは）で、PROGRAMMタプルはストリームと初期状態に分割されます。初期状態は、バイナリファイルからプログラムのロードプロシージャによって返されます。

次に、バリアント番号（1001）を設定し、1クロックサイクルを実行し、バリアントレジスタをクリアし（必要に応じて）、画面に初期状態を表示します（vmi_set_problemはプログラムに問題を引き起こしませんが、反対に、構成ポートに目的の値を設定します）



1秒のシミュレーション時間を実行する関数は、次のように見えることに同意しました。





  1. exec_one_cycle（プログラム： リスト [INSTR]、fromState：OVMState）：OVMState {
  2. リスト .FoldLeft（
  3. プログラム、 // <-誰？
  4. fromState、 // <-なぜ？ （どこから？）
  5. fun （命令：INSTR、currState：OVMState）{ //クライアントは各命令を実行します
  6. 命令（currState）
  7. }
  8. ）
  9. }
*このソースコードは、 ソースコードハイライターで強調表示されました。


同意したとおり、左側で畳み込みを行います。 FoldLeftは、Nemerleの標準リストライブラリメソッドです。

ここでの5行目の楽しみは、私が特に楽しいと感じたからではなく、匿名関数を「その場で」定義するNemerle言語の構築です。 原則として、デリゲート構文を使用できますが、より視覚的です。 軽く。

戻り値がないことに注意してください-実際、Nemerleでは、最後の式が関数から返される値になります。



ところで、funはNemerleライブラリのマクロでもあります。 関数を定義してすぐに返すことができます



点灯していないが重要なOVMState構造は残りました。 カバーをはがします。





  1. クラス OVMState
  2. {
  3. public MEM：array [ double ] = array（16384）;
  4. public OUTS：array [ double ] = array（16384）;
  5. public INS：array [ double ] = array（16384）;
  6. public mutable STATUS： bool = false ;
  7. }
*このソースコードは、 ソースコードハイライターで強調表示されました。


魔法はありません。 ワンポイント-Nemerleで変数を使用する場合は、これを明示的に指定する必要があります（可変）。 デフォルトでは、すべては罪から離れた読み取り専用です。



私たちは何を残しましたか？ 答えは、プログラムをロードし、バイトコードを関数のリスト（または、各命令の特定のデータで開始されるクロージャー）に変換することです。 あなたはすでに何が次に起こるか理解していると思います。





  1. load_program（ファイル： string ）：PROGRAMM {
  3. //多くのbukafは、ほとんど意味を損なうことなく、省略されています
  5. //やる
  6. using （stream = File .OpenRead（file））{
  7. def frames = read_frames（ストリーム）;
  8. （load_instructions（フレーム）、load_state（フレーム））
  9. }
  10. }
*このソースコードは、 ソースコードハイライターで強調表示されました。


入力ファイル（仕様ではフレームに分割されていると言われています）はフレームごとに読み取られ、デコードされます。 2種類のバイトコード（SとD）などの存在について詳しく説明しない場合、たとえばDのデコーダーは次のようになります。





  1. /// dタイプの命令をデコードします
  2. def decode_d_type（addr： int 、opcode：DOpCodes、r1： int 、r2： int ）：INSTR {
  3. match （opcode）{
  4. | DOpCodes.Add => make_add（addr、r1、r2）;
  5. | DOpCodes.Sub => make_sub（addr、r1、r2）;
  6. | DOpCodes.Mult => make_mult（addr、r1、r2）;
  7. | DOpCodes.Div => make_div（addr、r1、r2）;
  8. | DOpCodes.Phi => make_phi（addr、r1、r2）;
  9. | DOpCodes.Output => make_out（r1、r2）;
  10. | _ => throw InvalidOperationException（）; //例外
  11. }
  12. }
*このソースコードは、 ソースコードハイライターで強調表示されました。


S命令の場合-同様に。 matchはパターンマッチング操作であり、強力な機能を備えた一種の高度なスイッチです。



最後の仕上げ-実際、クロージャーコンストラクター自体は「make_bla_bla」です。 たとえば、addステートメントの「作成者」は乗算です。





  1. make_add（addr： int 、r1： int 、r2： int ）：INSTR {
  2. fun （s）{
  3. s.MEM [アドレス] = s.MEM [r1] + s.MEM [r2];
  4. s
  5. }
  6. }
*このソースコードは、 ソースコードハイライターで強調表示されました。


つまり 2つのオペランドの加算を実行できるクロージャーを作成し、新しく出現した命令を返します。 関数のタイプを示していることに注意してください。これは必要ではありません-Nemerleはそれらを単独で表示します。



おやつに



ある程度のサービスコードを見逃しましたが、アイデアが明確であることを願っています。OOPの庭よりも単純なタスクでより簡単で理解しやすい手順で上から下に設計します。 NemerleのAFを使用したハイブリッドOOPはこれに貢献し、タスクに集中できるようにします。



このOVMを使用して衛星を操縦したい人は、次のヒントを使用できます。

-icfp2009の煙仕様

-OVMをクラスとして設計し、たとえばCSharpのプロジェクトに接続し、その中に管理戦略を記述します。



この記事と残りのすべてのコードは、与えられていませんが、必要とされるため、pastebin.org から入手できます 。 標準的なラップトップ（Core2Duo 2GHz）の発射速度は、毎秒30,000シミュレーション秒（sims / s）です。 制御アルゴリズムを快適に実行することはかなり可能です。



PSどういうわけか。 いいフライトを。 軌道からの電信、それなら:)



PPS私はほとんど忘れていません。 C＃で実現された直接VM（サンプリング+各ステップでの命令のデコード）に対する関心-約24000 simsek /秒が出ました。 残念ながら、これはNemerleがそれほど高速（20％高速）であるという意味ではありません。C＃では、デコーダで使用されるビットの操作が最適化されていることを意味します。


More articles:


All Articles