Kotlinで セルフホストを したかった

(575)

## はじめに
こんにちは、unifarといいます。
Androidアプリを七個ぐらい作った。
随分前に、ruiさんの[低レイヤを知りたい人のためのcコンパイラ作成入門](https://www.sigbus.info/compilerbook)
を読んで「これなら作れそう!」と思い、大胆にも、Cコンパイラ作成入門を読んでKotlinコンパイラを作成し始めてしまった。

それから、
195日が過ぎ、
112コミットが積まれ、
本体は1827行になり、
私の受験勉強はいよいよ終盤に差し掛かかった。

そして、現状がこちら[(github)](https://github.com/negitorogithub/Lik)。

今現在動かせるのはこんな感じ

```kotlin
//まあまあ複雑なテストコード
    class TestClass(n) {
        val a = 4
        fun get42(m): Int {
            return n + m + a
        }
    }

    fun func(x): TestClass {
        val instance = TestClass(x)
        return instance
    }

    fun main(): Int {
        val instance = func(26)
        return instance.get42(12)
    } //->42

```

```kotlin
//フィボナッチ数列
fun fib(n): Int {
    if (n == 1) {
        return 1
    }
    if (n == 2) {
        return 1
    }
    return fib(n - 1) + fib(n - 2)
}

fun main(): Int {
    return fib(5) //->5
}
```


最初の内は「セルフホストしてやんよ!」と思っていたが、次第に雲行きが怪しくなり、他に作りたいものも出来て、一旦開発を止めることにした。しかし、ここまでの開発でも多くのことを学べた。例えば、再帰下降分析、アセンブラでのmain、加算、関数、文字の実装、など。ここからは、具体的な作成方法をコミットを追って解説していく。

## 1コミット目
```kotlin
fun main() {
    val input = readLine()
    println(input?.let { parse(it) })
}

fun parse(likScript: String): String {
    val tokens = tokenize(likScript)
    return "default"

}

fun tokenize(str: String): List<Token> {
    val spaceRemoved = str.split(space)
    var temporaryNumberList = mutableListOf<String>()
    val resultList = mutableListOf<Token>()

    spaceRemoved.forEach { char: String ->
        if (!(numbers.contains(char))) {
            resultList.add(Token(TokenType.NUMBER, numberList2number(temporaryNumberList)))
            temporaryNumberList = mutableListOf()
        }
        if (operators.contains(char)) {
            resultList.add(
                when (char) {
                    plus -> Token(TokenType.PLUS)
                    minus -> Token(TokenType.MINUS)
                    multiply -> Token(TokenType.MULTIPLY)
                    divide -> Token(TokenType.DIVIDE)
                    else -> Token(TokenType.NULL)//絶対来ない
                }
            )
            return@forEach
        }
        if (numbers.contains(char)) {
            temporaryNumberList.add(char)
            return@forEach
        }
    }
    return resultList
}

fun numberList2number(list: List<String>): Int {
    val buffer = StringBuilder()
    list.forEach {
        buffer.append(it)
    }
    return Integer.parseInt(buffer.toString())
}

```

これは主に入力を分解する関数（1+3 ->1,+,3)。
書き忘れていたけど、このKotlinもどき言語は、KotlinのKとLとIを並び替えて、Likという名前にしてある(どう発音するんだろうね？)。
本家のファーストコミットとはだいぶ違い、はなからCコンパイラ作成入門に従っていないのが分かる。
(最初はインタープリタを作るつもりだった)

##4コミット目

```kotlin
fun parseAdd(innerList: List<Token>): Int? {
    var cursor = 0
    innerList[cursor].value ?: run {
        throw IllegalArgumentException("first element must be number")
    }

    var result = innerList[cursor].value!!

    cursor++
    while (innerList.size - 1 > cursor)
        if (innerList[cursor].type == TokenType.PLUS) {
            cursor++
            innerList[cursor].value?.let {
                result += it
                cursor++
            }
        } else if (innerList[cursor].type == TokenType.MINUS) {
            cursor++
            innerList[cursor].value?.let {
                result -= it
                cursor++
            }
        }
    return result
}
```

これは加算のトークン列を受け取って結果をかえす関数(21 ,+ ,4 ,- ,2 -> 23 )
久々にこのコードを見たが、把握するのに結構時間がかかった。
おそらくこれはあまり良くないコードなのだろう。
しかし、コンパイラになる気配がない。

## 20コミット目

```kotlin
fun main() {
    val input = mutableListOf<String>()
    var next = readLine()
    while (next != "***") {
        input.add(next!!)
        next = readLine()
    }
    println(".intel_syntax noprefix")
    println(".global main")
    println("main:")
    println("  mov rax, ${input[0]}")
    println("  ret")
}
```

20コミット目にしてやっとアセンブリが出てきた。今まで何をやっていたんだ。(本当はインタープリターとしてif文くらいまで実装していた)。

これは「標準入力から受け取った数字を返却するアセンブリ」を出力するプログラム。
Kotlinプログラムは内部でアセンブラに変換され実行される。
解説すると、

```kotlin
println(".intel_syntax noprefix")
```
訳↑「これからintel記法を使うよ～」

 - アセンブラにはintel記法とAT&T記法がある

```kotlin
println(".global main")
```
訳↑「main関数を公開するよ～」

 - アセンブラもmainから実行される

```kotlin
println("main:")
```
訳↑「main関数　はっじまっるよ～～」

```kotlin
println("  mov rax, ${input[0]}")
```
訳↑「raxレジスタにinput[0]を入れるよ～」

 - アセンブラではレジスタという場所に値を保管する
 - raxはレジスタの名前
 - ${input[0]}はテンプレート記法
 - mov x, y　はyをxに入れる、というアセンブラの命令
 - 行頭を開けないと特殊な文として解釈される
 - 開けると普通の命令

```kotlin
println("  ret")
```
訳↑「撤退するよ～」
(ret命令で関数から抜ける際raxの値が戻り値となる)
という感じ。

コンパイラと聞くと難しそうな感じがするが、これもコンパイラの一種だと(私は)思う。


##34コミット目

```kotlin
fun printAssembly() {
        when (token.type) {
            PLUS -> {
                println("  push ${leftNode!!.token.value}")
                println("  push ${rightNode!!.token.value}")

                println("  pop rdi")
                println("  pop rax")
                println("  add rax, rdi")
            }
            NUMBER -> {
                println("  mov rax, ${token.value}")
            }
        }
    }

```
このprintAssebmly関数はNodeクラスの関数である。Nodeはtokenを本体として持っている。
これはアセンブラのmain関数の中身を出力する部分。3+4とかのコードがコンパイルできるようになった。
そろそろ疲れたので、解説はこれでおしまいにする。

前提としては、

- アセンブラでもスタックが利用できる
- push x はxの値をpushする
- pop x はスタックトップの値をxに入れる
- add x, yはx+yの結果をxのレジスタに代入する
- x + yは内部で↓のような構造になっている

.......x
.../
+
...\
.......y （わかりずらいね）
要するに、+ノードを親として左右にx,yという値を子として持っているということである。
(実は、1コミット目のトークン化する関数は、このような木構造を作るための下準備でもあった。)


ここでは、左右のノードの値をpushして、raxとrdiレジスタにそれぞれ保存(pop)、そして両者を加算し(add)、raxに値を保管する(自動的に保存される)、ということをやっている。この後ret命令を呼べば、めでたく戻り値もセットされた状態で関数から帰還できる。

##最後に
コンパイラを作るのは難しいことではない―――コンパイラの定義によっては。


関係ないけど、下に好きな曲を貼っておくので聞いてほしい。鳥肌立った。

[マグ・メル](https://www.youtube.com/watch?v=E0jiqu0P23M)