Привет! Сейчас расскажу как написать простую виртуальную машину на 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
ссылка на оригинал статьи http://habrahabr.ru/post/270797/
Добавить комментарий