私は言語設計に少し興味があり、現在、自分の趣味の言語で遊んでいます。( http://rogeralsing.com/2010/04/14/playing-with-plastic/ )
私の心を本当に出血させるのは、「ジェネレーター」と「収量」のキーワードです。C# が AST 変換を使用して列挙子メソッドをステートマシンに変換することは知っています。
しかし、他の言語ではどのように機能するのでしょうか? AST 変換のない言語でジェネレーターのサポートを取得する方法はありますか? たとえば、Python や Ruby などの言語は、これを解決するために AST 変換に頼っていますか?
(問題は、ジェネレーターがさまざまな言語で内部でどのように実装されているかであり、それらのいずれかでジェネレーターを記述する方法ではありません)
ジェネレーターは基本的にセミコルーチンであり、いくつかの厄介な制限があります。したがって、明らかに、セミコルーチン (もちろんフルコルーチンも) を使用してそれらを実装できます。
コルーチンがない場合は、他のユニバーサル制御フロー コンストラクトを使用できます。コルーチンを含むすべての制御フロー構造 (他のすべてのユニバーサル制御フロー構造を含む) を含む多くの「ユニバーサル」な制御フロー構造があり、したがってジェネレーターは (多かれ少なかれ) そのユニバーサルのみに自明に変換できます。構築します。
それらの中で最もよく知られているのは、おそらくGOTO. だけで、他の制御フロー構造GOTOを構築できます:IF-THEN-ELSE、WHILE、FOR、REPEAT-UNTIL、FOREACH例外、スレッド、サブルーチン呼び出し、メソッド呼び出し、関数呼び出しなど、そしてもちろんコルーチンとジェネレーターも。
ほとんどすべての CPU がサポートしていますGOTO(ただし、CPU では通常 と呼びますjmp)。実際、多くの CPU ではGOTOが唯一の制御フロー構造ですが、今日では、少なくともサブルーチン呼び出し ( call) のネイティブ サポートと、例外処理のプリミティブ形式や同時実行プリミティブ (比較とスワップ) も通常組み込まれています。 .
もう 1 つのよく知られた制御フロー プリミティブは継続です。GOTO継続は基本的に、特に関数型言語で人気のある、より構造化され、より管理しやすく、悪意の少ない の変種です。しかし、制御フローを継続に基づいた低レベル言語もいくつかあります。たとえば、Parrot Virtual Machine は制御フローに継続を使用しており、どこかの研究室には継続ベースの CPU さえあると思います。
C には一種の「くだらない」形式の継続 ( setjmpand longjmp) がありますが、これは「実際の」継続よりもはるかに強力ではなく、使いにくいものですが、ジェネレーターを実装するのに十分強力です (そして実際には、に使用できます完全な継続を実装します)。
Unix プラットフォームでは、 /setcontextのより強力で高レベルの代替手段として使用できます。setjmplongjmp
よく知られているが、他の制御フロー構造を上に構築する低レベルのサブストレートとしておそらく思い浮かばない別の制御フロー構造は例外です。例外は継続よりも強力である可能性があることを示す論文があり、したがって、例外は本質的に同等でGOTOあり、普遍的に強力です。実際、例外はユニバーサルな制御フロー構造として使用されることもあります。.NET バイトコードを JavaScript にコンパイルした Microsoft Volta プロジェクトは、JavaScript 例外を使用して .NET スレッドとジェネレーターを実装しました。
普遍的ではありませんが、おそらくジェネレーターを実装するのに十分強力なのは、単純な末尾呼び出しの最適化です。(ただし、私は間違っているかもしれません。残念ながら証明がありません。)ジェネレーターを相互末尾再帰関数のセットに変換できると思います。テール コールを使用してステート マシンを実装できることはわかっているので、ジェネレーターも実装できると確信しています。結局のところ、C# はジェネレーターをステート マシンとして実装するからです。(これは遅延評価と組み合わせると特にうまくいくと思います。)
最後になりましたが、具体化されたコール スタックを備えた言語 (たとえば、ほとんどの Smalltalks など) では、必要なほとんどすべての種類の制御フロー構造を構築できます。(実際、具体化された呼び出しスタックは、基本的に、機能的な高レベルの継続と同等の手続き型の低レベルです。)
では、ジェネレーターの他の実装はどのように見えるでしょうか?
Lua 自体にはジェネレーターはありませんが、完全な非対称コルーチンがあります。メインの C 実装はsetjmp/longjmpを使用してそれらを実装します。
また、Ruby にはジェネレーター自体はありませんが、ジェネレーターEnumeratorとして使用できる s があります。Enumerators は言語の一部ではなく、ライブラリの機能です。MRI はEnumerator継続を使用して s を実装し、これはsetjmp/を使用して実装されlongjmpます。YARV はEnumerators を使用してFibers を実装し (これは Ruby が「コルーチン」を綴る方法です)、それらsetjmpは/を使用して実装されlongjmpます。JRuby は現在Enumerator、スレッドを使用して s を実装していると思いますが、JVM がより優れた制御フロー構造を取得したらすぐに、より良いものに切り替えたいと考えています。
Python には、実際には多かれ少なかれ本格的なコルーチンであるジェネレーターがあります。CPython はsetjmp/を使用してそれらを実装しますlongjmp。