pythonでx86コンパイラ自作(スタック指向言語編)

Forthコンパイラの[記事](https://qiita.com/takl/items/e28c3298a0a043edeaa6)が格好良くて触発されてしまい、Forth処理系を作った。
前回の[C言語的なコンパイラ](https://qiita.com/s0sasaki/items/0b0d96838685fa290126)と同様に、Pythonでx86-64のGNU Assembler向けのコードを出力する。

##プロトタイプ実装

まずはとりあえず動くものをと思って最初に実装したのが[これ](https://github.com/s0sasaki/forth/blob/master/forth_primitive.py)。
初めてのアセンブリ言語の題材に良さそう。

```python:forth_primitive.py
code = "6 3 + 2 - . 3 4 * 2 / 1 + . 2 3 drop dup dup 1 + + + 7 dup . . ."

def translator(token):
    if token.isdigit():
        print("    pushq $"+token)
    elif token == "+":
        print("    popq %rax")
        print("    addq %rax, (%rsp)")
    elif token == "-":
        print("    popq %rax")
        print("    subq %rax, (%rsp)")
    elif token == "*":
        print("    popq %rax")
        print("    imulq (%rsp), %rax")
        print("    movq %rax, (%rsp)")
    elif token == "/":
        print("    popq %rbx")
        print("    popq %rax")
        print("    cqto")
        print("    idivq %rbx")
        print("    pushq %rax")
    elif token == ".":
        print("    popq %rsi")
        print("    leaq IO, %rdi")
        print("    movq $0, %rax")
        print("    callq printf")
    elif token == "dup":
        print("    movq (%rsp), %rax")
        print("    pushq %rax")
    elif token == "drop":
        print("    addq $8, %rsp")

prologue = """\
    .text
    .globl main
main:
    pushq %rbp
    movq %rsp, %rbp
"""
epilogue = """\
    movq $0, %rax
    leaveq
    retq
    .data
IO:
    .string "%lld"
"""
print(prologue)
tokens = code.split()
for token in tokens:
    translator(token)
print(epilogue)
```

##完成版

関数などを実装した完成版は[ここ](https://github.com/s0sasaki/forth)。

Forthの実装で特徴的なのは、演算のためのスタック(data stack)と、関数呼び出しのためのスタック(return stack)がそれぞれ必要なこと。
今回の実装では、data stackはrspレジスタでPUSH/POPしたけど、return stackは汎用レジスタとJMPを使って実装した。
（ちなみに、前述記事の実装では逆に、data stackを自前で用意して、return stackにCALL/RETを使っているみたい。）

呼び出すとき：

```python:forth.py
    elif token in funcdict.keys():
        print("    addq $8, %r15")
        print("    leaq (_L"+str(label_id)+"), %rax")
        print("    movq %rax, (%r15)")
        print("    jmp "+token)
        print("_L"+str(label_id)+":")
        print("    subq $8, %r15")
        label_id += 1
```
戻ってくるとき：

```python:forth.py        
    elif token == ";":
        print("    movq (%r15), %rax")
        print("    jmp *%rax")
```

入れ子構造や再帰構造にも対応できることを確認。

```forth:test.fth
: sq dup * ;
: sqsq sq sq ;
3 sqsq . 

 ( >>> 81 )
```

```forth:test.fth
: factorial
    dup 1 > if 
    dup 1 - factorial * endif
;
5 factorial .

 ( >>> 120 )
```


あとCの関数呼び出しも実装した。
前述記事はWindows環境だけど、僕はLinux環境なのでSystem V ABIの呼出し規約に則って実装した。

```python:forth.py   
    elif token == "call": print("    callq "+tokens.pop(0))     
    elif token == "rax>": print("    pushq %rax")
    elif token == ">rdi": print("    popq %rdi")
    elif token == ">rsi": print("    popq %rsi")
```
```c:f.c
#include <stdio.h>

int f(int a, int b){
    int c;
    c = a+b;
    printf("Hello form C!\n");
    return c;
}
```
```forth:test2.fth
: call_f
    >rdi >rsi
    call f
    rax>
;
200 100 call_f .

 ( >>> Hello from C! ) 
 ( >>> 300 ) 
```

今回の開発環境は以下の通り。

```text:開発環境
   CPU: Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz 64 bits
    OS: Ubuntu 14.04 LTS
   gcc: 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3)
python: 3.6.0
```


##感想

Forthは今回初めて触った。
最初はアセンブリ言語みたいな古代言語かと思いきや、意外と新食感だったかも。
Forth Standard 200x/16.1によると、"Forth is a language for direct communication between human beings and machines."とのこと。いいね。


##参考資料

 - [一日でできるセルフホスティングForthコンパイラ](https://qiita.com/takl/items/e28c3298a0a043edeaa6)
 - [Forth Standard 200x/16.1](http://www.forth200x.org/documents/forth16-1.pdf)
 - [Gforth Manual](http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/)
 - [System V Application Binary Interface](https://software.intel.com/sites/default/files/article/402129/mpx-linux64-abi.pdf)
 - [Forthについてのメモ書き](https://qiita.com/gyabo/items/f7e9b2ce14f3c0c12f16)