インタプリタ

プログラミング言語で書かれたソースコードないし中間表現を逐次解釈しながら実行するプログラム

インタプリタ: interpreter)とは、プログラミング言語で書かれたソースコードないし中間表現を逐次解釈しながら実行するプログラムのこと[1]。「インタープリタ」「インタープリター」などと表記することもある。

インタプリタは、およそ次のいずれかの動作をするプログラムである。

  1. ソースコードを直接解釈実行する。
  2. ソースコードを何らかの効率的な中間的なコード(中間表現)に、最初に全て変換して、あるいは、逐次変換しながら、解釈実行する。
  3. 何らかのコンパイラが生成し出力した、何らかの効率的な(マシンに依存しない、あるいは、マシン依存の)中間表現を解釈実行する[注 1]

このように程度の差はあるが、ソフトウェアがソフトウェアを実行するという形になる。

いずれにしても、「インタプリタ言語」などという分類は本来は存在しない。単にそれぞれの言語の代表的な処理系の実装がインタプリタであったというだけで、理論上はどの言語であってもインタプリタとコンパイラのどちらでも作ることができる。しかしながら、インタプリタかしか存在しない言語があるが故に、「インタプリタ言語」や「コンパイラ言語」と区別されているのが現実である。インタプリタは実行中何度もプログラムを再解釈するため、ダイナミックディスパッチ英語版ダイナミックバインディングリフレクション動的型付けのような機能を実現することが容易である。一方、コンパイラは事前にCPUで実行できるように変換するだけで実行には関与しないため、実行中に振る舞いを変更したいときはそのためのプログラムを別途用意しなければならないケースがほとんどである。さらに、自前の言語から既存の何らかの表現に変換するには、その表現と対応付けるための知識と技術が必要であり、言語機能が大規模化や複雑化するほど、既存の表現との互換性をできるだけ確保しながら、自前の言語での振る舞いを実現することは難しくなる。中間表現も自前であれば、変換する手間はずっと楽になる。

仕組み

編集

インタプリタは各仮想命令に紐づく命令ボディとディスパッチ機構をもち、ホストマシン上で実行可能になっている(例: x86マシンコードbinファイル)。仮想命令群からなるコードを引数としてインタプリタが実行されると、仮想命令に基づいて制御が移行され対応する命令ボディが実行される。これを繰り返すことでインタプリタはコードを実行する。

命令ボディ

編集

命令ボディ: instruction body、命令本体とも)は仮想命令をホスト言語でエミュレートするコードである[2]。命令ボディがホストマシンで実行されることで仮想命令が事実上実行される。すなわち命令ボディは仮想命令の実装である。例えば二項和仮想命令 ADD2 に対応してC言語で書かれた push(pop() + pop()) は命令ボディである。

ディスパッチ

編集

ディスパッチ: dispatch)は仮想命令に基づいた命令ボディから命令ボディへの制御移行メカニズムである[2][3]。ディスパッチの最もシンプルな例はSwitch文Jump命令)である。ある仮想命令の実行後、次の仮想命令に対応する命令ボディへ制御を移す(Jumpする)ことでその仮想命令実装が実行される。

誤解

編集

プログラミング言語処理系の実装には、インタプリタとコンパイラの2つがある、とされてきた。インタプリタは実行を行うが、コンパイラは実行を行わない、という差がある。

インタプリタは、インタプリタが提供する言語のプログラム文を1文ずつ、インタプリタを実装した言語の機能を呼び出していく(単純な)方式が一般的であった。コマンドラインインタプリタではこれに加えて、別のプログラムに処理を委ねて一つの機能を実現する。

この時代のインタプリタの長所と欠点については、およそ次のような解説がされることが一般的であった。

  • (長所)プログラムを作成している途中でも、とりあえず書かれた箇所まで実行させることができ、プログラマの期待通りの動作をしている場合も、期待通りの動作をしていない場合も、早期にそれを確認・発見し、そして修正後すばやく実行、再確認できる。
  • (短所)実行速度が遅い。(ループ(=繰り返し)の箇所などでは)1度構文解釈した文でも、毎回(あらためて、最初から)解釈と実行を行うので、コンパイラ方式に比べて実行速度が遅くなる。(ループを全く含まないような、全ての命令が一回だけ解釈され、一回だけ実行されるような(ある意味、特殊な)プログラムであれば、解釈+実行のトータルの時間は、インタプリタでもコンパイラでもさほど差は生じない。だが、実用的なプログラムは一般的に、多数のループを含んでおり、そうしたプログラムではインタプリタのほうが実行を完了するまでの時間が多くかかり、特に、ループ回数が多ければ多いほど(古典的な、単純な)インタプリタの相対的な遅さは顕著になってくる。→#長所と短所

その後、そうした欠点を解消すべく、(1990年代ころになって)毎回毎回、(高級言語から)機械語に変換するのではなく、中間言語に変換することで高速化をはかるインタプリタなどが作りだされた。

改良の結果、古典的な意味での「インタプリタ」と「コンパイラ」の双方の性質を備えたようなインタプリタが登場し、複雑化してきている。

(近年の)インタプリタがおこなう、(旧来の)コンパイラが行っているような変換のひとつとしては、高速化などを目的とした、実行時コンパイラによる動的コンパイルを挙げることができる。

[注 2]

歴史

編集

インタプリタという手法、すなわち、「そのハードウェアが直接解釈するのではないプログラム」を受け取り、「プログラムで実装された抽象的な、あるいは仮想上のコンピュータで解釈実行する」というプログラムの実行法は、コンピュータが登場した時から、ないしそれ以前からある。

万能チューリングマシンは、「どんなチューリングマシンについても、それを模擬できるチューリングマシン」というもので、ある種のエミュレータないしインタプリタであり、考察されたのは電子式のコンピュータの誕生する以前である。

EDSAC(実用的な機能を持ったプログラム内蔵方式の世界初の電子計算機とされている)において既に、ある種のインタプリタが実装されていたことが記録に残っている。同機におけるプログラミングの技法が書かれた The Preparation of Programs for an Electronic Digital Computer の chapter 2 の § 2-22 Interpretive subroutines で説明されているが、複素数演算などのサブルーチンを明示的にサブルーチンとして呼ぶのではなく、通常の加減算などと同様の形式のプログラムをインタプリタで解釈してそれらのサブルーチンを利用する、というものである。また日本においても、パンチカードを入力としてパッチパネルの配線によるプログラミングで処理するような機械で、配線によってある種のインタプリタのようなものを実装し、パンチカードの内容をデータとしてではなくプログラムのように扱う、というような例があると言われている[4]

最初の Lisp インタプリタはスティーブ・ラッセルIBM 704 上に実装した。これにはエピソードがあり、ジョン・マッカーシーが「Lisp の論文」[5]で「数学的」に示したものだったのであるが、マッカーシー自身は実装できるものだとは考えていなかった。それを、論文を読んだ、院生であったラッセルが、実装可能だと言って数学的な記述から変換して機械語で実装してみせたという。[6][7]

1960年代には(現在のJavaなどと同様な)、プログラミング言語から中間表現にコンパイルし、それをインタプリタで実行する、というような手法も一般的になった(pコードマシンを参照)。

長所と短所

編集

開発時に修正作業が容易

編集

プログラム開発中、プログラマは頻繁にソースコードに手を加える。コンパイラの場合、ソースコードを変更するたびにコンパイルし、リンクして実行ファイルを完成させないと、そのプログラムを実行できない。プログラムが大きくなると、ビルドの完了を待っている時間が長くなる。一方、インタプリタではソースコードをそのまま実行するか中間表現に変換するだけなので、ほとんど待つ必要がなく、修正がうまくいったかどうかのテストをより素早く確認できる。

この特性を利用したプログラムとしてREPLがある。入力を受け取る(Read)、入力の評価(Eval)、評価結果を提示する(Print)を繰り返す(Loop)、テスト環境の一つである。評価はインタプリタに限らずコンパイラで行なわれるかもしれないが、ユーザからの入力は常にソースコードの断片であり、それを逐次実行するという点で一種のインタプリタということもできる。実際、その挙動はソースコードを指定せずに起動したBASICなどのそれとよく似ている。しかし、テスト環境も兼ねているため、エラーが起きた場合のメッセージが詳細であることが多い。関数型言語論理型言語では、通常は機械語にコンパイルする処理系であっても用意される。

可搬性

編集

AOTコンパイラ方式では事前に生成された機械語実行ファイルがユーザーに配布される。機械語はプロセッサアーキテクチャに依存するため、このバイナリは特定のプロセッサでしか動作しない(可搬性が低い)。

一方インタプリタ形式ではソースコードとインタプリタが配布される。インタプリタは機械語実行ファイルであるため環境に依存するが、ソースコードには環境に依存しない言語を採用できる。その場合環境に合わせたインタプリタを事前配布しておけば、アーキテクチャに依存しないプログラムの配布が可能である(可搬性が高い)。またインタプリタの代わりにJITコンパイラを用いても同様の利点が得られる。同一動作の保証はインタプリタ実装に依存しており(JITであればコンパイラ)、互換性バグの例として表計算マクロやWebページ(HTML)が挙げられる。

複雑性

編集

AOTコンパイラ方式では1つのバイナリを実行するだけでプログラムが機能する。一方インタプリタ方式では、まずインタプリタをインストールしその上でソースコードを動かす必要がある。その結果全体のプログラムサイズが大きくなり、ユーザーの手間が増える場合がある(複雑性が高い)。またJITコンパイル方式でも同様の複雑性が生まれる。

可読性

編集

インタプリタ用コード(高級言語コードあるいはバイトコード)は機械語バイナリより容易に解読できる(可読性が高い)。ゆえに配布後のデバッグや修正が容易な一方、知的財産保護上の問題を起こしうる。そのための暗号化・難読化を考慮した言語・システムが存在する。またJITコンパイル方式でも同様の可読性に関する特性が現れる。

速度

編集

インタプリタ方式の実行速度はコンパイラ方式の実行速度よりも遅い傾向がある。

コンパイラではプログラム内のの解析を実行前に1回だけ行うが、単純な実装のインタプリタではそれを文ごとに実行時に毎回行うため、実行性能が低くなる。単純な実装のインタプリタでは変数にアクセスする際も識別子とメモリ上の位置のマッピングを確認しなければならず、しかもそれを実行中に何度も行わなければならないので、遅くなる。

またディスパッチはインタプリタが本質的に抱えるコストである。コンパイル方式では事前(コンパイル時)にディスパッチ相当の命令ボディ整列がおこなわれるため、実行時にディスパッチコストが発生しない。ゆえにインタプリタ方式ではディスパッチコスト×命令数分の追加コストが本質的に掛かる。

ディスパッチ分岐予測を難しくする。ゆえにパイプライン方式を採用するCPUにおいて速度へ影響を与える[8]。影響の大きさは分岐予測器の性能に左右され、2000年代以前のCPUではインタプリタの低速度がこのペナルティによって引き起こされるとされていた。予測器の性能が上昇した2010年代以降のCPU(例: x86 Haswell)ではその影響は小さい[9]

インタプリタによる開発の速さとコンパイラによる実行の速さの間で、様々な妥協案が考案されてきた。一部の LISP 処理系などでは、インタプリタのコードとコンパイルされたコードが相互に呼び出しあうことができ、変数も共有できる。そのため、あるルーチンをインタプリタで評価しデバッグした後、先行してコンパイルして実行性能を高めつつ、他のルーチンを開発し続けることができる。多くのインタプリタはソースコードをそのまま実行するわけではなく、よりコンパクトな内部形式に変換している。多くの BASIC インタプリタは予約語を1バイトトークンに置換し、それをジャンプテーブルのインデックスとして使用する。PBASIC など一部のインタプリタでは、バイト単位ではなくビット単位でプログラムの短縮を行っており、例えばコマンドを5ビットで表し、一般に16ビットで表される定数をその数値の大きさに対応して可変長(3、6、10、18ビットなど)で表し、アドレスオペランドとして「ビットオフセット」を用意している。多くの BASIC インタプリタは独自にトークン化された内部表現を保存し、読み込むことができる。

インタプリタがコンパイラと同様の字句解析構文解析を行い、その結果生成された抽象構文木を解釈することもある。

プログラムの実行時間はコンパイラよりもインタプリタの方が長いが、コンパイル時間と実行時間を合計すればインタプリタでの実行時間よりも長くなることがある。プロトタイピングテストにおいては、この差が重要となる。

その他の技法に制御フロー解析静的単一代入がある。

バリエーション

編集

スレッデッドコード

編集

それ自体はインタプリタの手法とも言えるしコンパイラの手法とも言える。そのどちらと言うよりも、中間表現の1種類というべきかもしれない。仮想関数テーブルテーブルジャンプによるフロー制御に似ていなくもない。

スレッデッドコードは、呼び出されるべきサブルーチンのアドレスのみが順番に羅列されたものである。「直接スレッディング」の場合は、そのアドレスが指す先は機械語のサブルーチンである。他にもいくつかのバリエーションがある。「サブルーチン・スレッディング」は最も違うタイプのバリエーションで、アドレスのみではなく、機械語のCALL命令として羅列するので、ハードウェアのプロセッサで直接実行できる。これは実行のオーバーヘッドは極小だが、メモリ効率は悪い[注 3]。サブルーチン・スレッディング以外のスレッデッドコードは、きわめて単純なインタプリタで実行できる。Forthでは「内部インタプリタ」と呼んでいる(これは、Forth言語自体を実装しているインタプリタである「外部インタプリタ」と対になっている)。

バイトコード

編集

ソースコードを実行可能な形にするには、まず、ソースコードを構文木に変換する必要がある。構文木のまま、インタプリタ型の処理系で実行する処理系もあるが、構文木をさらに、中間コード(バイトコードなど)などの中間表現に変換してから実行する物もある。中間コードをバイトコードと呼んでいる処理系ではそのインタプリタをバイトコードインタプリタと呼ぶ。Java.NET Framework のように、中間コードの仕様を公開しファイルに書き出すものもあるし、仕様は公開せず処理系内部だけで使用するものもある。動的コンパイルを使っているインタプリタは、内部で実機の機械語に変換し実行する。

インタプリタとコンパイラの間には様々な中間的実装が存在し、それぞれにプログラム実行前に行われる解析の度合いが異なる。例えば Emacs Lispバイトコードにコンパイルされ、LISP のソースを高度に圧縮し最適化した表現にしているが、それは機械語コードではない(したがって特定のプラットフォームに依存しない)。この「コンパイル」されたコードを解釈するのがバイトコードインタプリタである(それ自体は C で書かれている)。この場合のコンパイルされたコードは仮想機械の機械語コードであり、仮想機械はハードウェアで実装されておらず、バイトコードインタプリタとして実装されている。同様の手法は Open Firmware システムで使われている Forth コードでも使われている。ソース言語は「Fコード」(バイトコードの一種)にコンパイルされ、それを仮想機械が解釈実行する。他にPコードマシンなどがある。

コントロール・テーブル英語版はコンパイラを通さなくとも生成でき、バイトコードインタプリタと同様の方法でカスタマイズされたインタプリタでの適切なアルゴリズム的制御構造を記述できる。

抽象構文木

編集

インタプリタとコンパイラの中間的手法の1つとして、ソースコードを最適化された抽象構文木 (AST) に変換し、その木構造にしたがってプログラムを実行するか、実行時コンパイラでの機械語コード生成に使用する方法がある[10]。この方式では各文を1回だけ構文解析する必要がある。バイトコードに比べると、ASTではプログラムの全体的構造や文と文の関係を保持でき(それらはバイトコードでは失われる)、圧縮するとさらにコンパクトな表現になる[11]。そのため、実行時コンパイラにとってはバイトコードよりもASTの方が優れた中間表現だとして提案されてきた。また、実行時の解析もより優れたものにできる。

しかし、ASTはバイトコードよりも冗長であるため、インタプリタとしてはオーバーヘッドが大きくなるという問題がある[12]CRuby の場合は、1.8までは構文木インタプリタであったが、1.9では(開発中には YARV と呼ばれていた)バイトコードインタプリタに入れ替えられ、性能が向上した。

実行時コンパイル

編集

インタプリタとコンパイラの境界をさらにぼやけさせる方式として、中間表現を実行時コンパイラ (JIT) でコンパイルし、実行時にネイティブの機械語にコンパイルする技法がある。これはネイティブなコードの実行効率を実現する代わり、ASTやバイトコードを最初にコンパイルする際に起動時間やメモリ使用量が増大するという欠点がある。これを補う技法として適応的最適化英語版があり、インタプリタが実行中のプログラムを性能解析して最も頻繁に実行される部分をネイティブのコードにコンパイルする。これらの技法は1980年代の Smalltalk などの言語で使われ始めた[13]

実行時コンパイルは近年多くの言語処理系で採用されており、Java.NET Framework、最近のJavaScript の実装でも JIT が採用されている。

トランスレータ方式

編集

他のインタプリタ言語に変換して、ターゲット言語のインタプリタ上で実行する方式。例えば CoffeeScriptJavaScript に変換されて、JavaScript インタプリタ上で実行される。

応用

編集
  • インタプリタは、コマンドライン用言語やグルー言語でよく使われている。
  • 自己書き換えコードはインタプリタでは容易に実装できる。これは LISP人工知能研究がインタプリタの起源であったこととも関係している。
  • 仮想機械を使って、あるアーキテクチャを別のアーキテクチャ上で実行させる仮想化は、基本的にインタプリタである。
  • サンドボックス: インタプリタまたは仮想機械はソースコードの命令を全て実際に実行することを強制されない。特にセキュリティを脅かすような処理の実行は拒否できる。

デバッグ、教育用

編集

通常C言語はコンパイラで処理されるが、デバッグ目的および教育目的のインタプリタ型のC言語の処理系もある。MS-DOS時代に、いくつかの製品が提供されていた。C-Terpなどがその様な製品の例である。C/C++のインタプリタはほかにCINTChがある。

パンチカード

編集

パンチカードシステムにおいて、パンチカードを読み込んで、その内容を人間が読める形式(文字)でパンチカード上に印字する機械をインタプリタと呼ぶ。例えば、IBM 550英語版 Numeric Interpreter (1930年) や IBM 557英語版 Alphabetic Interpreter (1954年) がある。

プログラミング言語

編集

インタプリタとコンパイラ方式が併用のもの

編集

「共通言語ランタイム」のバイナリー・コードにコンパイルされるもの

編集

Erlang VM」(BEAM)のバイナリー・コードにコンパイルされるもの

編集

Java仮想機械」のバイナリー・コードにコンパイルされるもの

編集

JavaScript に変換されるもの

編集

Lua VM」のバイナリー・コードにコンパイルされるもの

編集

「Pコードマシン」のバイナリー・コードにコンパイルされるもの

編集

Parrot」のバイナリー・コードにコンパイルされるもの

編集

Smalltalk VM」のバイナリー・コードにコンパイルされるもの

編集

VBAのPコードにコンパイルされるもの

編集

脚注

編集

注釈

編集
  1. ^ この意味では、CPUは機械語インタプリタであると見ることができる。
  2. ^ 現在では、「インタプリタ / コンパイラ」という区分に関しては状況が変わっており、[誰?]に言わせると『だが、それらは必ずしも相互排他的に2つに分類できるわけではない。なぜなら多くのインタプリタ方式の処理系は、コンパイラが行っているような変換も内部で行っているからだ。[要出典]」とも言われ、『「インタプリタ言語」あるいは「コンパイラ言語」といった呼称も見掛けることがあるが、これらは単にその言語の規範的実装がインタプリタかコンパイラかを示しているに過ぎない(実際、詳しく調べれば、実験的な程度の実装まで含めれば両方ともあるということも多い)。』という見解も出てくることになる。高水準言語は基本的に抽象であり、(理想的には)特定の実装からは独立している。しかし、動的プログラミング言語のようにインタプリタでの実装が向いている方向性の言語、あるいはその逆もあるということは確かである。
  3. ^ つまり、近年では高速化にはキャッシュのほうが重要なので、高速化に有利か否かはわからない。

出典

編集
  1. ^ bit 編集部『bit 単語帳』共立出版、1990年8月15日、19頁。ISBN 4-320-02526-1 
  2. ^ a b "An interpreter dispatches a virtual instruction body to emulate each virtual instruction in turn." Zaleski (2007). YETI: a GraduallY Extensible Trace Interpreter. University of Toronto.
  3. ^ "we defined dispatch as the mechanism used by a high level language virtual machine to transfer control from the code to emulate one virtual instruction to the next." Zaleski (2007). YETI: a GraduallY Extensible Trace Interpreter. University of Toronto.
  4. ^ 日本のソフトウェアの草創期:座談会:日本のソフトウェアの草創期
  5. ^ Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I のこと
  6. ^ History of Lisp の、§3 の最後のほうに、次のようにある「S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter. (段落) The unexpected appearance of an interpreter ...(後略)」
  7. ^ ポール・グレアムの『ハッカーと画家』(原著「Hackers & Painters、185ページ)によれば、マッカーシーは「ラッセルは『ねえ、この eval をプログラムしようか』と言った。…私は『ほう、ほう。君は理論と実際を混同している。この eval は読み物として書いたもので、実際に動かすために書いたものじゃない』と答えた。しかし彼はそれをやってのけた。つまり彼は私の論文にある evalIBM 704 の機械語にコンパイルして、バグを修正し、それを LISP インタプリタだと宣伝したし、実際それはそのとおりだった。だからその時点で LISP は今日のような形態を本質的に備えていた」と述べたという。
  8. ^ "Conventional wisdom states that this indirect jump incurs a major performance degradation on deeply pipelined architectures because it is hardly predictable" Rohou, et al. (2015). Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore. International Symposium on Code Generation and Optimization, Feb 2015, Burlingame, United States.
  9. ^ "we show that the accuracy of indirect branch prediction is no longer critical for interpreters." Rohou, et al. (2015). Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore. International Symposium on Code Generation and Optimization, Feb 2015, Burlingame, United States.
  10. ^ AST intermediate representationsLambda the Ultimate forum
  11. ^ A Tree-Based Alternative to Java Byte-Codes — トーマス・キスラー、マイケル・フランズ
  12. ^ Annoucing SquirelFish
  13. ^ L. ドイチュ、A. シフマン、Efficient implementation of the Smalltalk-80 systemProceedings of 11th POPL symposium、1984年

関連項目

編集

外部リンク

編集

この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。