最小限VM

手元にWEB-DB Press vol.60の「言語設計の基礎知識」がある人はP.28を参照ください。ここにあるような「カウントダウンをするwhile」、原稿ではC言語で説明していますけど、本当は機械語とかにもふれたかったのですよ。紙面と時間の都合でできていないのですけど。
で、生の機械語はそれはそれで色々説明しないといけないから大変かな、と思ってwhileを実現するために最小限の仮想機械を作ってみました。

# -*- encoding: utf-8 -*-
"""
mini-VM 解説のための最小限のVM
最小限とは？最小限である必要があるか？
チューリング完全である必要があるのか？

jump pos : PCをposに変更
if_eq a1 v1 pos : mem[a1] == v1 ならjump pos
print a1 : mem[a1]をprint
set a1 v1 : mem[a1]をv1にする
sub v1 : mem[0]からv1を引く
"""

memory = [0] * 10
code = [
    ("set", 0, 10), # A = 10
    ("if_eq", 0, 5), # 1: if A == 0
    ("sub", 1), # A = A - 1
    ("print", 0), # print A
    ("jump", 1),
]

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_eq":
            if memory[0] == line[1]:
                cur = line[2]
        elif op == "sub":
            memory[0] -= line[1]
        elif op == "jump":
            cur = line[1]

eval(code)

あとPythonのバイトコードではこんな感じ。真偽値をスタックに詰んでるところがちょっと違うか。

>>> def foo():
...     x = 10
...     while x > 0:
...             print x
...             x -= 1
... 
>>> dis.dis(foo) # 必要ないところは削除
  2           0 LOAD_CONST               1 (10)
              3 STORE_FAST               0 (x)

  3           6 SETUP_LOOP              33 (to 42)
        >>    9 LOAD_FAST                0 (x)
             12 LOAD_CONST               2 (0)
             15 COMPARE_OP               4 (>)
             18 JUMP_IF_FALSE           19 (to 40)
             21 POP_TOP             

  4          22 LOAD_FAST                0 (x)
             25 PRINT_ITEM          
             26 PRINT_NEWLINE       

  5          27 LOAD_FAST                0 (x)
             30 LOAD_CONST               3 (1)
             33 INPLACE_SUBTRACT    
             34 STORE_FAST               0 (x)
             37 JUMP_ABSOLUTE            9
        >>   40 POP_TOP             
             41 POP_BLOCK           

で、これでif, while, forまでは作れるわけなのだけども、関数をつくろうと思うと今の「飛び先固定のジャンプ」ではできない。そこでcallとreturnを作ろう、と思ったのだけど、そもそもこのVMでプログラムカウンタがコードからいじれるメモリー領域上にないのが行けないのであって、こういう管理に必要な値自身もmemに入れるべきだったのかもなぁ。

---

Pythonで書いてディスアセンブルしたものを見せるんだったら別にネイティブでも良くない？と気づいたのでやってみた。

#include<stdio.h>
int main(){
  __asm__("#set x value");
  int x = 10;
  __asm__("#start loop");
  while(x > 0){
    __asm__("#print x");
    printf("%d\n", x);
    __asm__("#decrement x");
    x--;
    __asm__("#end of loop body");
  }
  __asm__("#end of loop");
}

        #set x value
        movl    $10, -4(%rbp)
        #start loop
        jmp     L2
L3:
        #print x
        movl    -4(%rbp), %esi
        leaq    LC0(%rip), %rdi
        movl    $0, %eax
        call    _printf
        #decrement x
        decl    -4(%rbp)
        #end of loop body
L2:
        cmpl    $0, -4(%rbp)
        jg      L3
        #end of loop

いきなり下に飛ぶのかー。ふむふむ。まあでもこれ説明をちゃんと書けば予備知識のない人でも読める気がする。