...

суббота, 14 ноября 2015 г.

Пишем простую виртуальную машину на 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()

Полный код с лексером (для удобства) и тестовым примером: http://ift.tt/1j03obq

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

Отправить комментарий