Edited at

数式言語を使って、インタプリタとコンパイラの違いを説明してみる


まえがき

先日、ツイッターで、(ある程度言語処理系に関わった人なら常識的な)「「コンパイラ型言語」と「インタプリタ型言語」という分類は誤り」という趣旨のことをつぶやいたところ、予想していなかった大きな反響をいただきました。

個々の反応については「うんうん、そうだよね」と思うものもあれば「いや、それは違うんじゃ」と思うものもあり、色々な意見を見られて有意義でしたが、その中で湧いた一つの疑問がありました。それは、「皆、インタプリタが何をやっているかイメージできていないのでは?」というものです。もちろん、トイ言語であれ何か言語処理系を作ったことがある人であればイメージできていないはずはないのですが、実際には、トイ言語であっても作ったことがある人というのは存外少ないものです。

そこで、この記事では、Kotlinで書かれた、簡単な数式言語のインタプリタとコンパイラを使って、それらの違いについて説明てみたいと思います。


処理する言語

今回、処理する数式言語は本当に単純なもので、


  • 数値:


    • 整数のみ(0, 1, 2, ...)



  • 演算:


    • 足し算: e1+e2

    • 引き算: e1-e2

    • 掛け算: e1*e2

    • 割り算: e1/e2

    • グルーピング: (e)



という形で定義されたものです。たとえば、有効な式としては、


  • 1+2

  • 1-2

  • 1*2

  • 1/2

  • 1+2*3/4

  • (1+2*3)/4

などがあります。単純化のために、空白文字は使えないものとします。それらの数式の解釈については、JavaでもRubyでもScalaでもPythonでもなんでもいいですが、そういう言語での挙動と同じものとします(ただし、整数の割り算の結果は整数となるものとし、余りは切り捨てます)。


実装


インタプリタの実装と振る舞い

さて、ここから、いよいよインタプリタが何をするかの説明に入っていきます。といっても、やっていることはとても簡単です。まず、インタプリタの実装に必要な算術式の抽象構文木を導入します。

sealed abstract class Ast {

//リテラル
data class Num(val value: Int) : Ast()
//足し算
data class Add(val left: Ast, val right: Ast): Ast()
//引き算
data class Sub(val left: Ast, val right: Ast): Ast()
//掛け算
data class Mul(val left: Ast, val right: Ast): Ast()
//割り算
data class Div(val left: Ast, val right: Ast): Ast()
}

それぞれの役割は次のようになっています。



  • Ast: が木構造のルートクラス


  • Num: 整数リテラル


  • Add: 足し算


  • Sub: 引き算


  • Mul: 掛け算


  • Div: 割り算

こうやって導入した抽象構文木を、次のようにして場合わけして再帰的にたどります。

object Interpreter {

fun interpret(input: Ast): Int {
when(input) {
is Ast.Num ->
return input.value
is Ast.Add ->
return interpret(input.left) + interpret(input.right)
is Ast.Sub ->
return interpret(input.left) - interpret(input.right)
is Ast.Mul ->
return interpret(input.left) * interpret(input.right)
is Ast.Div ->
return interpret(input.left) / interpret(input.right)
}
}
}

インタプリタの実装はたったこれだけです。ここで注目して欲しいのは、inputに対して、その場で場合わけして、抽象構文木を解釈して計算しているのであって、抽象構文木を何らかの命令に翻訳しているわけではない、ということです。

これだけだとイメージが湧かないかもしれないので、インタプリタ本体のコードを.classファイルに変換した結果を逆アセンブルした結果を載せます。


public final int interpret(com.github.kmizu.compiler_interpreter.Ast);
Code:
0: aload_1
1: ldc #9 // String input
3: invokestatic #15 // Method kotlin/jvm/internal/Intrinsics.checkParameterIsNotNull:(Ljava/lang/Object;Ljava/lang/String;)V
6: aload_1
7: astore_2
8: aload_2
9: instanceof #17 // class com/github/kmizu/compiler_interpreter/Ast$Num
12: ifeq 23
15: aload_1
16: checkcast #17 // class com/github/kmizu/compiler_interpreter/Ast$Num
19: invokevirtual #21 // Method com/github/kmizu/compiler_interpreter/Ast$Num.getValue:()I
22: ireturn
23: aload_2
24: instanceof #23 // class com/github/kmizu/compiler_interpreter/Ast$Add
27: ifeq 54
30: aload_0
31: aload_1
32: checkcast #23 // class com/github/kmizu/compiler_interpreter/Ast$Add
35: invokevirtual #27 // Method com/github/kmizu/compiler_interpreter/Ast$Add.getLeft:()Lcom/github/kmizu/compiler_interpreter/Ast;
38: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
41: aload_0
42: aload_1
43: checkcast #23 // class com/github/kmizu/compiler_interpreter/Ast$Add
46: invokevirtual #32 // Method com/github/kmizu/compiler_interpreter/Ast$Add.getRight:()Lcom/github/kmizu/compiler_interpreter/Ast;
49: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
52: iadd
53: ireturn
54: aload_2
55: instanceof #34 // class com/github/kmizu/compiler_interpreter/Ast$Sub
58: ifeq 85
61: aload_0
62: aload_1
63: checkcast #34 // class com/github/kmizu/compiler_interpreter/Ast$Sub
66: invokevirtual #35 // Method com/github/kmizu/compiler_interpreter/Ast$Sub.getLeft:()Lcom/github/kmizu/compiler_interpreter/Ast;
69: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
72: aload_0
73: aload_1
74: checkcast #34 // class com/github/kmizu/compiler_interpreter/Ast$Sub
77: invokevirtual #36 // Method com/github/kmizu/compiler_interpreter/Ast$Sub.getRight:()Lcom/github/kmizu/compiler_interpreter/Ast;
80: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
83: isub
84: ireturn
85: aload_2
86: instanceof #38 // class com/github/kmizu/compiler_interpreter/Ast$Mul
89: ifeq 116
92: aload_0
93: aload_1
94: checkcast #38 // class com/github/kmizu/compiler_interpreter/Ast$Mul
97: invokevirtual #39 // Method com/github/kmizu/compiler_interpreter/Ast$Mul.getLeft:()Lcom/github/kmizu/compiler_interpreter/Ast;
100: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
103: aload_0
104: aload_1
105: checkcast #38 // class com/github/kmizu/compiler_interpreter/Ast$Mul
108: invokevirtual #40 // Method com/github/kmizu/compiler_interpreter/Ast$Mul.getRight:()Lcom/github/kmizu/compiler_interpreter/Ast;
111: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
114: imul
115: ireturn
116: aload_2
117: instanceof #42 // class com/github/kmizu/compiler_interpreter/Ast$Div
120: ifeq 147
123: aload_0
124: aload_1
125: checkcast #42 // class com/github/kmizu/compiler_interpreter/Ast$Div
128: invokevirtual #43 // Method com/github/kmizu/compiler_interpreter/Ast$Div.getLeft:()Lcom/github/kmizu/compiler_interpreter/Ast;
131: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
134: aload_0
135: aload_1
136: checkcast #42 // class com/github/kmizu/compiler_interpreter/Ast$Div
139: invokevirtual #44 // Method com/github/kmizu/compiler_interpreter/Ast$Div.getRight:()Lcom/github/kmizu/compiler_interpreter/Ast;
142: invokevirtual #29 // Method interpret:(Lcom/github/kmizu/compiler_interpreter/Ast;)I
145: idiv
146: ireturn
147: new #46 // class kotlin/NoWhenBranchMatchedException
150: dup
151: invokespecial #50 // Method kotlin/NoWhenBranchMatchedException."<init>":()V
154: athrow

かなり長いですが、この中の52:83:114145に注目してください。これらは、それぞれ、整数の足し算、引き算、掛け算、割り算を行うJVMのバイトコード命令です。要はインタプリタ本体に、数式言語の解釈に対応する処理が既に埋め込まれているわけです。数式言語のインタプリタは、単にこれらの命令にジャンプするように抽象構文木を解釈しているわけであって(27:58:86:117:で対応する分岐にジャンプしています)、新しい命令を生成したりしていないわけです。


コンパイラの実装と振る舞い

この数式言語に対するコンパイラを作ることもできます。以下は、バイトコード(クラスファイル)にコンパイルするコードです。バイトコード生成を簡単にするために、ASMというライブラリを使っています。

            fun compileExp (arg: Ast) {

when(arg) {
is Ast.Add -> {
compileExp(arg.left)
compileExp(arg.right)
mv.visitInsn(IADD)
}
is Ast.Sub -> {
compileExp(arg.left)
compileExp(arg.right)
mv.visitInsn(ISUB)
}
is Ast.Mul -> {
compileExp(arg.left)
compileExp(arg.right)
mv.visitInsn(IMUL)
}
is Ast.Div -> {
compileExp(arg.left)
compileExp(arg.right)
mv.visitInsn(IDIV)
}
is Ast.Num -> {
mv.visitLdcInsn(arg.value)
}
}
}

実際には、ファイルに書き出したり、クラスファイルを生成するためにもうちょっと必要なコードがありますが、本体の処理はこれだけです。インタプリタより多少長いくらいですね。この関数compileExpでは、入力として与えられた抽象構文木をたどって、それぞれに対応する命令に翻訳しています(mv.visit...でバイトコードの書き込みが行われます)。

このコンパイラのコード全体はこちらにありますが、試しにこれを使って、5*3という数式をコンパイルしてみましょう。

 ~/work/compiler-interpreter (git master)

[mizushima]$ java -jar build/libs/compiler-interpreter-all.jar -c "5*3"

~/work/compiler-interpreter (git master)
[mizushima]$ javap -c Main
public class Main {
public Main();
Code:
0: aload_0
1: invokespecial #8 // Method java/lang/Object."<init>":()V
4: return

public static void run();
Code:
0: getstatic #15 // Field java/lang/System.out:Ljava/io/PrintStream;
3: ldc #16 // int 5
5: ldc #17 // int 3
7: imul
8: invokevirtual #23 // Method java/io/PrintStream.println:(I)V
11: return

public static void main(java.lang.String[]);
Code:
0: invokestatic #27 // Method run:()V
3: return
}

~/work/compiler-interpreter (git master)
[mizushima]$ java Main
15

ここで、

       3: ldc           #16                 // int 5

5: ldc #17 // int 3
7: imul

の部分が本体なわけですが、みればわかるように、まさに5*3に対応するバイトコード命令に翻訳されており、インタプリタ版にあった、命令を解釈する部分(処理の分岐)がありません。


まとめ

数式言語のインタプリタとコンパイラの実装を通して、インタプリタとコンパイラの違いについて簡単に解説してみました。インタプリタは元の言語の式を解釈(低レベルな視点では、式に対応する命令の開始位置にジャンプする)のに対して、コンパイラは元の言語の式に対応する命令(この場合、変換先の言語はJVMのバイトコードですが、機械語や他の言語の場合でも同様です)に翻訳(低レベルな視点では、命令を生成する)するのが違いであるという点を実感してもらえれば、と思います。

全体のコードはここにあり、リポジトリをクローンして、

$ ./gradlew build

$ java -jar build/libs/compiler-interpreter-all.jar -e "1+2" # インタプリタの場合
$ java -jar build/libs/compiler-interpreter-all.jar -c "1+2" # コンパイラの場合

とすれば簡単に試してみることができるので、この説明だけでは納得がいかなかった方も試してみていただければと思います。