メタ循環評価者

コンピューティングにおいて、メタ循環評価器( MCE ) またはメタ循環インタープリタ( MCI ) は、インタープリタのホスト言語と同様の機能を使用して、インタープリタ対象言語の各機能を定義するインタープリタです。たとえば、ラムダアプリケーションの解釈は、関数アプリケーションを使用して実装できます。 ^{[1]メタ循環評価は、} Lispのコンテキストで最も顕著です。^{[1] [2]}自己インタープリタは、インタープリタ対象言語がホスト言語とほぼ同じであるメタ循環インタープリタです。2つの用語はしばしば同義語として使用されます。^[3]

Corrado Böhmの博士論文^[4]では、セルフホスティングコンパイラ の設計について説明されています。 ^[5]高階関数のコンパイルが難しいため、多くの言語は代わりにインタープリタを介して定義され、最も有名なのはLispです。^{[1] [6]この用語自体は}John C. Reynoldsによって造られ、^{[1] 、}Structure and Interpretation of Computer Programsという本で使用されたことで普及しました。^{[3] [7]}

自己インタープリタは、ホスト言語が解釈される言語でもあるメタ循環インタープリタです。^[8]自己インタープリタは、問題の言語の普遍的な機能を示し、言語の特定の側面を学ぶのに役立ちます。^{[2]自己インタープリタは、ほとんどの言語構成要素の循環的で}空虚な定義を提供するため、評価戦略など、解釈される言語の意味についてほとんど洞察を提供しません。これらの問題に対処すると、「定義インタープリタ」というより一般的な概念が生まれます。^[1]

この部分はダンビーの論文の第3.2.4節に基づいています。 ^[9]

これが、計算の自己評価器の核心です 。計算の抽象構文は、 OCamlで次のように実装されており、変数を de Bruijn インデックス、つまり、語彙オフセット (0 から始まる) で表します。 ${\displaystyle \lambda}$${\displaystyle \lambda}$

type  term  =  IND  of  int     (* de Bruijn インデックス *) 
          | 期間のABS  |期間・期間のAPP 
               

評価者は環境を使用します:

型 value  =  FUN  of  ( value  ->  value )

rec  eval ( t : term ) ( e : value list ) : value = match t with IND n -> List . nth e n | ABS t' -> FUN  ( fun v - > eval t' ( v :: e )) | APP ( t0 , t1 ) -> apply ( eval t0 e ) ( eval t1 e )およびapply ( FUN f : value ) ( a : value ) = f aとします。          
    
      
       
     
             
      
           
         
   

 main  ( t  :  term )  :  value  = 
  evalt  [  ]とします。

値（型value）は、表現可能な値（環境内で式を評価した結果）と表示可能な値（環境内の変数によって表される値）を融合したもので、この用語はChristopher Stracheyによるものです。 ^{[10] [11]}

環境は、表示可能な値のリストとして表されます。

コア評価には 3 つの条項があります。

• これは、変数 (de Bruijn インデックスで表される) を、このインデックスの現在の環境の値にマッピングします。
• これは、構文関数を意味関数にマッピングします。(意味関数を引数に適用すると、引数で拡張された語彙環境内の対応する構文関数の本体を評価することになります。)
• 構文アプリケーションを意味アプリケーションにマッピングします。

この評価器は、それぞれの再帰呼び出しが指定された項の適切なサブ部分に対して行われるという点で合成的です。また、値の定義域が関数空間であるため、 高階でもあります。

「定義インタープリタ」で、レイノルズは、そのような自己インタープリタが適切に定義されているかどうかという疑問に答えています。定義される言語 (ソース言語) の評価戦略は、定義する言語 (メタ言語) の評価戦略によって決定されるため、彼は否定的に答えました。メタ言語が call by value に従う場合 (OCaml のように)、ソース言語は call by value に従います。メタ言語が call by name に従う場合 ( Algol 60のように)、ソース言語は call by name に従います。そして、メタ言語が call by need に従う場合 ( Haskellのように)、ソース言語は call by need に従います。

「定義的インタープリタ」では、レイノルズは自己インタープリタを、定義言語の評価戦略から独立させることで、明確に定義できるようにした。彼は自己インタープリタを評価戦略に依存しない継続渡しスタイルに変換することで評価戦略を修正し、後にゴードン・プロトキンの独立定理 に反映された。 ^[12]

さらに、論理関係がまだ発見されていなかったため、レイノルズは、(1)閉包変換し、(2)継続を非機能化することで、結果として得られる継続渡し評価器を一階にした。彼は、結果として得られるインタープリタの「マシンのような品質」を指摘した。これは、レイノルズの CPS 変換が値呼び出し用であったため、 CEK マシンの起源である。 ^[13] 名前呼び出しの場合、これらの変換は、自己インタープリタをKrivine マシンの初期インスタンスにマッピングします。 ^[14] SECDマシンと他の多くの抽象マシンは、この方法で相互に導出できます。 ^{[15] [16]}

注目すべきは、微積分学の最も有名な 3 つの抽象マシンが機能的に同じ自己インタープリタに対応していること です。${\displaystyle \lambda}$

強く正規化する全関数型プログラミング言語はチューリング完全ではあり得ない。そうでなければ、プログラムが型チェックされるかどうかを見ることによって停止問題を解決できる。つまり、全言語では定義できない計算可能な関数が存在する。^[17]特に、全プログラミング言語、例えば単純型付きラムダ計算、ジャン＝イヴ・ジラールのシステム F、ティエリー・コカンの構成計算などの型付きラムダ計算では、自己インタープリタを定義することは不可能である。^{[18] [19]}ここで、「自己インタープリタ」とは、何らかのプレーンな形式（文字列など）でソース項表現を受け取り、対応する正規化された項の表現を返すプログラムを意味する。この不可能性の結果は、「自己インタープリタ」の他の定義には当てはまらない。例えば、一部の著者は、型の関数を自己インタープリタと呼んでいる。ここで、は型付き項の表現の型である。混乱を避けるため、これらの関数を自己認識子と呼ぶことにする。Brown と Palsberg は、System Fや System F _ωなど、いくつかの強く正規化する言語で自己認識子を定義できることを示した。^[20] これは、符号化された用語の型が表現の型に反映されるため、対角線上の議論が構築できないため可能であることが判明した。Brown と Palsberg は、論文で自己解釈は不可能であるという「常識」を反証したと主張しているが (そして、彼らは Wikipedia を常識の例として挙げている)、実際に反証しているのは、異なる概念である自己認識子の不可能性である。その後の研究では、ここで使用されているより具体的な「自己認識子」という用語に切り替え、特にこれらを「自己評価子」(型) と区別している。^[21] 彼らはまた、自己評価の実装は自己認識よりも難しいと思われることを認識しており、強く正規化する言語での前者の実装は未解決の問題として残している。 ${\displaystyle \pi \,\tau \to \tau }$${\displaystyle \pi \,\tau }$${\displaystyle \tau}$${\displaystyle \pi \,\tau \to \pi \,\tau }$

既存の言語実装と組み合わせることで、メタ循環インタープリタは、機能を追加することで上方に、または機能を解釈するのではなくコンパイルすることで下方に、言語を拡張するためのベースラインシステムを提供します。^[22]また、高度なデバッガなど、プログラミング言語と緊密に統合されたツールを作成する場合にも役立ちます。^{[引用が必要]}メタ循環実装を念頭に置いて設計された言語は、ホスト言語とはまったく異なる言語であっても、一般的な言語の構築に適していることがよくあります。^{[引用が必要]}

多くの言語には、1 つ以上のメタ循環実装があります。以下は部分的なリストです。

下から上へ設計されたメタ循環実装を持つ言語のいくつかを、時系列順にグループ化します。

• リスプ、1958年
  • スキーム、1975
    • ピコ、1997年^[23]
    • ActorScript、2009年?
  • クロージュア、2007
• 1968年 フォース
  • ポストスクリプト、1982年
• プロローグ、1972年
• TeX、Virgin TeX に基づく、1978 年
• スモールトーク、1980年
• レボル、1997
  • レッド、2011
• ファクター、2003

サードパーティによるメタ循環実装を備えた言語:

• Jikes RVM、Squawk、Maxine、またはGraalVMのEspresso経由のJava
• Metascala 経由のScala
• Narcissus または JS-Interpreter 経由のJavaScript
• グリンダ経由のオズ
• PyPy経由のPython
• ルビニウス経由のルビー
• Metalua経由のLua

• M式
• 同図像性
• セルフホスティングコンパイラ

• コンピュータ プログラムの構造と解釈 (SICP)、全書のオンライン版、2009 年 1 月 18 日にアクセス。
• メタスカラ