Пишем простую виртуальную машину на Python
Привет! Сейчас расскажу как написать простую виртуальную машину на Python. Надеюсь кто-то найдет эту статью интересной.
Мы не будем реализовывать парсер и компилятор, а сделаем пока что только машину-интерпретатор нашего ассемблера.
У нас будет стековая машина, и она будет использовать два стека:
- стек значений, куда будут складываться/забираться временные значения вычислений и результаты вызова функций
- стек вызовов, куда мы будем запоминать, в какое место кода нужно вернуться после завершения функции
Сам код будет представлять собой list из команд, которые тоже являются list’ами:
code = [
['val', 2], # положить 2 на стек
['val', 3], # положить 3 на стек
['get', '*'], # положить на стек значение переменной с названием * (функция умножения)
['call', 2], # взять с вершины стека функцию и вызвать ее с 2 аргументами со стека (они тоже вынимаются), результат функции кладется на стек
['get', 'puts'], # положить функцию печати
['call', 1], # напечатать
]
Реализуем машину в виде функции:
# ops - список команд
# env - окружение в котором исполняется код
def vm(ops, env={}):
# нам нужен класс замыкания, чтобы мы могли понять что на стеке действительно лежит функция
class closure:
# pc - "адрес" кода функции (индекс первой команды в ops)
# env - окружение в котором было создано замыкание
def __init__(self, pc, env):
self.pc, self.env = pc, env
# pc - индекс следующей исполняемой команды
# stack - стек значений
# fstack (frame stack) - стек вызовов функций
pc, stack, fstack = 0, [], []
Перед тем как запустить основной цикл интерпретатора, нам нужно вычислить индексы метод в коде. Меткой у нас будет специальная команда label: ['label', 'label-name']
labels = {op[1]: index for index, op in enumerate(ops) if op[0] == 'label'}
Основной цикл:
while pc < len(ops):
# берем текущую команду и ее аргументы, увеличиваем указатель
op, args, pc = ops[pc][0], ops[pc][1:], pc + 1
arg = args[0] if args else None
# игнорировать команду label
if op == 'label':
pass
# положить знаение аргумента на стек
elif op == 'val':
stack.append(arg)
# присовить значение переменной либо положить значение переменной на стек
elif op == 'set' or op == 'get':
Здесь нужно чуть рассказать об устройстве окружений. У нас они являются объектами dict, в ключах которого хранятся названия переменных, а в значениях значения + в ключе '' (пустая строка) хранится «указатель» на родительское окружение. Поэтму чтобы найти окружение в котором была определена нужная нам переменная, мы должны искать сначала в текущем окружении, и если не нашли, то искать в родительском и так далее:
e = env
while e is not None and arg not in e:
e = e[''] if '' in e else None # ключа '' может и не быть, это значит что нет родительского окружения
# изменить значение переменной, если таковая была была определена, либо определить ее в текущем окружении
if op == 'set': (env if e is None else e)[arg] = stack.pop()
# положить на стек значение, либо вывести предупреждение о неопределенной переменной
elif op == 'get':
if e: stack.append(e[arg])
else: print('undefined variable %s' % arg)
В нашей виртуальной машине будет возможность передавать и возвращать функции из функций, соответственно, будем реализовывать замыкания. Самым простым способом. Когда мы будем встречать команду создания новой функции, эта функция будет запоминать в каком окружении (ассоциативном массиве переменная: значение) она была создана. Таким образом мы сможем писать такое на нашем языке высокого уровня (который будет компилироваться в байткод для нашей машины):
make-person = fn(name, age) {
return fn() { // запомнила значения name и age
print name, age++;
};
};
vasya = make-person("Vasily", 20);
petya = make-person("Peter", 24);
vasya(); // Vasily 20
vasya(); // Vasily 21
petya(); // Peter 24
petya(); // Peter 25
Созданием замыкания у нас будет заниматься команда fn. Все чт она делает: кладет на стек объект класса closure, у котором указаны адрес кода фукнции (на самом деле адрес метки с названием нужной фукнции) и текущее окружение.
elif op == 'fn':
stack.append(closure(labels[arg], env))
Теперь о вызовах функций.
Фукнции у нас могут быть двух типов:
- встроенные функции, например +, -, sin, cos
- определенные в коде
Обрабатываться они будут по-разному:
- встроенная функция просто вызывается виртуальной машиной и результат фукнции кладется на стек.
- чтобы вызвать определенную пользоватем фукнцию мы должны запомнить место, куда должно вернуться управление после того как фукнция закончит свое выполнение. Короче это означает мы должны сохранить значение pc и env на стеке вызовов, изменить pc на «адрес» кода функции, создать новое (локальное) окружение, в котором будет работать фукнция, родительским окружением укажем окружение, запомненное во время создания замыкания
Во время вызова функций мы будем указывать кол-во переданных аргументов n, а наш интерпретатор возьмет n элементов со стека, сделает из них массив и положит в стек, таким образом у нас функции могут принимать любое кол-во аргументов. Функции в своем коде сами будут должны разбирать массив аргументов и устанавливать соответствующие переменные.
Команда ret возвращает управление в место откуда она была вызвана.
# простой вызов либо вызов в хвостовой позиции
elif op == 'call' or op == 'tcall':
# берем функцию
fn = stack.pop()
# если указано кол-во аргументов то мы должны сделать из них массив
if args and arg:
stack.append(popn(arg))
# определенная в коде функция
if isinstance(fn, closure):
# если это вызов фукнции в нехвостовой позиции, то запомнить куда вернуть управление
if op == 'call':
fstack.append((pc, env))
# перейти в код фукнции
pc, env = fn.pc, {'': fn.env}
# встроенная функция
elif hasattr(fn, '__call__'):
stack.append(fn(stack.pop()))
# команда разбора аргументов
elif op == 'args':
vals = stack.pop()
if len(args) != len(vals): print 'warning: wrong arguments count: %d expected, %d given' % (len(args), len(vals))
env.update(dict(zip(args, vals)))
# return
elif op == 'ret':
# если return встретился на верхнем уровне, это означает конец выполнения программы
if not fstack: break
# возвращаем управление куда надо
pc, env = fstack.pop()
Полный код с лексером (для удобства) и тестовым примером: gist.github.com/Butjok/a531316e2a32576974d2
