Forthコンパイラの記事が格好良くて触発されてしまい、Forth処理系を作った。
前回のC言語的なコンパイラと同様に、Pythonでx86-64のGNU Assembler向けのコードを出力する。
プロトタイプ実装
まずはとりあえず動くものをと思って最初に実装したのがこれ。
初めてのアセンブリ言語の題材に良さそう。
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)
完成版
関数などを実装した完成版はここ。
Forthの実装で特徴的なのは、演算のためのスタック(data stack)と、関数呼び出しのためのスタック(return stack)がそれぞれ必要なこと。
今回の実装では、data stackはrspレジスタでPUSH/POPしたけど、return stackは汎用レジスタとJMPを使って実装した。
（ちなみに、前述記事の実装では逆に、data stackを自前で用意して、return stackにCALL/RETを使っているみたい。）
呼び出すとき：
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
戻ってくるとき：
forth.py
elif token == ";":
print(" movq (%r15), %rax")
print(" jmp *%rax")
入れ子構造や再帰構造にも対応できることを確認。
test.fth
: sq dup * ;
: sqsq sq sq ;
3 sqsq .
( >>> 81 )
test.fth
: factorial
dup 1 > if
dup 1 - factorial * endif
;
5 factorial .
( >>> 120 )
あとCの関数呼び出しも実装した。
前述記事はWindows環境だけど、僕はLinux環境なのでSystem V ABIの呼出し規約に則って実装した。
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")
f.c
#include <stdio.h>
int f(int a, int b){
int c;
c = a+b;
printf("Hello form C!\n");
return c;
}
test2.fth
: call_f
>rdi >rsi
call f
rax>
;
200 100 call_f .
( >>> Hello from C! )
( >>> 300 )
今回の開発環境は以下の通り。
開発環境
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."とのこと。いいね。