サブルーチン呼び出し付き最小限VM

ジャンプする前に自分の居た位置を記録する命令と、記録された位置にジャンプする命令があれば関数やサブルーチンと呼ばれる概念のとても原始的な形なら実装できるよね、というところまでを実装した。最初はスタックもつくろうとしていたんだけど、いきなりスタックまで実装された状態で見せられても読者が付いてこないと思ったので関数の中から関数を呼ぶと壊れる仕様で。

作ってみて痛感したんだけど、mov %ebx, $0とmov %ebx, %eaxのmovが同じもののように思ってしまうあたりがすでに高級言語脳で、この実装みたいに引数が数値だったら番地と実値の区別ができないから当然別の命令として実装する必要があるのであった。前者をset、後者をmovって名前で実装してて、そして「あ、-4(%rbp)とか出てきたらこの2つのどっちでもないじゃん…」と。

引数をスタックに積むとそこら辺の命令が出てきて、日本語で解説しても「『スタックの先頭を指す番地』が指している番地の2つ手前の番地にある値を読む」って感じで複雑だから、一気に入れずに徐々にやるべきかな、ということで引数の実装もやめました。

# -*- encoding: utf-8 -*-
"""
mini-VM 解説のための最小限のVM
最小限のサブルーチン呼び出し
・帰るアドレスはmem[5]に決め打ちで保管
　→つまり呼び出しをネストできない
　→ネストするにはどうすればいい？→スタックを作ろう！って解説する？
・返り値はmem[0]に入る
・引数？なにそれ？
　→呼び出し元とみえているものが同じ
　　書き換えれば呼び出し元にも波及
　→この問題の解決方法は動的スコープのところでやる

print a1 : mem[a1]をprint
set a1 v1 : mem[a1]をv1にする
jump pos : PCをposに変更
if_gt a1 v2 pos : mem[a1] == v1 ならjump pos
call pos : 今のPC + 1をmem[RETURN_ADDR]に入れてからjump pos
return a1 : mem[a1]の内容をmem[0]に入れてからmem[RETURN_ADDR]の指す位置へjump
"""

memory = [0] * 10
RETURN_ADDR = 5 # returnする場所を格納しておく番地

# サブルーチン(max)の実装
code = [
    ("set", 1, 10),      # B = 10
    ("set", 2, 20),      # C = 20
    ("call", 8),         # call max(B, C)
    ("print", 0),        # print A
    ("set", 1, 30),      # B = 30
    ("call", 8),         # call max(B, C)
    ("print", 0),        # print A
    ("jump", 999),       # goto end
    ("if_gt", 1, 2, 10), # 8(max): if B > C goto 10
    ("return", 2),       # return C
    ("return", 1),       # 10: return B
]

def eval(code):
    cur = 0
    while cur < len(code):
        line = code[cur]
        cur += 1
        op = line[0]
        if op == "set":
            memory[line[1]] = line[2]

        elif op == "print":
            print memory[line[1]]

        elif op == "if_gt":
            if memory[line[1]] > memory[line[2]]:
                cur = line[3]

        elif op == "jump":
            cur = line[1]

        elif op == "return":
            ret = memory[RETURN_ADDR]
            cur = ret
            memory[0] = memory[line[1]]

        elif op == "call":
            memory[RETURN_ADDR] = cur # +1でないのはすでに上で1進めているから
            cur = line[1]

        else:
            raise NotImplementedError(op)


eval(code)